Šifrovací algoritmus GOST 28147-89. Jednoduchá metoda výměny. - Archiv WASM.RU

"Dokud žiješ, neumírej, podívej se na tento svět."
Mnoho lidí zde má mrtvou duši - jsou mrtví uvnitř.
Ale chodí a smějí se, aniž by věděli, že nejsou,
Nespěchejte svou hodinu smrti, “řekla mi.

Aria, „vysoko nahoře“

2.1 Feistel sítě.
2.2 Bloková šifra GOST 28147-89

3.1 Klíčová informace
3.2 Hlavní krok krypto transformace

3.3 Základní cykly:“ 32-Z” , “ 32-R” .

4.1 Implementace hlavního kroku krypto transformace
4.2 Zvýšení rychlosti algoritmu
5. Klíčové informační požadavky
6. Seznam použité literatury
7. Poděkování.

Úvod.

Tento dokument je mým pokusem popsat metodu prostého nahrazení šifrovacího algoritmu GOST 28147-89 nejjednodušším, ale přesto technicky kompetentním jazykem. Po přečtení prvních šesti bodů čtenář podá svůj názor na to, jak dobře jsem to udělal.

Aby moje práce měla větší užitek, doporučuji se vyzbrojit díly autorů uvedených v seznamu použité literatury. Doporučuje se také, aby kalkulačka měla funkci pro výpočet operace. XOR od té doby čtení článku předpokládá, že čtenář zamýšlel prostudovat tento šifrovací algoritmus. Sice je to vhodné i jako reference, ale tento článek jsem napsal přesně jako tréninkový.

Předběžné informace o blokových šiferch.

Než se začneme zabývat algoritmem, musíme se seznámit s historií vzniku tohoto druhu šifer. Algoritmus patří do kategorie blokových šifer, v jejichž architektuře jsou informace rozděleny do konečného počtu bloků, přičemž konečný přirozeně nemusí být úplný. Proces šifrování probíhá přes celé bloky, které tvoří šifru. Poslední blok, pokud je neúplný, je něčím doplněn (o nuancích jeho vyplnění řeknu níže) a je šifrován stejným způsobem jako plné bloky. Šifrou mám na mysli výsledek šifrovací funkce působící na určité množství dat, která uživatel k šifrování předložil. Jinými slovy, šifra je konečným výsledkem šifrování.

Historie vývoje blokových šifer je spojena se začátkem 70. let, kdy si IBM, uvědomující si potřebu chránit informace při přenosu dat prostřednictvím počítačových komunikačních kanálů, pustila do vlastního výzkumného programu věnovaného ochraně informací v elektronických sítích, včetně kryptografie.

Skupinu výzkumníků - vývojářů z IBM, která začala zkoumat šifrovací systémy se schématem využití symetrického klíče, vedl Dr. Horst Feistel.

2.1 Sítě Feistel

Architektura nové šifrovací metody, kterou Feistel navrhl v klasické literatuře, se nazývá „The Feistel Architecture“, ale v současné době se v ruské a zahraniční literatuře používá ustálenější termín - „Feistel's network“ nebo Feistel's NetWork. Následně byla na této architektuře postavena šifra „Lucifer“ - která byla později publikována a způsobila novou vlnu zájmu o kryptografii obecně.

Myšlenka architektury „sítě Feistel“ je následující: vstupní tok informací je rozdělen do bloků o velikosti n bitů, kde n je sudé číslo. Každý blok je rozdělen na dvě části-L a R, poté jsou tyto části přiváděny do iterační blokové šifry, ve které je výsledek j-tého stupně určen výsledkem předchozího stupně j-1! To lze ilustrovat na příkladu:

Rýže. 1

Kde funkce A je hlavní činností blokové šifry. Může to být jednoduchá akce, například operace XOR, nebo může mít složitější formu jako sled řady jednoduchých akcí - přidání modula, posun vlevo, nahrazení prvku atd. Dohromady tyto jednoduché akce tvoří takzvaný - hlavní krok krypto transformace.

Je třeba poznamenat, že klíčovými prvky fungování funkce jsou dodávka klíčových prvků a operace XOR, a jak promyšlená práce těchto operací vypovídá o kryptografické síle šifry jako celku.

Aby byla myšlenka sítí Feistel konečně jasná, zvažte nejjednodušší případ zobrazený v rýže. 1, kde ve funkci A - budou operace „mod 2“ („xor“), ale toto nejjednodušší v případě vážnější situace, například skrývající informace státního významu, může být funkce A složitější (pokud jsem viděl, funkce A je opravdu velmi složitá):

Počáteční údaje:

L = 1110b, R = 0101, K = 1111b

Získejte šifru

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

L = 0101b, R = 1010b

Vysvětlíme naše akce:

1. Tato operace je doplňkový režim 2 4. V praxi se taková operace redukuje na jednoduché sčítání, kdy musíme sčítat dvě čísla a ignorovat přenos na 5. číslici. Protože pokud dáme exponenty nad číslice binární reprezentace čísla, bude nad pátou číslicí exponent čtyři, podívejme se na obrázek níže, který ukazuje akce naší operace:

Rýže. 2

Zde jsem ukázal na exponenty šipkou, jak vidíte, výsledek měl být 10100, ale protože přenos je během operace mod 2 4 ignorován, dostaneme 0100.

2. Tato operace se v literatuře nazývá mod 2, v jazyce sestavení je implementována příkazem XOR... Správnější název je však mod 2 1. Bez této jedinečné operace je sotva možné vybudovat rychlý, snadno implementovatelný šifrovací algoritmus a zároveň tak, aby byl stále dostatečně kryptograficky silný. Jedinečnost této operace spočívá v tom, že je sama opakem! Pokud je například číslo A XORed s číslem B, v důsledku toho dostaneme B, v budoucnu stačí znovu XORovat čísla B a C mezi sebou, abychom získali předchozí hodnotu A!

V této operaci jsme dostali 1010 s čísly 1110 a 0100, abychom se vrátili 1110, stačí přeexponovat čísla 0100 a 1010! Další podrobnosti o této operaci najdete v článku, který je připojen k webu. www.wasm.ru, « Základní průvodceAlgoritmy detekce chyb CRC_»Autor, který Ross N. Williams... Tato práce má smysl - „ 5. Binární aritmetika bez dělení slov“. V tomto článku je popsána operace. xor! Volám, protože v tomto článku je tato operace tak naplánovaná, že čtenář nejenže rozumí, jak tato operace funguje, ale dokonce ji spouští. vidět, slyšet a cítit!

3. Tato akce je nezbytná k tomu, aby bylo možné počáteční hodnoty získat ze šifrování během dešifrování.

2.2 Bloková šifra GOST 28147-89

Šifrovací algoritmus GOST 28147 - 89 patří do kategorie blokových šifer pracujících podle architektury vyvážených sítí Feistel, kde dvě části vybraného bloku informací mají stejnou velikost. Algoritmus byl vyvinut v hlubinách osmého oddělení KGB, nyní transformován do FAPSI a byl zakotven jako šifrovací standard Ruské federace v roce 1989 pod SSSR.

Aby tato metoda algoritmu fungovala, je nutné rozdělit informace do bloků o velikosti 64 bitů. Vygenerujte nebo zadejte do šifrovacího systému následující klíčové informace: klíč a substituční tabulka. Výběr klíče a substituční tabulky pro šifrování by měl být brán velmi vážně, protože to je základ zabezpečení vašich informací. Informace o tom, jaké požadavky jsou na klíč kladeny, a tabulce náhrad, viz položka „Požadavky na klíčové informace“.

Při zvažování metody se na to nebudeme soustředit, protože tento článek, jak jsem řekl výše, byl napsán s cílem naučit čtenáře šifrovat data metodou jednoduché náhrady tohoto šifrovacího algoritmu, ale této záležitosti se určitě dotkneme na konci článku.

Teoretické minimum.

3.1 Klíčové informace

Jak jsem řekl výše, do šifrování dat se aktivně zapojují následující:

3.1.1. Klíč je posloupnost osmi prvků, každý 32 bitů. V následujícím textu budeme označovat symbolem K a prvky, z nichž se skládá, jsou k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Substituční tabulka - matice osmi řádků a šestnácti sloupců, dále - Hij. Každý prvek v průsečíku řádku i a sloupce j zabírá 4 bity.

3.2 Základní krok krypto transformace

Hlavním krokem v procesu šifrování je - hlavní krok krypto transformace. Nejde o nic jiného než o akci šifrování dat podle určitého algoritmu, pouze vývojáři zavedli název příliš těžkopádně.

Před zahájením šifrování je blok rozdělen na dvě části L a R, každá po 32 bitech. Je vybrán klíčový prvek a teprve poté jsou tyto dvě části bloku, klíčový prvek, substituční tabulka, zavedeny do funkce hlavního kroku, výsledkem hlavního kroku je jedna iterace základního cyklu, která bude diskutováno v následujícím odstavci. Hlavní krok se skládá z následujících:

1. Přidávací část bloku R je shrnuta s klíčovým prvkem K mod 2 32. Podobnou operaci jsem popsal výše, zde totéž, jen exponent není „4“, ale „32“ - výsledek této operace bude v budoucnu označován jako Smod.
2. Rozdělte dříve získaný výsledek Smod na čtyřbitové prvky s7, s6, s5, s4, s3, s2, s1, s0 a přiveďte jej k náhradní funkci. Nahrazení je následující: vybereme prvek Smod - si, začneme od začátku s nejnižším prvkem a nahradíme hodnotou z tabulky náhrad za i - řádek a sloupec, na které ukazuje hodnota prvku s já. Přejdeme k prvku s i +1 a postupujeme stejným způsobem a pokračujeme tak dlouho, dokud nezměníme hodnotu posledního prvku Smod - výsledek této operace bude označen jako, Ssimple.
3. V této operaci posuneme hodnotu Ssimple cyklicky doleva o 11 bitů a dostaneme Srol.
4. Vybereme druhou část bloku L a přidáme ji mod 2 pomocí Srol, nakonec máme Sxor.
5. V této fázi se část bloku L rovná hodnotě části R a část R je zase inicializována s výsledkem Sxor, a tím je funkce hlavního kroku dokončena!

3.3 Základní cykly: "32-З", "32-Р".

Aby bylo možné šifrovat informace, je nutné je rozdělit na bloky o velikosti 64 bitů, poslední blok může mít samozřejmě méně než 64 bitů. Tato skutečnost je Achillovou patou této metody „snadné výměny“. Protože jeho přidání do 64 bitů je velmi důležitým úkolem ke zvýšení kryptografické síly šifrovacího programu a na toto citlivé místo, pokud je přítomno v informačním poli, ale nemusí existovat (například soubor 512 bajtů! ), Jeden by měl zacházet s velkou zodpovědností!

Poté, co rozdělíte informace do bloků, měli byste klíč rozdělit na prvky:

K = k1, k2, k3, k4, k5, k6, k7, k8

Samotné šifrování spočívá ve využití takzvaných základních cyklů. Což zase zahrnuje n-tý počet základních kroků krypto-transformace.

Základní cykly jsou označeny, jak to vyjádřit: n - m. Kde n je počet základních kroků krypto transformace v základním cyklu a m je „typ“ základního cyklu, tj. o čem mluvíme, o šifrování „Z“ nebo „R“ šifrování dat.

Základní šifrovací cyklus 32-З se skládá ze 32 základních kroků krypto-transformace. Blok N a prvek klíče K jsou přiváděny do funkce, která implementuje akce kroku, a první krok nastává s k1, druhý nad výsledkem získaným s prvkem k2 atd. podle následujícího schématu:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

Proces dešifrování pro 32-P probíhá podobným způsobem, ale klíčové prvky jsou uvedeny v opačném pořadí:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Praxe.

4.1 Implementace hlavního kroku krypto transformace

Poté, co jsme se seznámili s teorií šifrování informací, bylo na čase se podívat, jak šifrování funguje v praxi.

Počáteční údaje:

Vezměte blok informací N = 010203040506060708h, zde jsou části L a R stejné:

L = 01020304h, R = 05060708h, vezměme klíč:

K = ‘ jako28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(jedná se o kódy ASCII, pro zobrazení hexadecimální reprezentace můžete tento soubor otevřít v režimu zobrazení v Total Commander stisknutím klávesy F3"A pak klíč" 3 "). V tomto klíči budou hodnoty prvků:

k1 = ‘as28’, k2 = ‘zw37‘, k3 = ‘q839’, k4 = ‘7342‘

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Vezměte si také následující substituční tabulku:

Rýže. 3

Zde jsou řádky očíslovány od 0 do 7, sloupce od 0 do F.

Varování: Všechny informace, včetně klíče se substituční tabulkou, jsou brány jako příklad pro zvážení algoritmu!

Pomocí „Počátečních dat“ je nutné získat výsledek akce hlavního kroku krypto transformace.

1. Vyberte část R = 05060708h a klíčový prvek k1 = 'as28', v hexadecimálním tvaru bude klíčový prvek vypadat takto: 61733238h. Nyní provedeme operaci součtu mod 2 32:

Rýže. 4

Jak vidíte na obrázku, neměli jsme přenos v 33 bitech označených červeně a s exponentem „ 32 “. A kdybychom měli jiné hodnoty pro R a klíčový prvek, mohlo by se to dobře stát, a pak bychom to ignorovali a dále používali pouze bity označené žlutě.

Tuto operaci provádím příkazem assembler přidat:

; eax = R, ebx = 'as28'

Výsledek této operace Smod = 66793940h

2. Nyní nejsložitější operace, ale pokud se na ni podíváte zblízka, už není tak strašidelná, jak se na první pohled zdá. Představme si Smod následovně:

Rýže. 5

Pokusil jsem se vizualizovat prvky Smodu na obrázku, ale stejně to vysvětlím:

s0 = 0, s1 = 4, s2 = 9 atd.

Nyní, počínaje od nejnižšího prvku s0, provedeme výměnu. Zapamatování odstavce „ 3.2 Základní krok krypto transformace»I - řádek, s i - sloupec, hledejte hodnotu v nulovém řádku a nulovém sloupci:

Obr

Aktuální hodnota Smodu tedy není 6679394 0 h, a 6679394 5 h.

Pokračujeme k nahrazení s1, tj. čtyři. Pomocí prvního řádku a čtvrtého sloupce (s1 = 4!). Podíváme se na obrázek:

Rýže. 7

Nyní již hodnota Smod, nikoli 667939 4 5h, 667939 2 5h. Předpokládám, že nyní je náhradní algoritmus čtenáři jasný, a mohu říci, že po konečném výsledku Ssimple bude mít následující hodnotu - 11e10325h.

O tom, jak je to nejsnazší implementovat formou příkazů assembleru, budu hovořit později v dalším odstavci poté, co mluvím o rozšířené tabulce.

1. Výslednou hodnotu Ssimple musíme posunout o 11 bitů doleva.

Rýže. osm

Jak vidíte, tato akce je poměrně jednoduchá a je implementována jedním příkazem jazyka sestavení - rol a výsledek této operace Srol je 0819288Fh.

4. Nyní bude část L našeho bloku informací XOROVÁNA s hodnotou Srol. Vezmu kalkulačku z w2k sp4 a dostanu Sxor = 091b2b8bh.

5. Tato akce je konečná a jednoduše přiřadíme, vyčistíme R, hodnotu části L a inicializujeme část L hodnotou Sxor.

Konečný výsledek:

L = 091b2b8bh, R = 01020304h

4.2 Zvýšení rychlosti algoritmu

Nyní pojďme mluvit o optimalizaci algoritmu pro rychlost. Při provádění projektu je třeba vzít v úvahu, že program, který pracuje s registry častěji než s pamětí, pracuje nejrychleji, a zde je tento úsudek také velmi důležitý, protože přes jeden blok informací až 32 šifrovacích akcí!

Když jsem do svého programu implementoval šifrovací algoritmus, provedl jsem následující:

1. Vybraná část bloku L do registru eax a R do edx.

2. V registru esi, inicializovaném adresou rozšířeného klíče, více o tom níže.

3. V registru ebx přiřazena hodnota adresy rozšířené tabulky substitucí, více o tom níže

4. Přenesly informace z položek 1, 2, 3 do funkce základního cyklu 32 - З nebo 32 - Р, v závislosti na situaci.

Pokud se podíváte na vývojový diagram klíčových prvků v odstavci " Základní cykly: „32-З“, „32-Р““, Pak náš klíč pro základní cyklus 32 - 3 lze znázornit následovně:

K 32-Z =

„As28“, „zw37“, „q839“, „7342“, „ui23“, „8e2t“, „wqm2“, „ewp1“,

„As28“, „zw37“, „q839“, „7342“, „ui23“, „8e2t“, „wqm2“, „ewp1“,

„Ewp1“, „wqm2“, „8e2t“, „ui23“, „7342“, „q839“, „zw37“, „as28“

Tito. od začátku je k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ‘,‘zw37 ‘,‘q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ‘,‘ewp1 ' tato sekvence se opakuje třikrát. Poté jdou prvky v opačném pořadí, tj.: K8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1“, „wqm2“, „8e2t“, „ui23“, „7342“, „q839“, „zw37“, „as28“.

Prvky v poli jsem uspořádal předem v pořadí, v jakém by měly být napájeny 32 - Z. Tím jsem zvýšil požadovanou paměť na klíč, ale zachránil jsem se před některými myšlenkovými procesy, které jsem nepotřeboval, a zvýšil rychlost algoritmu, protože zkrácením doby přístupu do paměti! Zde jsem popsal pouze klíč pro 32 - З, pro cyklus 32 - Р udělal jsem to samé, ale s použitím jiného schématu dodávání prvků, které jsem také popsal v odstavci „ Základní cykly: „32-Z“, „32-P».

Nyní je čas popsat implementaci náhradní funkce, jak jsem slíbil výše. Nemohl jsem to popsat dříve, protože to vyžaduje zavedení nového konceptu - rozšířené substituční tabulky. Nedokážu vám vysvětlit, co to je. Místo toho vám to ukážu a vy sami formulujete sami, co to je - rozšířená tabulka náhrad?

Abychom pochopili, co je to rozšířená substituční tabulka, potřebujeme například substituční tabulku, vezmu si tu, která je znázorněna na obr. 3.

Potřebovali jsme například nahradit číslo 66793940h. Představím to následovně:

Rýže. devět

Když vezmeme prvky s1, s0, tj. nejméně významný bajt, výsledek náhradní funkce bude 25 hodin! Po přečtení článku Andreje Vinokurova, který jsem citoval v odstavci „ Seznam použité literatury", Ve skutečnosti zjistíte, že když vezmete dva řádky, můžete získat pole, což vám umožní rychle najít náhradní prvky pomocí příkazu assembler xlat.Říká se, že to lze udělat jiným způsobem rychleji, ale Andrey Vinokurov strávil asi čtyři roky výzkumem rychlých algoritmů pro implementaci GOST! Nemyslím si, že byste měli znovu objevovat kolo, když už ho máte.

Takže o poli:

Vezměme první dva řádky nula a první, vytvořte pole 256 bajtů. Nyní pozorujeme jednu zvláštnost, že pokud je nutné transformovat 00h, pak bude výsledek 75h (na základě obr. 3) - tuto hodnotu vložíme do pole při offsetu 00h. Vezmeme hodnotu 01h, výsledek substituční funkce 79h, vložíme ji do pole při offsetu 01 atd. Až do 0FFh, což nám poskytne 0FCh, které vložíme do pole při offsetu 0FFh. Takže jsme dostali rozšířenou substituční tabulku pro první skupinu řádků: první a nulu. Ale stále existují tři skupiny: druhá stránka 2, stránka 3, třetí stránka 4, strana 5, čtvrtá stránka 6, strana 7. S těmito třemi skupinami jednáme stejně jako s první. Výsledkem je rozšířená substituční tabulka!

Nyní můžeme implementovat algoritmus, který provede výměnu. K tomu použijeme zdrojové kódy, které Andrei Vinokurov zveřejnil na své stránce, viz „ Bibliografie».

lea ebx, extended_table_simple

mov eax, [vložte číslo, které má být nahrazeno]

přidat ebx, 100h; skok na další dva uzly

sub ebx, 300 h; takže v budoucnu bude odliv ukazovat na tabulku

Nyní ještě jedna funkce, s předchozími akcemi jsme nejen vyměnili, ale také posunuli číslo o 8 bitů doleva! Musíme posunout číslo o další 3 bity doleva:

a získáme výsledek operace rol eax, 11!

K optimalizaci nemohu přidat nic víc, jediné, co mohu zdůraznit, je to, co jsem řekl výše - používejte registry častěji než přístup do paměti. Myslím, že tato slova jsou pouze pro začátečníky, zkušené a bez mých slov to dokonale chápou.

Požadavky na klíčové informace.

Jak je uvedeno v článku Andrey Vinokurova, klíč je vybrán podle dvou kritérií:

Kritériem pro rovnoměrné rozdělení bitů mezi hodnotami 1 a 0. Obvykle je kritériem pro rovnoměrně pravděpodobné rozdělení bitů Pearsonovo kritérium („chi-square“).

To znamená klíč, v zásadě může libovolné číslo. To znamená, že když se vytvoří další bit klíče, pravděpodobnost jeho inicializace o jednu nebo nulu je 50/50!

Vezměte prosím na vědomí, že klíč se skládá z osmi prvků, každý z 32 bitů, takže v klíči je 32 * 8 = 256 bitů a počet možných klíčů je 2 256! Nenapadá vás to?

Kritérium série.

Podíváme -li se na náš klíč, který jsem dal v odstavci " 4.1 Implementace hlavního kroku krypto transformace», Pak si všimnete, že platí následující zápis:

Rýže. deset

V jedné frázi by hodnota k 1 neměla být opakována ani v k 2, ani v žádném jiném prvku klíče.

To znamená, že klíč, který jsme vybrali jako úvahu šifrovacího algoritmu, je v souladu se dvěma výše uvedenými kritérii.

Nyní o výběru tabulky náhrad:

Nyní si promluvme o tom, jak vybrat správnou substituční tabulku. Hlavním požadavkem pro výběr náhradních tabulek je fenomén „neopakovatelnosti“ prvků, z nichž každý má velikost 4 bity. Jak jste viděli výše, každý řádek substituční tabulky se skládá z hodnot 0h, 1h, 2h, 3h,…, 0fh. Hlavním požadavkem tedy je, aby každý řádek obsahoval hodnoty 0h, 1h, 2h, ..., 0fh a každou takovou hodnotu v jedné kopii. Například sekvence:

1 2 3 4 5 6 7 8 9 A B C D E F

Tento požadavek plně splňuje, ale přesto! Nedoporučuje se vybrat tuto sekvenci jako řetězec. Protože pokud zadáte hodnotu na funkci funkce, která se na takový řetězec spoléhá, ​​získáte stejnou hodnotu na výstupu! Nevěříš mi? Jako substituční tabulku pak vezměte číslo 332DA43Fh a osm takových řádků. Proveďte operaci výměny a ujišťuji vás, že výstupem bude číslo 332DA43Fh! To je totéž, co jste předložili vstupu operace! A to není známka dobré formy šifrování, a byla?

To byl jeden požadavek, další kritérium říká, že - každý bit výstupního bloku musí být statisticky nezávislý na každém bitu vstupního bloku!

Jak to vypadá jednodušeji? A tady je příklad toho, jak jsme například vybrali z výše uvedeného čísla prvek s0 = 0Fh, 01111b. Pravděpodobnost, že nyní nahradíme první bit jednou nebo nulou, je 0,5! Pravděpodobnost nahrazení druhého, třetího a čtvrtého bitu, každý bit, zvažujeme samostatně, s jednotkami nebo nulami, je také 0, 5. Při výběru s1 = 0Eh je pravděpodobnost, že jsme nulový bit, a toto je „0“ , bude nahrazeno nulou nebo se také rovná - 0,5! Podle tohoto kritéria tedy neexistuje náhrada nulových bitů prvků s0, s1! Ano, můžete nahradit jedny, ale můžete také nahradit nuly.

K vyhodnocení tabulky podle tohoto kritéria můžete vytvořit tabulku korelačních koeficientů vypočítanou podle vzorce:

Pokud p = 1, pak je hodnota bitu j na výstupu rovna hodnotě bitu i na vstupu pro jakékoli kombinace bitů na vstupu;

Pokud p = -1, pak hodnota bitu j na výstupu je vždy inverzní ke vstupnímu bitu i;

Pokud p = 0, pak výstupní bit j se stejnou pravděpodobností nabývá hodnot 0 a 1 pro jakoukoli pevnou hodnotu vstupního bitu i.

Vezměme si jeden příklad řádku:

Pojďme to rozdělit na „komponenty“:

Vypočítáme jeden koeficient podle výše uvedeného vzorce. Aby bylo snazší pochopit, jak se to dělá, vysvětlím podrobněji:

Na vstupu vezmeme 0. bit 0. čísla (0) a 0. bit 0. čísla na výstupu (1) provedeme operaci 0 XOR 1 = 1.

Vezmeme 0. bit 1. čísla (1) na vstupu a 0. bit 1. čísla na výstupu (1) provedeme operaci 1 XOR 1 = 0.

Vezmeme 0. bit 2. čísla (0) na vstupu a 0. bit 2. čísla na výstupu (0) provedeme operaci 0 XOR 0 = 0.

Vezmeme 0. bit 3. čísla (1) na vstupu a 0. bit 3. čísla na výstupu (1) provedeme operaci 1 XOR 1 = 0.

Při postupném provádění operací XOR v takové posloupnosti spočítáme počet všech nenulových hodnot a dostaneme hodnotu 6. Proto P 00 = 1- (6/2 4-1) = 0,25. Ukázalo se tedy, že hodnota bitu 0 na výstupu se rovná hodnotě bitu 0 na vstupu ve 4 případech ze 16;

Tabulka konečných kurzů:

Jak je patrné z tabulky korelačních koeficientů, bit 3 na vstupu je invertován vzhledem k bitu 0 na výstupu ve 14 případech ze 16, což je 87,5%. To již není pro normální šifrovací systémy přijatelné. Uveďme si pro změnu další příklad:

Tabulka koeficientů bude následující (pro koho není líné přepočítat)

V této tabulce jsou věci ještě horší - bity 1 a 2 skupiny zůstávají beze změny! Cryptanalyst se má kde obrátit S přihlédnutím ke všem těmto požadavkům jednoduché vyhledávání („hlava na hlavě“) našlo permutační tabulky odpovídající uvedené teorii (dnes - 1276 kombinací) Zde jsou některé z nich:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Seznam použité literatury.

1. Článek Andreje Vinokurova:

Šifrovací algoritmus GOST 28147-89, jeho použití a implementace

pro počítače platformy Intel x86.

Existují také zdrojové kódy pro implementaci šifrovacího algoritmu.

1. Článek Horsta Feistela:

Kryptografie a počítačová bezpečnost.

(najdete na stejné adrese jako předchozí článek)

1. Ross N.Williams:

Základní průvodce algoritmy detekce chyb CRC

Publikováno na webu www.wasm.ru.

Poděkování.

Chtěl bych poděkovat všem návštěvníkům fóra www.wasm.ru. Zvláště bych ale chtěl poděkovat ChS, která je v současné době známá jako SteelRat, pomohl mi porozumět věcem, kterým bych pravděpodobně nikdy nerozuměl, a také mi pomohl při psaní odstavce: „ Klíčové informační požadavky“Hlavní část tohoto odstavce napsal on. Jsem také hluboce vděčný zaměstnanci KSTU pojmenovaného po A.N. Tupolev Anikin Igor Vyacheslavovich a byl by hřích nezmínit Chris Kaspersky za to, že je a Volodya / wasm.ru za jeho pokyny. A mám to od něj. Chtěl bych také poznamenat Sega-Zero / Callipso, ale to mi přineslo do mysli matematickou džungli.

To je snad vše, co bych vám chtěl říci.

Byl bych vděčný za jakoukoli kritiku nebo otázky související s tímto článkem nebo jen rady. Moje kontaktní údaje: [chráněno emailem], ICQ - 337310594.

S pozdravem Evil's Interrupt.

P.S .: Tímto článkem jsem se nesnažil nikoho překonat. Byl napsán s úmyslem usnadnit studium GOST, a pokud máte potíže, neznamená to, že jsem za to vinen. Buďte rozumní a mějte trpělivost, všechno nejlepší!

"Dokud žiješ, neumírej, podívej se na tento svět."
Mnoho lidí zde má mrtvou duši - jsou mrtví uvnitř.
Ale chodí a smějí se, aniž by věděli, že nejsou,
Nespěchejte svou hodinu smrti, “řekla mi.

Aria, „vysoko nahoře“

1. Úvod

1. Předběžné informace o blokových šiferch

2.1 Feistel sítě.
2.2 Bloková šifra GOST 28147-89

1. Teoretické minimum

3.1 Klíčová informace
3.2 Hlavní krok krypto transformace

3.3 Základní cykly:“ 32-Z” , “ 32-R” .

1. Praxe

4.1 Implementace hlavního kroku krypto transformace
4.2 Zvýšení rychlosti algoritmu
5.
6. Seznam použité literatury
7. Poděkování.

Úvod.

Tento dokument je mým pokusem popsat metodu prostého nahrazení šifrovacího algoritmu GOST 28147-89 nejjednodušším, ale přesto technicky kompetentním jazykem. Po přečtení prvních šesti bodů čtenář podá svůj názor na to, jak dobře jsem to udělal.

Aby moje práce měla větší užitek, doporučuji se vyzbrojit díly autorů uvedených v seznamu použité literatury. Doporučuje se také, aby kalkulačka měla funkci pro výpočet operace. XOR od té doby čtení článku předpokládá, že čtenář zamýšlel prostudovat tento šifrovací algoritmus. Sice je to vhodné i jako reference, ale tento článek jsem napsal přesně jako tréninkový.

Předběžné informace o blokových šiferch.

Než se začneme zabývat algoritmem, musíme se seznámit s historií vzniku tohoto druhu šifer. Algoritmus patří do kategorie blokových šifer, v jejichž architektuře jsou informace rozděleny do konečného počtu bloků, přičemž konečný přirozeně nemusí být úplný. Proces šifrování probíhá přes celé bloky, které tvoří šifru. Poslední blok, pokud je neúplný, je něčím doplněn (o nuancích jeho vyplnění řeknu níže) a je šifrován stejným způsobem jako plné bloky. Šifrou mám na mysli výsledek šifrovací funkce působící na určité množství dat, která uživatel k šifrování předložil. Jinými slovy, šifra je konečným výsledkem šifrování.

Historie vývoje blokových šifer je spojena se začátkem 70. let, kdy si IBM, uvědomující si potřebu chránit informace při přenosu dat prostřednictvím počítačových komunikačních kanálů, pustila do vlastního výzkumného programu věnovaného ochraně informací v elektronických sítích, včetně kryptografie.

Skupinu výzkumníků - vývojářů z IBM, která začala zkoumat šifrovací systémy se schématem využití symetrického klíče, vedl Dr. Horst Feistel.

2.1 Sítě Feistel

Architektura nové šifrovací metody, kterou Feistel navrhl v klasické literatuře, se nazývá „Feistel Architecture“, ale v současné době se v ruské a zahraniční literatuře používá ustálenější termín - „Feistel's network“ nebo Feistel's NetWork. Následně byla na této architektuře postavena šifra „Lucifer“ - která byla později publikována a způsobila novou vlnu zájmu o kryptografii obecně.

Myšlenka architektury „sítě Feistel“ je následující: vstupní tok informací je rozdělen do bloků o velikosti n bitů, kde n je sudé číslo. Každý blok je rozdělen na dvě části-L a R, poté jsou tyto části přiváděny do iterační blokové šifry, ve které je výsledek j-tého stupně určen výsledkem předchozího stupně j-1! To lze ilustrovat na příkladu:

Rýže. 1

Kde funkce A je hlavní činností blokové šifry. Může to být jednoduchá akce, například operace XOR, nebo může mít složitější formu jako sled řady jednoduchých akcí - přidání modula, posun vlevo, nahrazení prvku atd. Dohromady tyto jednoduché akce tvoří takzvaný - hlavní krok krypto transformace.

Je třeba poznamenat, že klíčovými prvky fungování funkce jsou dodávka klíčových prvků a operace XOR, a jak promyšlená práce těchto operací vypovídá o kryptografické síle šifry jako celku.

Aby byla myšlenka sítí Feistel konečně jasná, zvažte nejjednodušší případ zobrazený v rýže. 1, kde ve funkci A - budou operace „mod 2“ („xor“), ale toto nejjednodušší v případě vážnější situace, například skrývající informace státního významu, může být funkce A složitější (pokud jsem viděl, funkce A je opravdu velmi složitá):

Počáteční údaje:

L = 1110b, R = 0101, K = 1111b

Získejte šifru

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Vysvětlíme naše akce:

1. Tato operace je přidáním režimu 2 4. V praxi se taková operace redukuje na jednoduché sčítání, kdy musíme sčítat dvě čísla a ignorovat přenos na 5. číslici. Protože pokud dáme exponenty nad číslice binární reprezentace čísla, bude nad pátou číslicí exponent čtyři, podívejme se na obrázek níže, který ukazuje akce naší operace:

Rýže. 2

Zde jsem ukázal na exponenty šipkou, jak vidíte, výsledek měl být 10100, ale protože přenos je během operace mod 2 4 ignorován, dostaneme 0100.

1. Tato operace se v literatuře nazývá mod 2, v jazyce sestavení je implementována příkazem XOR... Správnější název je však mod 2 1. Bez této jedinečné operace je sotva možné vybudovat rychlý, snadno implementovatelný šifrovací algoritmus a zároveň tak, aby byl stále dostatečně kryptograficky silný. Jedinečnost této operace spočívá v tom, že je sama opakem! Pokud je například číslo A XORed s číslem B, v důsledku toho dostaneme B, v budoucnu stačí znovu XORovat čísla B a C mezi sebou, abychom získali předchozí hodnotu A!

V této operaci jsme dostali 1010 s čísly 1110 a 0100, abychom se vrátili 1110, stačí přeexponovat čísla 0100 a 1010! Další podrobnosti o této operaci najdete v článku, který je připojen k webu. www.wasm.ru, « Základní průvodceAlgoritmy detekce chyb CRC_»Autor, který Ross N. Williams... Tato práce má smysl - „ 5. Binární aritmetika bez dělení slov“. V tomto článku je popsána operace. xor! Volám, protože v tomto článku je tato operace tak naplánovaná, že čtenář nejenže rozumí, jak tato operace funguje, ale dokonce ji spouští. vidět, slyšet a cítit!

1. Tato akce je nezbytná k tomu, aby během dešifrování bylo možné získat počáteční hodnoty ze šifry.

2.2 Bloková šifra GOST 28147-89

Šifrovací algoritmus GOST 28147 - 89 patří do kategorie blokových šifer pracujících podle architektury vyvážených sítí Feistel, kde dvě části vybraného bloku informací mají stejnou velikost. Algoritmus byl vyvinut v hlubinách osmého oddělení KGB, nyní transformován do FAPSI a byl zakotven jako šifrovací standard Ruské federace v roce 1989 pod SSSR.

Aby tato metoda algoritmu fungovala, je nutné rozdělit informace do bloků o velikosti 64 bitů. Vygenerujte nebo zadejte do šifrovacího systému následující klíčové informace: klíč a substituční tabulka. Výběr klíče a substituční tabulky pro šifrování by měl být brán velmi vážně, protože to je základ zabezpečení vašich informací. Informace o tom, jaké požadavky jsou na klíč kladeny, a tabulce náhrad, viz položka „Požadavky na klíčové informace“.

Při zvažování metody se na to nebudeme soustředit, protože tento článek, jak jsem řekl výše, byl napsán s cílem naučit čtenáře šifrovat data metodou jednoduché náhrady tohoto šifrovacího algoritmu, ale této záležitosti se určitě dotkneme na konci článku.

Teoretické minimum.

3.1 Klíčové informace

Jak jsem řekl výše, do šifrování dat se aktivně zapojují následující:

3.1.1. Klíč je posloupnost osmi prvků, každý 32 bitů. V následujícím textu budeme označovat symbolem K a prvky, z nichž se skládá, jsou k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Substituční tabulka - matice osmi řádků a šestnácti sloupců, dále - Hij. Každý prvek v průsečíku řádku i a sloupce j zabírá 4 bity.

Hlavním krokem v procesu šifrování je - hlavní krok krypto transformace. Nejde o nic jiného než o akci šifrování dat podle určitého algoritmu, pouze vývojáři zavedli název příliš těžkopádný :).

Před zahájením šifrování je blok rozdělen na dvě části L a R, každá po 32 bitech. Je vybrán klíčový prvek a teprve poté jsou tyto dvě části bloku, klíčový prvek, substituční tabulka, zavedeny do funkce hlavního kroku, výsledkem hlavního kroku je jedna iterace základního cyklu, která bude diskutováno v následujícím odstavci. Hlavní krok se skládá z následujících:

1. Přidávací část bloku R je shrnuta s klíčovým prvkem K mod 2 32. Podobnou operaci jsem popsal výše, zde totéž, jen exponent není „4“, ale „32“ - výsledek této operace bude v budoucnu označován jako Smod.
2. Rozdělte dříve získaný výsledek Smod na čtyřbitové prvky s7, s6, s5, s4, s3, s2, s1, s0 a přiveďte jej k náhradní funkci. Nahrazení je následující: vybereme prvek Smod - si, začneme od začátku s nejnižším prvkem a nahradíme hodnotou z tabulky náhrad za i - řádek a sloupec, na které ukazuje hodnota prvku s já. Přejdeme k prvku s i +1 a postupujeme stejným způsobem a pokračujeme tak dlouho, dokud nezměníme hodnotu posledního prvku Smod - výsledek této operace bude označen jako, Ssimple.
3. V této operaci posuneme hodnotu Ssimple cyklicky doleva o 11 bitů a dostaneme Srol.
4. Vybereme druhou část bloku L a přidáme ji mod 2 pomocí Srol, nakonec máme Sxor.
5. V této fázi se část bloku L rovná hodnotě části R a část R se zase inicializuje s výsledkem Sxor, a tím je funkce hlavního kroku dokončena!

3.3 Základní cykly: "32-З", "32-Р".

Aby bylo možné šifrovat informace, je nutné je rozdělit na bloky o velikosti 64 bitů, poslední blok může mít samozřejmě méně než 64 bitů. Tato skutečnost je Achillovou patou této metody „snadné výměny“. Protože jeho přidání do 64 bitů je velmi důležitým úkolem ke zvýšení kryptografické síly šifrovacího programu a na toto citlivé místo, pokud je přítomno v informačním poli, ale nemusí existovat (například soubor 512 bajtů! ), Jeden by měl zacházet s velkou zodpovědností!

Poté, co rozdělíte informace do bloků, měli byste klíč rozdělit na prvky:

K = k1, k2, k3, k4, k5, k6, k7, k8

Samotné šifrování spočívá ve využití takzvaných základních cyklů. Což zase zahrnuje n-tý počet základních kroků krypto-transformace.

Základní cykly jsou označeny, jak to vyjádřit: n - m. Kde n je počet základních kroků krypto transformace v základním cyklu a m je „typ“ základního cyklu, tj. o čem mluvíme, o šifrování „Z“ nebo „R“ šifrování dat.

Základní šifrovací cyklus 32-З se skládá ze 32 základních kroků krypto-transformace. Blok N a prvek klíče K jsou přiváděny do funkce, která implementuje akce kroku, a první krok nastává s k1, druhý nad výsledkem získaným s prvkem k2 atd. podle následujícího schématu:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

Proces dešifrování pro 32-P probíhá podobným způsobem, ale klíčové prvky jsou uvedeny v opačném pořadí:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Praxe.

Poté, co jsme se seznámili s teorií šifrování informací, bylo na čase se podívat, jak šifrování funguje v praxi.

Počáteční údaje:

Vezměte blok informací N = 010203040506060708h, zde jsou části L a R stejné:

L = 01020304h, R = 05060708h, vezměme klíč:

K = ‘ jako28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(jedná se o kódy ASCII, pro zobrazení hexadecimální reprezentace můžete tento soubor otevřít v režimu zobrazení v Total Commander stisknutím klávesy F3"A pak klíč" 3 "). V tomto klíči budou hodnoty prvků:

k1 = ‘as28’, k2 = ‘zw37‘, k3 = ‘q839’, k4 = ‘7342‘

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Vezměte si také následující substituční tabulku:

Rýže. 3

Zde jsou řádky očíslovány od 0 do 7, sloupce od 0 do F.

Varování: Všechny informace, včetně klíče se substituční tabulkou, jsou brány jako příklad pro zvážení algoritmu!

Pomocí „Počátečních dat“ je nutné získat výsledek akce hlavního kroku krypto transformace.

1. Vybereme část R = 05060708h a klíčový prvek k1 = ‘as28’, v hexadecimálním tvaru bude klíčový prvek vypadat takto: 61733238h. Nyní provedeme operaci součtu mod 2 32:

Rýže. 4

Jak vidíte na obrázku, neměli jsme přenos v 33 bitech označených červeně a s exponentem „ 32 “. A kdybychom měli jiné hodnoty pro R a klíčový prvek, mohlo by se to dobře stát, a pak bychom to ignorovali a dále používali pouze bity označené žlutě.

Tuto operaci provádím příkazem assembler přidat:

; eax = R, ebx = 'as28'

Výsledek této operace Smod = 66793940h

1. Nyní nejsložitější operace, ale pokud se podíváte pozorně, už to není tak hrozné, jak se na první pohled zdá. Představme si Smod následovně:

OBRÁZEK ​​NENÍ ULOŽEN

Rýže. 5

Pokusil jsem se vizualizovat prvky Smodu na obrázku, ale stejně to vysvětlím:

s0 = 0, s1 = 4, s2 = 9 atd.

Nyní, počínaje od nejnižšího prvku s0, provedeme výměnu. Zapamatování odstavce „ 3.2 Základní krok krypto transformace»I - řádek, s i - sloupec, hledejte hodnotu v nulovém řádku a nulovém sloupci:

Obr

Aktuální hodnota Smodu tedy není 6679394 0 h, a 6679394 5 h.

Pokračujeme k nahrazení s1, tj. čtyři. Pomocí prvního řádku a čtvrtého sloupce (s1 = 4!). Podíváme se na obrázek:

Rýže. 7

Nyní již hodnota Smod, nikoli 667939 4 5h, 667939 2 5h. Předpokládám, že nyní je náhradní algoritmus čtenáři jasný, a mohu říci, že po konečném výsledku Ssimple bude mít následující hodnotu - 11e10325h.

O tom, jak je to nejsnazší implementovat formou příkazů assembleru, budu hovořit později v dalším odstavci poté, co mluvím o rozšířené tabulce.

1. Výslednou hodnotu Ssimple musíme posunout o 11 bitů doleva.

Rýže. osm

Jak vidíte, tato akce je poměrně jednoduchá a je implementována jedním příkazem jazyka sestavení - rol a výsledek této operace Srol je 0819288Fh.

1. Nyní zůstává část L našeho bloku informací, která má být XORována s hodnotou Srol. Vezmu kalkulačku z w2k sp4 a dostanu Sxor = 091b2b8bh.
2. Tato akce je konečná a jednoduše přiřadíme, vyčistíme R, hodnotu části L a inicializujeme část L hodnotou Sxor.

Konečný výsledek:

L = 091b2b8bh, R = 01020304h

4.2 Zvýšení rychlosti algoritmu

Nyní pojďme mluvit o optimalizaci algoritmu pro rychlost. Při provádění projektu je třeba vzít v úvahu, že program, který pracuje s registry častěji než s pamětí, pracuje nejrychleji, a zde je tento úsudek také velmi důležitý, protože přes jeden blok informací až 32 šifrovacích akcí!

Když jsem do svého programu implementoval šifrovací algoritmus, provedl jsem následující:

1. Vybraná část bloku L do registru eax a R do edx.
2. V registru esi byla inicializována s adresou rozšířeného klíče, více o tom níže.
3. V registru ebx přiřazena hodnota adresy rozšířené tabulky substitucí, více o tom níže
4. Přenesly informace o položkách 1, 2, 3 do funkce základního cyklu 32 - З nebo 32 - Р, v závislosti na situaci.

Pokud se podíváte na vývojový diagram klíčových prvků v odstavci " Základní cykly: „32-З“, „32-Р““, Pak náš klíč pro základní cyklus 32 - 3 lze znázornit následovně:

K 32-Z =

„As28“, „zw37“, „q839“, „7342“, „ui23“, „8e2t“, „wqm2“, „ewp1“,

„As28“, „zw37“, „q839“, „7342“, „ui23“, „8e2t“, „wqm2“, „ewp1“,

„Ewp1“, „wqm2“, „8e2t“, „ui23“, „7342“, „q839“, „zw37“, „as28“

Tito. od začátku je k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ‘,‘zw37 ‘,‘q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ‘,‘ewp1 ' tato sekvence se opakuje třikrát. Poté jdou prvky v opačném pořadí, tj.: K8, k7, k6, k5, k4, k3, k2, k1 - „Ewp1“, „wqm2“, „8e2t“, „ui23“, „7342“, „q839“, „zw37“, „as28“.

Prvky v poli jsem uspořádal předem v pořadí, v jakém by měly být napájeny 32 - Z. Tím jsem zvýšil požadovanou paměť na klíč, ale zachránil jsem se před některými myšlenkovými procesy, které jsem nepotřeboval, a zvýšil rychlost algoritmu, protože zkrácením doby přístupu do paměti! Zde jsem popsal pouze klíč pro 32 - З, pro cyklus 32 - Р udělal jsem to samé, ale s použitím jiného schématu dodávání prvků, které jsem také popsal v odstavci „ Základní cykly: „32-Z“, „32-P».

Nyní je čas popsat implementaci náhradní funkce, jak jsem slíbil výše. Nemohl jsem to popsat dříve, protože to vyžaduje zavedení nového konceptu - rozšířené substituční tabulky. Nedokážu vám vysvětlit, co to je. Místo toho vám to ukážu a vy sami formulujete sami, co to je - rozšířená tabulka náhrad?

Abychom pochopili, co je to rozšířená substituční tabulka, potřebujeme například substituční tabulku, vezmu si tu, která je znázorněna na obr. 3.

Potřebovali jsme například nahradit číslo 66793940h. Představím to následovně:

OBRÁZEK ​​NENÍ ULOŽEN

Rýže. devět

Když vezmeme prvky s1, s0, tj. nejméně významný bajt, výsledek náhradní funkce bude 25 hodin! Po přečtení článku Andreje Vinokurova, který jsem citoval v odstavci „ Seznam použité literatury", Ve skutečnosti zjistíte, že když vezmete dva řádky, můžete získat pole, což vám umožní rychle najít náhradní prvky pomocí příkazu assembler xlat.Říká se, že to lze udělat jiným způsobem rychleji, ale Andrey Vinokurov strávil asi čtyři roky výzkumem rychlých algoritmů pro implementaci GOST! Nemyslím si, že byste měli znovu objevovat kolo, když už ho máte.

Takže o poli:

Vezměme první dva řádky nula a první, vytvořte pole 256 bajtů. Nyní pozorujeme jednu zvláštnost, že pokud je nutné transformovat 00h, pak bude výsledek 75h (na základě obr. 3) - tuto hodnotu vložíme do pole při offsetu 00h. Vezmeme hodnotu 01h, výsledek substituční funkce 79h, vložíme ji do pole při offsetu 01 atd. Až do 0FFh, což nám poskytne 0FCh, které vložíme do pole při offsetu 0FFh. Takže jsme dostali rozšířenou substituční tabulku pro první skupinu řádků: první a nulu. Ale stále existují tři skupiny: druhá stránka 2, stránka 3, třetí stránka 4, strana 5, čtvrtá stránka 6, strana 7. S těmito třemi skupinami jednáme stejně jako s první. Výsledkem je rozšířená substituční tabulka!

Nyní můžeme implementovat algoritmus, který provede výměnu. K tomu použijeme zdrojové kódy, které Andrei Vinokurov zveřejnil na své stránce, viz „ Bibliografie».

lea ebx, extended_table_simple

mov eax, [vložte číslo, které má být nahrazeno]

přidat ebx, 100h; skok na další dva uzly

sub ebx, 300 h; takže v budoucnu bude odliv ukazovat na tabulku

Nyní ještě jedna funkce, s předchozími akcemi jsme nejen vyměnili, ale také posunuli číslo o 8 bitů doleva! Musíme posunout číslo o další 3 bity doleva:

a získáme výsledek operace rol eax, 11!

K optimalizaci nemohu přidat nic víc, jediné, co mohu zdůraznit, je to, co jsem řekl výše - používejte registry častěji než přístup do paměti. Myslím, že tato slova jsou pouze pro začátečníky, zkušené a bez mých slov to dokonale chápou :).

Požadavky na klíčové informace.

Jak je uvedeno v článku Andrey Vinokurova, klíč je vybrán podle dvou kritérií:

- kritérium pro rovnoměrné rozdělení bitů mezi hodnotami 1 a 0. Obvykle se jako kritérium pro rovnoměrné rozdělení bitů používá Pearsonovo kritérium („chi-square“).

To znamená klíč, v zásadě může libovolné číslo. To znamená, že když se vytvoří další bit klíče, pravděpodobnost jeho inicializace o jednu nebo nulu je 50/50!

Vezměte prosím na vědomí, že klíč se skládá z osmi prvků, každý z 32 bitů, takže v klíči je 32 * 8 = 256 bitů a počet možných klíčů je 2 256! Nenapadá vás to? 🙂

- kritérium série.

Podíváme -li se na náš klíč, který jsem dal v odstavci " 4.1 Implementace hlavního kroku krypto transformace», Pak si všimnete, že platí následující zápis:

Rýže. deset

V jedné frázi by hodnota k 1 neměla být opakována ani v k 2, ani v žádném jiném prvku klíče.

To znamená, že klíč, který jsme vybrali jako úvahu šifrovacího algoritmu, je v souladu se dvěma výše uvedenými kritérii.

Nyní o výběru tabulky náhrad:

Nyní si promluvme o tom, jak vybrat správnou substituční tabulku. Hlavním požadavkem pro výběr náhradních tabulek je fenomén „neopakovatelnosti“ prvků, z nichž každý má velikost 4 bity. Jak jste viděli výše, každý řádek substituční tabulky se skládá z hodnot 0h, 1h, 2h, 3h,…, 0fh. Hlavním požadavkem tedy je, aby každý řádek obsahoval hodnoty 0h, 1h, 2h, ..., 0fh a každou takovou hodnotu v jedné kopii. Například sekvence:

1 2 3 4 5 6 7 8 9 A B C D E F

Tento požadavek plně splňuje, ale přesto! Nedoporučuje se vybrat tuto sekvenci jako řetězec. Protože pokud zadáte hodnotu na funkci funkce, která se na takový řetězec spoléhá, ​​získáte stejnou hodnotu na výstupu! Nevěříš mi? Jako substituční tabulku pak vezměte číslo 332DA43Fh a osm takových řádků. Proveďte operaci výměny a ujišťuji vás, že výstupem bude číslo 332DA43Fh! To je totéž, co jste předložili vstupu operace! A to není známka dobré formy šifrování, a byla? 🙂

To byl jeden požadavek, další kritérium říká, že - každý bit výstupního bloku musí být statisticky nezávislý na každém bitu vstupního bloku!

Jak to vypadá jednodušeji? A tady je příklad toho, jak jsme například vybrali z výše uvedeného čísla prvek s0 = 0Fh, 01111b. Pravděpodobnost, že nyní nahradíme první bit jednou nebo nulou, je 0,5! Pravděpodobnost nahrazení druhého, třetího a čtvrtého bitu, každý bit, zvažujeme samostatně, s jednotkami nebo nulami, je také 0, 5. Při výběru s1 = 0Eh je pravděpodobnost, že jsme nulový bit, a toto je „0“ , bude nahrazeno nulou nebo se také rovná - 0,5! Podle tohoto kritéria tedy neexistuje náhrada nulových bitů prvků s0, s1! Ano, můžete nahradit jedny, ale můžete také nahradit nuly. 🙂

K vyhodnocení tabulky podle tohoto kritéria můžete vytvořit tabulku korelačních koeficientů vypočítanou podle vzorce:

- pokud p = 1, pak je hodnota bitu j na výstupu rovna hodnotě bitu i na vstupu pro jakékoli kombinace bitů na vstupu;

- pokud p = -1, pak hodnota bitu j na výstupu je vždy inverzní ke vstupnímu bitu i;

- pokud p = 0, pak výstupní bit j se stejnou pravděpodobností nabývá hodnot 0 a 1 pro jakoukoli pevnou hodnotu vstupního bitu i.

Vezměme si jeden příklad řádku:

D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Pojďme to rozdělit na „komponenty“:

Vypočítáme jeden koeficient podle výše uvedeného vzorce. Aby bylo snazší pochopit, jak se to dělá, vysvětlím podrobněji:

- vezmeme 0. bit 0. čísla (0) na vstupu a 0. bit 0. čísla na výstupu (1) provedeme operaci 0 XOR 1 = 1.

- vezmeme 0. bit 1. čísla (1) na vstupu a 0. bit 1. čísla na výstupu (1) provedeme operaci 1 XOR 1 = 0.

- vezmeme 0. bit 2. čísla (0) na vstupu a 0. bit 2. čísla na výstupu (0) provedeme operaci 0 XOR 0 = 0.

- vezmeme 0. bit 3. čísla (1) na vstupu a 0. bit 3. čísla na výstupu (1) provedeme operaci 1 XOR 1 = 0.

Při postupném provádění operací XOR v takové posloupnosti spočítáme počet všech nenulových hodnot a dostaneme hodnotu 6. Proto P 00 = 1- (6/2 4-1) = 0,25. Ukázalo se tedy, že hodnota bitu 0 na výstupu se rovná hodnotě bitu 0 na vstupu ve 4 případech ze 16;

Tabulka konečných kurzů:

Tabulka koeficientů bude následující (pro koho není líné přepočítat)

	vchod
Výstup		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

V této tabulce jsou věci ještě horší - bity 1 a 2 skupiny zůstávají beze změny! Kryptanalytik se má kam obrátit 🙂 S přihlédnutím ke všem těmto požadavkům, jednoduchým vyhledáním („hlava na hlavě“) byly nalezeny permutační tabulky odpovídající uvedené teorii (dnes - 1276 kombinací) Zde jsou některé z nich:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Seznam použité literatury.

1. Článek Andreje Vinokurova:

Šifrovací algoritmus GOST 28147-89, jeho použití a implementace

pro počítače platformy Intel x86.

(najdete na: http://www.enlight.ru/crypto/frame.htm).

Existují také zdrojové kódy pro implementaci šifrovacího algoritmu.

1. Článek Horsta Feistela:

Kryptografie a počítačová bezpečnost.

(najdete na stejné adrese jako předchozí článek)

1. Ross N.Williams:

Základní průvodce algoritmy detekce chyb CRC

Publikováno na webu www.wasm.ru.

Poděkování.

Chtěl bych poděkovat všem návštěvníkům fóra www.wasm.ru. Zvláště bych ale chtěl poděkovat ChS, která je v současné době známá jako SteelRat, pomohl mi porozumět věcem, kterým bych pravděpodobně nikdy nerozuměl, a také mi pomohl při psaní odstavce: „ Klíčové informační požadavky“Hlavní část tohoto odstavce napsal on. Jsem také hluboce vděčný zaměstnanci KSTU pojmenovaného po A.N. Tupolev Anikin Igor Vyacheslavovich a byl by hřích nezmínit Chris Kaspersky za to, že je a Volodya / wasm.ru za jeho pokyny. A mám to od něj :). Chtěl bych také poznamenat Sega-Zero / Callipso, ale to mi přineslo do mysli matematickou džungli.

To je snad vše, co bych vám chtěl říci.

Byl bych vděčný za jakoukoli kritiku nebo otázky související s tímto článkem nebo jen rady. Moje kontaktní údaje: [chráněno emailem], ICQ - 337310594.

S pozdravem Evil's Interrupt.

P.S .: Tímto článkem jsem se nesnažil nikoho překonat. Byl napsán s úmyslem usnadnit studium GOST, a pokud máte potíže, neznamená to, že jsem za to vinen. Buďte rozumní a mějte trpělivost, všechno nejlepší!

Tento algoritmus je povinný pro použití jako šifrovací algoritmus ve vládních organizacích Ruské federace a v řadě komerčních.

Popis algoritmu

Algoritmický diagram je znázorněn na obr. 3.1. Jak vidíte, schéma tohoto algoritmu je poměrně jednoduché, což jednoznačně zjednodušuje jeho implementaci softwaru nebo hardwaru.

Algoritmus GOST 28147-89 šifruje informace v blocích po 64 bitech, které jsou rozděleny do dvou dílčích bloků po 32 bitech (N1 a N2). Subblock N1 je zpracován určitým způsobem, po kterém je přidána jeho hodnota

s hodnotou podbloku N2 (sčítání se provádí modulo 2), pak se dílčí bloky prohodí. Taková transformace se provádí pro určitý počet kol: 16 nebo 32, v závislosti na režimu činnosti algoritmu (popsaném níže). V každém kole jsou provedeny následující operace:

1. Překrytí kláves. Obsah subbloku / 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, to znamená, že 256bitový šifrovací klíč je reprezentován jako zřetězení 32bitových podklíčů (obr. 3.2) :

SH ATI, AG2, YU, AG4, K5, KB, K7.

V procesu šifrování se používá jeden z těchto podklíčů v závislosti na zaokrouhleném čísle a režimu provozu algoritmu.

Rýže. 3.1. Schéma algoritmu GOST 28147-

Rýže. 3.2. Šifrovací klíč algoritmu GOST 28147-89

2. Výměna tabulky. Poté, co je klíč překryt, je dílčí blok / VI rozdělen na 8 částí po 4 bitech, přičemž hodnota každého z nich je jednotlivě nahrazena v souladu s náhradní tabulkou pro tuto část dílčího bloku. Substituční boxy (S-boxy) se často používají v moderních šifrovacích algoritmech, takže stojí za to je zvážit podrobněji.

Tabulární náhrada se používá tímto způsobem: na vstup se přivádí blok dat určité dimenze (v tomto případě 4bitový), jehož číselné vyjádření 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 15, to znamená. „1111“ (0 se nahradí 4, 1 se nahradí 11, hodnota 2 se nezmění atd.).

Jak vidíte, schéma algoritmu je velmi jednoduché, což znamená, že největší zátěž šifrování dat připadá na náhradní tabulky. Algoritmus má bohužel tu vlastnost, že existují „slabé“ substituční tabulky, při jejichž použití lze algoritmus odhalit kryptanalytickými metodami. Mezi slabé patří například tabulka, ve které se výstup rovná 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ů.

Režimy provozu algoritmu

Algoritmus GOST 28147-89 má 4 provozní režimy:

□ jednoduchý režim výměny;

□ režim gama;

P gamma režim se zpětnou vazbou;

□ způsob výroby simulátorů.

Tyto režimy se poněkud liší od obecně přijímaných (popsaných v části 1.4), takže stojí za to je podrobněji zvážit.

Tyto režimy mají různé účely, ale používají stejnou transformaci šifrování popsanou výše.

Snadný režim výměny

V režimu jednoduché výměny se výše popsaných 32 kol jednoduše provede k zašifrování každého 64bitového bloku informací. 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 posloupností podklíčů:

□ KO, K \, K2, KZ, K4, K5, Kb, KP - v kolech od 1 do 8;

□ KP, Kb, K5, K4, KZ, K2, K \, KO, K1, Kb atd. - v kolech od 9. do 32. místa.

Podobně jako ve standardním režimu ECB, kvůli oddělenému šifrování bloků, jednoduchý náhradní režim se důrazně nedoporučuje šifrovat samotná data; měl by být použit pouze k šifrování jiných šifrovacích klíčů ve víceklíčových schématech.

Režim gama

V režimu gama (obr. 3.3) se ke každému bloku prostého textu přidá bitově modul 2 se 64bitovým šifrovacím blokem gama. Gama šifry je speciální sekvence, která je generována pomocí výše popsaných transformací následovně:

1. V registrech N1 a N2 je zapsáno jejich počáteční naplnění-64bitová hodnota nazývaná „synchro-burst“ (synchro-burst je prakticky analogický s inicializačním vektorem v režimech CBC, CFB a OFB).

2. Šifrování obsahu registrů / VI a N2 (v tomto případě - synchronizační zprávy) se provádí v jednoduchém náhradním režimu.

3. K obsahu N1 se přidá modulo (2 32 - 1) s konstantou CI = 2 24 + 2 16 + 2 8 + 4, výsledek přidání se zapíše do registru / VI.

4. K obsahu N2 se přidá 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áván jako 64bitový šifrovací gama blok (tj. V tomto případě / VI a N2 tvoří první gama blok).

6. Pokud je zapotřebí další blok gama (tj. Musíte pokračovat v šifrování nebo dešifrování), vrátíte se ke kroku 2.

Pro dešifrování je gama generováno podobným způsobem, poté je operace XOR znovu aplikována na šifrový text a gama bity.

Aby uživatel vygeneroval stejný rozsah šifry, musí mít dešifrování kryptogramu stejný klíč a stejnou synchronizační hodnotu, jaké byly použity k šifrování informací. V opačném případě nebude možné získat původní text ze šifrovaného.

Ve většině implementací algoritmu GOST 28147-89 není synchronizační zpráva tajným prvkem, ale synchronizační zpráva může být stejně tajná jako šifrovací klíč. V tomto případě můžeme předpokládat, že efektivní délka klíče algoritmu (256 bitů) se zvýší 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 se jako plnění registrů / VI a L / 2, počínaje od 2. bloku, nepoužívá předchozí blok gama, ale výsledek šifrování předchozího bloku prostého textu (obr. 3.4) . První blok v tomto režimu je generován zcela podobně jako předchozí.

Rýže. 3.4. Generování šifry gama v režimu gama se zpětnou vazbou

Způsob výroby simulátoru

Předpona je kryptografický kontrolní součet vypočítaný pomocí šifrovacího klíče k ověření integrity zpráv. Pro jeho výpočet existuje speciální režim algoritmu GOST 28147-89.

Generování simulátoru se provádí následovně:

1. První 64bitový informační blok, pro který je vypočítána předpona, je zapsán do registrů N1 a N2 a zašifrován v redukovaném režimu jednoduché náhrady, 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 je uložen v N1 a N2.

3. M a N2 jsou opět šifrovány ve zmenšeném režimu jednoduché výměny a tak dále až do posledního bloku informací.

Imitátor je 64bitový výsledný obsah registrů N1 a N2 nebo jeho části. Nejčastěji se používá 32bitová předpona, tj. Polovina obsahu registru. To je dost, protože jako každý kontrolní součet je simulátor určen především k ochraně před náhodným zkreslením informací. K ochraně před záměrnou úpravou dat se používají jiné kryptografické metody - především elektronický digitální podpis (viz část 1.1).

Imitátor se používá následovně:

1. Při šifrování jakýchkoli informací se vypočítá předpona prostého textu a odešle se spolu se šifrovacím textem.

2. Po dešifrování se prefix znovu vypočítá a porovná s odeslaným.

3. Pokud se vypočítané a odeslané předpony neshodují - šifrový text byl při přenosu zkreslený nebo byly při dešifrování použity nesprávné klíče.

Předpona je zvláště užitečná pro ověření správného dešifrování klíčových informací při použití víceklíčových schémat.

Imitátor je jakýmsi analogem ověřovacího kódu zprávy MAC vypočítaného v režimu CBC; rozdíl je v tom, že synchronizační zpráva se nepoužívá při výpočtu předpony, zatímco inicializační vektor se používá při výpočtu MAC.

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 prováděné zahraničními odborníky; po značnou dobu však nebyly shledány žádné útoky blížící se uskutečnitelné.

□ velká délka klíče - 256 bitů; společně s tajnou synchronizační zprávou se efektivní délka klíče zvýší na 320 bitů;

□ 32 kol transformací; 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 šifrového textu a naopak, to znamená, že existuje více bezpečnostních rezerv.

Zvažte výsledky kryptoanalýzy algoritmu GOST 28147-89.

Analýza náhradních tabulek

Protože substituční tabulky nejsou v normě uvedeny, řada prací (například c) naznačuje, že „kompetentní organizace“ může produkovat „dobré“ i „špatné“ substituční tabulky. Nejslavnější odborník Bruce Schneier však takové předpoklady nazývá „fámy“. Je zřejmé, že kryptografická síla algoritmu do značné míry závisí na vlastnostech použitých náhradních tabulek; podle toho existují slabé náhradní tabulky (viz příklad výše), jejichž použití může útok na algoritmus zjednodušit. Přesto se možnost použití různých substitučních tabulek jeví jako velmi hodný nápad, ve prospěch kterého lze citovat dvě skutečnosti z historie šifrovacího standardu DES (podrobnosti viz část 3.15):

□ útoky využívající lineární i 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 pomocí 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 náhradní tabulky jsou ve standardu pevně definovány, respektive implementace algoritmu pravděpodobně nepodporuje schopnost měnit tabulky na jiné.

V řadě prací (například a) se mylně dochází k závěru, že tajné tabulky substitucí algoritmu GOST 28147-89 mohou být součástí klíče a zvyšovat jeho efektivní délku (což je nevýznamné, protože algoritmus má velmi velký 256bitový klíč). Práce však prokázala, že tajné substituční tabulky lze vypočítat pomocí následujícího útoku, který lze aplikovat v praxi:

1. Nastaví se nulový klíč a provede se hledání „nulového vektoru“, tj. Hodnot z = / (0), kde / () je funkce kola algoritmu. Tato fáze trvá asi 2 šifrovací operace.

2. Pomocí nulového vektoru se vypočítají hodnoty substitučních tabulek, což nezabere více než 2 11 operací.

Modifikace algoritmů a jejich analýza

Práce provedla kryptoanalýzu modifikací algoritmu GOST 28147-89:

Algor algoritmus GOST-H, ve kterém se oproti původnímu algoritmu změní pořadí použití podklíčů, konkrétně v kolech 25 až 32 se podklíče používají v přímém pořadí, tj. Stejným způsobem jako v předchozí kola algoritmu;

□ 20kolový algoritmus GOST®, který používá XOR k použití klíče místo přidání modulo 32.

Na základě výsledků analýzy byl učiněn závěr, že GOST-H a GOST © jsou slabší než původní algoritmus GOST 28147-89, protože oba mají třídy slabých klíčů. Je třeba poznamenat, že v části kryptoanalýzy GOST © práce slovo od slova opakuje část věnovanou kryptoanalýze algoritmu GOST 28147-89, publikované v roce 2000 známým dílem (bez jakýchkoli odkazů na originál) . To zpochybňuje profesionalitu autorů díla a zbytku jeho výsledků.

V práci je navržena velmi zajímavá modifikace algoritmu: tabulky S \ ... Ss se musí lišit; v každém kole algoritmu musí být uspořádány podle určitého zákona. Tato permutace může být závislá na šifrovacím klíči, nebo může být tajná (to znamená, že může být součástí šifrovacího klíče větší než původní 256bitový klíč). Obě tyto možnosti podle jejich autorů výrazně zvyšují odolnost algoritmu proti lineární a diferenciální kryptanalýze.

A v práci je uvedena ještě jedna modifikace týkající se substitučních tabulek, která analyzuje jednu z možných metod pro výpočet substitučních tabulek na základě šifrovacího klíče. Autoři práce dospě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í útoky na úplný GOST 28147-89 bez jakýchkoli úprav. Jeden z prvních otevřených příspěvků analyzujících algoritmus, známý článek, je věnován útokům, které využívají slabiny postupu klíčové expanze řady známých šifrovacích algoritmů. Zejména lze úplný algoritmus GOST 28147-89 prolomit pomocí diferenciální kryptoanalýzy na propojených klíčích, ale pouze pokud jsou použity slabé substituční tabulky. 24kolová varianta algoritmu (která postrádá prvních 8 kol) se otevírá stejným způsobem pro jakékoli substituční tabulky, ale silné substituční tabulky (například zobrazené v c) činí takový útok zcela nepraktickým.

Domácí vědci A.G. a požadovanou klíčovou hodnotu a nalezení jejího extrému odpovídající skutečné klíčové hodnotě. Našli také velkou třídu slabých klíčů algoritmu GOST 28147-89, které umožňují prolomit algoritmus pomocí pouze 4 vybraných prostých textů a odpovídajících šifrovacích textů s poměrně nízkou složitostí. V práci pokračuje kryptoanalýza algoritmu.

V roce 2004 skupina odborníků z Koreje navrhla útok, pomocí kterého je pomocí diferenciální kryptoanalýzy na propojených klíčích možné získat s pravděpodobností 91,7% 12 bitů tajného klíče. Útok vyžaduje 2 35 vybraných holých textů a 2 36 šifrovacích operací. Jak vidíte, tento útok je pro skutečný útok na algoritmus prakticky nepoužitelný.

Algoritmus GOST 28147-89 a šifra „Magma“ (GOST R 34.12-2015)

Obecné schéma algoritmu. Algoritmus popsaný v GOST 28147-89 „Systémy zpracování informací. Kryptografická ochrana. Kryptografický transformační algoritmus “je domácí standard pro symetrické šifrování (před 1. lednem 2016) a je povinný pro implementaci v certifikovaných nástrojích pro ochranu kryptografických informací používaných ve státních informačních systémech a v některých případech v komerčních systémech. Certifikace prostředků kryptografické ochrany informací je vyžadována k ochraně informací tvořících státní tajemství Ruské federace a informací, jejichž důvěrnost musí být zajištěna v souladu s aktuální legislativou. Také v Ruské federaci se pro ochranu bankovních informačních systémů doporučuje použití algoritmu GOST 28147-89.

Algoritmus GOST 28147-89 (obr. 2.21) je založen na Feistelově schématu a šifruje informace v blocích po 64 bitech, které jsou rozděleny do dvou dílčích bloků po 32 bitech (I a R). Subblock R, je zpracována funkcí kruhové transformace, načež se její hodnota přičte k hodnotě podbloku Lj, poté se podbloky prohodí. Algoritmus má 16 nebo 32 kol, v závislosti na režimu šifrování (výpočet vložení imitace nebo jiné režimy šifrování).

Rýže. 2.21.

V každém kole algoritmu jsou provedeny následující transformace.

1. Překrytí klíčem. Obsah podbloku R i přidáno modulo 2 32 s kulatým klíčem K. Kj je 32bitová část původního klíče používaná jako kulatá. Algoritmus GOST 28147-89 ns používá postup rozšíření klíče, původní 256bitový šifrovací klíč je reprezentován jako zřetězení (zřetězení) osmi 32bitových podklíčů (obr. 2.22): K 0, K (, K t K, K A, K 5, K 6, K 7.

Proces šifrování používá jeden z těchto podklíčů NA

Od 1. do 24. kola - v přímém pořadí:

Od 25. do 32. kola - v opačném pořadí:

Rýže. 2.22. Struktura šifrovacího klíče algoritmu GOST 28147-89

2. Tabelární náhrada. Poté, co byl klíč použit, dílčí blok R i je rozdělen na osm částí, ale 4 bity, přičemž hodnota každé z nich je jednotlivě nahrazena v souladu s její náhradní tabulkou (S-box). Používá se celkem osm S -boxů - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. Každý S-box algoritmu GOST 28147-89 je vektor (jednorozměrné pole) s ^ prvky číslovanými od 0 do 15. Hodnoty S-boxu jsou 4bitová čísla; celá čísla od 0 do 15.

Prvek je převzat z tabulky S-boxu, jehož pořadové číslo se shoduje s hodnotou, která přišla na substituční vstup.

Příklad 2.6.

Nechť existuje S-blok následující formy:

Vstupu tohoto S-boxu nechť je dána hodnota 0100 2 = 4. Výstupem S-boxu bude 4. prvek substituční tabulky, tzn. 15 = 1111 2 (prvky jsou číslovány od nuly).

substituční osoby nejsou standardem definovány, jak se to děje například v šifře DES. Změnitelné hodnoty substitučních tabulek výrazně komplikují kryptoanalýzu algoritmu. Robustnost algoritmu přitom v zásadě závisí na jejich správné volbě.

Algoritmus GOST 28147-89 má bohužel „slabé“ substituční tabulky, při jejichž použití lze algoritmus poměrně snadno odhalit kryptanalytickými metodami. Mezi „slabé“ patří například triviální tabulka substitucí, ve které se vstup rovná výstupu (tabulka 2.16).

Tabulka 2.16

Příklad slabého S-boxu

Předpokládá se, že konkrétní hodnoty náhradních tabulek by měly být utajeny a jsou dlouhodobým klíčovým prvkem, tj. jsou platné mnohem delší dobu než jednotlivé klíče. Tajné hodnoty náhradních tabulek však nejsou součástí klíče a nemohou zvýšit jeho efektivní délku.

Tajné substituční tabulky lze skutečně vypočítat pomocí následujícího útoku, který lze aplikovat v praxi:

• nastaví se nulový klíč a provede se hledání „nulového vektoru“, tj. význam z = F ( 0), kde F - funkce algoritmu kruhové transformace. To vyžaduje asi 2 32 testovacích šifrovacích operací;
• pomocí nulového vektoru se vypočítají hodnoty substitučních tabulek, což nezabere více než 2 11 operací.

I když je však narušena důvěrnost substitučních tabulek, síla šifry zůstává extrémně vysoká a neklesá pod přípustnou mez.

Rovněž se předpokládá, že substituční tabulky jsou společné pro všechny šifrovací uzly ve stejném systému kryptografické ochrany.

Vylepšení struktury S-boxů je jedním z nejintenzivněji zkoumaných problémů v oblasti symetrických blokových šifer. V zásadě je požadováno, aby se jakékoli změny vstupů S-boxů vysypaly do náhodný zdánlivě mění výstup. Na jedné straně, čím větší jsou S-boxy, tím je algoritmus odolnější vůči metodám lineární a diferenciální kryptoanalýzy. Na druhou stranu je velký náhradní stůl náročnější na design.

V moderních algoritmech jsou S-boxy obvykle vektorové (jednorozměrné pole) obsahující 2 "t- bitové prvky. Blokový vstup definuje číslo prvku, jehož hodnota slouží jako výstup S-bloku.

Pro konstrukci S-boxů byla předložena řada kritérií. Substituční tabulka musí splňovat:

• přísné lavinové kritérium;
• bitové kritérium nezávislosti;
• požadavek na nelinearitu ze vstupních hodnot.

Aby byl splněn poslední požadavek, bylo navrženo specifikovat lineární kombinaci já bity ( i = 1, ..., T) hodnoty substituční tabulky ohnuté funkce(angl., ohnutý - odchylující se, v tomto případě - od lineárních funkcí). Ohnuté funkce tvoří zvláštní třídu booleovských funkcí charakterizovaných nejvyšší třídou nelinearity a splněním přísného lavinového kritéria.

V některých pracích se u S-boxů navrhuje zkontrolovat splnění zaručeného lavinového efektu objednávky y-když se změní jeden vstupní bit, změní se alespoň výstupní bity S-boxu. Vlastnost zaručeného lavinového efektu v řádu y od 2 do 5 poskytuje dostatečně dobré difúzní charakteristiky S-boxů pro jakýkoli šifrovací algoritmus.

Při navrhování dostatečně velkých náhradních tabulek lze použít následující přístupy:

• náhodný výběr (u malých S-boxů to může vést k vytvoření slabých substitučních tabulek);
• náhodný výběr následovaný kontrolou shody s různými kritérii a odmítnutím slabých S-boxů;
• ruční výběr (příliš pracný pro velké bloky S);
• matematický přístup, například generování pomocí ohnutých funkcí (tento přístup je aplikován v algoritmu CAST).

Lze navrhnout následující postup pro navrhování jednotlivých bloků S algoritmu GOST 28147-89:

• každý S-box lze popsat čtyřmi logickými funkcemi, každá z funkcí musí mít čtyři logické argumenty;
• tyto funkce musí být dostatečně propracované. Tento požadavek složitosti nelze formálně vyjádřit, nicméně jako nezbytnou podmínku lze požadovat, aby odpovídající logické funkce zapsané v minimální formě (tj. S minimální možnou délkou výrazu) pomocí základních logických operací nebyly kratší než určitou požadovanou hodnotu;
• jednotlivé funkce, i když jsou použity v různých substitučních tabulkách, se musí navzájem dostatečně lišit.

V roce 2011 byl navržen nový útok „reflexní setkání uprostřed“, který mírně snižuje odpor GOST 28147-89 (z 2256 na 2225). Nejlepší výsledek kryptoanalýzy algoritmu z roku 2012 snižuje jeho sílu na 2 192, což vyžaduje relativně velkou velikost šifrového textu a objem předem vytvořených dat. Navzdory navrhovaným útokům zůstává GOST 28147-89 na současné úrovni rozvoje počítačové technologie prakticky stabilní.

Kód „Magma“ (GOST R 34.12-2015). Norma GOST 28147-89 platí v Rusku více než 25 let. Během této doby ukázal dostatečnou trvanlivost a dobrou účinnost softwarových a hardwarových implementací, včetně těch na zařízeních s nízkými zdroji. Přestože byly navrženy kryptoanalytické útoky, které snižují odhady jeho odolnosti (nejlepší je na 2 192), zdaleka nejsou proveditelné. Proto bylo rozhodnuto zahrnout algoritmus GOST 28147-89 do nově vyvinutého standardu symetrického šifrování.

V obchodě 2015 byly přijaty dva nové národní kryptografické standardy: GOST R 34.12-2015 „Informační technologie. Ochrana kryptografických informací. Blokové šifry “a GOST R 34.13-2015„ Informační technologie. Ochrana kryptografických informací. Režimy provozu blokových šifer “, které vstupují v platnost 1. ledna 2016.

Norma GOST R 34.12-2015 obsahuje popis dvou blokových šifer s délkou bloku 128 a 64 bitů. Šifra GOST 28147-89 s pevnými nelineárními substitučními bloky je v novém GOST R 34.12-2015 zahrnuta jako 64bitová šifra s názvem „Magma“.

Níže jsou uvedeny náhradní bloky opravené ve standardu:

Sada S-boxů uvedená ve standardu poskytuje nejlepší vlastnosti, které určují odolnost kryptoalgoritmu vůči diferenciální a lineární kryptanalýze.

Podle technické komise pro standardizaci „Kryptografická ochrana informací“ (TC 26) díky fixaci nelineárních substitučních bloků bude algoritmus GOST 28147-89 jednotnější a pomůže eliminovat používání „slabých“ nelineárních substitučních bloků. Fixace ve standardu všech dlouhodobých parametrů šifry navíc splňuje uznávanou mezinárodní praxi. Nový standard GOST R 34.12-2015 je terminologicky a koncepčně propojen s mezinárodními normami ISO / IEC 10116 „Informační technologie. Bezpečnostní metody. Provozní režimy pro „-bitové blokové šifry“ (ISO / IEC 10116: 2006 Informační technologie - Bezpečnostní techniky - Provozní režimy pro n -bitovou blokovou šifru) a ISO / IEC 18033 „Informační technologie. Metody a prostředky k zajištění bezpečnosti. Šifrovací algoritmy ": ISO / IEC 18033-1: 2005" Část 1. Obecné "(ISO / IEC 18033-1: 2005 Informační technologie - Bezpečnostní techniky - Šifrovací algoritmy - Část 1: Obecné) a ISO / IEC 18033-3: 2010 „Část 3. Blokové šifry“ (ISO / IEC 18033-3: 2010 (Informační technologie - Bezpečnostní techniky - Šifrovací algoritmy - Část 3: Blokové šifry)).

Standard GOST P 34.12-2015 také obsahuje novou blokovou šifru („Grasshopper“) s velikostí bloku 128 bitů. Očekává se, že tato šifra bude odolná proti všem dnes známým útokům na blokové šifry.

Režimy provozu blokových šifer (jednoduchá náhrada, gama, gama s výstupní zpětnou vazbou, gama s ciphertextovou zpětnou vazbou, jednoduchá náhrada za zapojení a generování imitační vložky) jsou obsaženy v samostatné normě GOST R 34.13-2015, která odpovídá uznávaná mezinárodní praxe. Tyto režimy jsou použitelné jak pro šifru Magma, tak pro novou šifru Grasshopper.

• Provádí se bitový kruhový posun doleva o 11 bitů. Dešifrování se provádí podle stejného schématu, ale s jiným plánem použití klíčů: od 1. do 8. kola dešifrování - v přímém pořadí: od 9. do 32. kola dešifrování - v opačném pořadí: Ve srovnání s Šifra DES v GOST 28147-89 má následující výhody: výrazně delší klíč (256 bitů oproti 56 pro šifru DES), útok, na který se v tuto chvíli zdá být vyjmenování sady klíčů hrubou silou nemožné; jednoduchý plán použití klíče, který zjednodušuje implementaci algoritmu a zvyšuje rychlost výpočtů. Návrh bloků S GOST 28147-89. Je zřejmé, že schéma algoritmu GOST 28147-89 je velmi jednoduché. To znamená, že největší zátěž šifrování připadá na substituční tabulky. Hodnoty tabulátoru
• Šifrovací algoritmy Panasepko S.P.: speciální příručka. SPb.: BHV-Peter-burg, 2009.
• Kara O. Reflexní útoky na produktové šifry. URL: http://eprint.iacr.org/2007/043.pdf
• Ruský šifrovací standard: síla snížena. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Achekseev E. K., Smyshlyaev S. V. GOST 28147-89: „Nespěchejte, abyste ho pochovali.“

Známý badatel, zakladatel algebraické kryptoanalýzy, Nicolas Courtois, tvrdí, že bloková šifra GOST, která se měla v blízké budoucnosti stát mezinárodním standardem, je ve skutečnosti rozbitá a v budoucnu čeká na mnoho publikací, které by měly rozvíjet jeho myšlenky o nestabilitě tohoto algoritmu.

Následuje stručné výňatky z této práce, kterou lze považovat za poplašný útok uprostřed mezinárodní standardizace (autor byl známý podobnými nadsázkami ve vztahu k AES, ale jeho práce měla tehdy velký teoretický vliv na kryptanalýzu, ale má nevedlo k praktickým útokům na samotný AES). Ale možná je to také skutečné varování před začátkem etapy „potápění letadla do ocasu“, které může skončit zhroucením národního šifrovacího standardu, jako tomu bylo v případě hashovacího algoritmu SHA-1 a de facto MD5 hashovací algoritmus.

GOST 28147-89 byl standardizován v roce 1989 a stal se oficiálním standardem pro ochranu důvěrných informací poprvé, ale specifikace šifry zůstala uzavřená. V roce 1994 byla norma odtajněna, publikována a přeložena do angličtiny. Analogicky s AES (a na rozdíl od DES) může GOST chránit utajované informace bez omezení v souladu se způsobem, který je uveden v ruské normě. Že. GOST není analogem DES, ale je konkurentem 3-DES se třemi nezávislými klíči nebo AES-256. GOST je očividně poměrně vážná šifra, která splňuje vojenská kritéria, vytvořená s očekáváním nejzávažnějších aplikací. Na základě aplikací používaných ruskými bankami byly identifikovány nejméně dvě sady GOST S-boxů. Tyto banky musí vést tajnou komunikaci se stovkami poboček a chránit miliardy dolarů před podvodnými krádežemi.

GOST je bloková šifra s jednoduchou Feistelovou strukturou, s velikostí bloku 64 bitů, 256bitovým klíčem a 32 koly. Každé kolo obsahuje přidání modulo 2 ^ 32 klíčů, sadu osmi 4bitových S-boxů a jednoduchý 11bitový cyklický posun. Funkce GOST je schopnost tajně ukládat S-bloky, které mohou být reprezentovány jako druhý klíč, který zvyšuje efektivní klíčový materiál na 610 bitů. Jedna sada S-boxů byla vydána v roce 1994 jako součást specifikace hashovací funkce GOST-R 34.11-94 a, jak napsal Schneier, byla použita centrální bankou Ruské federace. Je také součástí standardu RFC4357 v části „id-GostR3411-94-CryptoProParamSet“. Ve zdrojovém kódu na konci Schneierovy knihy (v pořadí S-box) došlo k chybě. Nejpřesnější referenční implementaci původního ruského původu lze nyní nalézt v knihovně OpenSSL. Pokud se někde používají tajné S-boxy, pak je lze extrahovat ze softwarových implementací a z mikroobvodů, ve skutečnosti byla publikována odpovídající díla.

GOST je vážným konkurentem

Kromě velmi velké velikosti klíče má GOST výrazně nižší náklady na provedení ve srovnání s AES a jinými podobnými šifrovacími systémy. Ve skutečnosti to stojí mnohem méně než AES, což vyžaduje čtyřikrát více hardwarových logických bran pro mnohem nižší deklarované zabezpečení.

Není divu, že se GOST stal internetovým standardem, zejména je obsažen v mnoha krypto knihovnách, jako jsou OpenSSL a Crypto ++, a získává na popularitě i mimo svou zemi původu. V roce 2010 byl GOST pro standardizaci ISO prohlášen za celosvětový šifrovací standard. Velmi malý počet algoritmů se dokázal stát mezinárodními standardy. ISO / IEC 18033-3: 2010 popisuje následující algoritmy: čtyři 64bitové šifry-TDEA, MISTY1, CAST-128, HIGHT-a tři 128bitové šifry-AES, Camellia, SEED. GOST se navrhuje přidat ke stejné normě ISO / IEC 18033-3.

Poprvé v historii průmyslové normalizace se zabýváme takovým konkurenčním algoritmem z hlediska optimality mezi náklady a úrovní zabezpečení. GOST má 20 let úsilí o dešifrování a donedávna nebylo jeho vojenské zabezpečení zpochybňováno.

Jak se autor nedávno dozvěděl ze soukromé korespondence, většina zemí byla proti GOST při hlasování ISO v Singapuru, ale výsledky tohoto hlasování budou ještě zváženy na plenárním zasedání ISO SC27, takže GOST je v době standardizace stále v procesu normalizace vydání této práce.

Názory odborníků na GOST

Nic z dostupných informací a literatury týkající se GOST nedává důvod se domnívat, že šifra může být nebezpečná. Naopak velká velikost klíče a velký počet nábojů činí GOST na první pohled vhodný pro desetiletí používání.

Každý, kdo zná Moorův zákon, si uvědomuje, že teoreticky 256bitové klíče zůstanou zabezpečené po dobu nejméně 200 let. GOST byl rozsáhle zkoumán předními odborníky v oblasti kryptografie, známými v oblasti analýzy blokových šifer, jako jsou Schneier, Biryukov, Dankelman, Wagner, mnoho australských, japonských a ruských vědců, odborníci na kryptografii z ISO a všichni výzkumníci vyjádřil, že vše vypadá takto, že může být nebo by měl být v bezpečí. Ačkoli názor dosáhl širokého porozumění, že samotná struktura GOST je například extrémně slabá, například ve srovnání s DES, zejména difúze není tak dobrá, ale vždy to bylo způsobeno skutečností, že by to mělo být kompenzováno velký počet kol (32), stejně jako další nelinearita a difúze zajištěné přidáním modulu.

Biryukov a Wagner napsali: „Velký počet nábojů (32) a dobře prostudovaná Feistelova konstrukce v kombinaci s postupnými Shannonovými permutacemi poskytují pevný základ pro bezpečnost GOST.“ Ve stejné práci čteme: „po značné investici času a úsilí nebyl v kryptanalýze standardu v otevřené literatuře učiněn žádný pokrok“. Neexistovaly tedy žádné významné útoky, které by umožňovaly dešifrování nebo obnovu klíčů v realistickém scénáři, kdy se při šifrování pomocí mnoha různých náhodných klíčů používá GOST. Naproti tomu je známo mnoho prací o útocích na slabé klíče v GOST, útocích s přidruženými klíči, útocích na obnovu tajných S-boxů. Na Crypto-2008 bylo představeno hackování hashovací funkce založené na této šifře. U všech útoků má útočník výrazně větší míru svobody, než je obvykle povoleno. V tradičních aplikacích šifrování pomocí náhodně vybraných klíčů nebyly dosud nalezeny žádné závažné kryptografické útoky na GOST, což v roce 2010 vyjadřovala závěrečná fráze: „navzdory značnému úsilí kryptanalytiků za posledních 20 let GOST dosud nebyl popraskané “(Axel Poschmann, San Ling a Huaxiong Wang: 256bitová standardizovaná kryptoměna pro 650 GE GOST Revisited, In CHES 2010, LNCS 6225, s. 219-233, 2010).

Lineární a diferenciální analýza GOST

Ve Schneierově známé knize čteme: „Proti diferenciální a lineární kryptoanalýze je GOST pravděpodobně robustnější než DES.“ Hlavní hodnocení bezpečnosti GOST bylo poskytnuto v roce 2000 Gabidulinem a spol. Jejich výsledky jsou velmi působivé: s úrovní zabezpečení 2 ^ 256, stačí pět kol na ochranu GOST před lineární kryptoanalýzou. Navíc i při výměně S -boxů za identické a jedinou nelineární šifrovací operaci - adiční mód 2 ^ 32 - je šifra stále odolná vůči lineární kryptoanalýze i po 6 kolech z 32. Diferenciální kryptoanalýza GOST vypadá relativně snadněji a přitahuje větší pozornost. Pro úroveň zabezpečení 2 ^ 128 vědci (Vitaly V. Shorin, Vadim V. Jelezniakov a Ernst M. Gabidulin: Lineární a diferenciální kryptoanalýza ruské GOST, předtisk předložen Elsevier Preprint, 4. dubna 2001) předpokládali dostatečnou trvanlivost v 7 kolech . Podle nich je prolomení GOST ve více než pěti kolech „extrémně obtížné“. Dva japonští vědci navíc prokázali, že klasický přímý diferenciální útok s jednou diferenciální charakteristikou má extrémně nízkou pravděpodobnost, že projde velkým počtem kol. Na základě studia dostatečně „dobré“ iterační diferenciální charakteristiky pro omezený počet kol (která sama má pravděpodobnost, že projde ne lépe než 2–11,4 na kolo), je hodnota sady vhodných klíčů menší než polovina . Pro úplnou GOST bude takový útok s jedinou charakteristikou fungovat pouze se zanedbatelnou částí klíčů řádově 2-62 (a dokonce i v této malé části bude mít pravděpodobnost, že projde maximálně 2-360 ).

Sofistikovanější útoky zahrnují více diferenciálů, které sledují určité vzorce, například pomocí samostatných S-boxů, které mají nulové diferenciály, zatímco jiné bity mají nenulové. Mluvíme o diskriminačních útocích na základě špatných difúzních vlastností GOST. Nejlepší z těchto útoků funguje proti 17 kolům GOST, závisí na klíči a má extrémně slabý diskriminátor od náhodných dat na samotném výstupu, takže jej lze nějakým způsobem použít k získání informací o klíči.

Klouzejte a odklánějte útoky

Podle Biryukova a Wagnera je struktura GOST, která v posledních kolech zahrnuje obrácené pořadí podklíčů, odolná vůči klouzavým útokům (takzvané „kluzné útoky“). Vzhledem k přítomnosti velké vlastní podobnosti v šifře to však umožňuje útokům inverze klíčů na kombinace pevných bodů a vlastností „odrazu“ (takzvané „reflexní útoky“) u určitých slabých klíčů. Složitost tohoto útoku je 2 ^ 192 a 2 ^ 32 shodných holých textů.

Nejnovější výsledky

Nové útoky také využívají reflexi a ve skutečnosti porušily GOST, který byl představen na konferenci FSE 2011. Tyto útoky byly také objeveny nezávisle autorem tohoto příspěvku. Útok vyžaduje 2 ^ 132 bajtů paměti, což je ve skutečnosti horší než pomalejší útoky s menšími nároky na paměť.

Různé nové útoky podobné podobnosti fungují proti všem klíčům GOST a umožňují vám rozbít úplnou GOST pomocí 256bitového klíče, nejen pro slabé klíče, jako tomu bylo dříve. Všechny tyto útoky vyžadují výrazně méně paměti a jsou výrazně rychlejší.

Tyto nové útoky lze považovat za příklady nového obecného paradigmatu pro kryptoanalýzu blokových šifer nazývaného „redukce algebraické složitosti“ s generalizací těchto útoků na mnoho zvláštních případů útoků se známými pevnými body, skluzavkami, evolucemi a cykly. Je důležité, aby mezi rodinou všech těchto útoků byly ty, které umožňují kryptoanalýzu GOST bez jakýchkoli odrazů a bez symetrických bodů, které se objevují v průběhu výpočtů. Jedním příkladem je jednoduchý hackerský útok GOST bez reflexe v této práci.

Algebraická kryptoanalýza a útoky s nízkou složitostí dat na šifry s omezeným počtem kol

Algebraické útoky na blokové a proudové šifry lze reprezentovat jako problém řešení velkého systému booleovských algebraických rovnic, který sleduje geometrii a strukturu konkrétního kryptografického schématu. Samotná myšlenka se vrací k Shannonovi. V praxi to bylo prezentováno pro DES (poprvé představeno autorem této práce) jako formální metoda kódování a může rozbít 6 kol v jednom známém prostém textu. Manipulace s rovnicemi je založena na algoritmech XL, Gröbnerových základnách, metodě ElimLin, SAT řešičích.

V praxi byly algebraické útoky implementovány proti velmi malému počtu blokových šifer, ale již vedly k popraskání proudových šifer a také se daří lámat ultralehké šifry pro mikrozařízení. Kvůli problémům s velikostí paměti a odhady výpočetních nákladů jsou kombinovány s dalšími útoky.

Jak hacknout GOST?

V této publikaci je podrobněji představen algebraický útok na úplný GOST. V předchozím díle autor již nastínil 20 algebraických útoků na GOST a v blízké budoucnosti očekává jejich velký počet. Útok navržený v této práci není nejlepší z nich, ale otevírá jednoduchou (alespoň pro porozumění kryptografům) cestu pro další vývoj k vytvoření specifické metodiky pro prolomení GOST.

Praktický výsledek je stále skromný: 2 ^ 64 známých holých textů a 2 ^ 64 paměť pro ukládání dvojic prostého textu / šifrového textu umožňuje rozbít GOST 2 ^ 8 rychleji než jednoduchá hrubá síla. Ale pokud jde o kryptoanalýzu, prohlášení, že „GOST byl hacknut“, je zcela fér.

závěry

GOST je navržen tak, aby poskytoval vojenskou úroveň zabezpečení po dobu 200 let. Většina předních odborníků, kteří studovali GOST, se shodli na tom, že „navzdory značnému kryptoanalytickému úsilí po dobu 20 let nebyla GOST dosud prolomena“. V roce 2010 byl GOST povýšen na ISO 18033 jako globální šifrovací standard.

Základ myšlenek o algebraické kryptoanalýze se datuje více než 60 let. Ale teprve za posledních 10 let byly vyvinuty efektivní softwarové nástroje pro (částečné) řešení mnoha NP-úplných problémů. Řada proudových šifer byla prolomena. Touto metodou byla prolomena pouze jedna bloková šifra - samotný slabý KeeLoq. V této práci autor láme důležitou, skutečně používanou šifru GOST. Poznamenává, že je to poprvé v historii, kdy byla standardizovaná státní šifra prolomena algebraickou kryptanalýzou.

Jednoduchý útok „GITM s odrazem“ na GOST již byl představen na konferenci FSE 2011. V práci diskutované v tomto článku je další útok uveden pouze pro ilustraci skutečnosti, kolik útoků na GOST se již objevilo nyní, z nichž mnohé jsou rychlejší a algebraický útok vyžaduje mnohem méně paměti a otevírá téměř nevyčerpatelný prostor možností pro protivníka zaútočit na šifru různými způsoby. Také v tomto článku je ukázáno, že pro hackování není nutné používat vlastnost odrazu.

Autor tvrdí, že je zřejmé, že GOST má závažné nedostatky a nyní neposkytuje úroveň trvanlivosti požadovanou ISO. Mnoho útoků na GOST je prezentováno v rámci potvrzení paradigmatu snížení algebraické složitosti.

Nakonec si badatel zejména všimne některých faktů, které ještě nejsou čtenáři k dispozici, ale jsou badateli známy a které jsou důležité v průběhu procesu normalizace ISO. Tento útok není jen „certifikačním“ útokem na GOST, který je rychlejší než útok hrubou silou hrubou silou. Ve skutečnosti by standardizace GOST byla nyní extrémně nebezpečná a nezodpovědná. Důvodem je, že některé útoky jsou praktické. V praxi lze některé klíče GOST dokonce dešifrovat, ať už jde o slabé klíče nebo klíče ze soukromých reálných aplikací GOST. V předchozím díle autor podrobně zvažuje případy možnosti praktických útoků. Je příznačné, že „toto je poprvé v historii, kdy byla vážná standardizovaná bloková šifra navržená k ochraně vojenských tajemství a určená k ochraně státních tajemství pro vlády, velké banky a další organizace kompromitována matematickým útokem“.