Bumeráng támadás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2014. december 18-án áttekintett verziótól ; az ellenőrzések 34 szerkesztést igényelnek .

A bumeráng támadás egy blokkrejtjel elleni titkosítási támadás , amely differenciális kriptográfiai módszereken alapul . A támadási algoritmust 1999-ben tette közzé a Berkeley Egyetem professzora, David Wagner, aki a COCONUT98 , Khufu és CAST-256 titkosítások feltörésére használta [1] .

Ez a módszer lehetővé tette, hogy sikeres támadásokat hajtsanak végre számos olyan rejtjel ellen, amelyeket korábban a „klasszikus” differenciális kriptoanalízisnek ellenállónak ismertek fel.

Ennek a kriptográfiai módszernek vannak módosításai: fokozott bumeráng támadás (erősített bumeráng támadás) és négyszögletű támadás (téglalap támadás).

Általános jellemzők

A bumeráng támadás a differenciális kriptoanalízis elvein alapul . A bumeráng-módszer abból áll, hogy egyszerű szövegek kvartettjét és a hozzájuk tartozó rejtjelezett szövegeket használjuk, nem pedig egy párat, mint a differenciális kriptoanalízisben.

Egy másik figyelemre méltó különbség a bumeráng-módszer és a klasszikus differenciális kriptoanalízis között, ahol a nyílt szöveg változásai által okozott rejtjelezett szöveg változásai a teljes rejtjelet lefedik, hogy a nyílt szöveg változtatásai csak a rejtjel egy részét fedhetik le.

Egyes esetekben ennek a támadási módszernek a használata jelentősen csökkentheti a szükséges adatok mennyiségét (a differenciális kriptoanalízishez képest). Ezenkívül a támadás heterogén kerek szerkezetű algoritmusokra is alkalmazható.

A támadási algoritmus egyik legérdekesebb tulajdonsága, hogy nagyon jól működik az aszimmetrikus kerek függvényekkel rendelkező rejtjelekkel. Az aszimmetrikus körfüggvények két típusra oszthatók: A-típusú körökre, amelyek jobb előre diffúzióval rendelkeznek, mint visszafelé, és B-típusú körökre, amelyek jobb visszafelé diffúzióval rendelkeznek. Megjegyzendő, hogy ha a rejtjel első fele B-típusú, a második pedig A-típusú lövedékekből áll, akkor egy ilyen rejtjel a legsebezhetőbb a bumeráng támadásokkal szemben.

Támadási algoritmus

Először is tegyük fel, hogy a titkosítási algoritmus két egymást követő részre osztható, amelyek bonyolultsága megközelítőleg egyenlő , és , és , ahol van néhány egyszerű szöveg. Például egy 16 körből álló DES algoritmus hasonló szerkezetű fordulókkal két 8 körből álló részre osztható. $E$ $E_{0}$ $E_1$ $E(M)=E_{1}(E_{0}(M))$ $M$
Válasszunk egy pár nyitott szöveget és különbséggel . Ezen szövegek függvény általi feldolgozása eredményeként megkapjuk a különbséget $P$ $P^{'}$ $\Delta =P\oplus P'$ $E_{0}$ $\Delta ^{*}=E_{0}(P)\oplus E_{0}(P^{'})$
Folytatjuk a nyílt szövegek titkosítását és a függvényt , és két titkosított szöveget kapunk és $P$ $P'$ $E_1$ $C=E_{1}(E_{0}(P))$ $C^{'}=E_{1}(E_{0}(P^{'}))$
Két másik rejtjelezett szöveget használunk és kapunk , amelyek az előző különbséghez kapcsolódnak $C$ $C^{'}$ $D$ $D^{'}$ $\nabla =C\oplus D=C^{'}\oplus D'$
Továbbá a kvartett kialakulása ellentétes irányban folytatódik: a "félig dekódoló" funkciókat alkalmazzák és és a különbség eléréséhez. $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^{'})$
A rejtjelezett szövegek további dekódolása és ad két egyszerű szöveget és $D$ $D^{'}$ $Q=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D))$ $Q^{'}=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D^{'}))$

Sőt, Wagner [1] munkájában bebizonyítja, hogy az így kapott nyílt szövegek és közötti különbség egyenlő az eredeti nyílt szövegek és és a különbséggel egyenlő . $K$ $Q^{'}$ $P$ $P^{'}$ $\Delta$

Egy bizonyos különbségű szövegnégyes halmazát elemezve ki lehet választani egy bizonyos kulcsot (vagy annak töredékét), amely vagy egyértelműen, vagy a legmagasabb (más kulcsokhoz képest) valószínűséggel a kívánt kulcs.

Továbbfejlesztett bumerángtámadás [2]

A továbbfejlesztett bumeráng támadás egy egyszerű szöveges támadás , míg a klasszikus bumerángtámadás egy adaptívan választott egyszerű szöveges támadás .

Ha összehasonlítjuk ezt a két algoritmust, a többi tényező azonossága mellett a klasszikus bumeráng támadás sokkal kevesebb adatot igényel, mint a továbbfejlesztett. Első pillantásra az algoritmus ilyen változtatása nem hoz előnyöket. Három pont különbözteti meg azonban a klasszikus támadástól, ami miatt bizonyos esetekben érdemes továbbfejlesztett támadást alkalmazni:

Egy egyszerű szöveges támadásnál lehetőség van a titkosítás végén lévő kulcs kitalálására anélkül, hogy növelni kellene a választott nyílt szövegek számát.
Nemcsak párokra, hanem K-halmazokra is lehet kiterjesztett bumeráng támadást alkalmazni.
Boost támadást használhatunk egy pár (vagy K) szöveg megszerzésére a titkosítás bizonyos részéhez, majd más algoritmusokat használhatunk a rejtjelezés hátralévő köreihez. Így használható a csonka differenciális kriptoanalízis , amely a blokknak csak egy kis részét határozza meg, és nem használható szabványos bumeráng támadásnál.

A bumeráng támadásokkal szemben kiszolgáltatott titkosítási algoritmusok

Leírva az eredeti cikkben [1]

A COCONUT98 adaptívan választott egyszerű és titkosított szövegekkel reped . $2^{16}$
A 16 körből álló Khufu adaptívan kiválasztott egyszerű és titkosított szövegekkel van feltörve. $2^{18}$
16 kerek CAST-256 repedés ismert szövegekkel. $2^{{49.3}}$

Leírva más forrásokban

A 6 körös KASUMI - t adaptívan választott sima szövegekkel és titkosított szövegekkel törik [3] . $2^{13}$
11 körös MARS - repedés híres szövegekkel [2] . $2^{{65}}$
8 körös Serpent cracks híres dalszövegekkel [2] . $2^{{114}}$
5 körös AES repedések ismert szövegekkel [4] . $2^{{39}}$
6 körös AES repedések ismert szövegekkel [4] . $2^{{71}}$

Alkalmazás teljes körű AES-re [5]

A bumeráng támadás és a továbbfejlesztett bumeráng támadás elvét alkalmazták az AES -192 és AES-256 teljes körű titkosítók linkelt kulcsú támadásainak végrehajtására . Ez a módszer a blokk titkosítások lokális ütközésének észlelésén és bumeráng kapcsolók használatán alapul.

Alapértelmezés szerint a titkosítás körökre van osztva, de ez a felosztás nem mindig a legjobb bumeráng támadáshoz. Javasoltuk, hogy a köröket egyszerű műveletekre ossza fel, és használja fel az ezekben a műveletekben meglévő párhuzamosságot. Például néhány bájt önállóan is feldolgozható. Ilyen esetben a titkosítási algoritmus a konverzió előtt először egy bájtot dolgozhat fel, majd az átalakítás után egy másik bájt feldolgozására vált át. Vannak létrakapcsolók, Feistel kapcsolók és s-box kapcsolók.

Ez a támadási módszer hatékonyabb, mint a brute force támadás . Ugyanakkor meg kell jegyezni, hogy a módszer elsősorban elméleti értékű a szakemberek számára, és a feldolgozási időre és a számítási teljesítményre vonatkozó magas követelmények miatt nem jelent veszélyt a közeljövőben az AES gyakorlati megvalósítására. Másrészt ez a technika meglehetősen hatékonyan alkalmazható kriptográfiai hash függvény támadásokra .

Alkalmazás hash függvényekhez

Mivel sok hash függvény blokk titkosításon alapul , természetes, hogy bumeráng támadásokat próbálunk ki ellenük, de ennek számos akadálya van. Konkrétan előfordulhat, hogy a visszafejtés, amely a bumeráng támadás szerves részét képezi, nem érhető el a hash függvényekkel kapcsolatban.

Mindazonáltal kimutatták [6] , hogy egy bumeráng támadás, nevezetesen annak egy változata, egy továbbfejlesztett egyszerű szöveg alapú bumeráng támadás, használható egy hash függvény feltörésére. Ez a fajta támadás előrelépést jelent a korábban használt differenciális támadásokhoz képest .

A támadás-adaptáció fő gondolata, hogy a klasszikus differenciális támadásokban használt, gondosan megválasztott globális differenciálút mellett számos további differenciálút is használható, amelyek korlátozott számú szakaszban nagyon jók, de nem fedik le teljesen a funkciót. . Ezen differenciális utak kombinálásához egy alap blokk titkosítási sémát használnak a bumeráng módszerrel.

Ezt a támadást sikeresen alkalmazták az SHA-1 algoritmuson .

Az algoritmus hátrányai

A bumeráng támadás a nyílt és titkosított szöveges támadás adaptív választása. Ez a kriptográfiai támadások egyik legnehezebben megvalósítható típusa a gyakorlatban.

Ami a differenciális kriptoanalízis módszerét illeti, a bumeráng támadás gyakorlati alkalmazását a feldolgozási időre és az adatmennyiségre vonatkozó magas követelmények korlátozzák.

A gyakorlatban a bumeráng támadást főként a csökkentett lövésszámú rejtjelekre alkalmazták.

Ebből a szempontból az algoritmus inkább elméleti vívmány.

Jegyzetek

↑ 1 2 3 David Wagner. A bumeráng támadás .
↑ 1 2 3 John Kelsey , Tadayoshi Kohno, Bruce Schneier . Erősített bumeráng támadások a redukált fordulójú MARS és a kígyó ellen .
↑ Eli Biham, Orr Dunkelman, Nathan Keller. Kapcsolódó kulcsú téglalap támadás a teljes KASUMI ellen .
↑ 12 Alex Biryukov . A Boomerang Attack 5 és 6 körös csökkentett AES-en .
↑ Alex Birjukov, Dmitrij Khovratovics. A teljes AES-192 és AES-256 kapcsolódó kulcsú kriptoanalízise .
↑ Antoine Joux, Thomas Peyrin. Hash függvények és a (erősített) bumeráng támadás .

Irodalom

Panasenko S. P. Titkosítási algoritmusok. Különleges kézikönyv - Szentpétervár. : BHV-SPb , 2009. - 576 p. — ISBN 978-5-9775-0319-8