Correlation Attack

V kryptografii , korelační útoky jsou třída známých holého útoků na lámáníproudových šifer , jejichž keystream je generován tím, že kombinuje výstup několika lineárních registrů zpětnovazební posuvný (tzv. LFSRs pro zbytek tohoto článku) pomocí logický funkce . Korelační útoky využít statistickou slabost, která plyne z chudé výběru Boolean funkce - je možné zvolit funkci, která se vyhýbá srovnávací útoky, takže tento typ šifry není ze své podstaty nebezpečné. Je to prostě důležité zvážit citlivost na srovnávací útoky při navrhování proudových šifer tohoto typu. ^{[ pochvalná zmínka potřebovaný ]}

[ editovat ]Vysvětlení

Korelační útoky jsou možné, pokud je významná korelace mezi výstupním stavu jednoho individuálního LFSR v keystream generátoru a výstup Boolean funkce, která kombinuje výstupní stav všech LFSRs. V kombinaci s částečnou znalostí keystream (který je snadno odvodit z dílčích poznatků holého textu, jak dva jsou prostě XORed dohromady), což umožňuje útočníkovi brute-force klíč pro tento individuální LFSR a zbytek systému samostatně. Například, pokud v keystream generátoru, ve kterém jsou čtyři 8-bitové LFSRs kombinaci produkovat keystream, a jeden z registrů koreluje s booleovské funkce výstupu, můžeme hrubá síla je první a pak zbývající tři, pro celkem útok složitost 2 ⁸ + 2²⁴ . Ve srovnání s náklady na zahájení pokusit útokem hrubou silou na celý systém, se složitostí 2 ³² , což představuje útok úsilí úspory faktor 255, což je podstatné. Pokud druhý registr souvisí s funkcí, můžeme opakovat tento proces, a drop útoku na složitosti 2 ⁸ + 2 ⁸ + 2 ¹⁶ za úsilí úspory faktor 65027.V tomto smyslu je možné korelační útoky za rozděl a panuj algoritmy .

[ editovat ]Příklad

[ upravit překlad ]Prolomit Geffe generátor

Korelační útoky jsou možná nejlépe vysvětlit pomocí příkladu. Budeme uvažovat případ tzv. Geffe generátoru klíčů. Generátor Geffe se skládá ze tří LFSRs: LFSR-1, LFSR-2 a LFSR-3. Označíme-li výstupy těchto rejstříků $x_1$ , $x_2$ a $x_3$ , respektive, pak booleovská funkce, která kombinuje tři registry poskytnout výstup generátoru je dána tím, $F (x_1, x_2, x_3) = (x_1 \ wedge x_2) \ oplus (\ neg x_1 \ wedge x_3)$ (tj. ( $x_1$ A $x_2$ ) XOR (NOT $x_1$ A $x_3$ )). K dispozici jsou 2 ³ = 8 možných hodnot pro výstupy tří registrů, a hodnota tohoto kombinuje funkce pro každý z nich je výstava v tabulce níže:

Booleovská funkce výstupní tabulka
$x_1$	$x_2$	$x_3$	$F (x_1, x_2, x_3)$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

Uvažujme výstup třetího registru, $x_3$ . Výše uvedená tabulka je jasné, že z 8 možných výstupů $x_3$ . 6 z nich jsou stejné na odpovídající hodnotu výkonu generátoru, $F (x_1, x_2, x_3)$ , tj. $x_3 = F (x_1, x_2, x_3)$ v 75% všech možných případů. Tak můžeme říci, že LFSR-3 je spojená s generátorem. To je slabost můžeme využít takto:

Předpokládejme, že zachytí ciphertext $c_1, c_2, c_3, \ ldots, C_n$ o otevřeném textu $p_1, p_2, p_3, \ ldots$ , který byl šifrován pomocí proudu šifrou pomocí Geffe generátor jako jeho keystream generátoru, tj. $c_i = p_i \ oplus F (x_ {1i}, x_ {2i}, x_ {} 3i)$ pro $i = 1, 2, 3, \ ldots, n$ , kde $x_ {1i}$ je výstup LFSR-1 v čase $já$ , atd. Dále předpokládejme, že víme, že některé části holý, např. víme $p_1, p_2, p_3, \ ldots, p_ {32}$ , že prvních 32 bitů otevřeného textu (odpovídá 4 znaky ASCII textu). To není tak nepravděpodobné, jak se to může zdát: víme-li, holý text je platný XML soubor, například víme, že první 4 znaky ASCII, musí být "<xml". Podobně jako toto, mnoho formáty souborů nebo síťové protokoly mají standardní záhlaví nebo zápatí, které mohou být uhodnuto snadno. Vzhledem k tomu, zachytil $c_1, c_2, c_3, \ ldots, c_ {32}$ a naše známé / hádal $p_1, p_2, p_3, \ ldots, p_ {32}$ , můžeme snadno najít $F (x_ {1i}, x_ {2i}, x_ {} 3i)$ pro $i = 1, 2, 3, \ ldots, 32$ XORing dva spolu. Nyní víme, 32 po sobě jdoucích bitů výstupu generátoru.

Nyní můžeme začít silovou hledání v prostoru možných klíčů (počáteční hodnoty) pro LFSR-3 (za předpokladu, že víme, že se závitem bity LFSR-3, předpoklad, který je v souladu se zásadou Kerckhoffs " ). Pro každý daný klíč v keyspace, můžeme rychle vytvářet prvních 32 bitů výstupu LFSR-3 je a porovnávat s našimi získaných 32 bitů z celého generátoru výstupu. Vzhledem k tomu, jsme založili již dříve, že je 75% korelace mezi výkonem LFSR-3 a generátorem, víme, že pokud jsme správně uhodl šipky na LFSR-3, cca 24 z prvních 32 bitů LFSR-3 výstup budou shodovat s odpovídajícími bity výstupu generátoru. Pokud jsme uhodli správně, měli bychom očekávat, že zhruba polovina, nebo 16, z prvních 32 bitů těchto dvou sekvencí, které vyhoví.Můžeme tedy obnovit tlačítko pro LFSR-3 nezávisle na klíče LFSR-1 a LFSR-2.V této fázi jsme snížili problém hovado nutit systém 3 LFSRs problému hovado nutit jednoho LFSR a pak se systém 2 LFSRs. Množství úsilí zde uložen, závisí na délce LFSRs. Pro realistické hodnoty, je velmi podstatné úspory a mohou brute force útoky velmi praktické.

Nepotřebujeme zde zastavit. Dodržujte v tabulce výše, která $x_2$ rovněž souhlasí s výstupu generátoru 6 krát ze 8, opět korelace 75% korelace mezi $x_2$ a výkon generátoru. Můžeme začít pokusit útokem hrubou silou proti LFSR-2 nezávisle na klíče LFSR-1 a LFSR-3, takže jen LFSR-1 neporušený. Tak, jsme schopni zlomit Geffe generátor s co největší úsilí je třeba k hrubé síle 3 zcela nezávislé LFSRs, což znamená, že generátor Geffe je velmi slabý generátor a nikdy by neměly být použity k výrobě keystreams proudová šifra.

Poznámka: z výše uvedené tabulky, která $x_1$ souhlasí s výkonem generátoru 4 krát ze 8 - 50% srovnávací. Nemůžeme použít k hrubé síle LFSR-1 nezávisle na ostatních: správný klíč přinese výkon, který souhlasí s výstupu generátoru 50% času, ale v průměru tak bude nesprávné tlačítko. To představuje ideální situaci z hlediska bezpečnosti - kombinuje funkce $F (x_1, x_2, x_3)$ by měla být zvolena tak, aby vztah mezi každou proměnnou a kombinování funkce výkon je tak blízko, jak je to možné, aby 50%. V praxi může být obtížné najít funkci, která dosahuje tato aniž by byla obětována další konstrukční kritéria, např. doba v délce, tak kompromis může být nezbytné.

[ upravit překlad ]Objasnění statistické povahy útoku

Zatímco výše uvedený příklad dobře ilustruje poměrně jednoduché pojmy za srovnávací útoky, to možná zjednodušuje vysvětlení přesně, jak brutální nutit jednotlivých LFSRs výnosů. Vyrábíme prohlášení, že nesprávně tipoval klíče budou generovat LFSR výstup, který souhlasí s výstupu generátoru zhruba 50% času, protože stejně dva náhodné bitové posloupnosti dané délky, pravděpodobnost shody mezi sekvencí v každém konkrétním kousku je 0,5.Nicméně, může konkrétní individuální nesprávné klávesy a vytvářet LFSR výstup, který souhlasí s výstupu generátoru více či méně často než přesně 50% času. To je zvláště patrné iv případě LFSRs, jejichž korelace s generátorem není nijak zvlášť silný, pro malé dost korelací to rozhodně není mimo oblasti možnosti, že nesprávně odhadl klíč bude také vést k LFSR výstup, který souhlasí s požadovaným počtem bity výstupu generátoru. Tak jsme nemusí být schopni najít klíč k tomuto LFSR jednoznačně a s jistotou.Můžeme místo toho najít řadu možných klíčů, i když je to stále podstatné porušení šifry bezpečností. Kdybychom, řekněme, megabajt známého otevřeného textu, by se situace podstatně odlišná. Nesprávný klíč může generovat LFSR výstup, který souhlasí s více než 512 kilobajtů výkonu generátoru, ale není pravděpodobné, že generovat výstup, který souhlasí s jak hodně jako 768 KB na výstupu generátoru, jako správně odhadl klíč by.Zpravidla, slabší korelace mezi individuálním rejstříku a výkonu generátoru, je více známý holý nutné najít ten klíč registru se s vysokou mírou jistoty. Čtenáři se zázemím v teorii pravděpodobnosti by měl být schopen vidět, snadno, jak formalizovat tento argument a získat odhady délky známého otevřeného textu potřebné pro danou korelaci pomocí binomického rozdělení .

[ upravit překlad ]Vyšší řád korelace

[ editovat ]Definice

Korelace, které byly využívány v příkladu útoku na generátoru Geffe jsou příklady toho, co se nazývá prvního řádu korelace : jsou korelace mezi hodnotou výkonu generátoru a individuální LFSR. Je možné definovat vyšších řádů korelace kromě nich. Například, to může být možné, že zatímco stejně Booleovská funkce nemá žádné silné korelaci s některou z jednotlivých registrů spojuje, může významná korelace existuje mezi některými booleovské funkce dvou registrů, např. $x_1 \ oplus x_2$ . To by byl příklad druhého řádu korelace .Můžeme definovat třetího řádu korelací a tak v explicitní formě.

Vyšší útoky řád korelace může být silnější než jednotlivé útoky řádu korelace, ale tento účinek je předmětem "zákon omezení vrátí". Níže uvedená tabulka ukazuje míru výpočetní nákladů pro různé útoky na keystream generátoru se skládá z osmi 8-bitových LFSRs kombinaci jediným Boolean funkce. Principy výpočet nákladů je poměrně jednoduché: vlevo termín součtu představuje velikost keyspace pro srovnávaných generátorů, a nejvíce vpravo výraz představuje velikost keyspace pro zbývající generátorů.

Generátor útok úsilí
Útok	Snaha (velikost keyspace)
Brute force	$2 ^ {8 \ times 8} = 18446744073709551616$
Single 1. řádu korelace útok	$2 ^ 8 + 2 ^ {7 \ times 8} = 72057594037928192$
Single 2. řádu korelace útok	$2 ^ {2 \ times 8} + 2 ^ {6 \ times 8} = 281474976776192$
Single 3. řádu korelace útok	$2 ^ {3 \ times 8} + 2 ^ {5 \ times 8} = 1099528404992$
Single 4. řádu korelace útok	$2 ^ {4 \ times 8} + 2 ^ {4 \ times 8} = 8589934592$
Single 5. objednávky korelace útok	$2 ^ {5 \ times 8} + 2 ^ {3 \ times 8} = 1099528404992$
Single 6. Aby vztah útok	$2 ^ {6 \ times 8} + 2 ^ {2 \ times 8} = 281474976776192$
Single 7. Aby korelace útok	$2 ^ {7 \ times 8} + 2 ^ {8} = 72057594037928192$

While vyšších řádů korelace vést k silnější útoky, oni jsou také více obtížné najít, jako prostor dostupných logických funkcí korelovat proti zvýšení výkonu generátoru jako počet argumentů funkce dělá.

[ editovat ]Terminologie

Booleovská funkce $F (x_1, \ ldots, x_n)$ na n proměnných je řekl, aby byl " m -tého řádu korelace imunní ", nebo mít" m -tého řádu srovnávací imunitu "pro nějaké celé číslo m , pokud není významná korelace mezi funkcí výstupu a některého Boolean funkce m ze svých vstupy. Například, booleovská funkce, která nemá žádné prvního pořadí nebo druhého řádu korelace, která však již třetího řádu korelace vykazuje 2. řádu srovnávací imunitu. Je zřejmé, že vyšší korelace imunita je funkce vhodnější pro použití v generátoru keystream (i když to není jediné, co je třeba vzít v úvahu).

Siegenthaler ukázala, že korelace imunita m z booleovské funkce algebraické studia d o n proměnných splňuje m + d ≤ n , pro daný soubor vstupních proměnných, to znamená, že vysoký stupeň algebraické omezí maximální možnou srovnávací imunitu. Kromě toho, v případě, že funkce je vyvážena pakm + d ≤ n -. 1 ^[ 1 ]

Z toho vyplývá, že není možné, aby funkce n proměnných n -tého řádu korelace imunní. To také vyplývá ze skutečnosti, že každý takový funkce může být napsáno pomocí Reed-Muller základ jako kombinace XORs o vstupních funkcí.

[ upravit překlad ]Cipher designu důsledky

Vzhledem k tomu, případně extrémní závažnost korelace útoku jejího vlivu na proudový šifrovací klíč je bezpečnost, by mělo být považováno za nezbytné pro testování kandidáta logická kombinace funkcí pro srovnávací imunity před rozhodnutím použít v proudu šifry. Je však třeba poznamenat, že vysoká korelace imunita je nezbytné, ale ne postačující podmínkou pro logickou funkci jako vhodné pro použití ve keystream generátoru. Existují i jiné problémy, aby zvážila, např. zda je nebo není funkce je vyvážená - ať už výstupy tolik nebo hrubě tolik 1 je, jak to dělá 0 let, kdy se považují všechny možné vstupy.

Výzkum byl proveden v metod pro snadné generování logické funkce dané velikosti, které jsou zaručené mít alespoň nějakou zvláštní objednávku srovnávací imunity. Tento výzkum odhalil vazby mezi korelační imunitních booleovských funkcí a chyba kódy korigování . ^[ 2 ]