Differential cryptanalysis
Diferenciální kryptoanalýza je obecná forma dešifrování použitelné především blokové šifry , ale také proudových šifer a kryptografické hašovací funkce . V nejširším slova smyslu, to je studie o tom, jak rozdíly v vstup může mít vliv na výslednou rozdíl na výstupu . V případě blokové šifry, to se odkazuje na soubor technik pro sledování rozdílů prostřednictvím sítě transformací, objevování, kde šifra vykazuje non- náhodné chování, a využití těchto vlastností obnovit tajný klíč .
Objev diferenciální kryptoanalýzy je obecně přičítán Eli Biham a Adi Shamir v pozdní 1980, který publikoval řadu útoků proti různým blokových šifer a hašovacích funkcí, včetně teoretické slabosti Data Encryption Standard (DES).Bylo konstatováno, podle Biham a Shamir že DES je překvapivě odolný vůči diferenciální kryptoanalýzy, v tom smyslu, že i malé změny v algoritmu by to mnohem citlivější. [ 1 ]
V roce 1994, člen původního IBM DES týmu, Don kotlář , publikoval článek o tom, že rozdíl kryptoanalýza byla známa IBM již v roce 1974, a že obrana proti diferenciální kryptoanalýzy byl cíl návrhu. [ 2 ] Podle autora Steven Levy , IBM objevil diferenciální dešifrování na jeho vlastní, a NSA byl zřejmě dobře vědom techniky. [ 3 ] IBM stále nějaké tajemství, jak Coppersmith vysvětluje: "Po jednáních s NSA, bylo rozhodnuto, že zpřístupnění návrhových úvah by odhalit techniku diferenciální kryptoanalýzy, silný technika, která by mohla být použita proti mnoha šifer. To by oslabilo konkurenční výhodu Spojené státy měly před ostatními zeměmi v oblasti kryptografie. " [ 2 ] V rámci IBM, byl známý rozdíl kryptoanalýza jako "T-útoku" [ 2 ] , nebo "Tickle útok". [ 4 ]
Zatímco DES byl navržen s odolností vůči diferenciální kryptoanalýzy na mysli, jiní současní kódy ukázaly jako zranitelné. Brzy cíl pro útok byl FEAL bloková šifra. Původní navrhované verze se čtyřmi koly (FEAL-4) lze rozdělit pomocí pouze osm vybraných holé , a dokonce i 31-kulatý verze FEAL je náchylná k útoku.
Diferenciální kryptoanalýza je obvykle vybrán útok holého textu , což znamená, že útočník musí být schopen získat šifrované ciphertexts pro nějakého souboruholé jeho výběru. Režim může úspěšně cryptanalyze DES s úsilím o objednávce 2 47 vybraných holé. Tam být, nicméně, rozšíření, které by umožňovalo známý holý nebo dokonce ciphertext-jediný útok . Základní metoda používá dvojice prostý text související s konstantní rozdíl , rozdíl může být definována několika způsoby, ale eXclusive OR (XOR) operace je obvyklé.Útočník poté vypočítá rozdíly odpovídajících ciphertexts, doufali, že detekujeme statistické vzory v jejich distribuci. Výsledný pár rozdílů se nazývádiferenciální . Jejich statistické vlastnosti závisí na povaze S-boxůpoužívaných pro šifrování, takže útočník analýzy rozdíly (Δ X , Δ Y ), kde Δ Y =S ( X ⊕ Δ X ) ⊕ S ( X ) (a ⊕ označuje výhradní nebo) pro každý takový S-box S. V základním útoku, je jedna konkrétní ciphertext rozdíl Očekává se, že bude obzvláště častý; tímto způsobem, šifrování mohou být rozlišeny od náhodné .Sofistikovanější varianty umožňují klíč má být navrácena rychleji nežvyčerpávající hledání .
V nejzákladnější podobě klíčového zotavení přes diferenciální kryptoanalýzy, útočník žádostí o ciphertexts pro velké množství párů holého, pak se předpokládá, že rozdíl platí pro alespoň r-1 kola, kde R je celkový počet kol.Útočník pak dovozuje, které kolo klíče (při závěrečném kole) jsou možné za předpokladu, že rozdíl mezi bloky před finále je stanoven. Když kulaté klávesy jsou krátké, toho lze dosáhnout tím, že prostě taxativně dešifrování ciphertext párů jedno kolo s každou možnou kulatým tlačítkem. Když jedno kolo klíč byl považován za potenciální kolo klíč podstatně častěji než jakékoli jiné klávesy, předpokládá se, že bude správné kolo klíč.
Pro konkrétní šifry, musí být vstup rozdíl být pečlivě vybrány, pokud útok je, aby byla úspěšná. Analýza algoritmu internals je proveden; standardní metoda je sledovat cestu z vysoce pravděpodobných rozdílů prostřednictvím různých fázích šifrování, nazval rozdíl charakteristika .
Vzhledem k tomu, rozdíl dešifrování stalo veřejně známým, se stala základním zájmem šifrovacích designérů. Nové vzory se očekává, že budou doloženy důkazem, že algoritmus je odolný proti tomuto útoku, a mnoho, včetněAdvanced Encryption Standard , byly prokázáno bezpečné před útokem.
Útok spočívá především v tom, že vzhledem k vstupní / výstupní rozdíl vzor dochází pouze k určité hodnoty vstupů. Obvykle útok se používá v podstatě na nelineárních prvků, jako kdyby byly Pevná složka (obvykle jsou ve skutečnosti vypadají-up stoly či sboxes ). Pozorování požadovanou výstupní rozdíl (mezi dvěma vybranými nebo známé vstupy holého) naznačuje možné hodnoty klíče.
Například, je-li diferenciál 1 => 1 (což znamená, že rozdíl v LSB vstupu vede k výstupu rozdílu v LSB) dochází s pravděpodobností z 4/256 (je to možné s nelineární funkce v kódu AES pro instance), pak za pouhých 4 hodnoty (nebo 2 páry) vstupů je, že rozdíl je to možné. Předpokládejme, že máme non-lineární funkci, kde je klíč XOR'ed před hodnocením a hodnot, které umožňují rozdíl je {2,3} a {4,5}. Pokud útočník odešle v hodnotách {6, 7} a dodržuje správnou výstupní rozdíl znamená to, že klíč je buď 6 xor K = 2 nebo 6 xor K = 4, což znamená, že klíč je buď K = {2,4}.
V podstatě u n-bitové nelineární funkce jeden by ideálně směřují k blízkosti 2 - (n-1), jak je to možné, aby bylo dosaženo diferenciální jednotnosti . Když se to stane, rozdíl útok vyžaduje tolik práce, aby určil klíč jak jednoduše hovado nutit klíč.
AES nelineární funkce má maximální diferenciální pravděpodobnosti 4/256 (většina záznamů však jsou 0 nebo 2). To znamená, že teoreticky by bylo možné určit klíč poloviny tolik práce jako hrubé síly, ale vysoká pobočka AES zabraňuje vysoká pravděpodobnost, stezky z existujících na více kolech. Ve skutečnosti, by AES šifra být stejně imunní diferenciální a lineární útoky s mnohem slabším nelineární funkce. Neuvěřitelně vysoké větev (aktivní sbox počet) ze dne 25. přes 4R znamená, že více než 8 kol žádný útok zahrnuje méně než 50 nelineárních transformací, což znamená, že pravděpodobnost úspěchu nepřesahuje Pr [útok] <= Pr [nejlepší útok na sbox ] 50 . Například, s aktuálním sbox AES vydává žádný pevný diferenciál s pravděpodobností vyšší než (4/256) 50 nebo 2 -300 , která je mnohem nižší než požadovaná hranicí 2-128 pro 128-bitová bloková šifra. To by umožnilo prostor pro efektivnější sbox, i když je to 16-jednotný pravděpodobnost útoku by ještě byli 2 -200 .
Existuje žádné bijections pro stejně velké vstupů / výstupů s 2-uniformitě.Existují v lichých polí (jako je GF (2 7 )) za použití buď Cubing nebo inverze (existují další exponenty, které mohou být použity i). Například S (x) = x 3 v každém zvláštním binární pole je imunní vůči diferenciálu a lineární dešifrování.Toto je z části proč mlhavé designy používají 7 - a 9-bitové funkce v 16-bitové nelineární funkce. Co jsou tyto funkce získat v imunitě diferenciálních a lineární útoky, které ztrácejí na algebraické útoky. To znamená, že je možné popsat a vyřešit přes sat solver. Toto je z části proto AES (například) má afinní mapování po inverzi.