Útok bumerangem

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é 18. prosince 2014; kontroly vyžadují 34 úprav .

Bumerangový útok je kryptografický útok na blokovou šifru založený na metodách diferenciální kryptoanalýzy . Algoritmus útoku publikoval v roce 1999 profesor Berkeley University David Wagner, který jej použil k prolomení šifer COCONUT98 , Khufu a CAST-256 [1] .

Tato metoda umožnila provádět úspěšné útoky na mnoho šifer dříve uznávaných jako odolné vůči „klasické“ diferenciální kryptoanalýze.

Existují modifikace této metody kryptoanalýzy: zesílený bumerangový útok (zesílený bumerangový útok) a obdélníkový útok (obdélníkový útok).

Obecná charakteristika

Bumerangový útok je založen na principech diferenciální kryptoanalýzy . Metoda bumerangu spočívá v použití kvartetu otevřených textů a jim odpovídajících šifrových textů, spíše než dvojice, jako v diferenciální kryptoanalýze.

Dalším významným rozdílem mezi metodou bumerangu a klasickou diferenciální kryptoanalýzou, kde změny v šifrovém textu způsobené změnami v otevřeném textu pokrývají celou šifru, je to, že změny v otevřeném textu mohou pokrýt pouze část šifry.

V některých případech může použití této metody útoku výrazně snížit množství požadovaných dat (ve srovnání s diferenciální kryptoanalýzou). Kromě toho je útok použitelný na algoritmy s heterogenní kruhovou strukturou.

Jednou z nejzajímavějších vlastností útočného algoritmu je, že velmi dobře funguje se šiframi, které mají asymetrické kruhové funkce. Asymetrické kruhové funkce lze rozdělit do dvou typů: náboje typu A, které mají lepší dopřednou difúzi než zpětné, a náboje typu B, které mají lepší zpětnou difúzi. Je třeba poznamenat, že pokud se první polovina šifry skládá z kol typu B a druhá z kol typu A, pak bude taková šifra nejzranitelnější vůči útoku bumerangu.

Algoritmus útoku

Předpokládejme nejprve, že šifrovací algoritmus lze rozdělit do dvou po sobě jdoucích částí, přibližně stejně složitých , a , a , kde je nějaký otevřený text. Například 16kolový algoritmus DES s koly podobné struktury lze rozdělit na dvě části po 8 kolech $E$ $E_{0}$ $E_1$ $E(M)=E_{1}(E_{0}(M))$ $M$
Zvolme dvojici otevřených textů a s rozdílem . V důsledku zpracování těchto textů funkcí získáme rozdíl $P$ $P^{'}$ $\Delta =P\oplus P'$ $E_{0}$ $\Delta ^{*}=E_{0}(P)\oplus E_{0}(P^{'})$
Pokračujeme v šifrování otevřených textů a funkcí a získáme dva šifrované texty a $P$ $P'$ $E_1$ $C=E_{1}(E_{0}(P))$ $C^{'}=E_{1}(E_{0}(P^{'}))$
Používáme a k získání dvou dalších šifrových textů spojených s předchozím rozdílem $C$ $C^{'}$ $D$ $D^{'}$ $\nabla =C\oplus D=C^{'}\oplus D'$
Tvorba kvarteta dále pokračuje v opačném směru: funkce „polodešifrování“ jsou aplikovány na a a pro získání rozdílu $D$ $D^{'}$ $E_{{1}}^{{-1}}$ $E_{{0}}^{{-1}}$ $\nabla ^{*}=E_{{1}}^{{-1}}(D)\oplus E_{{0}}(P)=E_{{1}}^{{-1}}(D ^{'})\oplus E_{{0}}(P^{'})$
Další dešifrování šifrových textů a dává dva otevřené texty a $D$ $D^{'}$ $Q=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D))$ $Q^{'}=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D^{'}))$

Wagner navíc ve své práci [1] dokazuje, že rozdíl mezi takto získanými otevřenými texty a je roven rozdílu mezi původními otevřenými texty a a je roven . $Q$ $Q^{'}$ $P$ $P^{'}$ $\Delta$

Při analýze souboru kvartetů textů s určitým rozdílem lze vybrat určitý klíč (nebo jeho fragment), který je požadovaným klíčem buď jednoznačně nebo s nejvyšší (ve srovnání s jinými klíči) pravděpodobností.

Rozšířený útok bumerangem [2]

Vylepšený bumerangový útok je útok v prostém textu , zatímco klasický bumerangový útok je adaptivně zvolený útok v prostém textu .

Při porovnání těchto dvou algoritmů, za jinak stejných okolností, klasický bumerangový útok vyžaduje mnohem méně dat než vylepšený. Na první pohled taková změna v algoritmu nepřináší výhody. Existují však tři body, které jej odlišují od klasického útoku, a proto se v některých případech vyplatí použít vylepšený útok:

Při útoku v otevřeném textu je možné uhodnout klíč na konci šifry, aniž by bylo nutné zvyšovat počet vybraných otevřených textů.
Zesílený bumerangový útok je možné aplikovat nejen na dvojice, ale i na K-sady textů.
Jeden může použít posilovací útok k získání páru (nebo K) textů pro určitou část šifry a pak použít jiné algoritmy pro zbývající kola šifry. Lze tedy použít zkrácenou diferenciální kryptoanalýzu , která definuje pouze malou část bloku a nelze ji použít se standardním bumerangovým útokem.

Šifrovací algoritmy zranitelné vůči bumerangovým útokům

Popsáno v původním článku [1]

COCONUT98 praská s adaptivně vybranými otevřenými a šifrovými texty. $2^{16}$
Šestnáctikolový Chufu je prošpikován adaptivně vybranými otevřenými a šifrovými texty. $2^{18}$
16 kulatých trhlin CAST-256 se známými texty. $2^{{49,3}}$

Popsáno v jiných zdrojích

6- kolová KASUMI je prolomena adaptivně vybranými holými texty a šifrovými texty [3] . $2^{13}$
11- kolové MARS trhliny se slavnými texty [2] . $2^{{65}}$
8kolové Hadí cracky se slavnými texty [2] . $2^{{114}}$
5-kruhové trhliny AES se známými texty [4] . $2^{{39}}$
6-kruhové trhliny AES se známými texty [4] . $2^{{71}}$

Aplikace na plnohodnotné AES [5]

Principy bumerangového útoku a vylepšeného bumerangového útoku byly použity k provedení útoku s propojeným klíčem na šifry AES -192 a AES-256. Tato metoda se opírá o detekci lokálních kolizí v blokových šifrách a použití bumerangových přepínačů.

Standardně je šifra rozdělena na kola, ale toto rozdělení není pro útok bumerangem vždy nejlepší. Bylo navrženo rozdělit kola na jednoduché operace a využít paralelismus existující v těchto operacích. Některé bajty lze například zpracovat nezávisle. V takovém případě může být před převodem šifrovacím algoritmem nejprve zpracován jeden bajt, načež se po převodu přepne na zpracování dalšího bajtu. Existují žebříkové spínače, spínače Feistel a spínače s-box.

Tato metoda útoku je účinnější než útok hrubou silou . Zároveň je však třeba poznamenat, že metoda má pro specialisty především teoretickou hodnotu a nebude v blízké budoucnosti představovat hrozbu pro praktické implementace AES kvůli vysokým nárokům na čas zpracování a výpočetní výkon. Na druhou stranu lze tuto techniku poměrně efektivně aplikovat na útoky pomocí kryptografických hashovacích funkcí .

Aplikace pro hašovací funkce

Protože mnoho hashovacích funkcí je založeno na blokových šifrách , je přirozené zkoušet na ně bumerangové útoky, ale existuje několik překážek. Zejména dešifrování, které je nedílnou součástí bumerangového útoku, nemusí být dostupné v kontextu hašovacích funkcí.

Bylo však ukázáno [6] , že bumerangový útok, konkrétně jeho varianta, vylepšený bumerangový útok založený na otevřeném textu, lze použít k prolomení hashovací funkce. Tento typ útoku poskytuje vylepšení oproti dříve používaným diferenciálním útokům .

Hlavní myšlenkou adaptace útoku je použít kromě pečlivě zvolené globální diferenciální cesty používané v klasických diferenciálních útocích několik dalších diferenciálních cest, které jsou velmi dobré v omezeném počtu fází, ale nepokrývají úplně celou funkci. . Aby bylo možné tyto rozdílové cesty zkombinovat dohromady, je použito základní schéma útoků blokovou šifrou využívající metodu bumerang.

Tento útok byl úspěšně aplikován na algoritmus SHA-1 .

Nevýhody algoritmu

Bumerangový útok je adaptivní volba útoku v otevřeném a šifrovaném textu. Jedná se o jeden z nejobtížněji realizovatelných typů kryptografických útoků v praxi.

Pokud jde o metodu diferenciální kryptoanalýzy, je praktická aplikace bumerangového útoku limitována vysokými nároky na čas zpracování a objem dat.

V praxi byl útok bumerangem aplikován především na šifry se sníženým počtem nábojů.

V tomto ohledu je algoritmus spíše teoretickým úspěchem.

Poznámky

↑ 1 2 3 David Wagner. Útok bumerangem .
↑ 1 2 3 John Kelsey , Tadayoshi Kohno, Bruce Schneier . Zesílené bumerangové útoky proti redukovaným kruhům MARS a hadům .
↑ Eli Biham , Orr Dunkelman, Nathan Keller. Obdélníkový útok souvisejícího klíče na celé KASUMI .
↑ 12 Alex Biryukov . Útok bumerangu na 5 a 6 kol se sníženým AES .
↑ Alex Biryukov , Dmitrij Chovratovič. Související klíčová kryptoanalýza plného AES-192 a AES-256 .
↑ Antoine Joux, Thomas Peyrin. Hashovací funkce a (zesílený) útok bumerangu .

Literatura

Panasenko S. P. Šifrovací algoritmy. Speciální referenční kniha - Petrohrad. : BHV-SPb , 2009. - 576 s. — ISBN 978-5-9775-0319-8