DES, domáci štandard šifrovania, je vhodnejší na implementáciu softvéru.

Na rozdiel od amerického DES domáci štandard používa dlhší kľúč – 256 bitov. Okrem toho ruský štandard navrhuje použiť 32 kôl šifrovania, zatiaľ čo DES vyžaduje iba 16.

Hlavné parametre algoritmu transformácie kryptografických údajov GOST 28147-89 sú teda nasledovné: veľkosť bloku je 64 bitov, veľkosť kľúča je 256 bitov, počet kôl je 32.

Algoritmus je klasická Feishtelova sieť. Šifrovaný dátový blok je rozdelený na dve identické časti, pravú R a ľavú L. Pravá časť je pridaná do okrúhleho podkľúča a pomocou nejakého algoritmu zašifruje ľavú časť. Pred ďalším kolom sa ľavá a pravá časť vymenia. Táto štruktúra umožňuje použiť rovnaký algoritmus na šifrovanie aj dešifrovanie bloku.

Šifrovací algoritmus používa nasledujúce operácie:

• doplnenie slov modulo 2 32;
• cyklicky posúvať slovo doľava o určený počet bitov;
• bitové sčítanie modulo 2;
• výmena podľa tabuľky.

V rôznych krokoch algoritmov GOST sa údaje, s ktorými pracujú, interpretujú a používajú rôznymi spôsobmi. V niektorých prípadoch sa s dátovými prvkami zaobchádza ako s poliami nezávislých bitov, v iných prípadoch ako celé číslo bez znamienka, v iných ako so štruktúrou komplexný prvok, pozostávajúci z niekoľkých jednoduchších prvkov.

Okrúhla konštrukcia GOST 28147-89

Štruktúra jedného kola GOST 28147-89 je znázornená na obr. 5.1.

Šifrovaný dátový blok je rozdelený na dve časti, ktoré sú potom spracované ako samostatné 32-bitové celé čísla bez znamienka. Najprv sa pridá pravá polovica bloku a podkľúč kola modulo 2 32. Potom sa uskutoční substitúcia blok po bloku. 32-bitová hodnota získaná v predchádzajúcom kroku (nazvime ju S) sa interpretuje ako pole ôsmich 4-bitových blokov kódu: S=(S0,S1,S2,S3,S4,S5,S6,S7). Ďalej sa hodnota každého z ôsmich blokov nahradí novou, ktorá sa vyberie z tabuľky nahradenia takto: hodnota bloku S i sa nahradí S i -tým prvkom v poradí (číslovanie od nuly) i-tého náhradného uzla (t. j. náhradné tabuľky i-tého riadku, číslovanie tiež od začiatku). Inými slovami, prvok s číslom riadka rovným číslu nahrádzaného bloku a číslom stĺpca rovným hodnote nahrádzaného bloku ako 4-bitové nezáporné celé číslo sa vyberie ako náhrada za hodnotu bloku. Každý riadok náhradnej tabuľky obsahuje čísla od 0 do 15 v náhodnom poradí bez opakovania. Hodnoty prvkov substitučnej tabuľky sa berú od 0 do 15, pretože štyri bity, ktoré sú nahradené, môžu obsahovať celé číslo bez znamienka v rozsahu od 0 do 15. Napríklad prvý riadok S-boxu môže obsahovať nasledujúce hodnoty: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . V tomto prípade bude hodnota bloku So (štyri najmenej významné bity 32-bitového čísla S) nahradená číslom na pozícii, ktorého číslo sa rovná hodnote nahradzovaného bloku. Ak S 0 = 0, potom sa nahradí 5, ak S 0 = 1, nahradí sa 8 atď.

Ryža.

5.1. Po vykonaní substitúcie sa všetky 4-bitové bloky opäť spoja do jedného 32-bitového slova, ktoré sa potom otočí o 11 bitov doľava. Nakoniec pomocou bitovej operácie"súčet modulo 2"

výsledok sa spojí s ľavou polovicou, čím vznikne nová pravá polovica R i. Nová ľavá strana Li sa rovná spodnej časti konvertovaného bloku: Li = R i-1.

Výsledná hodnota konvertovaného bloku sa považuje za výsledok jedného kola šifrovacieho algoritmu.

Postupy šifrovania a dešifrovania GOST 28147-89 je teda bloková šifra konverzia údajov realizované v blokoch v tzv základné cykly

. Základné slučky pozostávajú z opakovaného vykonávania hlavného kola, o ktorom sme hovorili vyššie pre dátový blok, s použitím rôznych kľúčových prvkov a navzájom sa líšia v poradí, v akom sa kľúčové prvky používajú. Každé kolo používa jeden z ôsmich možných 32-bitových podkľúčov.

Tabuľka 5.1. Postupnosť použitia podkľúčov počas šifrovania

Okrúhly	1	2	3	4	5	6	7	8
Kompletná konštrukcia	K 0	K 1	K2	K 3	K 4	K5	K 6	K 7
Okrúhly	9	10	11	12	13	14	15	16
Kompletná konštrukcia	K 0	K 1	K2	K 3	K 4	K5	K 6	K 7
Okrúhly	17	18	19	20	21	22	23	24
Kompletná konštrukcia	K 0	K 1	K2	K 3	K 4	K5	K 6	K 7
Okrúhly	25	26	27	28	29	30	31	32
Kompletná konštrukcia	K 7	K 6	K5	K 4	K 3	K2	K 1	K 0

Proces dešifrovania sa vykonáva pomocou rovnakého algoritmu ako šifrovanie. Jediný rozdiel je v poradí, v ktorom sa používajú podkľúče K i. Pri dešifrovaní sa musia podkľúče použiť v opačnom poradí, konkrétne ako je uvedené v

Tento algoritmus je povinný používať ako šifrovací algoritmus vo vládnych organizáciách Ruskej federácie a mnohých komerčných.

Popis algoritmu

Schéma algoritmu je znázornená na obr. 3.1. Ako vidíte, návrh tohto algoritmu je pomerne jednoduchý, čo jednoznačne zjednodušuje jeho softvérovú alebo hardvérovú implementáciu.

Algoritmus GOST 28147-89 šifruje informácie v blokoch po 64 bitoch, ktoré sú rozdelené do dvoch podblokov po 32 bitoch (N1 a N2). Podblok N1 je spracovaný určitým spôsobom, po ktorom sa jeho hodnota sčítava

s hodnotou podbloku N2 (sčítanie sa vykoná modulo 2), potom sa podbloky vymenia. Táto transformácia sa vykonáva v určitom počte kôl: 16 alebo 32, v závislosti od prevádzkového režimu algoritmu (opísaného nižšie). V každom kole sa vykonávajú tieto operácie:

1. Aplikácia kľúča. Obsah podbloku /VI je pridaný modulo 2 32 s časťou kľúča Kx.

Šifrovací kľúč algoritmu GOST 28147-89 má rozmer 256 bitov a Kx je jeho 32-bitová časť, t. j. 256-bitový šifrovací kľúč je reprezentovaný ako zreťazenie 32-bitových podkľúčov (obr. 3.2):

Shch ATI, AG2, Yu, AG4, K5, Kb, K7.

Počas procesu šifrovania sa používa jeden z týchto podkľúčov v závislosti od čísla kola a prevádzkového režimu algoritmu.

Ryža. 3.1. Schéma algoritmu GOST 28147-

Ryža. 3.2. Šifrovací kľúč algoritmu GOST 28147-89

2. Výmena stola. Po kľúčovaní sa podblok /VI rozdelí na 8 častí po 4 bitoch, pričom hodnota každého z nich sa individuálne nahradí v súlade s náhradnou tabuľkou pre túto časť podbloku. Substitúcie tabuliek (Substitution box, S-box) sa často používajú v moderných šifrovacích algoritmoch, takže stojí za to ich podrobnejšie zvážiť.

Substitúcia tabuľky sa používa týmto spôsobom: na vstup sa privádza blok údajov určitej veľkosti (v tomto prípade 4-bitový), ktorého číselné znázornenie určuje číslo výstupnej hodnoty. Napríklad máme S-box nasledujúceho tvaru:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Na vstup nech príde 4-bitový blok „0100“, teda hodnota 4. Podľa tabuľky bude výstupná hodnota rovná 15, t.j. „1111“ (0 je nahradené 4, 1 11, hodnota 2 zostáva nezmenená atď.).

Ako vidíte, návrh algoritmu je veľmi jednoduchý, čo znamená, že najväčšia záťaž pri šifrovaní údajov padá na náhradné tabuľky. Bohužiaľ, algoritmus má tú vlastnosť, že existujú „slabé“ náhradné tabuľky, pomocou ktorých je možné algoritmus vyriešiť kryptanalytickými metódami. Medzi slabé patrí napríklad tabuľka, v ktorej sa výstup rovná vstupu:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Bitový cyklický posun doľava o 11 bitov.

Prevádzkové režimy algoritmov

Algoritmus GOST 28147-89 má 4 prevádzkové režimy:

□ jednoduchý režim výmeny;

□ gama režim;

P gama režim s spätná väzba;

□ spôsob vývoja imitácie príloh.

Tieto režimy sa trochu líšia od všeobecne akceptovaných režimov (popísaných v časti 1.4), preto je vhodné ich zvážiť podrobnejšie.

Tieto režimy majú rôzne účely, ale použite rovnakú transformáciu šifrovania opísanú vyššie.

Jednoduchý režim výmeny

V režime jednoduchého nahradzovania je každý 64-bitový blok informácií jednoducho zašifrovaný pomocou 32 kôl opísaných vyššie. 32-bitové podkľúče sa používajú v nasledujúcom poradí:

□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI atď. - v kolách 1 až 24;

□ K1, Kb, K5, K4, KZ, K2, K\, KO - v kolách od 25. do 32.

Dešifrovanie v režime jednoduchého nahradenia sa vykonáva presne rovnakým spôsobom, ale s mierne odlišnou postupnosťou použitia podkľúčov:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - v 1. až 8. kole;

□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb atď. - v kolách od 9. do 32.

Podobne ako v štandardnom režime ECB sa režim jednoduchej výmeny vzhľadom na samostatné šifrovanie blokov striktne neodporúča na šifrovanie samotných údajov; mal by sa používať iba na šifrovanie iných šifrovacích kľúčov vo viackľúčových schémach.

Režim gama

V gama režime (obr. 3.3) sa každý blok otvoreného textu pridáva bit po bite modulo 2 do 64-bitového šifrového gama bloku. Gama šifra je špeciálna sekvencia, ktorá sa generuje pomocou transformácií opísaných vyššie takto:

1. Ich počiatočné naplnenie sa zapíše do registrov N1 a N2 - 64-bitová hodnota nazývaná „synchronizačná správa“ (synchronizačná správa je prakticky analógom inicializačného vektora v režimoch CBC, CFB a OFB).

2. Obsah registrov /VI a N2 je zašifrovaný (v v tomto prípade- synchronizácia správ) v režime jednoduchej výmeny.

3. Obsah N1 sa sčíta modulo (2 32 – 1) s konštantou CI = 2 24 + 2 16 + 2 8 + 4, výsledok sčítania sa zapíše do registra /VI.

4. K obsahu N2 sa pripočíta modulo 2 s konštantou C2 = 2 24 + 2 16 + 2 8 +1, výsledok sčítania sa zapíše do registra N2.

5. Obsah registrov /VI a N2 je na výstupe ako 64-bitový šifrovací gama blok (t.j. v tomto prípade /VI a N2 tvoria prvý gama blok).

6. Ak je potrebný ďalší gama blok (t. j. je potrebné vykonať ďalšie šifrovanie alebo dešifrovanie), vráťte sa na krok 2.

Na dešifrovanie sa gama generuje podobným spôsobom, potom sa šifrový text a bity gama opäť XORujú.

Na vygenerovanie rovnakého rozsahu šifier musí mať používateľ dešifrujúci kryptogram rovnaký kľúč a rovnakú hodnotu synchronizačnej správy, aké boli použité pri šifrovaní informácií. V opačnom prípade nebude možné získať pôvodný text zo zašifrovaného.

Vo väčšine implementácií algoritmu GOST 28147-89 nie je synchronizačná správa tajným prvkom, ale synchronizačná správa môže byť rovnako tajná ako šifrovací kľúč. V tomto prípade môžeme uvažovať, že efektívna dĺžka kľúča algoritmu (256 bitov) sa zvýši o ďalších 64 bitov synchronizačnej správy, čo možno považovať za dodatočný kľúčový prvok.

Gamma režim so spätnou väzbou

V režime gama so spätnou väzbou sa na vyplnenie registrov /VI a L/2 použije výsledok zašifrovania predchádzajúceho bloku otvoreného textu, počnúc 2. blokom, nie predchádzajúci blok gama, ale výsledok zašifrovania predchádzajúceho bloku otvoreného textu. (obr. 3.4). Prvý blok v tento režim sa generuje úplne podobne ako predchádzajúci.

Ryža. 3.4. Generovanie šifry gama v režime gama so spätnou väzbou

Režim výroby imitácie prílohy

Predpona je kryptografický kontrolný súčet vypočítaný pomocou šifrovacieho kľúča a určený na overenie integrity správ. Na jeho výpočet existuje špeciálny režim algoritmu GOST 28147-89.

Generovanie predpony imitácie sa vykonáva takto:

1. Prvý 64-bitový blok informácií, pre ktorý sa vypočítava predpona imitácie, sa zapíše do registrov N1 a N2 a zašifruje sa v režime redukovanej jednoduchej náhrady, v ktorom sa vykoná prvých 16 kôl z 32.

2. Získaný výsledok sa sčíta modulo 2 s ďalším blokom informácií, pričom sa výsledok uloží do N1 a N2.

3. M a N2 sú opäť zašifrované v skrátenom režime jednoduchej náhrady atď. až do posledného bloku informácií.

Za imitáciu prefixu sa považuje 64-bitový výsledný obsah registrov N1 a N2 alebo ich časti. Najčastejšie sa používa 32-bitová imitujúca predpona, t.j. polovica obsahu registrov. To stačí, pretože ako každý kontrolný súčet je imitácia prílohy určená predovšetkým na ochranu pred náhodným skreslením informácií. Na ochranu pred úmyselnou úpravou údajov sa používajú iné kryptografické metódy – predovšetkým elektronické digitálny podpis(pozri časť 1.1).

Predpona imitácie sa používa takto:

1. Pri šifrovaní akejkoľvek informácie sa vypočíta imitátor otvoreného textu a odošle sa spolu so šifrovaným textom.

2. Po dešifrovaní sa predpona imitácie opäť vypočíta a porovná s odoslanou.

3. Ak sa vypočítané a odoslané predpony imitácie nezhodujú, pri prenose došlo k skresleniu textu šifry alebo pri dešifrovaní boli použité nesprávne kľúče.

Imitačná predpona je užitočná najmä na kontrolu správneho dešifrovania kľúčových informácií pri použití schém s viacerými kľúčmi.

Imitačná predpona je nejakým analógom autentifikačného kódu správy MAC, vypočítaného v režime CBC; Rozdiel je v tom, že pri výpočte prefixu imitácie sa nepoužíva synchronizačná správa, zatiaľ čo pri výpočte MAC sa použije inicializačný vektor.

Kryptografická sila algoritmu

V roku 1994 bol popis algoritmu GOST 28147-89 preložený do angličtiny a publikovaný; potom sa začali objavovať výsledky jeho analýzy, ktorú vykonali zahraniční odborníci; po značnú dobu sa však nenašli žiadne útoky blížiace sa uskutočniteľnosti.

□ veľká dĺžka kľúča - 256 bitov; spolu s tajnou synchronizačnou správou sa efektívna dĺžka kľúča zvyšuje na 320 bitov;

□ 32 kôl transformácií; už po 8 kolách sa dosiahne plný efekt rozptylu vstupných dát: zmena jedného bitu bloku otvoreného textu ovplyvní všetky bity bloku šifrovaného textu a naopak, t.j. existuje viacnásobná rezerva sily.

Pozrime sa na výsledky kryptoanalýzy algoritmu GOST 28147-89.

Analýza substitučných tabuliek

Keďže náhradné tabuľky nie sú v norme uvedené, množstvo prác (napríklad v) naznačuje, že „kompetentná organizácia“ môže vydať „dobré“ aj „zlé“ náhradné tabuľky. Slávny odborník Bruce Schneier však takéto predpoklady nazýva „fámami“. Je jasné, že kryptografická sila algoritmu do značnej miery závisí od vlastností použitých náhradných tabuliek, preto existujú slabé náhradné tabuľky (pozri príklad vyššie), ktorých použitie môže zjednodušiť útok na algoritmus. Napriek tomu sa možnosť použitia rôznych náhradných tabuliek javí ako veľmi hodnotný nápad, v prospech ktorého možno uviesť nasledujúce dva fakty z histórie šifrovacieho štandardu DES (podrobnosti pozri v časti 3.15):

□ útoky využívajúce lineárnu aj diferenciálnu kryptoanalýzu algoritmu DES využívajú špecifické vlastnosti náhradných tabuliek; pri použití iných tabuliek bude musieť kryptoanalýza začať odznova;

□ boli urobené pokusy posilniť DES proti lineárnej a diferenciálnej kryptoanalýze použitím robustnejších substitučných tabuliek; takéto tabuľky, ktoré sú skutočne robustnejšie, boli navrhnuté napríklad v algoritme s 5 DES; ale, bohužiaľ, nebolo možné nahradiť DES s 5 DES, pretože náhradné tabuľky sú striktne definované v štandarde, a preto implementácie algoritmu pravdepodobne nepodporujú schopnosť meniť tabuľky na iné.

Viaceré práce (napríklad , a ) chybne dospeli k záveru, že tajné náhradné tabuľky algoritmu GOST 28147-89 môžu byť súčasťou kľúča a môžu zvýšiť jeho efektívnu dĺžku (čo nie je podstatné, pretože algoritmus má veľmi veľké 256 -bitový kľúč). Práca však dokazuje, že tajné náhradné tabuľky možno vypočítať pomocou nasledujúceho útoku, ktorý sa dá prakticky použiť:

1. Nastaví sa nulový kľúč a vykoná sa vyhľadávanie „nulového vektora“, t. j. hodnota z = /(0), kde /() je okrúhla funkcia algoritmu. Táto fáza trvá približne 2 šifrovacie operácie.

2. Pomocou nulového vektora sa vypočítajú hodnoty náhradných tabuliek, čo nezaberie viac ako 2 11 operácií.

Úpravy algoritmov a ich analýza

Práca vykonala kryptoanalýzu modifikácií algoritmu GOST 28147-89:

□ Algoritmus GOST-H, v ktorom sa oproti pôvodnému algoritmu zmenilo poradie použitia podkľúčov, a to v kolách od 25 do 32 podkľúčov v priamom poradí, t.j. presne tak ako v predchádzajúcich kolách algoritmu;

□ 20-kolový algoritmus GOST®, v ktorom kolo používa na prekrytie kľúča XOR namiesto pridania modulo-2.

Na základe výsledkov analýzy sa dospelo k záveru, že GOST-H a GOST© sú slabšie ako pôvodný algoritmus GOST 28147-89, pretože oba majú triedy slabých kľúčov. Stojí za zmienku, že pokiaľ ide o kryptoanalýzu GOST©, práca doslovne opakuje časť venovanú kryptoanalýze algoritmu GOST 28147-89, známej práce publikovanej v roku 2000 (bez akýchkoľvek odkazov na originál). To spochybňuje profesionalitu autorov práce a jej ďalšie výsledky.

V práci bola navrhnutá veľmi zaujímavá modifikácia algoritmu: tabuľky S\…Ss musia byť nevyhnutne odlišné; v každom kole algoritmu musia byť preusporiadané podľa určitého zákona. Táto permutácia môže závisieť od šifrovacieho kľúča alebo môže byť aj tajná (t. j. môže byť súčasťou väčšieho šifrovacieho kľúča ako pôvodný 256-bitový kľúč). Obe tieto možnosti podľa ich autorov výrazne zvyšujú odolnosť algoritmu voči lineárnej a diferenciálnej kryptoanalýze.

A ešte jedna modifikácia týkajúca sa substitučných tabuliek je uvedená v práci, v ktorej je jedna z možné metódy výpočet náhradných tabuliek na základe šifrovacieho kľúča. Autori práce dospeli k záveru, že takáto závislosť oslabuje algoritmus, pretože vedie k prítomnosti slabých kľúčov a k niektorým potenciálnym zraniteľnostiam algoritmu.

Kompletná analýza algoritmov

Existujú aj útoky na celoobvodový GOST 28147-89 bez akýchkoľvek úprav. Jeden z prvých otvorené diela, v ktorej bola vykonaná analýza algoritmu, známa práca je venovaná útokom, ktoré využívajú slabiny postupu rozšírenia kľúča množstva známych šifrovacích algoritmov. Najmä úplný algoritmus GOST 28147-89 je možné prelomiť pomocou diferenciálnej kryptoanalýzy súvisiacich kľúčov, ale iba ak sa použijú slabé náhradné tabuľky. 24-kolová verzia algoritmu (v ktorej chýba prvých 8 kôl) sa otvára podobným spôsobom s akýmikoľvek náhradnými tabuľkami, ale silné náhradné tabuľky (napríklad tá uvedená) robia takýto útok úplne nepraktickým.

Domáci vedci A.G. Rostovtsev a E.B. Makhovenko v roku 2001 navrhli, že nová metóda kryptoanalýza (podľa autorov výrazne efektívnejšia ako lineárna a diferenciálna kryptanalýza) vytvorením objektívnej funkcie zo známeho otvoreného textu, zodpovedajúceho šifrového textu a požadovanej hodnoty kľúča a nájdením jej extrému zodpovedajúceho skutočnej hodnote kľúča. Našli tiež veľkú triedu slabých kľúčov algoritmu GOST 28147-89, ktoré umožňujú otvoriť algoritmus iba pomocou 4 vybraných otvorených textov a zodpovedajúcich šifrových textov s pomerne nízkou zložitosťou. V práci pokračuje kryptoanalýza algoritmu.

V roku 2004 skupina špecialistov z Kórey navrhla útok, ktorý pomocou diferenciálnej kryptoanalýzy súvisiacich kľúčov dokáže získať 12 bitov tajného kľúča s pravdepodobnosťou 91,7 %. Útok si vyžaduje 2 35 vybraných otvorených textov a 2 36 šifrovacích operácií. Ako vidíte, tento útok je prakticky nepoužiteľný na skutočné prelomenie algoritmu.

). Zároveň v ruských médiách a blogoch ruských používateľov rastie počet poznámok o tomto algoritme: pokrývajú výsledky útokov na ruský štandard s rôznym stupňom spoľahlivosti a obsahujú názory na jeho prevádzkové vlastnosti. Autori (a následne čitatelia) týchto poznámok majú často dojem, že domáci šifrovací algoritmus je zastaraný, pomalý a má slabé miesta, vďaka ktorým je výrazne náchylnejší na útoky ako zahraničné šifrovacie algoritmy s podobnou dĺžkou kľúča. S touto sériou poznámok by sme chceli prístupná forma hovoriť o súčasnom stave vecí s ruským štandardom. Prvá časť sa bude týkať všetkých útokov na GOST 28147-89 známych medzinárodnej kryptografickej komunite a súčasných hodnotení jej sily. V budúcich publikáciách sa bližšie pozrieme aj na vlastnosti normy z pohľadu schopnosti budovať efektívne implementácie.

Nicolas Courtois - "veľký a hrozný"

Začnime príbehom o činnosti Nicolasa Courtoisa, ktorý je autorom celej série diel venovaných ruskému štandardu blokového šifrovania ().

V októbri 2010 sa začal proces zvažovania začlenenia algoritmu GOST 28147-89 do medzinárodnej normy ISO/IEC 18033-3. Už v máji 2011 sa v elektronickom archíve ePrint objavil článok slávneho kryptografa Nicolasa Courtoisa, poznačený veľmi nejednoznačným postojom svetovej kryptografickej komunity k nemu. Courtoisove publikácie sú smutným príkladom manipulácie s pojmami, ktorá síce neodhaľuje žiadne nové vlastnosti predmetného predmetu, no s nárokom na senzáciu vyvoláva v nekompetentnom prostredí šírenie mylných názorov o jeho skutočných vlastnostiach.

Algebraická metóda

Courtoisove úvahy sú postavené na dvoch triedach kryptoanalytických metód: algebraických metódach a diferenciálnych metódach. Pozrime sa na prvú triedu metód.

Zjednodušene možno metódu algebraickej kryptoanalýzy opísať ako zostavenie a riešenie veľkého systému rovníc, z ktorých každé riešenie zodpovedá cieľu kryptoanalytika (ak je napríklad systém zostavený pomocou jednej dvojice otvoreného textu a šifrovaného textu, potom všetky riešenia tohto systému zodpovedajú kľúčom, ktorými sa tento otvorený text konvertuje na tento je zašifrovaný). To znamená, že v prípade problému kryptoanalýzy blokovej šifry je podstatou algebraickej metódy kryptoanalýzy to, že kľúč sa nájde ako výsledok riešenia systému polynomických rovníc. Hlavným problémom je, aby bolo možné zostaviť čo najviac, berúc do úvahy vlastnosti konkrétnej šifry. jednoduchý systém aby proces jeho riešenia trval čo najmenej času. Kľúčovú úlohu tu zohrávajú vlastnosti každej konkrétnej analyzovanej šifry.

Algebraická metóda použitá Courtoisom sa dá stručne opísať nasledovne. V prvej fáze sa takéto vlastnosti GOST 28147-89 používajú ako existencia pevného bodu pre časť transformácie šifrovania, ako aj takzvaný bod odrazu. Vďaka týmto vlastnostiam sa z dostatočne veľkého počtu párov otvoreného textu a šifrového textu vyberá niekoľko párov, ktoré umožňujú uvažovať o transformáciách nie pri 32, ale len pri 8 kolách. Druhá fáza spočíva v tom, že na základe výsledkov 8 kruhových transformácií získaných v prvej fáze je skonštruovaný systém nelineárnych rovníc, v ktorých sú kľúčové bity neznáme. Ďalej je tento systém vyriešený (to znie jednoducho, ale v skutočnosti je to časovo najnáročnejšia časť metódy, pretože systém pozostáva z nelineárnych rovníc).

Ako je uvedené vyššie, v práci sa nikde nenachádza Detailný popis a analýza zložitosti druhej a hlavnej fázy určovania kľúča. Práve zložitosť druhej etapy určuje zložitosť celej metódy ako celku. Namiesto toho autor uvádza notoricky známe „fakty“, na základe ktorých robí odhady náročnosti práce. Tieto „fakty“ sú vraj založené na experimentálnych výsledkoch. Rozbor „faktov“ z Courtoisovej tvorby ako celku je uvedený v tvorbe domácich autorov. Autori tejto práce poznamenávajú, že mnohé z Courtoisových „faktov“ prezentovaných bez akýchkoľvek dôkazov sa počas experimentálneho testovania ukázali ako nepravdivé. Autori článku zašli ďalej a po Courtoisovi vykonali analýzu zložitosti druhej etapy pomocou dobre podložených algoritmov a odhadov. Výsledné odhady zložitosti ukazujú úplnú nepoužiteľnosť prezentovaného útoku. Okrem domácich autorov boli v diele zaznamenané napríklad aj veľké problémy, ktoré má Courtois s hodnoteniami a zdôvodňovaním svojich metód.

Diferenciálna metóda

Uvažujme o druhej Courtoisovej metóde, ktorá je založená na diferenciálnej kryptoanalýze.

Všeobecná metóda diferenciálnej kryptoanalýzy je založená na využívaní vlastností nelineárnych zobrazení používaných v kryptografických primitívoch, spojených s vplyvom hodnoty kľúča na závislosti medzi rozdielmi medzi pármi vstupných a pármi výstupných hodnôt týchto zobrazení. . Opíšme hlavnú myšlienku diferenciálnej metódy kryptografickej analýzy blokovej šifry. Typicky blokové šifry transformujú vstupné dáta po etapách pomocou množstva takzvaných okrúhlych transformácií, pričom každá okrúhla transformácia nepoužíva celý kľúč, ale len jeho časť. Zoberme si trochu „oklieštenú“ šifru, ktorá sa od pôvodnej líši tým, že nemá posledné kolo. Predpokladajme, že bolo možné zistiť, že zašifrovanie dvoch otvorených textov, ktoré sa líšia v určitých pevných pozíciách pomocou takejto „skrátenej“ šifry, s najväčšou pravdepodobnosťou povedie k šifrovým textom, ktoré sa tiež líšia v niektorých pevných pozíciách. Táto vlastnosť ukazuje, že „skrátená“ šifra s najväčšou pravdepodobnosťou zanecháva závislosť medzi niektorými otvorenými textami a výsledkami ich šifrovania. Aby bolo možné obnoviť časť kľúča pomocou tejto zjavnej chyby, je potrebné vedieť zašifrovať vopred vybrané otvorené texty na kľúči, ktorý chceme obnoviť (takzvaný „útok so zvoleným otvoreným textom“). Na začiatku postupu „otvárania kľúča“ sa náhodne vygeneruje niekoľko párov otvorených textov, ktoré sa líšia v rovnakých pevných pozíciách. Všetky texty sú šifrované pomocou „úplnej“ šifry. Výsledné páry šifrovaného textu sa použijú na obnovenie tých kľúčových bitov, ktoré boli použité v poslednej transformácii cyklu, a to nasledovne. Pomocou náhodne vybranej hodnoty požadovaných kľúčových bitov sa na všetky šifrové texty aplikuje transformácia inverzná k transformácii posledného kola. V skutočnosti, ak sme uhádli požadovanú hodnotu bitov kľúča, dostaneme výsledok „skrátenej“ šifry, a ak sme neuhádli, v skutočnosti „zašifrujeme dáta ešte viac“, čo len zníži závislosť medzi blokmi uvedená vyššie (rozdiel je v niektorých pevných polohách). Inými slovami, ak medzi výsledkami takéhoto „dodatočného spracovania“ šifrových textov bolo pomerne veľa párov, ktoré sa líšia v nám známych pevných pozíciách, znamená to, že sme uhádli požadované kľúčové bity. Inak bude takýchto párov podstatne menej. Keďže v každom kole sa používa iba časť kľúča, nie je toľko vyhľadávaných bitov (t. j. bitov kľúča použitých v poslednom kole), koľko je bitov v v plnom kľúči a môžete ich jednoducho triediť opakovaním vyššie uvedených krokov. V tomto prípade raz určite natrafíme na správny význam.

Z vyššie uvedeného popisu vyplýva, že najdôležitejšou vecou v metóde diferenciálnej analýzy sú počty práve tých pozícií v otvorených textoch a šifrových textoch, pričom rozdiely v nich hrajú kľúčovú úlohu pri obnove kľúčových bitov. Zásadná prítomnosť týchto pozícií, ako aj množina ich čísel, priamo závisí od vlastností tých nelineárnych transformácií, ktoré sa používajú v ktorejkoľvek blokovej šifre (zvyčajne je všetka „nelinearita“ sústredená v tzv. S-boxoch resp. náhradné uzly).

Courtois používa mierne upravenú verziu diferenciálnej metódy. Okamžite si všimnime, že Courtois vykonáva svoju analýzu pre S-boxy, ktoré sa líšia od súčasných a od tých, ktoré sú navrhnuté v ISO. Práca poskytuje diferenciálne charakteristiky (tie čísla, v ktorých by sa bloky mali líšiť) pre malý počet kôl. Zdôvodnenie rozšírenia charakteristík na viac kôl je ako obvykle založené na „faktoch“. Courtois vyjadruje opäť ničím iným ako svojou autoritou nepodložený predpoklad, že zmena S-boxov neovplyvní odolnosť GOST 28147-89 proti jeho útoku (zatiaľ čo z neznámych dôvodov S-boxy z 1. pracovného návrhu doplnenie normy ISO/IEC 18033-3 sa neuvažovalo). Analýza vykonaná autormi článku ukazuje, že aj keď vezmeme Courtoisove nepodložené „fakty“ o viere a analyzujeme GOST 28147-89 s inými S-blokmi, útok sa opäť ukáže byť o nič lepší ako úplné vyhľadávanie.

V prácach bola vykonaná podrobná analýza Courtoisových prác s podrobným zdôvodnením neopodstatnenosti všetkých vyhlásení o znížení odolnosti ruského štandardu [,].

Zároveň aj samotný Courtois priznáva absolútnu nepresnosť vo výpočtoch! Nasledujúca snímka je prevzatá z Courtoisovej prezentácie na krátkej sekcii FSE 2012.

Treba poznamenať, že Courtoisovu prácu opakovane kritizovali aj zahraniční výskumníci. Napríklad jeho práca na konštrukcii útokov na blokový šifrovací algoritmus AES pomocou metódy XSL obsahovala rovnaké základné nedostatky ako práca na analýze ruského štandardu: väčšina odhadov náročnosti práce sa v texte objavuje úplne nepodložená a nepodložená - podrobná kritiku možno nájsť napríklad v práci. Okrem toho sám Courtois priznáva, že často odmieta publikovať svoju prácu na veľkých konferenciách o kryptografii a v zavedených recenzovaných časopisoch, pričom mu často ponecháva len príležitosť vystúpiť v sekcii s krátkym oznámením. Môžete si o tom napríklad prečítať v časti 3 práce. Tu je niekoľko citátov od samotného Courtoisa týkajúcich sa jeho práce:

• "Myslím si, že publikum Asiacrypt nebude mať pocit, že je to zaujímavé." Recenzent Asiacrypt 2011.
• „...je tu veľký, veľký, veľký problém: tento útok, ktorý je hlavným prínosom tohto článku, už bol publikovaný na FSE’11 (bol to dokonca najlepší článok), ...“. Recenzent pre Crypto 2011.

Odborná časť medzinárodnej kryptografickej komunity teda o kvalite Courtoisovej práce nepochybuje menej ako povedzme vyjadrenia niektorých ruských špecialistov o ich schopnosti prelomiť AES za 2 100, ktoré nepotvrdzujú žiadne konzistentné výpočty, resp. najnovší „dôkaz“ dvojstranovej hypotézy o nerovnosti tried zložitosti P a NP.

Útoky Isobe a Dinur-Dankelman-Shamir

Všeobecnou myšlienkou útokov Isobe () a Dinur-Dankelman-Shamir (ďalej len: útok DDS) () je vytvoriť pre určitú (kľúčovo závislú) úzku množinu otvorených textov ekvivalentnú transformáciu na tejto množine, ktorá má štruktúra je jednoduchšia ako samotná transformácia šifrovania. V prípade metódy Isobe ide o množinu 64-bitových blokov x takých, že F 8 -1 (Swap(F 8 (z))) = z, kde z = F 16 (x), až F 8 ( x) a F 16 ( x) označujú prvých 8 a prvých 16 kôl šifrovania GOST 28147-89 prostredníctvom Swap - operácie výmeny polovíc 64-bajtového slova. Ak je v tomto súbore zahrnutý otvorený text, výsledok úplnej 32-kolovej transformácie GOST 28147-89 sa zhoduje s výsledkom 16-kolovej, čo autor útoku využíva. V prípade metódy DDS je to množina x taká, že F 8 (x) = x (pevný bod transformácie F 8). Pre akýkoľvek otvorený text z tejto sady funguje transformácia GOST 28147-89 presne rovnako ako posledných 8 kôl, čo zjednodušuje analýzu.

Zložitosť útoku Isobe je 2 224 šifrovacích operácií, útok DDS je 2 192. Všetky otázky o tom, či útoky Isobe a DDS zavádzajú nové obmedzenia podmienok používania nášho algoritmu, sú však odstránené posúdením požiadaviek na objem materiálu potrebného na vykonanie každého z útokov: metóda Isobe vyžaduje 2 32 párov otvoreného textu. a šifrový text a pre metódu DDS - 2 64. Spracovanie takýchto objemov materiálu bez zmeny kľúča je a priori neprijateľné pre akúkoľvek blokovú šifru s dĺžkou bloku 64: na materiáli s objemom 2 32, berúc do úvahy problém narodenín (pozri napr. ), pravdepodobnosť výskytu opakovaných blokov sa blíži k 1/2, čo poskytne útočníkovi možnosť vyvodiť určité závery o otvorených textoch zo zašifrovaných textov bez toho, aby musel určiť kľúč. Prítomnosť 2 64 párov obyčajných a zašifrovaných textov získaných na jednom kľúči v skutočnosti umožňuje nepriateľovi vykonávať šifrovacie a dešifrovacie operácie bez toho, aby tento kľúč vôbec poznal. Je to spôsobené čisto kombinatorickou vlastnosťou: nepriateľ má v tomto prípade celú tabuľku prevodu šifrovania. Táto situácia je absolútne neprijateľná za akýchkoľvek primeraných prevádzkových podmienok. Napríklad v CryptoPro CSP Existuje technické obmedzenie objemu šifrovaného materiálu (bez konverzie kľúča) na 4 MB (pozri). Prísny zákaz používania kľúča na materiáli takého objemu je teda súčasťou každej blokovej šifry s dĺžkou bloku 64 bitov, a preto útoky Isobe a DDS nijako nezužujú rozsah použitia algoritmu GOST 28147-89. pri zachovaní maximálnej možnej pevnosti 2 256.

Samozrejme, treba poznamenať, že výskumníci (Isobe a Dinur-Dankelman-Shamir) ukázali, že niektoré vlastnosti algoritmu GOST 28147-89 umožňujú nájsť cesty analýzy, ktoré tvorcovia algoritmu nezohľadnili. Jednoduchá forma plánu kľúčov, ktorá výrazne zjednodušuje úlohu konštrukcie efektívnych implementácií, tiež umožňuje v niektorých zriedkavých prípadoch kľúčov a otvorených textov vytvoriť viac jednoduché popisy transformácie vykonávané algoritmom.

Práca demonštruje, že túto negatívnu vlastnosť algoritmu možno ľahko eliminovať pri plnom zachovaní prevádzkových charakteristík, no, žiaľ, je neoddeliteľnou súčasťou algoritmu v jeho bežne používanej podobe.

Všimnite si, že určitá nedbanlivosť v odhadoch priemernej intenzity práce je prítomná aj v práci Dinura, Dunkelmana a Shamira. Pri konštrukcii útoku sa teda nevenuje náležitá pozornosť nasledujúcemu bodu: pre značnú časť kláves je množina otvorených textov x, teda F 8 (x) = x, prázdna: jednoducho tam nemusia byť žiadne pevné body. na 8 kôl transformácie. Existencia pevných bodov závisí aj od výberu náhradných uzlov. Útok je teda použiteľný len pre určité náhradné uzly a kľúče.

Za zmienku stojí ešte jedna práca s útokom na GOST 28147-89. Vo februári 2012 sa objavil elektronický archív ePrint medzinárodnej kryptografickej asociácie aktualizovaná verziačlánok (z novembra 2011), ktorý obsahoval nový útok na GOST 28147-89. Charakteristiky prezentovaného útoku sú nasledovné: objem materiálu je 2 32 (ako Isobe) a pracovná náročnosť je 2 192 (ako DDS). Tento útok teda zlepšil časový rekord útoku DDS z hľadiska objemu materiálu z 2 64 na 2 32. Samostatne poznamenávame, že autori poctivo prezentovali všetky výpočty s odôvodnením zložitosti a objemu materiálu. Po 9 mesiacoch bola vo vyššie uvedených výpočtoch zistená zásadná chyba a od novembra 2012 aktualizovaná verzia článku v elektronickom archíve už neobsahuje žiadne výsledky týkajúce sa domáceho algoritmu.

Útoky za predpokladu, že útočník vie „niečo“ o kľúčoch

Nakoniec poznamenávame, že v literatúre existuje aj množstvo prác (pozri napríklad a ) venovaných útokom na GOST 28147-89 v takzvanom prepojenom kľúčovom modeli. Tento model v zásade obsahuje predpoklad, že útočník môže získať prístup na analýzu nielen k párom otvoreného textu a zašifrovaného pomocou požadovaného kľúča, ale aj k párom otvoreného textu a šifrovaného textu získaného pomocou (tiež neznámych) kľúčov, ktoré sa líšia od hľadaného v známom regulárnom spôsobom (napríklad na pevných pozíciách bitov). V tomto modeli je skutočne možné získať zaujímavé výsledky o GOST 28147-89, avšak v tomto modeli nie je možné získať nemenej silné výsledky napríklad o tom, čo sa najčastejšie používa v moderných sieťach. bežné používanieŠtandard AES (pozri napríklad). Všimnite si, že podmienky na vykonanie tohto typu útoku vznikajú pri použití šifry v určitom protokole. Treba poznamenať, že výsledky tohto druhu, hoci sú z hľadiska štúdia vlastností kryptografických transformácií nepochybným akademickým záujmom, v skutočnosti nie sú pre prax relevantné. Napríklad všetky nástroje na ochranu kryptografických informácií certifikované FSB Ruska spĺňajú najprísnejšie požiadavky na schémy generovania šifrovacích kľúčov (pozri napríklad). Ako je uvedené vo výsledkoch analýzy, ak existuje 18 priradených kľúčov a 2 10 párov blokov otvoreného textu a šifrového textu, zložitosť úplného otvorenia súkromného kľúča s pravdepodobnosťou úspechu 1-10-4 je v skutočnosti 2 26 . Ak sú však splnené vyššie uvedené požiadavky na vývoj kľúčového materiálu, pravdepodobnosť nájdenia takýchto kľúčov je 2 -4352, teda 24096-krát menšia, ako keď sa jednoducho pokúsite uhádnuť tajný kľúč na prvý pokus.

K dielam súvisiacim s modelom s prepojenými kľúčmi patrí aj práca, ktorá v roku 2010 spôsobila veľký hluk v ruských elektronických publikáciách, ktoré si netrpia zvykom starostlivo kontrolovať materiál v pretekoch o senzácie. Výsledky v ňom uvedené neboli podložené žiadnym rigoróznym odôvodnením, obsahovali však hlasné vyhlásenia o možnosti hacknutia štátnej normy Ruská federácia na slabom notebooku v priebehu niekoľkých sekúnd - vo všeobecnosti bol článok napísaný v najlepších tradíciách Nicolasa Courtoisa. Ale napriek absolútne zjavnej neopodstatnenosti článku pre čitateľa, ktorý je viac-menej oboznámený so základnými princípmi vedeckých publikácií, práve na uistenie ruskej verejnosti po práci Rudsky napísal podrobný a dôkladný text obsahujúci komplexnú analýzu. tohto nedostatku. Článok so samovysvetľujúcim názvom „O nulovom praktickom význame práce „Útok na obnovenie kľúča na úplnú blokovú šifru GOST s nulovým časom a pamäťou““ poskytuje odôvodnenie, že priemerná zložitosť metódy uvedenej v tomto dokumente nie je menšia ako zložitosť. o kompletnom hľadaní.

Suchý zvyšok: aká je trvanlivosť v praxi?

Na záver uvádzame tabuľku obsahujúcu údaje o všetkých výsledkoch prísne opísaných a odôvodnených útokov na GOST 28147-89 známych medzinárodnej kryptografickej komunite. Všimnite si, že zložitosť je daná v šifrovacích operáciách algoritmu GOST 28147-89 a pamäť a materiál sú uvedené v blokoch algoritmu (64 bitov = 8 bajtov).

Útok	Intenzita práce	Pamäť	Potrebný 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äťou	2 204	2 19	2 64
	2 224	2 36	2 32
Dinur-Dankelman-Shamir, Reflection, 2DMitM	2 236	2 19	2 32
Dokončite vyhľadávanie	2 256	1	4
Počet nanosekúnd od stvorenia vesmíru	2 89

Napriek pomerne rozsiahlemu cyklu výskumu v oblasti stability algoritmu GOST 28147-89, tento moment Nie je známy jediný útok, ktorý by bol dosiahnuteľný pri prevádzkových požiadavkách na dĺžku 64-bitového bloku. Obmedzenia objemu materiálu, ktorý je možné spracovať na jednom kľúči, vyplývajúce z parametrov šifry (dĺžka bitu kľúča, dĺžka bitu bloku) sú výrazne prísnejšie ako minimálny objem potrebný na vykonanie akéhokoľvek aktuálne známeho útoku. V dôsledku toho pri splnení existujúcich prevádzkových požiadaviek žiadna z doteraz navrhovaných metód kryptoanalýzy podľa GOST 28147-89 neumožňuje určiť kľúč s náročnosťou menšou ako vyčerpávajúce vyhľadávanie.