Propojený klíčový útok

Related- key attack [ 1] je typ   kryptografického útoku , ve kterém si kryptoanalytik zvolí vztah mezi párem klíčů, ale klíče samotné mu zůstávají neznámé. Data jsou šifrována oběma klíči. Ve známé variantě otevřeného textu zná kryptoanalytik otevřený a šifrovaný text dat zašifrovaných dvěma klíči. Cílem útočníka je najít skutečné tajné klíče. Předpokládá se, že útočník zná nebo zvolí nějaký matematický vztah, který spojuje klíče dohromady. Vztah má tvar ( ) [2] , kde  je funkce zvolená útočníkem a  jsou k ní přidružené klíče. Pro každé šifrování se poměr mezi klíči volí individuálně. Existuje mnoho způsobů, jak tento poměr správně zjistit [3] . Ve srovnání s jinými útoky, ve kterých může útočník manipulovat pouze s otevřeným textem a/nebo šifrovaným textem, dává volba vztahu mezi tajnými klíči útočníkovi další stupeň svobody. Nevýhodou této svobody je, že takové útoky mohou být v praxi obtížnější. Návrháři se však obvykle snaží vytvořit „ideální“ primitiva, která lze automaticky použít bez další analýzy v co nejširší sadě protokolů nebo provozních režimů. Odolání takovým útokům je tedy důležitým cílem návrhu blokových šifer a ve skutečnosti to byl jeden z uvedených cílů návrhu algoritmu Rijndael .

Rozšíření klíče

Většina šifrovacích algoritmů upravuje původní klíč pro pozdější použití. Tato modifikace se nazývá rozšíření klíče . Existují příklady algoritmů, ve kterých je postup rozšiřování klíče extrémně složitý ve srovnání se skutečným šifrováním, mezi nimi stojí za zmínku algoritmy HPC a FROG . Název procedury je dán tím, že počáteční šifrovací klíč má obvykle velikost výrazně menší než sada podklíčů používaných v kolech algoritmu, tedy rozšířený klíč.


Ukazuje se, že šifrovací algoritmus lze logicky rozdělit na dva podalgoritmy: vlastní šifrovací transformace a proceduru rozšíření klíče. Existuje řada požadavků na postup rozšíření klíče [4] :

Klasický propojený klíčový útok [1]

Tento typ útoku poprvé navrhl izraelský vědec Eli Biham v roce 1992 v článku New Types of Cryptanalytic Attacks Using Related Keys . Jím popsaný útok propojeným klíčem připomíná útok smykem . Shift attack ( anglicky  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 [5] . Útok shift používá dva otevřené texty a splňují následující vztah: , kde je  funkce round a  je podklíč 1. kola. Související klíčový útok používá podobný vztah mezi klíči. Předpokládejme, že požadovaný šifrovací klíč K po jeho modifikaci procedurou rozšíření klíče dává sekvenci podklíčů: , kde  je počet kol šifrovacího algoritmu. Předpokládejme, že existuje klíč, jehož expanze dává následující sekvenci: , to znamená, že sekvence podklíčů vytvořená na základě klíče se cyklicky posouvá vzhledem k sekvenci požadovaného klíče o 1 kolo [6] .

Esence útoku

  1. Předpokládejme, že kryptoanalytik zná dvojice otevřených textů a jim odpovídající šifrované texty (zašifrované klíčem ), kde  je velikost bloku zašifrovaných dat vyjádřená v bitech .
  2. Kromě toho kryptoanalytik zná dvojice textů zašifrovaných pomocí klíče spojeného s výše uvedeným poměrem.
  3. Pro každou korelaci textů musí kryptoanalytik najít řešení soustavy rovnic [7] :

Který z textů odpovídá každému textu z , kryptoanalytik předem neví. Pravděpodobnost, že dva náhodně vybrané texty budou vyhovovat požadovanému poměru, je však .Potřebný pár pak musí být nalezen po analýze maximálně textů, v souladu s narozeninovým paradoxem . Podmínka textů není striktní, jde o odhad a bude splněna pouze průměrně [8] .

Klíč nalezený ve výše uvedeném systému je požadovaným podklíčem . V závislosti na operaci generování klíčů mohou znalosti poskytnout kryptoanalytikovi mnoho příležitostí k neoprávněnému přístupu k informacím. Například generování klíče algoritmu LOKI89 je konstruováno tak, že jde jednoduše o levou 32bitovou část klíče . Vzhledem k tomu, že tento algoritmus používá 64bitový klíč, stačí po výpočtu pouze vyčíslit možnosti jeho nalezení . [9]

Kruhová funkce napadeného algoritmu musí být dostatečně slabá pro výpočet , což je případ většiny moderních šifrovacích algoritmů. Složitost útoku lze navíc ve vztahu k výše popsanému případu výrazně snížit, vše závisí na zvoleném šifrovacím algoritmu otevřeného textu. Výpočty jsou například zjednodušeny pro algoritmy založené na vyvážené síti Feistel .

Útoky na různé šifrovací algoritmy

Útok na DES

DES ( data encryption s standard ) je algoritmus pro symetrické šifrování vyvinutý společností IBM a schválený vládou USA v roce 1977 jako oficiální standard ( FIPS 46-3  ). Velikost bloku pro DES je 64 bitů . Algoritmus je založen na Feistelově síti s 16 cykly ( koly ) a klíčem 56 bitů . Algoritmus využívá kombinaci nelineárních (S-boxy) a lineárních (E, IP, IP-1 permutace) transformací.

Šifrovací algoritmus DES je proti takovému útoku odolný. Během procesu šifrování pro hlavní šifrovací funkci je nutné vypočítat šestnáct 48bitových klíčů, které jsou výsledkem převodu původního 56bitového klíče ( další podrobnosti viz část „Generování klíčů“ ). Počet posunů v algoritmu výpočtu klíče se ve všech kolech neshoduje. Typicky jsou registry klíčů posunuty o dva bity po každém kole a pouze o jeden bit po prvním, devátém a patnáctém kole. Pokud však toto schéma přepínání změníte, nastavíte posun na stejný ve všech kolech, pak se výsledný kryptosystém stane zranitelným vůči útoku s propojeným klíčem. Nejméně bezpečný k útoku je modifikovaný DES, ve kterém je klíč po každé fázi posunut o dva bity [10] .

Tabulka popisuje počet směn před každým kolem generování klíčů a modifikovanou variantu čísla směny, která je zranitelná vůči útoku spojeného klíče. K rozluštění takové varianty algoritmu by kryptoanalytik potřeboval pouze 2 17 vybraných otevřených textů pro zvolené klíče nebo 2 33 známých otevřených textů pro zvolené klíče. Pro prolomení upraveného DES je potřeba provést 1,43*2 53 operací, což je malý zisk oproti vyčerpávajícímu vyhledávání, kde je počet operací 2 56 [11] . V roce 1998 byl DES pomocí superpočítače EFF DES cracker za 250 000 USD prolomen za méně než tři dny [12] . Cracker EFF DES použil pro cracker hledání hrubou silou [13] . Obrovské nároky na čas a objem dat neumožňují realizovat útok na připojené klíče bez pomoci drahého vybavení. Útok je však zajímavý ze dvou důvodů:

Útok na AES

Advanced Encryption Standard ( AES ), také známý jako Rijndael (vyslovováno [rɛindaːl] (Randal [14] )) je symetrický algoritmus blokové šifry (velikost bloku 128 bitů, klíč 128/192/256 bitů) přijatý jako šifrovací standard . Vláda USA podle výsledků soutěže AES . Tento algoritmus byl dobře analyzován a nyní je široce používán, jako tomu bylo u jeho předchůdce DES . AES se dodává ve třech variantách, z nichž každá poskytuje jinou úroveň zabezpečení v závislosti na délce tajného klíče. Klíč může být dlouhý 128, 192 a 256 bitů. Od roku 2001, po volbě AES jako kryptografického standardu, je pokrok v kryptoanalýze extrémně nízký [15] . Nejlepších výsledků bylo dosaženo v průběhu útoků na základě souvisejících klíčů v roce 2009. Alex Biryukov spolu s Dmitrijem Khovratovičem zajistili první kryptoanalytický útok s propojeným klíčem na AES-192 a AES-256, vyvinutá metoda je rychlejší než hrubá síla.

Vyvinutý útok na AES-256 je vhodný pro všechny typy klíčů a má složitost cca 2 96. Představen byl i útok na AES-192. Oba útoky minimalizují počet aktivních S-boxů algoritmu generování klíčů. Tato operace je aplikována pomocí bumerangového útoku . Diferenciální charakteristiky bumerangu byly stanoveny hledáním lokálních kolizí v šifře [16] . Hlavním rysem AES-256, který je rozhodující pro uvažované útoky, je to, že šifrovací algoritmus má 14 kol a 256bitový klíč, který se ve vnitřním stavu zdvojnásobuje. Algoritmus generování klíčů se tedy skládá pouze ze 7 kol a každé kolo má zase 8 S-boxů. Podobně pro AES-192, vzhledem k tomu, že klíč je ve vnitřním stavu jedenapůlkrát větší, sestává algoritmus generování klíče pouze z 8, nikoli z 12 kol. Každé kolo má pouze 4 S-bloky.

Útok na AES-256

Je nutné provést následující kroky 2 25,5krát [ 17] :

  1. Připravte strukturu otevřených textů , jak je uvedeno níže.
  2. Zašifrujte jej pomocí klíčů a a výsledné sady uložte a .
  3. Je nutné provést operaci pro všechny šifrové texty v a dešifrovat upravené šifrové texty pomocí klíče .  - nová sada otevřených textů.
  4. Podobně pro a klíč .  - nová sada otevřených textů.
  5. Porovnání všech dvojic otevřených textů od as délkou 56 bitů.
  6. U všech ostatních zkontrolujte rozdíl v hodnotě pravděpodobnosti v . Pokud je stejná na obou stranách 16bitového filtru, pak se pro páry klíčů nebo jinak nazývají kvartet a , v , budou také stejné na obou stranách strany.
  7. Je nutné vybrat kvartety, jejichž rozdíly nelze ovlivnit aktivními S-boxy v prvním kole a aktivními S-boxy v algoritmu generování klíčů.
  8. Odfiltrováním nesprávných kvartetů částečně obnovíme hodnotu klíče.

Každá struktura má nejrůznější možnosti pro sloupec nula, řádek nula a konstantní hodnotu v jiných bajtech. Z 272 textů v každé struktuře lze porovnat 2144 párů. Z těchto dvojic projde prvním kolem 2 (144−8*9) = 2 72 . Získáme tak 1 požadovaný kvartet 2 (96-72) = 2 24 struktur a 3 požadované kvartety 2 25,5 struktur. Vypočítáme počet kvartetů z minulých 6 kroků, budou asi 2 (144-56-16) = 2 72 párů. Dalším krokem je aplikace 16bitového filtru, takže dostaneme celkový počet možných kvartetů 2 (72+25,5−6) = 2 91,5 [18] .

Útok na AES-192

Algoritmus generování klíče má v tomto případě nejlepší difúzi. Proto bumerangový útok používá dvě dílčí stopy po 6 kolech. Analyzujme 2 73 struktur s 2 48 texty podle následujícího schématu [19] :

  1. Porovnejte všechny dvojice možných otevřených textů pro dvojice klíčů a .
  2. Porovnejte a uložte všechny kvartety šifrovaného textu.
  3. Pro každý očekávaný klíčový bajt : a in ; v a :
    1. vypočítat hodnoty pro tyto bajty ve všech klíčích z delta trasování. Získejte klíčové rozdíly v a ;
    2. vybrat kvarteta, která si odporují ;
    3. připravit čítače pro nevypočítané klíčové bajty, které odpovídají aktivním S-boxům v prvních dvou a posledních: , , ,  — v klíčích a , , , ,  — v klíčích a , celkem 16 bajtů;
    4. pro každý kvartet nastavte možné hodnoty pro jejich neznámé bajty a zvyšte čítače;
    5. vytvořit skupinu 16 klíčových bajtů s maximálním počtem čísel;
    6. vyzkoušejte všechny možné hodnoty dosud neznámých 9 bajtů klíče a zkontrolujte, zda je klíč správný. Pokud scénář selže, přejděte k prvnímu kroku [19] .

Oba prezentované útoky jsou především teoretického zájmu a v praxi nepředstavují reálnou hrozbu pro aplikace využívající AES.

Praktická aplikace

Popsané útoky pomocí souvisejících klíčů nevypadají prakticky. V mnoha vývoji jim oproti vyčerpávajícímu vyhledávání příliš neprospívají, navíc vyžadují velké množství předpokladů. Tento útok byl dlouho považován za poměrně silný, ale čistě teoretický [20] . Odborníci jako John Kelsey a Bruce Schneier [20] se však nyní domnívají, že útoky s propojeným klíčem mohou mít praktické využití. Některé implementace kryptografických algoritmů nebo síťových protokolů (například autentizační protokoly nebo protokoly pro výměnu klíčů) již mohou být náchylné k útoku spojeného klíče [20] . Jednou z potenciálních aplikací je analýza hashovací funkce . Teoreticky mohou být útoky s propojeným klíčem nebezpečné, pokud se k vytváření hashovacích funkcí používají symetrické šifrovací algoritmy. V současné době není známa žádná konkrétní aplikace pro hašovací funkce, ale návrháři hašovacích funkcí by měli při navrhování vzít v úvahu, že taková slabina existuje. V každém případě se důrazně doporučuje vzít v úvahu kryptoanalýzu souvisejících klíčů při vývoji šifrovacích algoritmů a jejich implementaci [21] . V [20] je poznamenáno , že hlavní podmínka útoku vypadá poněkud zvláštně: kryptoanalytik může klíč zapsat, to znamená upravit požadovaný neznámý klíč požadovaným způsobem, ale nemůže jej přečíst. Některé implementace kryptografických algoritmů nebo síťových protokolů však mohou být napadeny pomocí přidružených klíčů. V každém případě se důrazně doporučuje vzít v úvahu kryptoanalýzu propojených klíčů [20] při vývoji šifrovacích algoritmů a jejich implementaci. Je také třeba poznamenat, že útoky na související klíče mohou být velmi nebezpečné, pokud jsou k vytváření hashovacích funkcí použity symetrické šifrovací algoritmy.

Existují další potenciální zranitelnosti zavedené do šifrovacího algoritmu špatně navrženým postupem rozšíření klíče, zejména [22] :

  • zranitelnost vůči útokům „setkání ve střední“ třídě, protože tyto útoky využívají skutečnost, že první část šifrovacích transformací napadeného algoritmu používá jinou sadu klíčových bitů. než druhá část.
  • Slabé klíče  jsou klíče, které jsou ekvivalentní dešifrování nebo mají jiné vlastnosti, které usnadňují jejich prolomení.
  • ekvivalentní klíče  – různé klíče, ale poskytující stejný výsledek šifrování na určité podmnožině otevřených textů.
  • třídy klíčů  - vznikají, když kryptoanalytik může relativně snadno určit podmnožinu sady klíčů, ke které požadovaný klíč patří, a podle toho zmenšit oblast úplného výčtu klíče.

Viz také

Poznámky

  1. ↑ 1 2 Panasenko S., 2009 , s. 54.
  2. ↑ Birjukov a Chovratovič, 2009 , s. osm.
  3. ↑ Bellare, 2003 , str. 491.
  4. ↑ Panasenko S., 2009 , s. 53.
  5. ↑ Biryukov, Wagner, 1999 , str. 245-259.
  6. ↑ Birjukov a Chovratovič, 2009 , s. 7.
  7. ↑ Biham, 1994 , s. 16.
  8. ↑ Panasenko S., 2009 , s. 55.
  9. ↑ Panasenko S., 2009 , s. 56.
  10. ↑ Biham, 1994 , s. patnáct.
  11. ↑ Biham, 1994 , s. 17.
  12. ↑ Počítačový svět, 1998 .
  13. ↑ DES Cracker Project (downlink) . Eff. — "Ve středu 17. července 1998 EFF DES Cracker, který byl postaven za méně než 250 000 $, snadno vyhrál soutěž RSA Laboratory "DES Challenge II" a peněžní cenu 10 000 $." Získáno 8. července 2007. Archivováno z originálu dne 7. května 2017. 
  14. ↑ "... V souladu s vlámskými pravidly se název čte jako "Randal" - "Computerra", prosinec 1999, č. 49
  15. ↑ Birjukov a Chovratovič, 2009 , s. jeden.
  16. ↑ Birjukov a Chovratovič, 2009 , s. 2.
  17. ↑ Birjukov a Chovratovič, 2009 , s. 9.
  18. ↑ Birjukov a Chovratovič, 2009 , s. deset.
  19. ↑ 1 2 Birjukov a Chovratovič, 2009 , str. 12.
  20. ↑ 1 2 3 4 5 John Kelsey, 1996 .
  21. ↑ Biham, 1994 , s. 2.
  22. ↑ Panasenko S., 2009 , s. 59.

Literatura