Länkad nyckelattack

Related- key attack [ 1] är en typ av kryptografisk attack där en kryptoanalytiker väljer ett förhållande mellan ett par nycklar, men själva nycklarna förblir okända för honom. Data krypteras med båda nycklarna. I den kända klartextvarianten känner kryptoanalytikern till klartexten och chiffertexten för data krypterad med två nycklar. Angriparens mål är att hitta de faktiska hemliga nycklarna. Det antas att angriparen känner till eller väljer någon matematisk relation som länkar ihop nycklarna. Relationen har formen ( ) [2] , där är funktionen vald av angriparen och är de associerade nycklarna. För varje kryptering väljs förhållandet mellan nycklarna individuellt. Det finns många sätt att hitta detta förhållande korrekt [3] . Jämfört med andra attacker där angriparen bara kan manipulera klartexten och/eller chiffertexten, ger valet av relationen mellan de hemliga nycklarna en ytterligare grad av frihet för angriparen. Nackdelen med denna frihet är att sådana attacker kan vara svårare i praktiken. Men designers försöker vanligtvis skapa "ideala" primitiver som automatiskt kan användas utan ytterligare analys i den bredaste möjliga uppsättningen av protokoll eller driftsätt. Att motstå sådana attacker är således ett viktigt designmål för blockchiffer, och i själva verket var det ett av de uttalade designmålen för Rijndael- algoritmen . $K$ $B$ $=$ $F$ $K$ $A$ $F$ $K$ $A$ $K$ $B$

Nyckelförlängning

De flesta krypteringsalgoritmer modifierar den ursprungliga nyckeln för senare användning. Denna modifiering kallas nyckelexpansion . Det finns exempel på algoritmer där nyckelexpansionsproceduren är extremt komplex jämfört med den faktiska krypteringen, bland dem är HPC- och FROG- algoritmerna värda att nämna . Namnet på proceduren bestäms av det faktum att den initiala krypteringsnyckeln vanligtvis har en storlek som är betydligt mindre än uppsättningen av undernycklar som används i omgångarna av algoritmen, det vill säga den utökade nyckeln.

Det visar sig att krypteringsalgoritmen logiskt kan delas in i två subalgoritmer: de faktiska krypteringstransformationerna och nyckelexpansionsproceduren. Det finns ett antal krav för nyckelexpansionsproceduren [4] :

Det krävs att nyckelexpansionsproceduren beräknar nycklar parallellt med krypteringstransformationer: detta kommer att tillåta både parallellisering av beräkningar i multiprocessorsystem och att inte slösa minne för att lagra hela den utökade nyckeln vid kryptering under resursbegränsade förhållanden.
I många tillämpningar av symmetriska krypteringsalgoritmer är det ofta nödvändigt att ändra nycklarna i krypteringsenheten. Följaktligen kommer en mycket komplex nyckelexpansionsprocedur inte att tillåta användningen av en krypteringsalgoritm i dessa fall.
I vilken utsträckning en algoritm är mottaglig för attacker på relaterade nycklar är också starkt beroende av nyckelexpansionsproceduren.

Klassisk länkad nyckelattack [1]

Denna typ av attack föreslogs först av den israeliska vetenskapsmannen Eli Biham 1992 i artikeln New Types of Cryptanalytic Attacks Using Related Keys . Den länkade nyckelattacken som beskrivs av honom liknar en skjuvningsattack . Shift attack ( engelska slide attack ) - kryptografisk attack , som i det allmänna fallet är en attack baserad på vald klartext , som tillåter kryptoanalys av block med flera runda chiffer, oavsett antalet omgångar som används. Föreslagen av Alex Biryukov och David Wagner 1999 [5] . Skiftattacken använder två klartexter och uppfyller följande relation: , där är rundfunktionen och är undernyckeln till den första omgången . En relaterad nyckelattack använder en liknande relation mellan nycklar. Låt oss anta att den önskade krypteringsnyckeln K efter dess modifiering genom nyckelexpansionsproceduren ger en sekvens av undernycklar: , där är antalet rundor av krypteringsalgoritmen. Antag att det finns en nyckel vars expansion ger följande sekvens: , det vill säga sekvensen av undernycklar som skapas på basis av nyckeln skiftas cykliskt i förhållande till sekvensen för den önskade tangenten med 1 varv [6] . $P$ $P'$ $P'=F(P,k_{1})$ $F()$ $k_{1}$ $Ex(K)$ $Ex(K)=\left\{{k_{1},k_{2},\ldots ,k_{r-1},k_{r}}\right\}$ $r$ $K'$ $Ex(K')=\left\{{k_{2},k_{3},\ldots ,k_{r},k_{1}}\right\}$ $K'$ $K$

Kärnan i attacken

Anta att kryptoanalytikern känner till par av klartexter och deras motsvarande chiffertexter (krypterade med nyckeln ), där är storleken på blocket med krypterad data, representerad i bitar . $2^{\frac {n}{2}}$ $\left({P,C}\right)$ $K$ $n$
Dessutom känner kryptoanalytikern till par av texter som krypteras med nyckeln som är associerad med ovanstående förhållande. $2^{\frac {n}{2}}$ $\left({P',C'}\right)$ $K'$ $K$
För varje korrelation av texter måste kryptoanalytikern hitta lösningar på ekvationssystemet [7] : $\left({P,C}\right)$ $\left({P',C'}\right)$

${\begin{cases}F(P,k^{*})=P'\\F(C,k^{*})=C'\end{cases))$

Vilken av texterna som motsvarar respektive text från , vet kryptanalytikern inte i förväg. Men sannolikheten för att två slumpmässigt utvalda texter kommer att uppfylla det erforderliga förhållandet är . Då måste det obligatoriska paret hittas efter att ha analyserat inte mer än texter, i enlighet med födelsedagsparadoxen . Villkoret för texterna är inte strikt, det är en uppskattning och kommer endast att uppfyllas i genomsnitt [8] . $2^{\frac {n}{2}}$ $P$ $P$ ${\displaystyle {\frac {1}{2^{n))))$ $\left({P,P'}\right)$ $2^{{\frac {n}{2}}+1}$ $2^{{\frac {n}{2}}+1}$

Nyckeln som hittas från ovanstående system är den nödvändiga undernyckeln . Beroende på nyckelgenereringsoperationen kan kunskap ge kryptoanalytikern många möjligheter till obehörig åtkomst till information. Till exempel är nyckelgenereringen av LOKI89 -algoritmen konstruerad på ett sådant sätt att den helt enkelt är den vänstra 32-bitarsdelen av nyckeln . Eftersom denna algoritm använder en 64-bitars nyckel räcker det efter beräkningen att bara räkna upp alternativen för att hitta den. [9] $k^{*}$ $k_{1}$ $k_{1}$ $k_{1}$ $K$ $k_{1}$ $K$ $2^{32}$

Den runda funktionen för den attackerade algoritmen måste vara tillräckligt svag för att beräkna , vilket är fallet för de flesta moderna krypteringsalgoritmer. Dessutom kan attackens komplexitet reduceras avsevärt i förhållande till fallet som beskrivs ovan, allt beror på den valda klartextkrypteringsalgoritmen. Till exempel är beräkningar förenklade för algoritmer baserade på ett balanserat Feistel-nätverk . $F()$ $k^{*}$

Attacker på olika krypteringsalgoritmer

Attack mot DES

DES ( data encryption s tandard ) är en algoritm för symmetrisk kryptering utvecklad av IBM och godkänd av den amerikanska regeringen 1977 som en officiell standard ( FIPS 46-3). Blockstorleken för DES är 64 bitar . Algoritmen är baserad på ett Feistel-nätverk med 16 cykler ( rundor ) och en nyckel på 56 bitar . Algoritmen använder en kombination av icke-linjära (S-boxar) och linjära (E, IP, IP-1 permutationer) transformationer.

DES-krypteringsalgoritmen är resistent mot en sådan attack. Under krypteringsprocessen för huvudkrypteringsfunktionen krävs det att man beräknar sexton 48-bitarsnycklar, som är resultatet av att konvertera 56-bitars originalnyckeln ( för mer information, se avsnittet "Nyckelgenerering" ). $k_i$ Antalet skift i nyckelberäkningsalgoritmen stämmer inte överens i alla omgångar. Typiskt skiftas nyckelregistren två bitar efter varje omgång och endast en bit efter den första, nionde och femtonde omgången. Men om du ändrar detta växlingsschema, ställ in växlingen till att vara densamma i alla omgångar, då blir det resulterande kryptosystemet sårbart för en attack med länkad nyckel. Den minst säkra att attackera är den modifierade DES, där nyckeln skiftas med två bitar efter varje steg [10] . $k_i$

Tabellen beskriver antalet skift före varje omgång av nyckelgenerering och den modifierade skiftnummervarianten, som är sårbar för en länkad nyckelattack. För att knäcka en sådan variant av algoritmen skulle kryptoanalytikern bara behöva 2 17 valda klartexter för de valda nycklarna eller 2 33 kända klartexter för de valda nycklarna. För att bryta den modifierade DES är det nödvändigt att utföra 1,43*2 53 operationer, vilket är en liten vinst jämfört med den uttömmande sökningen, där antalet operationer är 2 56 [11] . 1998, med hjälp av en $250 000 EFF DES cracker superdator, knäcktes DES på mindre än tre dagar [12] . EFF DES-cracker använde en brute-force-sökning [13] för att spricka . Enorma krav på tid och datavolym tillåter inte att genomföra en attack på anslutna nycklar utan hjälp av dyr utrustning. Men inte desto mindre är attacken intressant av två anledningar:

Detta är det första försöket till en kryptoanalytisk attack på DES-algoritmen för generering av undernyckel.
Komplexiteten beror inte på antalet steg i den kryptografiska algoritmen, den är lika effektiv mot DES med 16, 32 eller 1000 steg.

Attack mot AES

Advanced Encryption Standard ( AES ), även känd som Rijndael (uttalas [rɛindaːl] (Randal [14] )) är en symmetrisk blockchifferalgoritm (blockstorlek 128 bitar, nyckel 128/192/256 bitar) antagen som en krypteringsstandard av USA:s regering enligt resultaten av AES-tävlingen . Denna algoritm har analyserats väl och används nu flitigt, vilket var fallet med dess föregångare DES . AES finns i tre smaker, var och en ger olika säkerhetsnivåer beroende på längden på den hemliga nyckeln. Nyckeln kan vara 128, 192 och 256 bitar lång. Sedan 2001, efter valet av AES som kryptografisk standard, har framstegen i dess kryptoanalys varit extremt låg [15] . De bästa resultaten erhölls under attacker baserade på relaterade nycklar under 2009. Alex Biryukov , tillsammans med Dmitry Khovratovich, gav den första kryptoanalytiska attacken med länkad nyckel på full-round AES-192 och AES-256, den utvecklade metoden är snabbare än brute force.

Den utvecklade attacken på AES-256 är lämplig för alla typer av nycklar och har en komplexitet på cirka 2 96. En attack mot AES-192 presenterades också. Båda attackerna minimerar antalet aktiva S-boxar i nyckelgenereringsalgoritmen. Denna operation tillämpas med en bumerangattack . Differentiella egenskaper för bumerangen etablerades genom att söka efter lokala kollisioner i chiffer [16] . Den huvudsakliga egenskapen hos AES-256, som är avgörande för de attacker som övervägs, är att krypteringsalgoritmen har 14 rundor och en 256-bitars nyckel som fördubblas i internt tillstånd. Därför består nyckelgenereringsalgoritmen av endast 7 omgångar, och varje omgång har i sin tur 8 S-boxar. På samma sätt för AES-192, på grund av att nyckeln blir en och en halv gånger större i det interna tillståndet, består nyckelgenereringsalgoritmen av endast 8, inte 12 omgångar. Varje omgång har endast 4 S-block.

Attack mot AES-256

Det är nödvändigt att utföra följande steg 2 25,5 gånger [17] :

Förbered strukturen för klartexterna enligt nedan.
Kryptera den med nycklar och och spara de resulterande uppsättningarna och . $K_{A}$ $K_{B}$ $S_{A}$ $S_{B}$
Det är nödvändigt att utföra operationen för alla chiffertexter i och dekryptera de modifierade chiffertexterna med nyckeln . - en ny uppsättning öppna texter. $xor~\Delta _{C}$ $S_{A}$ $K_C$ $S_{C}$
Likaså för och nyckel . - en ny uppsättning öppna texter. $S_{B}$ $K_{D}$ $S_{D}$
Jämförelse av alla par klartexter från och med en längd på 56 bitar. $S_{C}$ $S_{D}$
För alla övriga, kontrollera om det finns en skillnad i sannolikhetsvärdet vid . Om det är lika på båda sidor av 16-bitarsfiltret, då för nyckelpar, annars kallas de en kvartett och , vid , kommer också att vara lika på båda sidorna sidor. $p_{i,0}$ $i>1$ $\left({K_{A},K_{B}}\right)$ $\left({K_{C},K_{D))\right)$ $\nabla k_{i,7}^{0}=0$ $\Delta k_{i,0}^{0}$
Det är nödvändigt att välja kvartetter vars skillnader inte kan påverkas av aktiva S-boxar i den första omgången och aktiva S-boxar i nyckelgenereringsalgoritmen.
Genom att filtrera bort felaktiga kvartetter återställer vi delvis nyckelns värde.

Varje struktur har alla möjliga alternativ för kolumn noll, rad noll och ett konstant värde i andra byte. Av de 272 texterna i varje struktur kan 2144 par jämföras. Av dessa par kommer 2 (144−8*9) = 2 72 att klara den första omgången. Således får vi 1 obligatorisk kvartett om 2 (96-72) = 2 24 strukturer och 3 nödvändiga kvartetter om 2 25,5 strukturer. Vi beräknar antalet kvartetter av de senaste 6 stegen, det blir cirka 2 (144-56-16) = 2 72 par. Nästa steg är att tillämpa ett 16-bitars filter, så vi får det totala antalet möjliga kvartetter 2 (72+25,5−6) = 2 91,5 [18] .

Attack mot AES-192

Nyckelgenereringsalgoritmen i detta fall har den bästa spridningen. Därför använder bumerangattacken två delspår med 6 omgångar vardera. Låt oss analysera 2 73 strukturer med 2 48 texter enligt följande schema [19] :

Jämför alla par av möjliga klartexter för nyckelpar och . $\left({K_{A},K_{B}}\right)$ $\left({K_{C},K_{D))\right)$
Jämför och lagra alla chiffertextkvartetter.
För varje förväntad nyckelbyte : , och in ; i och : $k^{0,3}$ $k^{2,3}$ $k^{0.5}$ $K_{A}$ $k^{0.5}$ $K_{A}$ $K_{B}$
1. beräkna värdena för dessa byte i alla nycklar från deltaspåret. Få nyckelskillnader i och ; $\Delta K^{0}$ $\nabla K^{8}$
2. välj kvartetter som motsäger ; $\nabla K^{8}$
3. förbered räknare för oberäknade nyckelbytes som motsvarar aktiva S-boxar i de två första och sista: , , , — i nycklarna och , , , , — i nycklarna och , 16 byte totalt; $K^{0,0}$ $k^{0,1}$ $k^{1,2}$ $k^{3,0}$ $K_{A}$ $K_C$ $k^{0,0}$ $k^{0,1}$ $k^{0,2}$ $k^{0,3}$ $K_{A}$ $K_{B}$
4. för varje kvartett, ställ in de möjliga värdena för deras okända byte och öka räknarna;
5. skapa en grupp med 16 nyckelbytes med maximala antal;
6. prova alla möjliga värden på nyckelns ännu okända 9 byte och kontrollera att nyckeln är korrekt. Om scenariot misslyckas, gå till första steget [19] . $K^{0}$

Båda presenterade attackerna är huvudsakligen av teoretiskt intresse och utgör i praktiken inte ett verkligt hot mot applikationer som använder AES.

Praktisk tillämpning

De beskrivna attackerna med relaterade nycklar ser inte praktiska ut. I många utvecklingar gynnar de inte mycket jämfört med uttömmande sökning, dessutom kräver de ett stort antal antaganden. Denna attack har länge ansetts vara ganska kraftfull, men rent teoretisk [20] . Men experter som John Kelsey och Bruce Schneier [20] tror nu att attacker med länkade nyckel kan ha praktiska tillämpningar. Vissa implementeringar av kryptografiska algoritmer eller nätverksprotokoll (till exempel autentiserings- eller nyckelutbytesprotokoll) kan redan vara mottagliga för en länkad nyckelattack [20] . En potentiell tillämpning är hashfunktionsanalys . Teoretiskt sett kan attacker med länkade nyckel vara farliga om symmetriska krypteringsalgoritmer används för att bygga hashfunktioner. För närvarande är ingen specifik applikation för hashfunktioner känd, men hashfunktionsdesigner bör ta hänsyn till att en sådan svaghet finns när de designar. I vilket fall som helst rekommenderas det starkt att ta hänsyn till kryptoanalys på associerade nycklar när man utvecklar krypteringsalgoritmer och deras implementering [21] . Det noteras i [20] att huvudvillkoret för attacken ser ganska konstigt ut: kryptoanalytikern kan skriva nyckeln, det vill säga modifiera den önskade okända nyckeln på det sätt som krävs, men kan inte läsa den. Vissa implementeringar av kryptografiska algoritmer eller nätverksprotokoll kan dock attackeras med associerade nycklar. I vilket fall som helst rekommenderas det starkt att ta hänsyn till kryptoanalys på länkade nycklar [20] när man utvecklar krypteringsalgoritmer och deras implementering. Det noteras också att attacker på relaterade nycklar kan vara mycket farliga om symmetriska krypteringsalgoritmer används för att bygga hashfunktioner.

Det finns andra potentiella sårbarheter som introduceras i krypteringsalgoritmen genom en dåligt utformad nyckelexpansionsprocedur, särskilt [22] :

sårbarhet för attacker från "meeting in the middle"-klassen, eftersom dessa attacker utnyttjar det faktum att den första delen av krypteringstransformationerna av den attackerade algoritmen använder en annan uppsättning nyckelbitar. än den andra delen.
Svaga nycklar är nycklar som motsvarar dechiffrering eller har andra egenskaper som gör det lättare att knäcka.
ekvivalenta nycklar - olika nycklar, men ger samma krypteringsresultat på en viss delmängd av klartext.
nyckelklasser - uppstår när en kryptoanalytiker relativt enkelt kan bestämma delmängden av nyckeluppsättningen som den nödvändiga nyckeln tillhör, och följaktligen minska området för den fullständiga uppräkningen av nyckeln.

Se även

Nyckelgissad attack

Anteckningar

↑ 1 2 Panasenko S., 2009 , sid. 54.
↑ Biryukov och Khovratovich, 2009 , sid. åtta.
↑ Bellare, 2003 , sid. 491.
↑ Panasenko S., 2009 , sid. 53.
↑ Biryukov, Wagner, 1999 , sid. 245-259.
↑ Biryukov och Khovratovich, 2009 , sid. 7.
↑ Biham, 1994 , sid. 16.
↑ Panasenko S., 2009 , sid. 55.
↑ Panasenko S., 2009 , sid. 56.
↑ Biham, 1994 , sid. femton.
↑ Biham, 1994 , sid. 17.
↑ Computerworld, 1998 .
↑ DES Cracker Project (nedlänk) . Eff. — "Onsdagen den 17 juli 1998 vann EFF DES Cracker, som byggdes för mindre än $250 000, enkelt RSA Laboratorys "DES Challenge II"-tävling och ett kontantpris på $10 000." Hämtad 8 juli 2007. Arkiverad från originalet 7 maj 2017. (obestämd)
↑ "... I enlighet med de flamländska reglerna läses namnet som "Randal" - "Computera", december 1999, nr 49
↑ Biryukov och Khovratovich, 2009 , sid. ett.
↑ Biryukov och Khovratovich, 2009 , sid. 2.
↑ Biryukov och Khovratovich, 2009 , sid. 9.
↑ Biryukov och Khovratovich, 2009 , sid. tio.
↑ 1 2 Biryukov och Khovratovich, 2009 , sid. 12.
↑ 1 2 3 4 5 John Kelsey, 1996 .
↑ Biham, 1994 , sid. 2.
↑ Panasenko S., 2009 , sid. 59.

Litteratur

Shnaer B. Tillämpad kryptografi. Protokoll, algoritmer, källtexter i C-språk. - Triumph, 2002. - 816 sid. - ISBN 5-89392-055-4 , 0-471-11709-9.
Eli Biham . Nya typer av kryptoanalytiska attacker med relaterade nycklar // Springer-Verlag: Journal. - 1994. - Nej . 4 . - S. 229-246 . — ISSN 1432-1378 . - doi : 10.1007/BF00203965 .
Alex Biryukov , Dmitry Khovratovich. Related-Key Cryptanalysis of the Full AES-192 and AES-256 // Springer Berlin Heidelberg: Journal. - 2009. - S. 1-18 . — ISSN 978-3-642-10366-7 . - doi : 10.1007/978-3-642-10366-7_1 .
Alex Biryukov, David Wagner. Bildattacker // Snabb mjukvarukryptering. 6th International Workshop, FSE'99 Rom, Italien, 24–26 mars, 1999 Proceedings. - Springer Berlin Heidelberg, 1999. - ISBN 978-3-540-66226-6 . (inte tillgänglig länk)
Panasenko S. Kryptanalytiska attacker på länkade nycklar // CIO-World : journal. – 2007.
Panasenko S. Krypteringsalgoritmer. Särskild handbok . - BHV-Petersburg. - 2009. - S. 53-59.
Alexander Tyrenko. DES-algoritmen knäcktes på tre dagar // Computerworld Russia: magazine. - 1998. - Nr 28-29 .
John Kelsey, Bruce Schneier, David Wagner. Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES // Advances in Cryptology - CRYPTO '96, 16th Annual International Cryptology Conference, Santa Barbara, Kalifornien, USA, 18-22 augusti 1996, Proceedings : tidning. — 1996.
Mihir Bellare och Tadayoshi Kohno. En teoretisk behandling av relaterade nyckelattacker: RKA-PRP, RKA-PRF och applikationer . — EUROCRYPT. - 2003. - S. 491-506.