Diferenciální kryptoanalýza

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 3. ledna 2020; kontroly vyžadují 5 úprav .

Diferenciální kryptoanalýza je metoda dešifrování symetrických blokových šifer (a dalších kryptografických primitiv , zejména hašovacích funkcí a proudových šifer ).

Diferenciální kryptoanalýza je založena na studiu transformace rozdílů mezi zašifrovanými hodnotami v různých kolech šifrování . Rozdílně se zpravidla používá operace bitového součtu modulo 2 , i když dochází k útokům s výpočtem rozdílového modulo . Je to statistický útok. Použitelné pro luštění DES , FEAL a některých dalších šifer, zpravidla vyvinutých dříve než začátkem 90. let. Počet kol moderních šifer ( AES , Camellia , atd.) byl vypočítán s ohledem na bezpečnost , včetně diferenciální kryptoanalýzy. $2^{32}$

Historie

Diferenciální kryptoanalýzu navrhli v roce 1990 izraelští experti Eli Biham a Adi Shamir , aby rozbili kryptosystémy jako DES. Ve své práci ukázali, že algoritmus DES se ukázal jako poměrně odolný vůči této metodě kryptoanalýzy a jakákoli sebemenší změna ve struktuře algoritmu jej činí zranitelnějším.

V roce 1994 publikoval Don Coppersmith z IBM článek [1] , v němž se uvádí, že metoda diferenciální kryptoanalýzy byla IBM známa již v roce 1974 a jedním z cílů při vývoji DES bylo chránit před touto metodou. IBM mělo svá tajemství. Coppersmith vysvětlil:

Návrh využíval určité kryptoanalytické metody, zejména metodu „diferenciální kryptoanalýzy“, která nebyla publikována v otevřené literatuře. Po diskusích s NSA bylo rozhodnuto, že odhalení procesu návrhu by také odhalilo metodu diferenciální kryptoanalýzy, jejíž síla by mohla být použita proti mnoha šifrám. To by zase snížilo výhodu USA oproti jiným zemím v oblasti kryptografie.

DES se na rozdíl od některých jiných šifer ukázal jako kryptograficky odolný vůči diferenciální kryptoanalýze. Takže například šifra FEAL se ukázala jako zranitelná . Čtyřkolový FEAL-4 může být prolomen pouze 8 vybranými otevřenými texty a dokonce i 31kolový FEAL je zranitelný vůči útoku.

DES Hacking Scheme

V roce 1990 našli Eli Biham a Adi Shamir pomocí diferenciální kryptoanalýzy způsob, jak zlomit DES , který byl účinnější než hrubá síla. Při práci s dvojicemi šifrových textů , jejichž otevřené texty mají určité rozdíly, vědci analyzovali vývoj těchto rozdílů, když otevřené texty procházejí fázemi DES .

Jednokolová analýza

Základní metodou diferenciální kryptoanalýzy je adaptivně zvolený útok v otevřeném textu , i když má rozšíření pro útok v otevřeném textu . K provedení útoku se používají dvojice otevřených textů spojených určitým rozdílem. Pro DES a systémy podobné DES je definováno jako exkluzivní OR (XOR) . Při dešifrování je potřeba pouze hodnota odpovídajících dvojic šifrovaného textu.

Diagram ukazuje Feistelovu funkci . Dovolit a být dvojice vstupů, které se liší o . Výstupy jim odpovídající jsou známé a rovny a , rozdíl mezi nimi je . Permutace s rozšířením a -blokem jsou tedy také známé a jsou také známé . a jsou neznámé, ale víme, že jejich rozdíl je , protože rozdíly c a jsou neutralizovány. Jedinými nelineárními prvky v obvodu jsou -bloky. Pro každý -blok můžete uložit tabulku, jejíž řádky jsou rozdíly na vstupu -bloku, sloupce jsou rozdíly na výstupu a na průsečíku - počet párů, které daly vstup a výstup. rozdíly a kde si tyto páry sami uložit. $X$ $X'$ $\Delta X$ $Y$ $Y'$ $\Delta Y$ $P$ $\Delta A$ $\Delta C$ $B$ $B'$ $\Delta A$ $XOR\ K_{{i}}$ $A$ $A'$ $S$ $S$ $S$

Otevření kulatého klíče je založeno na skutečnosti, že pro danou hodnotu nejsou všechny hodnoty stejně pravděpodobné, ale kombinace a umožňuje převzít hodnoty a . Pro známé a to nám umožňuje určit . S výjimkou všech potřebných informací pro poslední kolo jsou obsaženy v závěrečné dvojici šifrových textů. $\Delta A$ $\Delta C$ $\Delta A$ $\Delta C$ $A\ XOR\ K_{{i}}$ $A'\ XOR\ K_{{i}}$ $A$ $A'$ $K_{{i}}$ $\Delta C$

Po určení kulatého klíče pro poslední cyklus je možné částečně dešifrovat šifrové texty a poté použít výše uvedenou metodu k nalezení všech kulatých klíčů.

Charakteristika

K určení možných rozdílů šifrových textů přijatých v i-tém kole se používají charakteristiky kola .

Charakteristikou N-kol je n-tice , složená z rozdílů v otevřeném textu , rozdílů v šifrovaném textu a souboru rozdílů v mezilehlých výsledcích šifrování pro každé minulé kolo. $\Omega \ =\ (\Omega _{{P)),\Omega _({\Lambda )),\Omega _{{T)))$ $\Omega _{{P}}$ $\Omega _{{T}}$ $\Omega _{{\Lambda }}\ =\ (\Lambda _{{1}},\Lambda _{{2}},\ ...\ ,\Lambda _{{n}})$

Charakteristice je přiřazena pravděpodobnost rovna pravděpodobnosti, že náhodný pár otevřených textů s rozdílem v důsledku šifrování náhodnými klíči má kulaté rozdíly a rozdíly v šifrovém textu, které odpovídají těm, které jsou specifikovány v charakteristice. Dvojice otevřených textů odpovídající charakteristice se nazývá "správné" . Dvojice otevřených textů, které neodpovídají charakteristice, se nazývají „nesprávné“ . $\Omega _{{P}}$

Vezměme si hodnotu rozdílu textů na výstupu předposledního cyklu, použitou při určení možného podklíče posledního kola, . V takovém případě „správná“ dvojice textů určuje správný klíč, zatímco „špatná“ dvojice určuje náhodný klíč. $\Delta A=\Omega _{{T}}$

Při útoku se obvykle používá několik vlastností současně. Struktury se běžně používají k šetření paměti.

Kvartet je struktura čtyř textů, která současně obsahuje dvě dvojice textů pro dvě různé charakteristiky. Umožňuje ušetřit 1/2 paměti pro prosté texty.
Oktet - struktura 16 textů obsahujících 8 párů, 4 pro každou charakteristiku. Umožňuje ušetřit 2/3 paměti pro prosté texty.

Poměr signálu k šumu

Pro všechny možnosti klíče můžete vytvořit čítače, a pokud některá dvojice navrhne tuto možnost jako platný klíč, zvýšíme odpovídající čítač. Klíč, který odpovídá největšímu čítači, má vysokou pravděpodobnost, že bude správný.

Pro naše schéma výpočtu budeme poměr počtu správných párů S k průměrné hodnotě čítače N nazývat poměr signálu k šumu a budeme ho označovat . $S/N$

Chcete-li najít správný klíč a zajistit, aby byly přítomny správné páry, musíte:

charakteristika s dostatečnou pravděpodobností;
dost párů.

Počet požadovaných párů je určen:

pravděpodobnost charakteristiky;
počet klíčových bitů (bity, které chceme definovat);
úroveň identifikace chybných párů (páry nepřispívají do počítadel, protože jsou dříve vyřazeny).

Nechť velikost klíče je k bitů, pak potřebujeme čítače. Pokud: $2^k$

m je počet použitých párů;
$\alpha$ - průměrný přírůstek do počítadel pro jeden pár;
$\beta$ je poměr párů, které přispívají do žetonů, ke všem párům (včetně vyřazených),

pak průměrná hodnota čítače N je:

N={\frac {m\cdot \alpha \cdot \beta }{2^{{k))))

Pokud je pravděpodobnost charakteristiky, pak počet správných dvojic S je roven: $p$

S=m\cdot p.

Pak je poměr signálu k šumu :

S/N={\frac {m\cdot p}{m\cdot \alpha \cdot \beta /2^{{k))))={\frac {2^{{k))\cdot p}{ \alpha \cdot \beta }}.

Všimněte si, že pro naše návrhové schéma nezávisí poměr signálu k šumu na celkovém počtu párů. Počet potřebných platných párů je obecně funkcí poměru signálu k šumu . Experimentálně bylo zjištěno, že pokud S/N=1-2 , je nutných 20-40 výskytů správných párů. Pokud je poměr mnohem vyšší, pak mohou stačit i 3-4 správné páry. A konečně, když je mnohem nižší, počet potřebných párů je enormní.

S/N	Požadovaný počet párů
méně než 1	Veliko
1-2	20-40
více než 2	3-4

Efektivita hackování

S rostoucím počtem kol se zvyšuje složitost kryptoanalýzy, ale zůstává menší než složitost vyčerpávajícího vyhledávání, když je počet cyklů menší než 16.

Závislost na počtu kol
Počet kol	Složitost útoku
$čtyři$	$2^{{4}}$
$6$	$2^{{8}}$
$osm$	$2^{16}$
$9$	$2^{26}$
$deset$	$2^{{35}}$
$jedenáct$	$2^{{36}}$
$12$	$2^{43}$
$13$	$2^{{44}}$
$čtrnáct$	$2^{{51}}$
$patnáct$	$2^{{52}}$
$16$	$2^{{58}}$

Konstrukce S-boxů také významně ovlivňuje účinnost diferenciální kryptoanalýzy. Zejména DES S-boxy jsou optimalizovány pro odolnost proti útokům.

Srovnání s jinými metodami

Viz Známé útoky na DES

Diferenciální kryptoanalýza a systémy podobné DES

Zatímco plný 16-kolový DES byl původně navržen tak, aby byl odolný vůči diferenciální kryptoanalýze, útok se ukázal jako úspěšný proti široké skupině šifer podobných DES [2] .

Lucifer , zkrácený na osm kol, prolomí pomocí méně než 60 šifrových textů.
FEAL -8 je prolomeno pomocí méně než 2000 šifrovaných textů.
FEAL-4 je prolomeno pomocí 8 šifrovaných textů a jednoho otevřeného textu .
FEAL-N a FEAL-NX lze hacknout pomocí . $N\leq 31$

Diferenciální kryptoanalýza je také použitelná proti hashovacím funkcím .

Po publikaci prací o diferenciální kryptoanalýze na počátku 90. let byly následující šifry navrženy tak, aby byly vůči tomuto útoku odolné.

Nevýhody metody

Metoda diferenciální kryptoanalýzy je do značné míry teoretickým úspěchem. Jeho uplatnění v praxi je limitováno vysokými nároky na čas a objem dat.

Být primárně vybraný-prostý text metoda útoku, diferenciální kryptoanalýza je těžko realizovatelná v praxi. Lze jej použít k útoku se známým otevřeným textem, ale v případě plného 16kolového DES je to ještě méně efektivní než útok hrubou silou.

Metoda vyžaduje velké množství paměti pro uložení kandidátských klíčů. Účinnost metody také silně závisí na struktuře S-boxů hacknutého algoritmu.

Viz také

Poznámky

↑ Coppersmith, Don. Data Encryption Standard (DES) a jeho síla proti útokům // IBM Journal of Research and Development : deník. - 1994. - Květen ( roč. 38 , č. 3 ). — S. 243 . - doi : 10.1147/rd.383.0243 . (vyžadováno předplatné)
↑ Biham E. , Shamir A. Diferenciální kryptoanalýza kryptosystémů podobných DES . - 1990. - S. 7 .

Literatura

Bruce Schneier. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojové texty v jazyce C.
Panasenko, S. „Moderní metody pro prolomení šifrovacích algoritmů, část 3“ . Hlavní informační důstojník - 2006 . Archivováno 15. ledna 2010 na Wayback Machine
Biham E. , Shamir A. Diferenciální kryptoanalýza standardu pro šifrování dat.
Biham E. , Shamir A. Diferenciální kryptoanalýza kryptosystémů podobných DES (anglicky) . — 1990.