Skjuvning 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 6 maj 2018; kontroller kräver 9 redigeringar .

Shift attack ( eng.  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 [1] .

Skapande historia

Idén att skapa en skjuvattack kom först upp med Edna Grossman och Brian Tuckerman 1977. Motsvarande rapport publicerades [2] tillsammans med IBM . Grossman och Tuckerman kunde visa möjligheten för en attack på ett ganska svagt New Data Seal (NDS) -chiffer . Attacken utnyttjar det faktum att chiffern i varje omgång bara blandar samma nyckel och använder samma tabell i varje omgång. Användningen av klartexter kringgår detta och låter oss betrakta det som den tidigaste versionen av skiftattacken.

1990 föreslogs differentiell kryptoanalys , som visar sårbarheten hos flerrunda DES-liknande kryptosystem [3] . Ett sätt att säkerställa deras kryptografiska styrka var att öka antalet använda rundor, vilket ökade beräkningskomplexiteten för attacken i proportion till deras antal. Användningen av denna förbättring för många krypteringsalgoritmer baserades i synnerhet på den empiriska bedömningen att alla, även ganska svaga chiffer, kan göras kryptografiskt starka genom att upprepa krypteringsoperationerna många gånger:

Med undantag för endast ett fåtal degenererade fall kan algoritmen göras godtyckligt säker genom att öka antalet omgångar.

Originaltext  (engelska)[ visaDölj] Förutom i några få degenererade fall kan en algoritm göras godtyckligt säker genom att lägga till fler rundor. — B. Preneel, V. Rijmen, A. Bosselears: Principer och prestanda för kryptografiska algoritmer [4]

Till exempel hade några chiffer som föreslogs som kandidater till AES-tävlingen 1997 ett ganska stort antal omgångar: RC6(20), MARS(32), SERPENT(32), CAST(48) [1] .

Men 1999 publicerades en artikel av Alex Biryukov och David Wagner som beskrev en skjuvattack, vilket motbevisade detta antagande. Ett särdrag för denna attack var att den inte berodde på antalet chifferrundor; dess framgång krävde bara identiteten för rundorna och möjligheten till kryptoanalys av krypteringsfunktionen i en separat omgång. Artikeln beskrev också tillämpningen av denna attack på TREYFER- chifferet och förenklade versioner av DES -chiffrorna (2K-DES) och BLOWFISH [1] .

År 2000 publicerades en andra artikel, som visade förbättrade versioner av skiftattacken - "Sliding with a twist" och "Complementation slide", vilket gjorde det möjligt att utöka den till chiffer vars rundor har små skillnader. Så, med hjälp av dessa förbättringar, knäcktes vissa modifieringar av DES -chifferet , såväl som en förenklad 20-runda version av krypteringsstandarden GOST 28147-89 [5] [6] .

Allmän beskrivning

I det enklaste fallet [7] tillämpas en skiftattack på krypteringsalgoritmer, som är flera upprepningar av någon krypteringsfunktion , vars indata vid varje omgång är chiffertexten (resultatet av kryptering i föregående omgång) och någon rundnyckel , vilket är samma för alla omgångar. Huvudkraven för ett framgångsrikt genomförande av denna attack är [7] :

  1. Omgångarnas identitet (vilket garanteras genom att använda samma funktion och samma nyckel på varje omgång)
  2. Möjligheten att enkelt hitta nyckeln , känna till texten vid ingången och texten vid utgången av någon runda

Algoritmen för den enklaste attacken

Steg 1. Låt oss ta lite klartext vid ingången och motsvarande chiffertext vid utgången av krypteringsalgoritmen. Steg 2. Ta någon annan klartext och dess motsvarande chiffertext så att paret skiljer sig från det redan valda paret . Steg 3. Antag att det är relaterat till relationen = , och är relaterat till relationen , d.v.s. och är resultatet av engångskryptering och resp. Låt oss kalla ett sådant par för ett "glidande par" (glidpar) [1] . Genom att använda påståendet att krypteringsnyckeln lätt kan beräknas, genom att känna till texten vid ingången och texten vid utmatningen av någon omgång, beräknar vi nyckeln vid den första omgången av kryptering av relationen och nyckeln vid den sista omgången av kryptering av relationen . Steg 4. Låt oss kontrollera jämställdheten . Därför att genom villkor är alla runda nycklar desamma, då måste denna likhet vara uppfylld, annars är antagandet som gjordes i steg 3 felaktigt, och det är nödvändigt att återgå till steg 2, exklusive det testade paret från listan över möjliga kandidater. Uppfyllelsen av jämlikhet indikerar att nyckeln potentiellt är den önskade runda nyckeln. Steg 5. För att kontrollera den hittade nyckeln för falska positiva, bör du ersätta den i krypteringsalgoritmen och kontrollera korrekt operation på flera olika kända par av "klartext - chiffertext ". Trots att det är möjligt för fel nyckel att klara detta test, vid bra chiffer, är sannolikheten för detta extremt liten [7] , vilket innebär att den verifierade nyckeln med stor sannolikhet är den önskade runda nyckeln. Således, vid framgångsrik verifiering, förklarar vi nyckeln som ska sökas, annars återgår vi till steg 2, och exkluderar det verifierade paret och nyckeln från listan över möjliga kandidater.

Anmärkningar om algoritmen

Shift attack modifieringar

När det gäller moderna blockchiffer är de runda nycklarna vanligtvis inte desamma. Detta leder till det faktum att algoritmen som används vid konstruktionen av den enklaste attacken i allmänhet inte är tillämplig för sådana chiffer och kräver vissa tillägg.

Förklaring av problemet

Låt det finnas en krypteringsalgoritm nr 1, bestående av block, så att nyckeln används i den:e omgången (vi antar att det totala antalet nycklar , nyckeln kommer att behövas senare), och låt oss välja något par av "klartext - chiffertext" . Vid utgången av den första omgången får vi texten , där är krypteringsfunktionen.

Skiftattacken innebär vidare att texten krypteras med ett nytt blockchiffer nr 2, bestående av block från till . Låt oss beteckna chiffertexten vid utgången av det -th blocket som . Det är lätt att se att i det här fallet, vid utgången av det i-te blocket, kommer vi att få den text som redan finns ovan , vilket betyder att texten och chiffertexten är relaterade av relationen .

Således har vi fått ett par som uppfyller relationerna och , vilket inte är något annat än ett allmänt skiftpar. Följaktligen, i det enklaste fallet, kommer dessa relationer att ta formen och .

Om vi ​​antar att viss text är relaterad till förhållandet , bör vi få chiffertexten vid utgången av krypteringsalgoritm #2 med texten vid ingången, för att bekräfta eller motbevisa den med förhållandena . I fallet med ett trivialt nyckelschema är krypteringsalgoritmerna nr 1 och nr 2 identiska, vilket innebär att det kan erhållas genom att kryptera texten med ett redan existerande blockchiffer. Annars är krypteringsalgoritmerna nr 1 och nr 2 olika, och kryptanalytikern kan inte konstruera algoritm nr 2, vilket gör att chiffertexten inte kan erhållas.

Fallet med ett Feistel-nätverk med självlikhet i två rundor

Kompletteringsbild [ 5 ]  _

Som nämnts i anteckningarna till attackalgoritmen kan fallet med kryptoanalys av chiffer med p-runda självlikhet lätt reduceras till det enklaste fallet av en shift-attack genom att kombinera flera omgångar till en, vilket motsvarar att flytta chifferblock med rundor. I fallet med ett Feistel-nätverk med växelvis omväxlande runda nycklar och , dvs. med självlikhet i två omgångar kan detta tillvägagångssätt öka komplexiteten i kryptoanalys och därmed göra skiftattacken ineffektiv. Istället föreslogs, som tidigare, att skifta med endast en varv istället för två, men samtidigt något ändra de krav som ställs på skiftparet.

I beskrivningen av problemet ovan angavs att för att söka efter ett skiftpar, i det allmänna fallet, är det nödvändigt att kunna arbeta med två blockchiffer - det ursprungliga, bestående av block från till , och den nya, bestående av block från till . Kompletteringsbilden låter dig arbeta endast med det ursprungliga blockchifferet.

Även om följande resonemang kommer att demonstreras med ett 4-runds chiffer, kan det utökas till valfritt antal omgångar. Låt oss först titta på hur klartexten förändras i olika omgångar av kryptering. Låt oss representera klartexten som , var och är vänster respektive höger del av texten.

Runt nummer Vänster sida Höger del
ett
2
3
fyra

Låt oss beteckna texten vid utgången av omgång 1 , och chiffertexten . Notera nu att för att hitta chiffertexten vid utgången av ett blockchiffer med fyra rundor med ett nyckelschema räcker det att lägga till skillnaden på höger sida av varje omgång av det ursprungliga chiffret och sedan kryptera texten med resulterande chiffer (fig. 2, höger diagram). För att göra detta kommer vi att leverera texten till ingången av det initiala chifferet . Låt oss beteckna chiffertexten som . Låt oss överväga hur texten förändras i olika omgångar av kryptering.

Runt nummer Vänster sida Höger del
ett
2
3

fyra

Av detta kan man se att den införda skillnaden bevaras vid varje omgång, vilket innebär att chiffertexterna och är relaterade av relationerna: och , och paren "klartext - chiffertext" och av relationerna och .

Om texterna är relaterade med ett förhållande , säger de att texterna och har en skjuvskillnad ( engelska slide difference ) .  

Således erhålls följande ekvationer för skjuvningsparet:


Som tidigare, i fallet med -bit-texter, krävs klartext för att hitta skiftparet . Skjuvparet måste nu uppfylla ekvationen (se fig. 2). När det gäller att hitta ett potentiellt skiftpar tillåter den andra ekvationen att hitta en kandidat , och om funktionen är tillräckligt sårbar för kryptoanalys tillåter dessa ekvationer oss att hitta de potentiella önskade nycklarna och . Efter det återstår det bara att kontrollera falska positiva resultat.

Att glida med en twist  [ 5 ]

Kravet som anges i problemformuleringen för att kunna arbeta med det ursprungliga chiffer #1, bestående av block från till , och det nya chiffer #2, bestående av block från från till , kan enkelt transformeras med den så kallade shift- och rotera tillvägagångssätt.

Om vi ​​utesluter den sista permutationen av textens vänstra och högra del och omvänder nycklarnas ordning, kommer dekryptering i Feistel-nätverket att ske på exakt samma sätt som kryptering [1] . Skift-och-rotera-metoden använder denna egenskap, nämligen att den föreslår att dekrypteringsalgoritmen ska användas som chiffer #2 (se fig. 3).

Detta tillvägagångssätt har inga grundläggande skillnader från den enklaste algoritmen. Som i det enklaste fallet gäller kraven för skiftparet , där . Vi får alltså ekvationerna:


och ett tillstånd som gör det lättare att hitta skiftpar:

Som vanligt, när det gäller -bit-texter, behövs klartexter för att hitta skiftparet . Om den hittas låter funktionens sårbarhet dig hitta nyckeln från ekvationerna .

Antalet obligatoriska texter i detta steg kan reduceras till . För att göra detta, krypterar vi olika texter i formuläret och dekrypterar olika texter i formuläret , där och är fixerade och uppfyller villkoret . Således, eftersom vi nu faktiskt arbetar med - bittexter, enligt födelsedagsparadoxen, bland dessa "klartext-chiffertext"-par, finns det stor sannolikhet för ett skiftpar.

Nyckeln kan hittas genom att tillämpa metoden som beskrivs för det allmänna fallet med blockchiffer med p-runda självlikhet, nämligen genom att kombinera varje efterföljande två omgångar till en - så reducerar vi problemet till det enklaste fallet. Även om storleken på den runda nyckeln kommer att fördubblas, kommer detta inte att komplicera kryptoanalysen, eftersom nyckeln , som är hälften av den nya runda nyckeln, redan är känd, och vi behöver bara hitta den andra halvan, lika stor som rundan. knappa in det ursprungliga problemet.

Andra ändringar

En separat modifiering kan betraktas som den samtidiga användningen av de två tillvägagångssätten som beskrivs ovan - Komplementeringsglid och Sliding with a twist, vilket gör det möjligt att utöka skiftattacken till chiffer med självlikhet i 4 rundor [5] .

Problemet med kryptoanalys av chiffer med ojämna omgångar skiljer sig från alla fall som hittills behandlats, i vars lösning ingen av de övervägda attackmodifikationerna kan användas. För fallet med sådana chiffer föreslogs en omplacering av glidattacken [ 8 ]  , demonstrerad på exemplet med modifieringar av DES -chifferet , i synnerhet på exemplet med den fullständiga versionen av DES med 16 omgångar

Sliding-linear attack ( engelska  slide-linear attack ) [9] är ett exempel på implementeringen av en skiftattack med hjälp av principerna för linjär kryptoanalys . Arbetet med denna attack visades på chifferen 4K-DES.

Det finns också förbättringar för att påskynda implementeringen av redan befintliga modifieringar av skjuvningsattacken. I synnerhet en av dessa förbättringar, som beskrivs i arbetet av Eli Biham, Orr Dunkelman, Nathan Keller: Improved Slide Attacks [10] , gör det möjligt att hitta skiftpar mycket snabbare med hjälp av en cyklisk chifferstruktur och motsvarande nyckelpermutationer. Funktionen av denna modifiering visades på exemplet på olika varianter av GOST 28147-89 (GOST) chiffer.

Krypteringsalgoritmer som är sårbara för skiftattack och dess modifieringar

Beskrivs i originalartiklarna: [1] [5]

  • 2K-DES (DES med alternerande tangenter)
  • DES med Brown Seberry Key Schema
  • DESX
  • GOST
  • DIMMIG
  • TREYFER
  • WAKE-ROFB
  • Blowfish varianter

Beskrivs i andra källor

Skiftattacker av klassen hashfunktioner [13]

Förutom deras ursprungliga syfte - att attackera blockchiffer, har principerna för skiftattacken också funnit tillämpning inom området för hashfunktionskryptanalys. I likhet med fallet med blockchiffer, där en skiftattack har använts för att hitta nyckelschemat, har det visat sig vara potentiellt tillämpbart för att hitta den hemliga nyckeln som används för att generera och validera hashen för det överförda meddelandet. I synnerhet demonstrerades detta tillvägagångssätt på exemplet med generering av simulerad insättning (MAC) .

Skiftattacken visade sig också vara användbar inte bara i fallet med kryptografiska hashfunktioner som tar värdet av någon hemlig nyckel som en parameter, utan även i fallet med hashfunktioner som producerar en hash endast baserat på ett meddelande. En analys av sådana funktioner baserad på en skiftattack gör det möjligt att med en hög grad av sannolikhet identifiera vissa skiftegenskaper och, som ett resultat, vissa mönster i driften av hashalgoritmer.

Hash-funktioner som är sårbara för skiftattack: [13]

Sätt att öka kryptografiskt motstånd mot ändringar av skiftattacker [7] [16]

Eftersom sårbarheterna i nyckelschemat används under skiftattacken är en av åtgärderna att komplicera det. I synnerhet är det nödvändigt att undvika cykliska upprepningar i nyckelschemat om möjligt, eller åtminstone använda en tillräckligt lång upprepningsperiod. I fallet med ett litet antal nycklar, istället för en enkel periodisk upprepning, bör någon slumpmässig ordningsföljd av deras sekvens användas.

Förutom svagheten i nyckelschemat utnyttjar skiftattacken också samma omgångar. Ett sätt att undvika detta är att använda några olika runda konstanter som en parameter för krypteringsfunktionen på separata omgångar - detta gör att du kan göra skillnader i driften av enskilda krypteringsblock utan att avsevärt komplicera krypteringsalgoritmen som helhet.

Effektiviteten av en skiftattack kan också reduceras avsevärt genom att öka den kryptografiska styrkan hos den runda krypteringsfunktionen. Så dess motstånd mot attacker baserade på klartext kommer att göra det mycket svårare att hitta den runda nyckeln även i närvaro av ett skiftpar.

Anteckningar

  1. ↑ 1 2 3 4 5 6 7 Alex Biryukov, David Wagner. Bildattacker  //  Snabb mjukvarukryptering. 6th International Workshop, FSE'99 Rom, Italien, 24–26 mars, 1999 Proceedings. - Springer Berlin Heidelberg, 1999. - P. 245-259 . - ISBN 978-3-540-66226-6 .  (inte tillgänglig länk)
  2. ↑ EK Grossman, Thomas J. Watson IBM Research Center Research Division, B. Tuckerman. Analys av ett Feistel-liknande chiffer som försvagats av att det inte finns någon roterande nyckel . - IBM Thomas J. Watson Research Division, 1977. - 33 sid.
  3. ↑ Eli Biham, Adi Shamir. Differentiell krypteringsanalys av DES-liknande kryptosystem  //  Framsteg i kryptologi-CRYPT0' 90 Proceedings. - Springer Berlin Heidelberg, 1990. - S. 2-21 . — ISBN 978-3-540-54508-8 .  (inte tillgänglig länk)
  4. ↑ B. Preneel, V. Rijmen, A. Bosselears. Principer och prestanda för kryptografiska algoritmer  //  Dr. Dobbs tidning. - Miller Freeman, 1998. - Vol. 23 , nr. 12 . - S. 126-131 .
  5. ↑ 1 2 3 4 5 6 Alex Biryukov, David Wagner. Advanced Slide Attacks  (engelska)  // Advances in Cryptology - EUROCRYPT 2000. Internationell konferens om teorin och tillämpningen av kryptografiska tekniker Brygge, Belgien, 14–18 maj 2000 Proceedings. - Springer Berlin Heidelberg, 2000. - P. 589-606 . — ISBN 978-3-540-67517-4 .  (inte tillgänglig länk)
  6. ↑ 1 2 Panasenko S.P. Shift attack // Krypteringsalgoritmer. Särskild uppslagsbok - St Petersburg. : BHV-SPb , 2009. - S. 40-42. — 576 sid. — ISBN 978-5-9775-0319-8
  7. ↑ 1 2 3 4 5 Chalermpong Worawannotai, Isabelle Stanton. En handledning om bildattacker  . Arkiverad från originalet den 29 november 2014.
  8. ↑ Raphael C.-W. Phan. Advanced Slide Attacks Revisited: Realigning Slide on DES  //  Progress in Cryptology – Mycrypt 2005. Första internationella konferensen om kryptologi i Malaysia, Kuala Lumpur, Malaysia, 28-30 september 2005. Proceedings. - Springer Berlin Heidelberg, 2005. - P. 263-276 . — ISBN 978-3-540-28938-8 . Arkiverad från originalet den 12 juni 2018.
  9. ↑ 1 2 Soichi Furuya. Slide Attacks with a Known-Plaintext Cryptanalysis  (engelska)  // Information Security and Cryptology - ICISC 2001. 4:e internationella konferensen Seoul, Korea, 6–7 december 2001 Proceedings. - Springer Berlin Heidelberg, 2002. - S. 214-225 . - ISBN 978-3-540-43319-4 . Arkiverad från originalet den 9 juni 2018.
  10. ↑ Eli Biham, Orr Dunkelman, Nathan Keller. Förbättrade glidattacker  //  Snabb mjukvarukryptering. 14th International Workshop, FSE 2007, Luxemburg, Luxemburg, 26-28 mars 2007, Revised Selected Papers. - Springer Berlin Heidelberg, 2007. - P. 153-166 . — ISBN 978-3-540-74617-1 .  (inte tillgänglig länk)
  11. ↑ Selçuk Kavut, Melek D. Yücel. Slide Attack on Spectr-H64  //  Progress in Cryptology - INDOCRYPT 2002. Tredje internationella konferensen om kryptologi i Indien Hyderabad, Indien, 16–18 december 2002 Proceedings. - Springer Berlin Heidelberg, 2002. - S. 34-47 . - ISBN 978-3-540-00263-5 . Arkiverad från originalet den 11 juni 2018.
  12. ↑ Nicolas T. Courtois, Gregory V. Bard, David Wagner. Algebraiska och glidattacker på KeeLoq  //  Snabb mjukvarukryptering. 15th International Workshop, FSE 2008, Lausanne, Schweiz, 10-13 februari 2008, Revised Selected Papers. - Springer Berlin Heidelberg, 2008. - S. 97-115 . — ISBN 978-3-540-71038-7 . Arkiverad från originalet den 30 oktober 2018.
  13. ↑ 1 2 Michael Gorski, Stefan Lucks, Thomas Peyrin. Slide Attacks on a Class of Hash Functions  //  Framsteg inom kryptologi - ASIACRYPT 2008. 14:e internationella konferensen om teorin och tillämpningen av kryptologi och informationssäkerhet, Melbourne, Australien, 7-11 december 2008. Proceedings. - Springer Berlin Heidelberg, 2008. - S. 143-160 . - ISBN 978-3-540-89254-0 .  (inte tillgänglig länk)
  14. ↑ Yu Sasaki, Lei Wang, Kazuo Ohta, Noboru Kunihiro. Password Recovery on Challenge and Response: Impossible Differential Attack on Hash Function  //  Progress in Cryptology – AFRICACRYPT 2008. Första internationella konferensen om kryptologi i Afrika, Casablanca, Marocko, 11-14 juni 2008. Proceedings. - Springer Berlin Heidelberg, 2008. - S. 290-307 . — ISBN 978-3-540-68159-5 . Arkiverad från originalet den 6 juni 2018.
  15. ↑ 1 2 Markku-Juhani O. Saarinen. Krypteringsanalys av blockchiffer baserad på SHA-1 och MD5  //  Snabb mjukvarukryptering. 10th International Workshop, FSE 2003, Lund, Sverige, 24-26 februari 2003. Reviderade papper. - Springer Berlin Heidelberg, 2003. - S. 36-44 . - ISBN 978-3-540-20449-7 .  (inte tillgänglig länk)
  16. ↑ Francois-Xavier Standaert, Gilles Piret, Jean-Jacques Quisquater. Krypteringsanalys av blockchiffer: A Survey  //  UCL Crypto Group Technical Report Series. - 2003. Arkiverad den 10 februari 2014.