Boomerang attack

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 december 2014; kontroller kräver 34 redigeringar .

En bumerangattack är en kryptografisk attack på ett blockchiffer baserat på differentiella kryptoanalysmetoder . Attackalgoritmen publicerades 1999 av professorn David Wagner vid Berkeley University, som använde den för att bryta chifferna COCONUT98 , Khufu och CAST-256 [1] .

Denna metod gjorde det möjligt att utföra framgångsrika attacker på många chiffer som tidigare erkänts som resistenta mot "klassisk" differentiell kryptoanalys.

Det finns modifieringar av denna kryptoanalysmetod: förstärkt boomerangattack (förstärkt boomerangattack) och rektangulär attack (rektangelattack).

Allmänna egenskaper

Bumerangattacken är baserad på principerna för differentiell kryptoanalys . Boomerangmetoden består i att använda en kvartett av klartexter och deras motsvarande chiffertexter, snarare än ett par, som i differentiell kryptoanalys.

En annan anmärkningsvärd skillnad mellan boomerangmetoden och klassisk differentiell kryptoanalys, där ändringar i chiffertexten orsakade av ändringar i klartexten täcker hela chifferet, är att ändringar av klartexten bara kan täcka en del av chifferen.

I vissa fall kan användningen av denna attackmetod avsevärt minska mängden nödvändig data (jämfört med differentiell kryptoanalys). Dessutom är attacken tillämpbar på algoritmer med en heterogen rund struktur.

En av de mest intressanta egenskaperna hos attackalgoritmen är att den fungerar väldigt bra med chiffer som har asymmetriska runda funktioner. Asymmetriska runda funktioner kan delas in i två typer: rundor av A-typ, som har bättre diffusion framåt än bakåt, och rundor av B-typ, som har bättre diffusion bakåt. Det noteras att om den första halvan av chifferet består av rundor av B-typ, och den andra av rundor av A-typ, kommer ett sådant chiffer att vara mest sårbart för en bumerangattack.

Attackalgoritm

Låt oss först anta att krypteringsalgoritmen kan delas upp i två på varandra följande delar, ungefär lika i komplexitet , och , och , där är viss klartext. Till exempel kan en 16-runda DES-algoritm med rundor av liknande struktur delas upp i två delar om 8 omgångar $E$ $E_{0}$ $E_1$ $E(M)=E_{1}(E_{0}(M))$ $M$
Låt oss välja ett par öppna texter och med skillnad . Som ett resultat av att bearbeta dessa texter med funktionen får vi skillnaden $P$ $P^{'}$ $\Delta =P\oplus P'$ $E_{0}$ $\Delta ^{*}=E_{0}(P)\oplus E_{0}(P^{'})$
Vi fortsätter att kryptera klartexter och funktion och får två chiffertexter och $P$ $P'$ $E_1$ $C=E_{1}(E_{0}(P))$ $C^{'}=E_{1}(E_{0}(P^{'}))$
Vi använder och för att få två andra chiffertexter och associerade med den tidigare skillnaden $C$ $C^{'}$ $D$ $D^{'}$ $\nabla =C\oplus D=C^{'}\oplus D'$
Vidare fortsätter bildandet av kvartetten i motsatt riktning: "semi-dekrypterings"-funktionerna tillämpas på och och för att erhålla skillnaden $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^{'})$
Ytterligare dekryptering av chiffertexter och ger två klartexter och $D$ $D^{'}$ $Q=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D))$ $Q^{'}=E_{{0}}^{{-1}}(E_{{1}}^{{-1}}(D^{'}))$

Dessutom bevisar Wagner i sitt arbete [1] att skillnaden mellan de sålunda erhållna klartexterna och är lika med skillnaden mellan de ursprungliga klartexterna och och är lika med . $F$ $Q^{'}$ $P$ $P^{'}$ $\Delta$

Genom att analysera en uppsättning kvartetter av texter med en viss skillnad kan man välja en viss tonart (eller dess fragment), som är den önskade tonarten antingen entydigt eller med högst (jämfört med andra tonarter) sannolikhet.

Förbättrad boomerangattack [2]

Förbättrad bumerangattack är en klartextattack , medan klassisk bumerangattack är en adaptivt vald klartextattack .

När man jämför dessa två algoritmer, allt annat lika, kräver den klassiska bumerangattacken mycket mindre data än den förbättrade. Vid första anblicken ger en sådan förändring i algoritmen inga fördelar. Det finns dock tre punkter som skiljer den från den klassiska attacken, vilket gör det värt att använda en utökad attack i vissa fall:

I en klartextattack är det möjligt att gissa nyckeln i slutet av chifferet utan att behöva öka antalet valda klartexter.
Det är möjligt att tillämpa en förbättrad boomerangattack inte bara på par utan också på K-uppsättningar av texter.
Man kan använda en boostattack för att få ett par (eller K) texter för någon del av chifferet, och sedan använda andra algoritmer för de återstående omgångarna av chifferet. Således kan trunkerad differentiell kryptoanalys användas , som bara definierar en liten del av blocket, och kan inte användas med en standardboomerangattack.

Krypteringsalgoritmer sårbara för boomerangattacker

Beskrivs i den ursprungliga artikeln [1]

COCONUT98 spricker med adaptivt valda klartexter och chiffertexter. $2^{16}$
Den 16 runda Khufu är knäckt med adaptivt valda klartexter och chiffertexter. $2^{18}$
16 runda CAST-256 sprickor med kända texter. $2^{{49.3}}$

Beskrivs i andra källor

6-round KASUMI är knäckt med adaptivt valda klartexter och chiffertexter [3] . $2^{13}$
11-runda MARS - sprickor med kända texter [2] . $2^{{65}}$
8-round Serpent spricker med berömda texter [2] . $2^{{114}}$
5-runda AES - sprickor med kända texter [4] . $2^{{39}}$
6-runda AES-sprickor med kända texter [4] . $2^{{71}}$

Ansökan till full-round AES [5]

Principerna för bumerangattack och förbättrad bumerangattack tillämpades för att utföra en länkad-key-attack på AES -192 och AES-256 helomgångs-chiffer . Denna metod bygger på detektering av lokala kollisioner i blockchiffer och användning av bumerangbrytare.

Som standard är chiffret uppdelat i omgångar, men denna uppdelning är inte alltid den bästa för en bumerangattack. Det föreslogs att dela upp omgångarna i enkla operationer och använda den parallellitet som finns i dessa operationer. Till exempel kan vissa bytes bearbetas oberoende. I ett sådant fall kan en byte bearbetas först före konvertering av krypteringsalgoritmen, varefter den växlar till att bearbeta en annan byte efter konvertering. Det finns stegbrytare, Feistel-brytare och s-box-brytare.

Denna attackmetod är effektivare än brute force attack . Men samtidigt noteras att metoden främst är av teoretiskt värde för specialister och inte kommer att utgöra något hot mot praktiska implementeringar av AES inom en snar framtid på grund av höga krav på bearbetningstid och datorkraft. Å andra sidan kan denna teknik tillämpas ganska effektivt på kryptografiska hashfunktionsattacker .

Applikation för hashfunktioner

Eftersom många hashfunktioner är baserade på blockchiffer är det naturligt att prova bumerangangrepp på dem, men det finns flera hinder. I synnerhet kanske dekryptering, som är en integrerad del av en bumerangattack, inte är tillgänglig i samband med hashfunktioner.

Det har dock visat sig [6] att en bumerangattack, nämligen en variant av den, en utökad klartextbaserad bumerangattack, kan användas för att knäcka en hashfunktion. Denna typ av attack ger en förbättring jämfört med tidigare använda differentialattacker .

Huvudidén med attackanpassning är att använda, utöver den noggrant utvalda globala differentialbanan som används vid klassiska differentialattacker, flera ytterligare differentialvägar som är mycket bra i ett begränsat antal stadier, men som inte täcker hela funktionen helt . För att kombinera dessa differentiella vägar tillsammans, används ett grundläggande blockchifferattackschema som använder bumerangmetoden.

Denna attack har framgångsrikt tillämpats på SHA-1- algoritmen .

Nackdelar med algoritmen

En bumerangattack är ett adaptivt val av klartext- och chiffertextattack. Detta är en av de svåraste typerna av kryptografiska attacker att genomföra i praktiken.

När det gäller metoden för differentiell kryptoanalys begränsas den praktiska tillämpningen av bumerangattacken av höga krav på bearbetningstid och datavolym.

I praktiken tillämpades bumerangattacken främst på chiffer med ett minskat antal omgångar.

I detta avseende är algoritmen mer av en teoretisk prestation.

Anteckningar

↑ 1 2 3 David Wagner. Boomerangattacken .
↑ 1 2 3 John Kelsey , Tadayoshi Kohno, Bruce Schneier . Förstärkt Boomerang attackerar mot reducerad runda MARS och orm .
↑ Eli Biham , Orr Dunkelman, Nathan Keller. En relaterad rektangelangrepp på hela KASUMI .
↑ 12 Alex Biryukov . Boomerang-attacken på 5 och 6-rundor reducerad AES .
↑ Alex Biryukov , Dmitrij Khovratovich. Relaterad nyckelkrypteringsanalys av hela AES-192 och AES-256 .
↑ Antoine Joux, Thomas Peyrin. Hash-funktioner och den (förstärkta) Boomerang-attacken .

Litteratur

Panasenko S. P. Krypteringsalgoritmer. Särskild uppslagsbok - St Petersburg. : BHV-SPb , 2009. - 576 sid. — ISBN 978-5-9775-0319-8