Algoritmus GOST 28147 89 je. Domácí standard šifrování dat. Variace na téma host
Na rozdíl od amerického DES používá tuzemský standard delší klíč – 256 bitů. Kromě toho ruský standard navrhuje použít 32 kol šifrování, zatímco DES vyžaduje pouze 16.
Hlavní parametry algoritmu transformace kryptografických dat GOST 28147-89 jsou tedy následující: velikost bloku je 64 bitů, velikost klíče je 256 bitů, počet kol je 32.
Algoritmus je klasická Feishtelova síť. Šifrovaný datový blok je rozdělen na dvě identické části, pravou R a levou L. Pravá část se přidá ke kulatému podklíči a pomocí nějakého algoritmu zašifruje levou část. Před dalším kolem se prohodí levá a pravá část. Tato struktura umožňuje použít stejný algoritmus pro šifrování i dešifrování bloku.
Šifrovací algoritmus používá následující operace:
- sčítání slov modulo 2 32;
- cyklicky posouvat slovo doleva o zadaný počet bitů;
- bitové sčítání modulo 2;
- výměna dle tabulky.
V různých krocích algoritmů GOST jsou data, se kterými pracují, interpretována a používána různými způsoby. V některých případech jsou datové prvky považovány za pole nezávislých bitů, v jiných případech jako celé číslo bez znaménka, v jiných jako mající strukturu komplexní prvek skládající se z několika jednodušších prvků.
Kruhová konstrukce GOST 28147-89
Struktura jednoho kola GOST 28147-89 je znázorněna na Obr. 5.1.
Šifrovaný datový blok je rozdělen na dvě části, které jsou následně zpracovány jako samostatná 32bitová celá čísla bez znaménka. Nejprve se přidá pravá polovina bloku a podklíč kola modulo 2 32. Poté se provede substituce blok po bloku. 32bitová hodnota získaná v předchozím kroku (říkejme jí S) je interpretována jako pole osmi 4bitových kódových bloků: S=(S0,S1,S2,S3,S4,S5,S6,S7). Dále je hodnota každého z osmi bloků nahrazena novou, která se vybere z náhradní tabulky následovně: hodnota bloku S i je nahrazena S i -tým prvkem v pořadí (číslování od nuly) i-tého náhradního uzlu (tj. nahrazovací tabulky i-tého řádku, číslování také od začátku). Jinými slovy, prvek s číslem řádku rovným číslu nahrazovaného bloku a číslem sloupce rovným hodnotě nahrazovaného bloku jako 4bitové nezáporné celé číslo je vybrán jako náhrada za hodnotu blok. Každý řádek náhradní tabulky obsahuje čísla od 0 do 15 v náhodném pořadí bez opakování. Hodnoty prvků substituční tabulky se berou od 0 do 15, protože čtyři bity, které jsou nahrazeny, mohou obsahovat celé číslo bez znaménka v rozsahu od 0 do 15. Například první řádek S-boxu může obsahovat následující hodnoty: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . V tomto případě bude hodnota bloku So (čtyři nejméně významné bity 32bitového čísla S) nahrazena číslem na pozici, jehož číslo se rovná hodnotě nahrazovaného bloku. Pokud S 0 = 0, bude nahrazeno 5, pokud S 0 = 1, bude nahrazeno 8 atd.
Rýže. 5.1.
Po provedení substituce jsou všechny 4bitové bloky opět zřetězeny do jediného 32bitového slova, které je poté otočeno o 11 bitů doleva. Nakonec pomocí bitové operace "součet modulo 2" výsledek je kombinován s levou polovinou a výsledkem je nová pravá polovina R i. Nová levá strana Li se rovná spodní části převedeného bloku: Li = R i-1.
Výsledná hodnota převedeného bloku je považována za výsledek jednoho kola šifrovacího algoritmu.
Postupy šifrování a dešifrování
GOST 28147-89 je tedy bloková šifra konverze dat prováděné v blocích v tzv základní cykly. Základní smyčky se skládají z opakovaného provádění hlavního kola, o kterém jsme hovořili dříve pro datový blok, s použitím různých klíčových prvků a liší se od sebe pořadím, ve kterém jsou klíčové prvky použity. Každé kolo používá jeden z osmi možných 32bitových podklíčů.
Podívejme se na proces vytváření kulatých podklíčů. V GOST je tento postup velmi jednoduchý, zejména ve srovnání s DES. 256bitový klíč K je rozdělen do osmi 32bitových podklíčů, označených K0, K1, K2, K3, K4, K5, K6, K7. Algoritmus obsahuje 32 kol, takže každý podklíč během šifrování je použit ve čtyřech kolech v pořadí uvedeném v tabulce 5.1.
| Kolo | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Kompletní konstrukce | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Kolo | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| Kompletní konstrukce | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Kolo | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| Kompletní konstrukce | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Kolo | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| Kompletní konstrukce | K 7 | K 6 | K5 | K 4 | K 3 | K2 | K 1 | K 0 |
Proces dešifrování se provádí pomocí stejného algoritmu jako šifrování. Jediný rozdíl je v pořadí, ve kterém se používají podklíče Ki. Při dešifrování musí být podklíče použity v opačném pořadí, konkrétně jak je uvedeno v
Tento algoritmus je povinný pro použití jako šifrovací algoritmus ve vládních organizacích Ruské federace a řadě komerčních.
Popis algoritmu
Schéma algoritmu je znázorněno na Obr. 3.1. Jak vidíte, návrh tohoto algoritmu je poměrně jednoduchý, což jednoznačně zjednodušuje jeho softwarovou nebo hardwarovou implementaci.
Algoritmus GOST 28147-89 šifruje informace v blocích po 64 bitech, které jsou rozděleny do dvou podbloků po 32 bitech (N1 a N2). Podblok N1 je zpracován určitým způsobem, načež se jeho hodnota sečte
s hodnotou podbloku N2 (sčítání se provádí modulo 2), pak se podbloky prohodí. Tato transformace se provádí v určitém počtu kol: 16 nebo 32, v závislosti na provozním režimu algoritmu (popsáno níže). V každém kole se provádějí následující operace:
1. Klíčová aplikace. Obsah podbloku /VI je přidán modulo 2 32 s částí klíče Kx.
Šifrovací klíč algoritmu GOST 28147-89 má rozměr 256 bitů a Kx je jeho 32bitová část, tj. 256bitový šifrovací klíč je reprezentován jako zřetězení 32bitových podklíčů (obr. 3.2):
Shch ATI, AG2, Yu, AG4, K5, Kb, K7.
Během procesu šifrování je použit jeden z těchto podklíčů v závislosti na čísle kola a provozním režimu algoritmu.
Rýže. 3.1. Schéma algoritmu GOST 28147-
Rýže. 3.2. Šifrovací klíč algoritmu GOST 28147-89
2. Výměna stolu. Po zaklíčování se podblok /VI rozdělí na 8 částí po 4 bitech, z nichž hodnota každé je individuálně nahrazena v souladu s tabulkou náhrad pro tuto část podbloku. Náhrady tabulek (Substitution box, S-box) se často používají v moderních šifrovacích algoritmech, takže stojí za to se nad nimi podrobněji zabývat.
Substituce tabulky se používá tímto způsobem: na vstup je přiveden blok dat určité velikosti (v tomto případě 4bitový), jehož číselná reprezentace určuje číslo výstupní hodnoty. Máme například S-box následujícího tvaru:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
Na vstup nechť přijde 4bitový blok „0100“, tedy hodnota 4. Podle tabulky bude výstupní hodnota rovna 15, tzn. „1111“ (0 je nahrazeno 4, 1 11, hodnota 2 zůstává nezměněna atd.).
Jak vidíte, návrh algoritmu je velmi jednoduchý, což znamená, že největší zátěž šifrování dat dopadá na náhradní tabulky. Algoritmus má bohužel tu vlastnost, že existují „slabé“ náhradní tabulky, pomocí kterých lze algoritmus řešit kryptoanalytickými metodami. Mezi slabé patří například tabulka, ve které je výstup roven vstupu:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Bitový cyklický posun doleva o 11 bitů.
Provozní režimy algoritmů
Algoritmus GOST 28147-89 má 4 provozní režimy:
□ jednoduchý režim výměny;
□ režim gama;
P gama režim s zpětná vazba;
□ způsob vývoje imitace příloh.
Tyto režimy se poněkud liší od obecně přijímaných režimů (popsaných v části 1.4), takže stojí za to se nad nimi podrobněji zabývat.
Tyto režimy mají různé účely, ale používají stejnou transformaci šifrování popsanou výše.
Režim snadné výměny
V režimu jednoduchého nahrazování je každý 64bitový blok informací jednoduše zašifrován pomocí výše popsaných 32 kol. 32bitové podklíče se používají v následujícím pořadí:
□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI atd. - v kolech 1 až 24;
□ K1, Kb, K5, K4, KZ, K2, K\, KO - v kolech od 25. do 32.
Dešifrování v režimu jednoduchého nahrazení se provádí přesně stejným způsobem, ale s mírně odlišnou sekvencí použití podklíčů:
□ KO, K\, K2, KZ, K4, K5, Kb, KP - v kolech 1 až 8;
□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb atd. - v kolech od 9. do 32.
Podobně jako standardní režim ECB se kvůli samostatnému šifrování bloků režim jednoduchého nahrazení přísně nedoporučuje pro šifrování samotných dat; měl by být používán pouze k šifrování jiných šifrovacích klíčů ve víceklíčových schématech.
Režim gama
V gama režimu (obr. 3.3) je každý blok otevřeného textu bit po bitu modulo 2 přidáván do 64bitového šifrovacího gama bloku. Gama šifra je speciální sekvence, která se generuje pomocí transformací popsaných výše:
1. Jejich počáteční naplnění se zapíše do registrů N1 a N2 - 64bitová hodnota nazývaná „synchronizační zpráva“ (synchronizační zpráva je prakticky obdobou inicializačního vektoru v režimech CBC, CFB a OFB).
2. Obsah registrů /VI a N2 (v tomto případě synchronizační zprávy) je zašifrován v režimu jednoduchého nahrazení.
3. Obsah N1 se sečte modulo (2 32 – 1) s konstantou CI = 2 24 + 2 16 + 2 8 + 4, výsledek sčítání se zapíše do registru /VI.
4. K obsahu N2 se přičte modulo 2 s konstantou C2 = 2 24 + 2 16 + 2 8 +1, výsledek sčítání se zapíše do registru N2.
5. Obsah registrů /VI a N2 je vydán jako 64bitový šifrovací gama blok (tj. v tomto případě /VI a N2 tvoří první gama blok).
6. Pokud je potřeba další gama blok (tj. je třeba provést další šifrování nebo dešifrování), vraťte se ke kroku 2.
Pro dešifrování se gama generuje podobným způsobem, poté se šifrový text a bity gama znovu XORují.
Pro vygenerování stejného rozsahu šifry musí mít uživatel dešifrující kryptogram stejný klíč a stejnou hodnotu synchronizační zprávy, jaké byly použity při šifrování informací. V opačném případě nebude možné ze zašifrovaného získat původní text.
Ve většině implementací algoritmu GOST 28147-89 není synchronizační zpráva tajným prvkem, nicméně synchronizační zpráva může být stejně tajná jako šifrovací klíč. V tomto případě můžeme uvažovat, že efektivní délka klíče algoritmu (256 bitů) se zvětší o dalších 64 bitů synchronizační zprávy, což lze považovat za další klíčový prvek.
Gamma režim se zpětnou vazbou
V režimu gama se zpětnou vazbou je výsledek zašifrování předchozího bloku otevřeného textu použit k vyplnění registrů /VI a L/2, počínaje 2. blokem, nikoli předchozím blokem gama, ale výsledkem zašifrování předchozího bloku otevřeného textu. (obr. 3.4). První blok v tento režim se generuje zcela podobně jako předchozí.
Rýže. 3.4. Generování šifry gama v režimu gama se zpětnou vazbou
Režim výroby imitace přílohy
Prefix je kryptografický kontrolní součet vypočítaný pomocí šifrovacího klíče a určený k ověření integrity zpráv. Pro jeho výpočet existuje speciální režim algoritmu GOST 28147-89.
Generování předpony imitace se provádí následovně:
1. První 64bitový blok informací, pro který je vypočítána předpona imitace, je zapsán do registrů N1 a N2 a zašifrován v režimu redukovaného jednoduchého nahrazení, ve kterém je provedeno prvních 16 kol z 32.
2. Získaný výsledek se sečte modulo 2 s dalším blokem informací, přičemž výsledek se uloží do N1 a N2.
3. M a N2 jsou opět zašifrovány ve zkráceném režimu jednoduché výměny atd. až do posledního bloku informací.
Za imitaci prefixu se považuje 64bitový výsledný obsah registrů N1 a N2 nebo jejich části. Nejčastěji se používá 32bitový imitativní prefix, tedy polovina obsahu registrů. To stačí, protože jako každý kontrolní součet je imitace přílohy určena především k ochraně před náhodným zkreslením informací. K ochraně před úmyslnou úpravou dat se používají jiné kryptografické metody – především elektronické digitální podpis(viz část 1.1).
Předpona imitace se používá takto:
1. Při šifrování jakékoli informace se vypočítá předpona imitace otevřeného textu a odešle se spolu se šifrovaným textem.
2. Po dešifrování je předpona imitace znovu vypočítána a porovnána s odeslanou.
3. Pokud se vypočítané a odeslané předpony imitace neshodují, došlo při přenosu ke zkreslení textu šifry nebo byly při dešifrování použity nesprávné klíče.
Imitační předpona je zvláště užitečná pro kontrolu správného dešifrování klíčových informací při použití víceklíčových schémat.
Imitační předpona je nějaká analogie autentizačního kódu zprávy MAC, vypočítaného v režimu CBC; Rozdíl je v tom, že při výpočtu prefixu imitace se nepoužívá synchronizační zpráva, zatímco při výpočtu MAC se používá inicializační vektor.
Kryptografická síla algoritmu
V roce 1994 byl popis algoritmu GOST 28147-89 přeložen do angličtiny a publikován; poté se začaly objevovat výsledky jeho analýzy provedené zahraničními specialisty; po dlouhou dobu však nebyly nalezeny žádné útoky blížící se proveditelnosti.
□ velká délka klíče – 256 bitů; spolu s tajnou synchronizační zprávou se efektivní délka klíče zvýší na 320 bitů;
□ 32 kol transformací; již po 8 kolech je dosaženo plného efektu rozptylu vstupních dat: změna jednoho bitu bloku prostého textu ovlivní všechny bity bloku šifrovaného textu a naopak, tj. existuje vícenásobná rezerva síly.
Podívejme se na výsledky kryptoanalýzy algoritmu GOST 28147-89.
Analýza substitučních tabulek
Vzhledem k tomu, že standard neobsahuje náhradní tabulky, řada prací (například v) naznačuje, že „kompetentní organizace“ může vydávat „dobré“ i „špatné“ náhradní tabulky. Slavný odborník Bruce Schneier však takové domněnky nazývá „fámami“. Je zřejmé, že kryptografická síla algoritmu do značné míry závisí na vlastnostech použitých náhradních tabulek, a proto existují slabé náhradní tabulky (viz příklad výše), jejichž použití může zjednodušit útok na algoritmus. Přesto se možnost použití různých nahrazovacích tabulek jeví jako velmi cenný nápad, ve prospěch kterého lze uvést následující dvě skutečnosti z historie šifrovacího standardu DES (podrobnosti viz Sekce 3.15):
□ útoky využívající jak lineární, tak diferenciální kryptoanalýzu algoritmu DES využívají specifické vlastnosti náhradních tabulek; při použití jiných tabulek bude muset kryptoanalýza začít znovu;
□ byly učiněny pokusy posílit DES proti lineární a diferenciální kryptoanalýze použitím robustnějších substitučních tabulek; takové tabulky, které jsou skutečně robustnější, byly navrženy například v algoritmu s 5 DES; ale bohužel nebylo možné nahradit DES s 5 DES, protože nahrazující tabulky jsou striktně definovány ve standardu, a proto implementace algoritmu pravděpodobně nepodporují schopnost měnit tabulky na jiné.
Řada prací (například , a ) chybně dochází k závěru, že tajné náhradní tabulky algoritmu GOST 28147-89 mohou být součástí klíče a prodloužit jeho efektivní délku (což není významné, protože algoritmus má velmi velké 256 -bitový klíč). Práce však dokazuje, že tajné náhradní tabulky lze vypočítat pomocí následujícího útoku, který lze prakticky použít:
1. Nastaví se klíč nula a provede se hledání „nulového vektoru“, tj. hodnoty z = /(0), kde /() je zaokrouhlená funkce algoritmu. Tato fáze trvá asi 2 šifrovací operace.
2. Pomocí nulového vektoru se vypočítají hodnoty nahrazovacích tabulek, což nezabere více než 2 11 operací.
Úpravy algoritmů a jejich analýza
Práce provedla kryptoanalýzu modifikací algoritmu GOST 28147-89:
□ Algoritmus GOST-H, ve kterém bylo oproti původnímu algoritmu změněno pořadí použití podklíčů, a to v kolech od 25 do 32 podklíčů se používá v přímém pořadí, tedy úplně stejně jako v předchozích kolech algoritmu;
□ 20kolový algoritmus GOST®, ve kterém kolo používá k překrytí klíče XOR místo přidání modulo-2.
Na základě výsledků analýzy se dospělo k závěru, že GOST-H a GOST© jsou slabší než původní algoritmus GOST 28147-89, protože oba mají třídy slabých klíčů. Stojí za zmínku, že pokud jde o kryptoanalýzu GOST©, práce slovo od slova opakuje část věnovanou kryptoanalýze algoritmu GOST 28147-89, známé práce publikované v roce 2000 (bez jakýchkoli odkazů na originál). To zpochybňuje profesionalitu autorů práce a její další výsledky.
V práci byla navržena velmi zajímavá modifikace algoritmu: tabulky S\…Ss musí být nutně odlišné; v každém kole algoritmu musí být přeskupeny podle určitého zákona. Tato permutace může být závislá na šifrovacím klíči, nebo může být také tajná (tj. být součástí většího šifrovacího klíče, než je původní 256bitový klíč). Obě tyto možnosti podle jejich autorů výrazně zvyšují odolnost algoritmu vůči lineární a diferenciální kryptoanalýze.
A ještě jedna úprava související se substitučními tabulkami je uvedena v práci, ve které je jedna z možné metody výpočet náhradních tabulek na základě šifrovacího klíče. Autoři práce došli k závěru, že taková závislost oslabuje algoritmus, protože vede k přítomnosti slabých klíčů a k některým potenciálním zranitelnostem algoritmu.
Kompletní analýza algoritmů
Existují také útoky na celoobvodový GOST 28147-89 bez jakýchkoli úprav. Jeden z prvních otevřená díla, ve kterém byla provedena analýza algoritmu, známá práce se věnuje útokům využívajícím slabiny procedury rozšiřování klíče řady známých šifrovacích algoritmů. Zejména úplný algoritmus GOST 28147-89 lze prolomit pomocí diferenciální kryptoanalýzy souvisejících klíčů, ale pouze v případě, že jsou použity slabé náhradní tabulky. 24kolová verze algoritmu (ve které chybí prvních 8 kol) se otevírá podobným způsobem s jakýmikoli náhradními tabulkami, ale silné náhradní tabulky (například ta uvedená) činí takový útok zcela nepraktickým.
Domácí vědci A.G. Rostovtsev a E.B. Makhovenko v roce 2001 ve své práci navrhli, že nová metoda kryptoanalýza (podle autorů výrazně účinnější než lineární a diferenciální kryptoanalýza) tak, že ze známého otevřeného textu, odpovídajícího šifrového textu a požadované hodnoty klíče vytvoříme objektivní funkci a zjistíme její extrém odpovídající skutečné hodnotě klíče. Našli také velkou třídu slabých klíčů algoritmu GOST 28147-89, které umožňují otevřít algoritmus pouze pomocí 4 vybraných otevřených textů a odpovídajících šifrových textů s poměrně nízkou složitostí. V práci pokračuje kryptoanalýza algoritmu.
V roce 2004 skupina specialistů z Koreje navrhla útok, který pomocí diferenciální kryptoanalýzy souvisejících klíčů může získat 12 bitů tajného klíče s pravděpodobností 91,7 %. Útok vyžaduje 2 35 vybraných otevřených textů a 2 36 šifrovacích operací. Jak vidíte, tento útok je prakticky nepoužitelný pro skutečné porušení algoritmu.
). Zároveň v ruských médiích a blozích ruských uživatelů roste počet poznámek o tomto algoritmu: jak s různou mírou spolehlivosti pokrývají výsledky útoků na ruský standard, tak obsahují názory na jeho provozní vlastnosti. Autoři (a následně i čtenáři) těchto poznámek často nabývají dojmu, že domácí šifrovací algoritmus je zastaralý, pomalý a má zranitelnosti, díky kterým je výrazně náchylnější k útokům než zahraniční šifrovací algoritmy s podobnou délkou klíče. S touto sérií poznámek bychom rádi přístupnou formou mluvit o současném stavu věcí s ruským standardem. První část bude pokrývat všechny útoky na GOST 28147-89 známé mezinárodní kryptografické komunitě a aktuální hodnocení její síly. V budoucích publikacích se také blíže podíváme na vlastnosti standardu z pohledu schopnosti budovat efektivní implementace.
Nicolas Courtois - "velký a hrozný"
Začněme příběhem o činnosti Nicolase Courtoise, který je autorem celé řady prací věnovaných ruskému standardu blokového šifrování ().
V říjnu 2010 začal proces zvažování zahrnutí algoritmu GOST 28147-89 do mezinárodní normy ISO/IEC 18033-3. Již v květnu 2011 se v elektronickém archivu ePrint objevil článek slavného kryptografa Nicolase Courtoise, poznamenaný velmi nejednoznačným postojem světové kryptografické komunity k němu. Courtoisovy publikace jsou smutným příkladem manipulace s pojmy, která sice neodhaluje žádné nové vlastnosti daného předmětu, ale s nárokem na senzaci vyvolává v nekompetentním prostředí šíření mylných názorů na jeho skutečné vlastnosti.
Algebraická metoda
Courtoisova úvaha je postavena na dvou třídách kryptoanalytických metod: algebraických metodách a diferenciálních. Podívejme se na první třídu metod.
Zjednodušeně lze metodu algebraické kryptoanalýzy popsat jako sestavení a řešení rozsáhlé soustavy rovnic, z nichž každé řešení odpovídá cíli kryptoanalytika (např. je-li soustava sestavena pomocí jedné dvojice otevřeného textu a šifrovaného textu, pak všechna řešení tohoto systému odpovídají klíčům, kterými se tento otevřený text převádí na tento je zašifrován). To znamená, že v případě problému dešifrování blokové šifry je podstatou algebraické metody dešifrování to, že klíč je nalezen jako výsledek řešení systému polynomiálních rovnic. Hlavním problémem je umět sestavit co nejvíce s přihlédnutím k vlastnostem konkrétní šifry. jednoduchý systém aby proces jeho řešení zabral co nejméně času. Klíčovou roli zde hrají vlastnosti každé konkrétní analyzované šifry.
Algebraická metoda použitá Courtoisem může být stručně popsána následovně. V první fázi se takové vlastnosti GOST 28147-89 používají jako existence pevného bodu pro část transformace šifrování a také jako takzvaný bod odrazu. Díky těmto vlastnostem je vybráno několik párů z dostatečně velkého počtu párů holého textu-šifrovaný text, což umožňuje uvažovat o transformacích nikoli ve 32, ale pouze v 8 kolech. Druhá fáze spočívá v tom, že na základě výsledků 8 kruhových transformací získaných v první fázi je sestaven systém nelineárních rovnic, ve kterých jsou klíčové bity neznámé. Dále je tento systém vyřešen (to zní jednoduše, ale ve skutečnosti je to časově nejnáročnější část metody, protože systém se skládá z nelineárních rovnic).
Jak bylo uvedeno výše, nikde v práci není podrobný popis a rozbor složitosti druhé a hlavní etapy určování klíče. Právě složitost druhé fáze určuje složitost celé metody jako celku. Místo toho autor uvádí notoricky známá „fakta“, na jejichž základě provádí odhady pracovní náročnosti. Tato „fakta“ jsou prý založena na experimentálních výsledcích. Rozbor „faktů“ z Courtoisova díla jako celku je uveden v díle domácích autorů. Autoři této práce poznamenávají, že mnoho Courtoisových „faktů“ prezentovaných bez jakýchkoli důkazů bylo během experimentálního testování shledáno nepravdivými. Autoři článku šli dále a po Courtoise provedli analýzu složitosti druhé etapy pomocí dobře podložených algoritmů a odhadů. Výsledné odhady složitosti ukazují naprostou nepoužitelnost prezentovaného útoku. Kromě domácích autorů byly v díle zaznamenány například i velké problémy, které má Courtois s posuzováním a zdůvodňováním svých metod.
Diferenciální metoda
Podívejme se na druhou Courtoisovu metodu, která je založena na diferenciální kryptoanalýze.
Obecná metoda diferenciální kryptoanalýzy je založena na využití vlastností nelineárních zobrazení používaných v kryptografických primitivech, spojených s vlivem hodnoty klíče na závislosti mezi rozdíly mezi páry vstupních a párů výstupních hodnot těchto zobrazení. . Popišme hlavní myšlenku diferenciální metody kryptografické analýzy blokové šifry. Typicky blokové šifry transformují vstupní data po etapách pomocí řady tzv. kulatých transformací a každá okrouhlá transformace nepoužívá celý klíč, ale pouze jeho část. Uvažujme mírně „osekanou“ šifru, která se od původní liší tím, že nemá poslední kolo. Předpokládejme, že bylo možné prokázat, že zašifrování dvou otevřených textů, které se liší v určitých pevných pozicích pomocí takovéto „zkrácené“ šifry, s největší pravděpodobností povede k šifrovaným textům, které se také liší v některých pevných pozicích. Tato vlastnost ukazuje, že „zkrácená“ šifra s největší pravděpodobností zanechává závislost mezi některými otevřenými texty a výsledky jejich šifrování. Aby bylo možné obnovit část klíče pomocí této zjevné chyby, je nutné umět zašifrovat předem vybrané otevřené texty na klíči, který chceme obnovit (tzv. „útok vybraného otevřeného textu“). Na začátku procedury „otevření klíče“ je náhodně vygenerováno několik dvojic otevřených textů, které se liší ve stejných pevných pozicích. Všechny texty jsou šifrovány pomocí „plné“ šifry. Výsledné dvojice šifrovaného textu se použijí k obnovení těch klíčových bitů, které byly použity v poslední transformaci kola, jak je uvedeno dále. Pomocí nějaké náhodně vybrané hodnoty požadovaných klíčových bitů se na všechny šifrové texty aplikuje transformace inverzní k transformaci posledního kola. Ve skutečnosti, pokud uhodneme požadovanou hodnotu bitů klíče, dostaneme výsledek „zkrácené“ šifry, a pokud neuhodneme, ve skutečnosti data „zašifrujeme ještě více“, což pouze sníží závislost mezi bloky uvedená výše (rozdíl je v některých pevných polohách). Jinými slovy, pokud mezi výsledky takového „dodatečného zpracování“ šifrových textů bylo poměrně mnoho dvojic, které se liší v nám známých pevných pozicích, znamená to, že jsme uhodli požadované klíčové bity. Jinak takových párů bude podstatně méně. Vzhledem k tomu, že v každém kole je použita pouze část klíče, není tolik prohledávaných bitů (tj. bitů klíče použitých v posledním kole), jako je bitů v v plném klíči a můžete je jednoduše třídit opakováním výše uvedených kroků. V tomto případě určitě někdy narazíme na správný význam.
Z výše uvedeného popisu vyplývá, že nejdůležitější věcí v metodě diferenciální analýzy jsou počty právě těch pozic v otevřených textech a šifrových textech, jejichž rozdíly hrají klíčovou roli při obnově klíčových bitů. Zásadní přítomnost těchto pozic, stejně jako množina jejich čísel, přímo závisí na vlastnostech těch nelineárních transformací, které jsou použity v kterékoli blokové šifře (většinou je veškerá „nelinearita“ soustředěna do tzv. S-boxů resp. náhradní uzly).
Courtois používá mírně upravenou verzi diferenciální metody. Okamžitě poznamenejme, že Courtois provádí svou analýzu pro S-boxy, které se liší od současných a od těch navržených v ISO. Práce poskytuje diferenciální charakteristiky (ta čísla, ve kterých by se bloky měly lišit) pro malý počet kol. Zdůvodnění pro rozšíření charakteristik na více kol je jako obvykle založeno na „faktech“. Courtois vyjadřuje opět ničím jiným než svou autoritou nepodložený předpoklad, že změna S-boxů neovlivní odolnost GOST 28147-89 proti jeho útoku (zatímco z neznámých důvodů S-boxy z 1. pracovního návrhu doplnění normy ISO/IEC 18033-3 nebylo zvažováno). Analýza provedená autory článku ukazuje, že i když vezmeme Courtoisova nepodložená „fakta“ o víře a analyzujeme GOST 28147-89 s jinými S-bloky, útok se opět ukáže být o nic lepší než úplné hledání.
V pracích byl proveden podrobný rozbor Courtoisových děl s podrobným zdůvodněním neopodstatněnosti všech tvrzení o poklesu odolnosti ruského standardu [,].
Absolutní nepřesnost ve výpočtech přitom přiznává i sám Courtois! Následující snímek je převzat z Courtoisovy prezentace na krátké sekci FSE 2012.
Je třeba poznamenat, že Courtoisova práce byla také opakovaně kritizována zahraničními badateli. Například jeho práce na konstrukci útoků na blokový šifrovací algoritmus AES pomocí metody XSL obsahovala stejné zásadní nedostatky jako práce na analýze ruského standardu: většina odhadů pracnosti se v textu objevuje zcela nepodložená a nepodložená - podrobné kritiku lze nalézt například v práci. Courtois sám navíc přiznává rozšířené odmítání publikovat svou práci na velkých kryptografických konferencích a v zavedených recenzovaných časopisech, takže mu často ponechává pouze příležitost promluvit v sekci krátkých oznámení. O tom se můžete dočíst například v části 3 této práce. Zde jsou některé citace od samotného Courtoise týkající se jeho práce:
- "Myslím, že diváci Asiacryptu nebudou mít pocit, že je to zajímavé." Recenzent Asiacrypt 2011.
- „…je tu velký, velký, velký problém: tento útok, který je hlavním příspěvkem článku, již vyšel na FSE’11 (byla to dokonce nejlepší práce), …“. Recenzent pro Crypto 2011.
Odborná část mezinárodní kryptografické komunity tak pohlíží na kvalitu Courtoisovy práce s nemenšími pochybnostmi, než jsou řekněme výroky některých ruských specialistů o jejich schopnosti prolomit AES za 2 100, které nejsou potvrzeny žádnými konzistentními výpočty, resp. nejnovější „důkaz“ dvoustránkové hypotézy o nerovnosti tříd složitosti P a NP.
Útoky Isobe a Dinur-Dankelman-Shamir
Obecnou myšlenkou útoků Isobe () a Dinur-Dankelman-Shamir (dále jen: útok DDS) () je vytvořit pro určitou (klíčově závislou) úzkou množinu otevřených textů ekvivalentní transformaci na této množině, která má struktura jednodušší než samotná transformace šifrování. V případě metody Isobe se jedná o množinu 64bitových bloků x tak, že F 8 -1 (Swap(F 8 (z))) = z, kde z = F 16 (x), až F 8 ( x) a F 16 ( x) označují prvních 8 a prvních 16 kol šifrování GOST 28147-89 prostřednictvím Swap - operace prohození polovin 64bajtového slova. Pokud je v této sadě zahrnut i prostý text, shoduje se výsledek úplné 32kolové transformace GOST 28147-89 s výsledkem 16kolové, čehož využívá autor útoku. V případě metody DDS je to množina x taková, že F 8 (x) = x (pevný bod transformace F 8). Pro jakýkoli prostý text z této sady funguje transformace GOST 28147-89 přesně stejně jako posledních 8 kol, což zjednodušuje analýzu.
Složitost útoku Isobe je 2 224 šifrovacích operací, útok DDS je 2 192. Všechny otázky, zda útoky Isobe a DDS zavádějí nová omezení podmínek pro použití našeho algoritmu, jsou však odstraněny posouzením požadavků na objem materiálu potřebného k provedení každého z útoků: metoda Isobe vyžaduje 2 32 párů prostého textu. a šifrový text a pro metodu DDS - 2 64. Zpracování takových objemů materiálu bez změny klíče je a priori nepřijatelné pro jakoukoli blokovou šifru s délkou bloku 64: na materiálu svazku 2 32 s přihlédnutím k problému narozenin (viz např. ), pravděpodobnost výskytu opakovaných bloků se blíží 1/2, což poskytne útočníkovi možnost vyvodit určité závěry o otevřených textech ze zašifrovaných textů bez určení klíče. Přítomnost 2 64 párů prostých a zašifrovaných textů získaných na jednom klíči ve skutečnosti umožňuje nepříteli provádět šifrovací a dešifrovací operace, aniž by tento klíč vůbec znal. To je způsobeno čistě kombinatorickou vlastností: nepřítel má v tomto případě celou tabulku převodu šifrování. Tato situace je za jakýchkoli rozumných provozních podmínek absolutně nepřijatelná. Například v CryptoPro CSP Existuje technické omezení objemu šifrovaného materiálu (bez konverze klíče) na 4 MB (viz). Přísný zákaz použití klíče na materiálu takového objemu je tedy vlastní jakékoli blokové šifře s délkou bloku 64 bitů, a proto útoky Isobe a DDS nijak nezužují rozsah použití algoritmu GOST 28147-89. při zachování maximální možné pevnosti 2 256.
Samozřejmě je třeba poznamenat, že výzkumníci (Isobe a Dinur-Dankelman-Shamir) prokázali, že některé vlastnosti algoritmu GOST 28147-89 umožňují najít cesty analýzy, které tvůrci algoritmu nezohlednili. Jednoduchá forma plánu klíčů, která výrazně zjednodušuje úkol konstrukce efektivních implementací, také umožňuje v některých vzácných případech klíčů a otevřených textů vytvořit více jednoduché popisy transformace prováděné algoritmem.
Práce ukazuje, že tuto negativní vlastnost algoritmu lze snadno eliminovat při plném zachování provozních charakteristik, ale bohužel je nedílnou součástí algoritmu v jeho běžně používané podobě.
Všimněte si, že určitá nedbalost v odhadech průměrné pracovní náročnosti je přítomna i v práci Dinura, Dunkelmana a Shamira. Při konstrukci útoku se tedy nevěnuje náležitá pozornost následujícímu bodu: pro významnou část klíčů je množina otevřených textů x, takže F 8 (x) = x, prázdná: nemusí tam být žádné pevné body na 8 kol transformace. Existence pevných bodů závisí také na volbě náhradních uzlů. Útok je tedy použitelný pouze pro určité náhradní uzly a klíče.
Za zmínku také stojí ještě jedna práce s útokem na GOST 28147-89. V únoru 2012 se objevil elektronický archiv ePrint mezinárodní kryptografické asociace aktualizovaná verzečlánek (z listopadu 2011), který obsahoval nový útok na GOST 28147-89. Charakteristiky prezentovaného útoku jsou následující: objem materiálu je 2 32 (jako Isobe) a pracnost 2 192 (jako DDS). Tento útok tedy vylepšil časově rekordní útok DDS z hlediska objemu materiálu z 2 64 na 2 32. Samostatně poznamenáváme, že autoři poctivě prezentovali všechny výpočty s odůvodněním složitosti a objemu materiálu. Po 9 měsících byla ve výše uvedených výpočtech zjištěna zásadní chyba a od listopadu 2012 již aktualizovaná verze článku v elektronickém archivu neobsahuje žádné výsledky týkající se domácího algoritmu.
Útoky za předpokladu, že útočník „něco“ o klíčích ví
Nakonec podotýkáme, že v literatuře existuje i řada prací (viz např. a ) věnovaných útokům na GOST 28147-89 v tzv. modelu propojeného klíče. Tento model v zásadě obsahuje předpoklad, že útočník může pro analýzu získat přístup nejen k párům otevřeného textu a zašifrovaného pomocí požadovaného klíče, ale také k párům otevřeného textu a šifrovaného textu získaného pomocí (také neznámých) klíčů, které se od hledaného liší ve známém běžném způsobem (například na pevných pozicích bitů). V tomto modelu je skutečně možné získat zajímavé výsledky o GOST 28147-89, nicméně v tomto modelu lze získat neméně silné výsledky například o tom, který je nejrozšířenější v moderních sítích běžné použití Standard AES (viz například). Všimněte si, že podmínky pro provedení tohoto typu útoku vznikají při použití šifry v určitém protokolu. Je třeba poznamenat, že výsledky tohoto druhu, přestože jsou z hlediska studia vlastností kryptografických transformací nepochybně akademické zajímavé, ve skutečnosti nejsou pro praxi relevantní. Například všechny nástroje ochrany kryptografických informací certifikované ruskou FSB splňují nejpřísnější požadavky na schémata generování šifrovacích klíčů (viz například). Jak je uvedeno ve výsledcích analýzy, pokud existuje 18 přidružených klíčů a 2 10 párů bloků otevřeného textu a šifrovaného textu, složitost úplného otevření soukromého klíče s pravděpodobností úspěchu 1-10-4 je ve skutečnosti 2 26 . Pokud jsou však splněny výše uvedené požadavky na vývoj klíčového materiálu, pravděpodobnost nalezení takových klíčů je 2 -4352, tedy 24096krát menší, než když se prostě pokusíte tajný klíč uhodnout na první pokus.
K dílům souvisejícím s modelem s propojenými klávesami patří i práce, které v roce 2010 způsobily mnoho hluku v ruských elektronických publikacích, které netrpí zvykem pečlivě kontrolovat materiál v závodě o senzace. Výsledky v něm uvedené nebyly podepřeny žádným rigorózním odůvodněním, obsahovaly však hlasitá prohlášení o možnosti hacknutí státní normy Ruská Federace na slabém notebooku během několika sekund - obecně byl článek napsán v nejlepších tradicích Nicolase Courtoise. Ale i přes naprosto zřejmou neopodstatněnost článku pro čtenáře, který je víceméně obeznámen se základními principy vědeckých publikací, právě pro uklidnění ruské veřejnosti po práci napsal Rudskij podrobný a důkladný text obsahující komplexní analýzu tohoto nedostatku. Článek se samovysvětlujícím názvem „O nulovém praktickém významu práce „Útok obnovy klíče na úplnou blokovou šifru GOST s nulovým časem a pamětí““ poskytuje odůvodnění, že průměrná složitost uvedené metody není menší než složitost. o kompletním hledání.
Suché zbytky: jaká je trvanlivost v praxi?
Na závěr uvádíme tabulku obsahující údaje o všech výsledcích přísně popsaných a oprávněných útoků na GOST 28147-89 známých mezinárodní kryptografické komunitě. Všimněte si, že složitost je dána šifrovacími operacemi algoritmu GOST 28147-89 a paměť a materiál jsou uvedeny v blocích algoritmu (64 bitů = 8 bajtů).
| Záchvat | Intenzita práce | Paměť | Požadovaný materiál |
| Isobe | 2 224 | 2 64 | 2 32 |
| Dinur-Dankelman-Shamir, FP, 2DMitM | 2 192 | 2 36 | 2 64 |
| Dinur-Dankelman-Shamir, FP, s nízkou pamětí | 2 204 | 2 19 | 2 64 |
| 2 224 | 2 36 | 2 32 | |
| Dinur-Dankelman-Shamir, Reflection, 2DMitM | 2 236 | 2 19 | 2 32 |
| Dokončete vyhledávání | 2 256 | 1 | 4 |
| Počet nanosekund od vzniku vesmíru | 2 89 |
Navzdory poměrně rozsáhlému cyklu výzkumu v oblasti stability algoritmu GOST 28147-89, tento moment Není znám jediný útok, který by byl dosažitelný za provozních požadavků 64bitové délky bloku. Omezení objemu materiálu, který lze zpracovat na jednom klíči, vyplývající z parametrů šifry (délka bitu klíče, délka bitu bloku) jsou výrazně přísnější než minimální objem potřebný k provedení jakéhokoli aktuálně známého útoku. V důsledku toho při splnění stávajících provozních požadavků žádná z dosud navržených metod kryptoanalýzy GOST 28147-89 neumožňuje určit klíč s pracností menší než vyčerpávající hledání.
