Smykový útok

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é 6. května 2018; kontroly vyžadují 9 úprav .

Shift attack ( angl.  slide attack ) - kryptografický útok , což je v obecném případě útok založený na vybraném otevřeném textu , který umožňuje dešifrování blokových vícekolových šifer bez ohledu na počet použitých kol. Navrhli Alex Biryukov a David Wagner v roce 1999 [1] .

Historie vytvoření

Myšlenka vytvořit smykový útok poprvé přišla s Ednou Grossmanovou a Brianem Tuckermanem v roce 1977. Odpovídající zpráva byla zveřejněna [2] společně s IBM . Grossman a Tuckerman dokázali prokázat možnost útoku na docela slabou šifru New Data Seal (NDS) . Útok využívá skutečnosti, že šifra v každém kole zamíchá pouze stejný klíč, přičemž v každém kole používá stejnou tabulku. Použití otevřených textů to obchází a umožňuje nám to považovat za nejranější verzi útoku typu shift.

V roce 1990 byla navržena diferenciální kryptoanalýza , která demonstrovala zranitelnost vícekolových kryptosystémů podobných DES [3] . Jedním ze způsobů, jak zajistit jejich kryptografickou sílu, bylo zvýšit počet použitých nábojů, což úměrně jejich počtu zvyšovalo výpočetní náročnost útoku. Použití tohoto vylepšení pro mnoho šifrovacích algoritmů bylo založeno zejména na empirickém úsudku, že jakékoli, i spíše slabé šifry, mohou být kryptograficky silné opakováním šifrovacích operací mnohokrát:

S výjimkou pouze několika degenerovaných případů může být algoritmus libovolně bezpečný zvýšením počtu kol.

Původní text  (anglicky)[ zobrazitskrýt] Kromě několika zvrhlých případů lze algoritmus libovolně zabezpečit přidáním dalších kol. — B. Preneel, V. Rijmen, A. Bosselears: Principles and Performance of Cryptographic Algorithms [4]

Například některé šifry navržené jako kandidáti do soutěže AES v roce 1997 měly poměrně velký počet kol: RC6(20), MARS(32), SERPENT(32), CAST(48) [1] .

V roce 1999 však vyšel článek Alexe Biryukova a Davida Wagnera popisující smykový útok, který tuto domněnku vyvrátil. Charakteristickým rysem tohoto útoku bylo, že nezávisel na počtu kol šifry; jeho úspěch vyžadoval pouze identitu kol a možnost kryptoanalýzy šifrovací funkce v samostatném kole. Článek také popisoval aplikaci tohoto útoku na šifru TREYFER a zjednodušené verze šifer DES (2K-DES) a BLOWFISH [1] .

V roce 2000 vyšel druhý článek, který demonstroval vylepšené verze posunového útoku – „Sliding with a twist“ a „Complementation slide“, umožňující jeho rozšíření na šifry, jejichž kola mají malé rozdíly. Takže s pomocí těchto vylepšení byly prolomeny některé úpravy šifry DES a také zjednodušená 20kolová verze šifrovacího standardu GOST 28147-89 [5] [6] .

Obecný popis

V nejjednodušším případě [7] je útok shift aplikován na šifrovací algoritmy, což jsou mnohonásobné opakování nějaké šifrovací funkce , jejímž vstupem v každém kole je šifrovaný text (výsledek šifrování v předchozím kole) a nějaký klíč kola. , která je stejná pro všechna kola. Hlavní požadavky pro úspěšnou implementaci tohoto útoku jsou [7] :

  1. Identita kol (která je zaručena použitím stejné funkce a stejného klíče v každém kole)
  2. Schopnost snadno najít klíč , znát text na vstupu a text na výstupu v nějakém kole

Algoritmus nejjednoduššího útoku

Krok 1. Vezměme nějaký prostý text na vstupu a odpovídající šifrovaný text na výstupu šifrovacího algoritmu. Krok 2. Vezměte nějaký jiný otevřený text a jeho odpovídající šifrovaný text tak, aby se dvojice lišila od již zvolené dvojice . Krok 3. Předpokládejme, že souvisí se vztahem = , a souvisí se vztahem , tzn. a jsou výsledkem jednokolového šifrování resp . Nazvěme takovou dvojici „sliding pair“ (slide pair) [1] . S použitím tvrzení, že šifrovací klíč lze snadno vypočítat, když známe text na vstupu a text na výstupu některého kola, vypočítáme klíč v prvním kole šifrování pomocí vztahu a klíč v posledním kole šifrování vztahem . Krok 4. Zkontrolujeme rovnost . Protože podle podmínky jsou všechny kruhové klíče stejné, pak musí být tato rovnost splněna, jinak je předpoklad učiněný v kroku 3 nesprávný a je nutné se vrátit ke kroku 2 s vyloučením testovaného páru ze seznamu možných kandidátů. Splnění rovnosti naznačuje, že klíč je potenciálně požadovaný kulatý klíč. Krok 5. Chcete-li zkontrolovat, zda nalezený klíč neobsahuje falešné poplachy, měli byste jej nahradit šifrovacím algoritmem a zkontrolovat správnou funkci na několika různých známých párech „prostý text – šifrovaný text “. Navzdory tomu, že je možné, že tímto testem projde nesprávný klíč, v případě dobrých šifer je pravděpodobnost extrémně malá [7] , což znamená, že ověřený klíč je s vysokou pravděpodobností požadovaný kulatý klíč. V případě úspěšného ověření tedy deklarujeme klíč k hledání, v opačném případě se vrátíme ke kroku 2 s vyloučením ověřeného páru a klíče ze seznamu možných kandidátů.

Poznámky k algoritmu

Úpravy Shift útoku

V případě moderních blokových šifer nejsou kulaté klíče obvykle stejné. To vede k tomu, že algoritmus použitý při konstrukci nejjednoduššího útoku je pro takové šifry obecně nepoužitelný a vyžaduje určité doplnění.

Prohlášení o problému

Nechť existuje šifrovací algoritmus č. 1, sestávající z bloků, tak, že klíč se použije v třetím kole (budeme předpokládat, že celkový počet klíčů , klíč bude potřeba později), a vybereme pár "prostý text - šifrovaný text" . Na výstupu prvního kola dostaneme text , kde je funkce šifrování.

Útok typu shift dále zahrnuje zašifrování textu pomocí nové blokové šifry č. 2, která se skládá z bloků od do . Označme šifrovaný text na výstupu -tého bloku jako . Je snadné vidět, že v tomto případě na výstupu i-tého bloku dostaneme text již nalezený výše , což znamená, že text a šifrový text spolu souvisí vztahem .

Tak jsme získali pár , který splňuje vztahy a , což není nic jiného než obecný posuvný pár. Podle toho v nejjednodušším případě budou mít tyto vztahy tvar a .

Za předpokladu, že nějaký text souvisí s poměrem , měli bychom získat šifrovaný text na výstupu šifrovacího algoritmu #2 s textem na vstupu, abychom jej poměry potvrdili nebo vyvrátili . V případě triviálního schématu klíče jsou šifrovací algoritmy č. 1 a č. 2 totožné, což znamená , že jej lze získat zašifrováním textu již existující blokovou šifrou. Jinak jsou šifrovací algoritmy č. 1 a č. 2 odlišné a kryptoanalytik není schopen sestavit algoritmus č. 2, což znamená, že šifrovaný text nelze získat.

Případ Feistelovy sítě s dvoukolovou sebepodobností

Doplňkový snímek  [ 5 ]

Jak je zmíněno v poznámkách k algoritmu útoku, případ kryptoanalýzy šifer s vlastní podobností p-kolů lze snadno zredukovat na nejjednodušší případ posunového útoku zkombinováním několika kol do jednoho, což je ekvivalentní posunu šifrovacích bloků o kola. V případě sítě Feistel se střídavě střídajícími se kulatými klíči a , tzn. s dvoukolovou sebepodobností může tento přístup zvýšit složitost kryptoanalýzy, a proto učinit útok posunem neúčinným. Místo toho bylo navrženo, stejně jako dříve, řadit pouze o jedno kolo místo dvou, ale zároveň mírně změnit požadavky kladené na směnovou dvojici.

V popisu výše uvažovaného problému bylo naznačeno, že pro hledání páru posunu je v obecném případě nutné umět pracovat s dvoublokovými šiframi - původní, skládající se z bloků od do , a nový, skládající se z bloků od do . Doplňovací snímek umožňuje pracovat pouze s původní blokovou šifrou.

Ačkoli bude následující úvaha demonstrována pomocí 4kolové šifry, lze ji rozšířit na libovolný počet kol. Nejprve se podívejme, jak se prostý text mění v různých kolech šifrování. Představme holý text jako , kde a jsou levá a pravá část textu.

Kulaté číslo Levá strana Pravá část
jeden
2
3
čtyři

Označme text na výstupu z 1. kola a šifrový text . Nyní si všimněte, že k nalezení šifrového textu na výstupu 4kolové blokové šifry s plánem klíče stačí přidat rozdíl na pravou stranu každého kola původní šifry a poté text zašifrovat pomocí výsledná šifra (obr. 2, schéma vpravo). K tomu dodáme text na vstup počáteční šifry . Označme šifrový text jako . Podívejme se, jak se text mění v různých kolech šifrování.

Kulaté číslo Levá strana Pravá část
jeden
2
3

čtyři

Z toho je vidět, že zavedený rozdíl je zachován v každém kole, což znamená, že šifrové texty a spolu souvisí vztahy: a , a dvojicemi "holý text - šifrový text" a vztahy a .

Pokud jsou texty propojeny poměrem , říkají, že texty a mají smykový rozdíl ( anglicky slide rozdíl ) .  

Pro smykovou dvojici tak získáme následující rovnice:


Stejně jako dříve jsou v případě -bitových textů vyžadovány prosté texty k nalezení páru posunu . Smyková dvojice nyní musí splňovat rovnici (viz obr. 2). V případě nalezení páru potenciálního posunu umožňuje druhá rovnice najít kandidáta , a pokud je funkce dostatečně zranitelná vůči kryptoanalýze, pak nám tyto rovnice umožňují najít potenciální požadované klíče a . Poté zbývá pouze zkontrolovat falešné poplachy.

Posuvné s kroucením  [ 5 ]

Požadavek uvedený v zadání problému na možnost pracovat s původní šifrou #1, skládající se z bloků od do , a novou šifrou #2 skládající se z bloků od do , lze snadno transformovat pomocí tzv. shift- a-rotační přístup.

Pokud vyloučíme poslední permutaci levé a pravé části textu a obrátíme pořadí klíčů, pak k dešifrování v síti Feistel dojde úplně stejně jako k šifrování [1] . Přístup shift-and-rotate využívá této vlastnosti, konkrétně navrhuje použít dešifrovací algoritmus jako šifru #2 (viz obr. 3).

Tento přístup nemá žádné zásadní rozdíly od nejjednoduššího algoritmu. Stejně jako v nejjednodušším případě jsou požadavky na směnný pár , kde . Dostáváme tedy rovnice:


a podmínka, která usnadňuje nalezení párů směn:

Jako obvykle v případě -bitových textů je k nalezení páru posunu potřeba prostý text . Pokud je nalezen, zranitelnost funkce vám umožní najít klíč z rovnic .

Počet požadovaných textů v tomto kroku lze snížit na . Za tímto účelem šifrujeme různé texty formuláře a dešifrujeme různé texty formuláře , kde a jsou pevně dané a splňují podmínku . Jelikož tedy nyní ve skutečnosti pracujeme s - bitovými texty, podle narozeninového paradoxu mezi těmito dvojicemi „šifrovaný text-prostý text“ existuje vysoká pravděpodobnost páru posunu.

Klíč lze nalézt aplikací metody popsané pro obecný případ blokových šifer se sebepodobností p-kol, totiž spojením každých následujících dvou kol do jednoho – tím problém zredukujeme na nejjednodušší případ. I když se velikost kulatého klíče zdvojnásobí, nebude to komplikovat kryptoanalýzu, protože klíč , který je polovinou nového kulatého klíče, je již znám a my potřebujeme najít pouze druhou polovinu, která se rovná velikosti kola. klíč k původnímu problému.

Další úpravy

Za samostatnou modifikaci lze považovat současné použití dvou výše popsaných přístupů - Complementation slide a Sliding with twist, které umožňují rozšířit útok shift na šifry se 4kolovou sebepodobností [5] .

Problém kryptoanalýzy šifer s nestejnými koly se liší od všech dosud uvažovaných případů, při jejichž řešení nelze použít žádnou z uvažovaných modifikací útoku. Pro případ takových šifer byl navržen realigning slide attack [ 8 ]  , demonstrovaný na příkladu modifikací DES šifry , konkrétně na příkladu plné 16kolové verze DES

Sliding-linear attack ( anglicky  slide-linear attack ) [9] je příkladem implementace posunového útoku pomocí principů lineární kryptoanalýzy . Práce tohoto útoku byla ukázána na šifře 4K-DES.

Nechybí ani vylepšení pro urychlení implementace již existujících úprav smykového útoku. Konkrétně jedno z těchto vylepšení, popsané v práci Eli Biham, Orr Dunkelman, Nathan Keller: Improved Slide Attacks [10] , umožňuje mnohem rychleji najít páry posunů pomocí struktury cyklické šifry a odpovídajících permutací klíče. Fungování této modifikace bylo ukázáno na příkladu různých variant šifry GOST 28147-89 (GOST).

Šifrovací algoritmy zranitelné vůči útoku shift a jeho modifikacím

Popsáno v původních článcích: [1] [5]

  • 2K-DES (DES se střídavými klávesami)
  • DES s plánem klíčů Brown Seberry
  • DESX
  • GOST
  • MISTY
  • TREYFER
  • WAKE-ROFB
  • Blowfish varianty

Popsáno v jiných zdrojích

Shift útoky třídy hašovacích funkcí [13]

Kromě svého původního účelu – útoku na blokové šifry, našly principy shift attack uplatnění také v oblasti kryptoanalýzy hashovací funkce. Podobně jako v případě blokových šifer, kde byl k nalezení plánu klíče použit útok shift, se ukázalo, že je potenciálně použitelný pro nalezení tajného klíče použitého ke generování a ověřování hash přenášené zprávy. Konkrétně byl tento přístup demonstrován na příkladu generování simulovaného vkládání (MAC) .

Útok shift se také ukázal být užitečný nejen v případě kryptografických hašovacích funkcí, které berou jako parametr hodnotu nějakého tajného klíče, ale také v případě hašovacích funkcí, které produkují hash pouze na základě zprávy. Analýza takových funkcí založená na útoku posunu umožňuje s vysokou mírou pravděpodobnosti identifikovat některé vlastnosti posunu a v důsledku toho určité vzorce ve fungování hashovacích algoritmů.

Hashovací funkce zranitelné vůči útoku shift: [13]

Způsoby, jak zvýšit kryptografickou odolnost vůči modifikacím útoků typu shift [7] [16]

Vzhledem k tomu, že při útoku na směnu se využívají zranitelnosti klíčového plánu, jedním z opatření je jeho zkomplikování. Zejména je nutné se pokud možno vyvarovat cyklického opakování v klíčovém rozvrhu, nebo alespoň využít dostatečně velkou periodu opakování. V případě malého počtu kláves by se místo prostého periodického opakování mělo použít nějaké náhodné pořadí jejich sekvence.

Kromě slabiny klíčového plánu využívá útok směny také stejná kola. Jedním ze způsobů, jak se tomu vyhnout, je použití různých konstant zaokrouhlení jako parametru funkce šifrování v samostatných kolech – to vám umožní provádět rozdíly ve fungování jednotlivých šifrovacích bloků, aniž by to výrazně komplikovalo šifrovací algoritmus jako celek.

Také účinnost útoku typu shift může být výrazně snížena zvýšením šifrovací síly kruhové šifrovací funkce. Takže jeho odolnost vůči útokům založeným na holém textu bude mnohem obtížnější najít kulatý klíč i v přítomnosti páru posunu.

Poznámky

  1. ↑ 1 2 3 4 5 6 7 Alex Biryukov, David Wagner. Slide Attacks  //  Rychlé softwarové šifrování. 6th International Workshop, FSE'99 Řím, Itálie, 24.–26. března 1999 Proceedings. - Springer Berlin Heidelberg, 1999. - S. 245-259 . - ISBN 978-3-540-66226-6 .  (nedostupný odkaz)
  2. ↑ EK Grossman, Thomas J. Watson Výzkumná divize IBM Research Center, B. Tuckerman. Analýza Feistelovy šifry oslabené tím, že nemá žádný rotační klíč . - IBM Thomas J. Watson Research Division, 1977. - 33 s.
  3. ↑ Eli Biham, Adi Shamir. Diferenciální kryptoanalýza kryptosystémů podobných DES  //  Pokroky v kryptologii-CRYPT0' 90 Proceedings. - Springer Berlin Heidelberg, 1990. - S. 2-21 . — ISBN 978-3-540-54508-8 .  (nedostupný odkaz)
  4. ↑ B. Preneel, V. Rijmen, A. Bosselears. Principy a výkon kryptografických algoritmů  //  Dr. Dobbův deník. - Miller Freeman, 1998. - Sv. 23 , č. 12 . - S. 126-131 .
  5. ↑ 1 2 3 4 5 6 Alex Biryukov, David Wagner. Advanced Slide Attacks  (anglicky)  // Advances in Cryptology - EUROCRYPT 2000. Mezinárodní konference o teorii a aplikaci kryptografických technik Bruggy, Belgie, 14.–18. května 2000 sborník příspěvků. - Springer Berlin Heidelberg, 2000. - S. 589-606 . — ISBN 978-3-540-67517-4 .  (nedostupný odkaz)
  6. ↑ 1 2 Panasenko S.P. Shift útok // Šifrovací algoritmy. Speciální referenční kniha - Petrohrad. : BHV-SPb , 2009. - S. 40-42. — 576 s. — ISBN 978-5-9775-0319-8
  7. ↑ 1 2 3 4 5 Chalermpong Worawannotai, Isabelle Stanton. Výukový program o útocích na slide  . Archivováno z originálu 29. listopadu 2014.
  8. ↑ Raphael C.-W. Phan. Advanced Slide Attacks Revisited: Realigning Slide on DES  //  Pokrok v kryptologii – Mycrypt 2005. První mezinárodní konference o kryptologii v Malajsii, Kuala Lumpur, Malajsie, 28.-30. září 2005. Sborník. - Springer Berlin Heidelberg, 2005. - S. 263-276 . — ISBN 978-3-540-28938-8 . Archivováno z originálu 12. června 2018.
  9. ↑ 1 2 Soichi Furuya. Slide Attacks with a Known-Plaintext Cryptanalysis  (anglicky)  // Information Security and Cryptology - ICISC 2001. 4th International Conference Soul, Korea, December 6–7, 2001 Proceedings. - Springer Berlin Heidelberg, 2002. - S. 214-225 . - ISBN 978-3-540-43319-4 . Archivováno z originálu 9. června 2018.
  10. ↑ Eli Biham, Orr Dunkelman, Nathan Keller. Vylepšené útoky na snímky  //  Rychlé softwarové šifrování. 14th International Workshop, FSE 2007, Lucemburk, Lucembursko, 26.-28. března 2007, Revised Selected Papers. - Springer Berlin Heidelberg, 2007. - S. 153-166 . — ISBN 978-3-540-74617-1 .  (nedostupný odkaz)
  11. ↑ Selçuk Kavut, Melek D. Yücel. Slide Attack on Spectr-H64  //  Progress in Cryptology - INDOCRYPT 2002. Third International Conference on Cryptology in India Hyderabad, India, December 16–18, 2002 Proceedings. - Springer Berlin Heidelberg, 2002. - S. 34-47 . - ISBN 978-3-540-00263-5 . Archivováno z originálu 11. června 2018.
  12. ↑ Nicolas T. Courtois, Gregory V. Bard, David Wagner. Algebraické a skluzové útoky na KeeLoq  //  Rychlé softwarové šifrování. 15. mezinárodní workshop, FSE 2008, Lausanne, Švýcarsko, 10.-13. února 2008, Revised Selected Papers. - Springer Berlin Heidelberg, 2008. - S. 97-115 . — ISBN 978-3-540-71038-7 . Archivováno z originálu 30. října 2018.
  13. ↑ 1 2 Michael Gorski, Stefan Lucks, Thomas Peyrin. Slide Attacks on a Class of Hash Functions  //  Advances in Cryptology - ASIACRYPT 2008. 14th International Conference on Theory and Application of Cryptology and Information Security, Melbourne, Australia, 7-11, 2008. Proceedings. - Springer Berlin Heidelberg, 2008. - S. 143-160 . - ISBN 978-3-540-89254-0 .  (nedostupný odkaz)
  14. ↑ Yu Sasaki, Lei Wang, Kazuo Ohta, Noboru Kunihiro. Password Recovery on Challenge and Response: Impossible Differential Attack on Hash Function  //  Pokrok v kryptologii – AFRICACRYPT 2008. První mezinárodní konference o kryptologii v Africe, Casablanca, Maroko, 11.–14. června 2008. Sborník příspěvků. - Springer Berlin Heidelberg, 2008. - S. 290-307 . — ISBN 978-3-540-68159-5 . Archivováno z originálu 6. června 2018.
  15. ↑ 1 2 Markku-Juhani O. Saarinen. Kryptoanalýza blokových šifer založených na SHA-1 a MD5  //  Rychlé softwarové šifrování. 10th International Workshop, FSE 2003, Lund, Švédsko, 24.-26. února 2003. Revidované příspěvky. - Springer Berlin Heidelberg, 2003. - S. 36-44 . — ISBN 978-3-540-20449-7 .  (nedostupný odkaz)
  16. ↑ Francois-Xavier Standaert, Gilles Piret, Jean-Jacques Quisquater. Kryptoanalýza blokových šifer: Průzkum  //  Série technických zpráv UCL Crypto Group. - 2003. Archivováno 10. února 2014.