GOST 28147 89-algoritmen är. Inhemsk datakrypteringsstandard. Variationer på temat gästen
Till skillnad från den amerikanska DES använder den inhemska standarden en längre nyckel - 256 bitar. Dessutom föreslår den ryska standarden att man använder 32 omgångar av kryptering, medan DES bara kräver 16.
Således är huvudparametrarna för GOST 28147-89-algoritmen för kryptografisk datatransformation som följer: blockstorleken är 64 bitar, nyckelstorleken är 256 bitar, antalet rundor är 32.
Algoritmen är ett klassiskt Feishtel-nätverk. Det krypterade datablocket är uppdelat i två identiska delar, höger R och vänster L. Den högra delen läggs till den runda undernyckeln och krypterar, med hjälp av någon algoritm, den vänstra delen. Inför nästa omgång byts vänster och höger del. Denna struktur gör att samma algoritm kan användas för både kryptering och dekryptering av ett block.
Krypteringsalgoritmen använder följande operationer:
- tillägg av ord modulo 2 32;
- cykliskt flytta ordet åt vänster med det specificerade antalet bitar;
- bitvis addition modulo 2;
- byte enligt tabellen.
I olika steg av GOST-algoritmer tolkas och används data som de arbetar på på olika sätt. I vissa fall behandlas dataelement som arrayer av oberoende bitar, i andra fall som ett heltal utan tecken, i andra som att de har en struktur komplext element, bestående av flera enklare element.
Rund struktur GOST 28147-89
Strukturen för en omgång av GOST 28147-89 visas i fig. 5.1.
Det krypterade datablocket delas upp i två delar, som sedan behandlas som separata 32-bitars osignerade heltal. Först läggs den högra halvan av blocket och undernyckeln till omgången till modulo 2 32. Därefter utförs block för block substitution. 32-bitarsvärdet som erhölls i föregående steg (låt oss kalla det S) tolkas som en matris med åtta 4-bitars kodblock: S=(S0,S1,S2,S3,S4,S5,S6,S7). Därefter ersätts värdet för vart och ett av de åtta blocken med ett nytt, som väljs från ersättningstabellen enligt följande: värdet på blocket Si ersätts av det Si-te elementet i ordning (numrering från noll) av den i:te ersättningsnoden (dvs. de i:te radens ersättningstabeller, numrering också från början). Med andra ord, ett element med ett radnummer lika med numret på blocket som ersätts och ett kolumnnummer lika med värdet på blocket som ersätts som ett 4-bitars icke-negativt heltal väljs som en ersättning för värdet på kvarteret. Varje rad i ersättningstabellen innehåller siffror från 0 till 15 i slumpmässig ordning utan upprepning. Värdena för substitutionstabellelementen tas från 0 till 15, eftersom de fyra bitarna som ersätts kan innehålla ett heltal utan tecken i intervallet från 0 till 15. Till exempel kan den första raden i en S-box innehålla följande värden: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . I detta fall kommer värdet på blocket So (de fyra minst signifikanta bitarna av 32-bitarstalet S) att ersättas med talet vid positionen vars nummer är lika med värdet på blocket som ersätts. Om S 0 = 0 kommer det att ersättas med 5, om S 0 = 1 kommer det att ersättas med 8 osv.
Ris. 5.1.
Efter att substitution har utförts sammanfogas alla 4-bitars block igen till ett enda 32-bitars ord, som sedan roteras 11 bitar åt vänster. Slutligen, med hjälp av den bitvisa operationen "summa modulo 2" resultatet kombineras med den vänstra halvan, vilket resulterar i en ny högerhalva av R i . Den nya vänstra sidan Li tas lika med den låga delen av det konverterade blocket: Li = R i-1 .
Det resulterande värdet av det konverterade blocket betraktas som resultatet av en omgång av krypteringsalgoritmen.
Kryptering och dekryptering
GOST 28147-89 är därför ett blockchiffer Datakonvertering utförs i block i den s.k grundläggande cykler. Grundslingor består av upprepad exekvering av huvudomgången vi diskuterade tidigare för ett datablock, med olika nyckelelement och skiljer sig från varandra i den ordning som nyckelelementen används. Varje omgång använder en av åtta möjliga 32-bitars undernycklar.
Låt oss titta på processen att skapa runda undernycklar. I GOST är denna procedur mycket enkel, särskilt jämfört med DES. 256-bitarsnyckeln K är uppdelad i åtta 32-bitars undernycklar, betecknade K0, K1, K2,K3, K4, K5, K6, K7. Algoritmen inkluderar 32 omgångar, så varje undernyckel under kryptering används i fyra omgångar i den sekvens som presenteras i tabell 5.1.
| Runda | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Full konstruktion | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Runda | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| Full konstruktion | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Runda | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| Full konstruktion | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Runda | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| Full konstruktion | K 7 | K 6 | K5 | K 4 | K 3 | K2 | K 1 | K 0 |
Dekrypteringsprocessen utförs med samma algoritm som kryptering. Den enda skillnaden är i vilken ordning K i-undernycklarna används. Vid dekryptering måste undernycklarna användas i omvänd ordning, nämligen enligt vad som anges i
Denna algoritm är obligatorisk för användning som en krypteringsalgoritm i statliga organisationer i Ryska federationen och ett antal kommersiella.
Beskrivning av algoritmen
Algoritmdiagrammet visas i fig. 3.1. Som du kan se är designen av denna algoritm ganska enkel, vilket tydligt förenklar implementeringen av mjukvaran eller hårdvaran.
GOST 28147-89-algoritmen krypterar information i block om 64 bitar, som är uppdelade i två underblock om 32 bitar (N1 och N2). Delblock N1 bearbetas på ett visst sätt, varefter dess värde adderas
med värdet av underblock N2 (addition utförs modulo 2), så byts underblocken. Denna transformation utförs i ett visst antal omgångar: 16 eller 32, beroende på algoritmens driftläge (beskrivs nedan). I varje omgång utförs följande operationer:
1. Nyckelapplikation. Innehållet i /VI-subblocket läggs till modulo 2 32 med en del av Kx-nyckeln.
Krypteringsnyckeln för GOST 28147-89-algoritmen har en dimension på 256 bitar, och Kx är dess 32-bitars del, dvs. 256-bitars krypteringsnyckel representeras som en sammanlänkning av 32-bitars undernycklar (Fig. 3.2):
Shch ATI, AG2, Yu, AG4, K5, Kb, K7.
Under krypteringsprocessen används en av dessa undernycklar, beroende på det runda numret och algoritmens driftläge.
Ris. 3.1. Algoritmdiagram GOST 28147-
Ris. 3.2. Krypteringsnyckel för GOST 28147-89-algoritmen
2. Bordsbyte. Efter nyckling delas /VI-delblocket i 8 delar om 4 bitar, vars värde ersätts individuellt i enlighet med ersättningstabellen för denna del av subblocket. Tabellersättningar (Substitution box, S-box) används ofta i moderna krypteringsalgoritmer, så det är värt att överväga dem mer i detalj.
Tabellsubstitution används på detta sätt: ett datablock av en viss storlek (i detta fall 4-bitars) tillförs ingången, vars numeriska representation bestämmer numret på utdatavärdet. Till exempel har vi en S-box av följande form:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
Låt 4-bitarsblocket "0100" komma till ingången, d.v.s. värdet 4. Enligt tabellen blir utmatningsvärdet lika med 15, d.v.s. "1111" (0 ersätts med 4, 1 mot 11, värdet på 2 förblir oförändrat, etc.).
Som du kan se är algoritmdesignen mycket enkel, vilket innebär att den största bördan av datakryptering faller på ersättningstabellerna. Tyvärr har algoritmen egenskapen att det finns "svaga" ersättningstabeller, med hjälp av vilka algoritmen kan lösas med kryptoanalytiska metoder. De svaga inkluderar till exempel en tabell där utdata är lika med input:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Bitvis cyklisk förskjutning åt vänster med 11 bitar.
Algoritm driftlägen
GOST 28147-89-algoritmen har 4 driftlägen:
□ enkelt ersättningsläge;
□ gammaläge;
P gammaläge med respons;
□ utvecklingssätt för imitationsfästen.
Dessa lägen skiljer sig något från de allmänt accepterade (beskrivna i avsnitt 1.4), så det är värt att överväga dem mer i detalj.
Dessa lägen har olika syften, men använder samma krypteringstransformation som beskrivs ovan.
Enkelt bytesläge
I enkelt ersättningsläge krypteras varje 64-bitars informationsblock helt enkelt med de 32 omgångarna som beskrivs ovan. 32-bitars undernycklar används i följande ordning:
□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI, etc. - i omgångarna 1 till 24;
□ K1, Kb, K5, K4, KZ, K2, K\, KO - i omgångar från 25 till 32.
Dekryptering i enkelt ersättningsläge utförs på exakt samma sätt, men med en något annorlunda sekvens av användning av undernycklar:
□ KO, K\, K2, KZ, K4, K5, Kb, KP - i omgångarna 1 till 8;
□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb, etc. - i omgångar från 9 till 32.
I likhet med standardläget ECB, på grund av den separata krypteringen av block, rekommenderas det enkla ersättningsläget absolut inte för att kryptera själva data; den bör endast användas för att kryptera andra krypteringsnycklar i flernyckelscheman.
Gamma-läge
I gammaläge (fig. 3.3) läggs varje klartextblock till bit för bit modulo 2 till ett 64-bitars chiffergammablock. Gammachifferet är en speciell sekvens som genereras med hjälp av de transformationer som beskrivs ovan enligt följande:
1. Deras initiala fyllning skrivs till registren N1 och N2 - ett 64-bitars värde som kallas "synkmeddelandet" (synkmeddelandet är praktiskt taget en analog till initialiseringsvektorn i CBC-, CFB- och OFB-lägena).
2. Innehållet i /VI- och N2-registren (i detta fall synkroniseringsmeddelanden) krypteras i enkelt ersättningsläge.
3. Innehållet i N1 adderas modulo (2 32 – 1) med konstanten CI = 2 24 + 2 16 + 2 8 + 4, resultatet av additionen skrivs till /VI-registret.
4. Innehållet i N2 adderas modulo 2 med konstanten C2 = 2 24 + 2 16 + 2 8 +1, resultatet av additionen skrivs till register N2.
5. Innehållet i /VI- och N2-registren matas ut som ett 64-bitars chiffergammablock (dvs. i detta fall bildar /VI och N2 det första gammablocket).
6. Om nästa gammablock behövs (dvs ytterligare kryptering eller dekryptering måste göras), gå tillbaka till steg 2.
För dekryptering genereras gamma på liknande sätt, sedan XOR-behandlas chiffertexten och gammabitarna igen.
För att generera samma chifferintervall måste användaren som dekrypterar kryptogrammet ha samma nyckel och samma synkroniseringsmeddelandevärde som användes vid kryptering av informationen. Annars kommer det inte att vara möjligt att hämta originaltexten från den krypterade.
I de flesta implementeringar av GOST 28147-89-algoritmen är synkroniseringsmeddelandet inte ett hemligt element, men synkroniseringsmeddelandet kan vara lika hemligt som krypteringsnyckeln. I det här fallet kan vi överväga att den effektiva nyckellängden för algoritmen (256 bitar) ökar med ytterligare 64 bitar av synkroniseringsmeddelandet, vilket kan betraktas som ett ytterligare nyckelelement.
Gammaläge med feedback
I gammaläget med återkoppling används resultatet av kryptering av det föregående blocket av klartext för att fylla /VI- och L/2-registren, med början från det andra blocket, inte det föregående gammablocket, utan resultatet av att kryptera det föregående klartextblocket (Fig. 3.4). Första kvarteret in detta läge genereras helt på samma sätt som den föregående.
Ris. 3.4. Generera ett chiffergamma i gammaläget med feedback
Imitationstillbehörsproduktionsläge
Ett prefix är en kryptografisk kontrollsumma som beräknas med hjälp av en krypteringsnyckel och utformad för att verifiera integriteten hos meddelanden. För att beräkna det finns det ett speciellt läge för GOST 28147-89-algoritmen.
Generering av ett imitationsprefix utförs på följande sätt:
1. Det första 64-bitarsblocket med information för vilket imitationsprefixet beräknas skrivs till registren N1 och N2 och krypteras i det reducerade enkla ersättningsläget, där de första 16 omgångarna av 32 utförs.
2. Det erhållna resultatet summeras modulo 2 med nästa informationsblock, varvid resultatet lagras i N1 och N2.
3. M och N2 krypteras igen i det förkortade enkla ersättningsläget, etc. till det sista informationsblocket.
Imitationsprefixet anses vara det 64-bitars resulterande innehållet i registren N1 och N2 eller del därav. Oftast används ett 32-bitars imitativt prefix, det vill säga hälften av innehållet i registren. Detta räcker, eftersom, precis som vilken kontrollsumma som helst, är imitationsbilagan först och främst avsedd att skydda mot oavsiktlig förvrängning av information. För att skydda mot avsiktlig modifiering av data används andra kryptografiska metoder - främst elektroniska digital signatur(se avsnitt 1.1).
Imitationsprefixet används enligt följande:
1. Vid kryptering av information beräknas klartextimitationsprefixet och skickas tillsammans med chiffertexten.
2. Efter dekryptering beräknas imitationsprefixet igen och jämförs med det som skickas.
3. Om de beräknade och skickade imitationsprefixen inte stämmer överens, förvrängdes chiffertexten under överföringen eller felaktiga nycklar användes under dekrypteringen.
Imitationsprefixet är särskilt användbart för att kontrollera korrekt dekryptering av nyckelinformation när du använder flernyckelscheman.
Imitationsprefixet är en analog av MAC-meddelandeautentiseringskoden, beräknad i CBC-läget; Skillnaden är att vid beräkning av imitationsprefixet används inte synkroniseringsmeddelandet, medan initialiseringsvektorn används vid beräkning av MAC.
Algoritm kryptografisk styrka
1994 översattes beskrivningen av GOST 28147-89-algoritmen till engelska och publicerades; det var efter detta som resultaten av dess analys, utförd av utländska specialister, började dyka upp; dock hittades inga attacker som närmade sig genomförbarheten under en längre tid.
□ stor nyckellängd - 256 bitar; tillsammans med det hemliga synkroniseringsmeddelandet ökar den effektiva nyckellängden till 320 bitar;
□ 32 omgångar av transformationer; redan efter 8 omgångar uppnås den fulla effekten av spridning av indata: att ändra en bit av klartextblocket kommer att påverka alla bitar av chiffertextblocket, och vice versa, det vill säga det finns en multipel styrka marginal.
Låt oss överväga resultaten av kryptoanalys av GOST 28147-89-algoritmen.
Analys av substitutionstabeller
Eftersom ersättningstabeller inte tillhandahålls i standarden, föreslår ett antal verk (till exempel i) att en "kompetent organisation" kan utfärda både "bra" och "dåliga" ersättningstabeller. Men den berömda experten Bruce Schneier kallar sådana antaganden "rykten". Det är tydligt att den kryptografiska styrkan hos algoritmen till stor del beror på egenskaperna hos de ersättningstabeller som används; följaktligen finns det svaga ersättningstabeller (se exempel ovan), vars användning kan förenkla attacken av algoritmen. Ändå verkar möjligheten att använda olika ersättningstabeller som en mycket värdig idé, till förmån för vilken följande två fakta från historien om DES-krypteringsstandarden kan citeras (för detaljer, se avsnitt 3.15):
□ attacker som använder både linjär och differentiell kryptoanalys av DES-algoritmen använder specifika egenskaper hos ersättningstabeller; när du använder andra tabeller måste kryptoanalys börja om;
□ försök har gjorts att stärka DES mot linjär och differentiell kryptoanalys genom att använda mer robusta substitutionstabeller; sådana tabeller, som verkligen är mer robusta, föreslogs till exempel i s 5 DES-algoritmen; men tyvärr var det omöjligt att ersätta DES med s 5 DES, eftersom ersättningstabellerna är strikt definierade i standarden, och följaktligen stöder implementeringar av algoritmen förmodligen inte möjligheten att ändra tabeller till andra.
Ett antal verk (till exempel, och ) drar felaktigt slutsatsen att de hemliga ersättningstabellerna för GOST 28147-89-algoritmen kan vara en del av nyckeln och öka dess effektiva längd (vilket inte är signifikant, eftersom algoritmen har en mycket stor 256 -bit nyckel). Men arbetet bevisar att hemliga ersättningstabeller kan beräknas med hjälp av följande attack, som kan användas praktiskt:
1. Nolltangenten sätts och sökningen efter "nollvektorn" utförs, det vill säga värdet z = /(0), där /() är algoritmens runda funktion. Detta steg tar cirka 2 krypteringsoperationer.
2. Med hjälp av nollvektorn beräknas värdena för ersättningstabellerna, vilket inte tar mer än 2 11 operationer.
Algoritmändringar och deras analys
Arbetet genomförde en kryptoanalys av ändringar av GOST 28147-89-algoritmen:
□ GOST-H-algoritm, i vilken, i förhållande till den ursprungliga algoritmen, ordningen för användning av undernycklar har ändrats, nämligen i omgångar från 25 till 32 undernycklar används i direkt ordning, d.v.s. exakt samma som i tidigare omgångar av algoritmen;
□ 20-round GOST®-algoritm, där en runda använder XOR istället för modulo-2-tillägg för att lägga över nyckeln.
Baserat på resultaten av analysen drogs slutsatsen att GOST-H och GOST© är svagare än den ursprungliga GOST 28147-89-algoritmen, eftersom båda har klasser av svaga nycklar. Det är värt att notera att när det gäller GOST©-krypteringsanalys, upprepar verket ord för ord avsnittet som ägnas åt kryptoanalysen av GOST 28147-89-algoritmen, ett välkänt verk som publicerades 2000 (utan några referenser till originalet). Detta ifrågasätter professionalismen hos författarna till verket och dess övriga resultat.
En mycket intressant modifiering av algoritmen föreslogs i arbetet: tabeller S\...Ss måste nödvändigtvis vara olika; i varje omgång av algoritmen måste de ordnas om enligt en viss lag. Denna permutation kan vara beroende av krypteringsnyckeln, eller så kan den också vara hemlig (dvs. vara en del av en större krypteringsnyckel än den ursprungliga 256-bitarsnyckeln). Båda dessa alternativ, enligt deras författare, ökar avsevärt motståndet hos algoritmen mot linjär och differentiell kryptoanalys.
Och ytterligare en modifiering relaterad till substitutionstabeller ges i arbetet, där en av möjliga metoder beräkning av ersättningstabeller baserat på krypteringsnyckeln. Författarna till arbetet drog slutsatsen att ett sådant beroende försvagar algoritmen, eftersom det leder till närvaron av svaga nycklar och till vissa potentiella sårbarheter i algoritmen.
Helrunda algoritmanalys
Det finns också attacker på full-round GOST 28147-89 utan några ändringar. En av de första öppna verk, där en analys av algoritmen genomfördes, ett välkänt verk, ägnas åt attacker som utnyttjar svagheterna i nyckelexpansionsproceduren hos ett antal välkända krypteringsalgoritmer. I synnerhet kan hela GOST 28147-89-algoritmen brytas med hjälp av differentiell kryptoanalys på relaterade nycklar, men bara om svaga ersättningstabeller används. 24-rundsversionen av algoritmen (där de första 8 omgångarna saknas) öppnas på liknande sätt med eventuella ersättningstabeller, men starka ersättningstabeller (till exempel den som ges in) gör en sådan attack helt opraktisk.
Inhemska vetenskapsmän A.G. Rostovtsev och E.B. Makhovenko föreslog 2001 i sitt arbete att ny metod kryptoanalys (enligt författarna, betydligt effektivare än linjär och differentiell kryptoanalys) genom att bilda en objektiv funktion från en känd klartext, motsvarande chiffertext och det önskade nyckelvärdet och hitta dess extremum som motsvarar nyckelns sanna värde. De hittade också en stor klass av svaga nycklar av GOST 28147-89-algoritmen, som gör det möjligt att öppna algoritmen med endast 4 utvalda klartexter och motsvarande chiffertexter med en ganska låg komplexitet. Krypteringsanalys av algoritmen fortsätter i arbetet.
2004 föreslog en grupp specialister från Korea en attack som med hjälp av differentiell kryptoanalys på relaterade nycklar kan få 12 bitar av den hemliga nyckeln med en sannolikhet på 91,7 %. Attacken kräver 2 35 utvalda klartexter och 2 36 krypteringsoperationer. Som du kan se är denna attack praktiskt taget värdelös för att faktiskt bryta algoritmen.
). Samtidigt växer antalet anteckningar om denna algoritm i ryska medier och bloggar för ryska användare: både som täcker resultaten av attacker mot den ryska standarden med varierande grad av tillförlitlighet och innehåller åsikter om dess operativa egenskaper. Författarna (och följaktligen läsarna) av dessa anteckningar får ofta intrycket av att den inhemska krypteringsalgoritmen är föråldrad, långsam och har sårbarheter som gör den betydligt mer mottaglig för attacker än utländska krypteringsalgoritmer med liknande nyckellängd. Med denna serie av anteckningar skulle vi vilja tillgänglig form prata om det aktuella läget med den ryska standarden. Den första delen kommer att täcka alla attacker på GOST 28147-89 kända för det internationella kryptografiska samfundet och aktuella bedömningar av dess styrka. I kommande publikationer kommer vi även att titta närmare på standardens egenskaper utifrån förmågan att bygga effektiva implementeringar.
Nicolas Courtois - "den store och fruktansvärda"
Låt oss börja med en berättelse om aktiviteterna hos Nicolas Courtois, som är författare till en hel serie verk som ägnas åt den ryska blockkrypteringsstandarden ().
I oktober 2010 började processen med att överväga införandet av GOST 28147-89-algoritmen i den internationella standarden ISO/IEC 18033-3. Redan i maj 2011 dök en artikel av den berömda kryptografen Nicolas Courtois upp på ePrints elektroniska arkiv, märkt av en mycket tvetydig inställning till honom från världens kryptografiska community. Courtois publikationer är ett sorgligt exempel på manipulation av begrepp, som inte avslöjar några nya egenskaper hos föremålet i fråga, men med anspråk på sensation framkallar spridningen av felaktiga åsikter om dess faktiska egenskaper i en inkompetent miljö.
Algebraisk metod
Courtois resonemang är uppbyggt kring två klasser av kryptoanalysmetoder: algebraiska metoder och differentiella metoder. Låt oss titta på den första klassen av metoder.
På ett förenklat sätt kan metoden för algebraisk kryptoanalys beskrivas som sammanställning och lösning av ett stort ekvationssystem, vars lösningar motsvarar kryptoanalytikerns mål (till exempel om ett system kompileras med ett par av klartext och chiffertext, så motsvarar alla lösningar i detta system de nycklar där denna klartext konverteras till denna är krypterad). Det vill säga, när det gäller problemet med kryptoanalys av ett blockchiffer, är kärnan i den algebraiska metoden för kryptoanalys att nyckeln hittas som ett resultat av att lösa ett system av polynomekvationer. Den största svårigheten är att kunna komponera så många som möjligt, med hänsyn till egenskaperna hos ett visst chiffer. enkelt system så att processen att lösa det tar så kort tid som möjligt. Här spelas nyckelrollen av egenskaperna hos varje specifik chiffer som analyseras.
Den algebraiska metoden som används av Courtois kan kort beskrivas enligt följande. I det första steget används sådana egenskaper hos GOST 28147-89 som förekomsten av en fast punkt för en del av krypteringstransformationen, såväl som den så kallade reflektionspunkten. Tack vare dessa egenskaper väljs flera par från ett tillräckligt stort antal klartext-chiffertext-par, vilket gör det möjligt att överväga transformationer inte vid 32, utan endast vid 8 omgångar. Det andra steget är att, baserat på resultaten av 8 runda transformationer erhållna i det första steget, konstrueras ett system av olinjära ekvationer, där nyckelbitarna är okända. Därefter löses detta system (detta låter enkelt, men är i verkligheten den mest tidskrävande delen av metoden, eftersom systemet består av icke-linjära ekvationer).
Som nämnts ovan finns det ingenstans i arbetet en detaljerad beskrivning och analys av komplexiteten i det andra och huvudstadiet för att bestämma nyckeln. Det är komplexiteten i det andra steget som avgör komplexiteten för hela metoden som helhet. Istället ger författaren de ökända "fakta" på grundval av vilka han gör uppskattningar av arbetsintensiteten. Dessa "fakta" sägs vara baserade på experimentella resultat. En analys av "fakta" från Courtois verk som helhet ges i inhemska författares arbete. Författarna till detta arbete noterar att många av Courtois "fakta" som presenterades utan några bevis visade sig vara falska under experimentell testning. Författarna till artikeln gick längre och, efter Courtois, genomförde en analys av komplexiteten i det andra steget med hjälp av välgrundade algoritmer och uppskattningar. De resulterande komplexitetsuppskattningarna visar att den presenterade attacken är fullständigt otillämplig. Förutom inhemska författare noterades även de stora problem som Courtois har med bedömningar och motivering av sina metoder, till exempel i arbetet.
Differentiell metod
Låt oss överväga den andra Courtois-metoden, som är baserad på differentiell kryptoanalys.
Den allmänna metoden för differentiell kryptoanalys är baserad på utnyttjandet av egenskaperna hos icke-linjära mappningar som används i kryptografiska primitiver, förknippade med inverkan av nyckelvärdet på beroenden mellan skillnaderna mellan par av ingång och par av utgångsvärden för dessa mappningar . Låt oss beskriva huvudidén för den differentiella metoden för kryptografisk analys av ett blockchiffer. Vanligtvis transformerar blockchiffer indata i steg med hjälp av ett antal så kallade runda transformationer, och varje rund transformation använder inte hela nyckeln, utan bara en del av den. Låt oss betrakta ett något "stympat" chiffer, som skiljer sig från det ursprungliga genom att det inte har den sista omgången. Låt oss anta att det har varit möjligt att fastställa att kryptering av två klartexter som skiljer sig åt i vissa fasta positioner med hjälp av ett sådant ”avkortat” chiffer med största sannolikhet kommer att resultera i chiffertexter som också skiljer sig åt i vissa fasta positioner. Den här egenskapen visar att ett "stympat" chiffer med största sannolikhet lämnar ett beroende mellan vissa klartexter och resultaten av deras kryptering. För att återställa en del av nyckeln med detta uppenbara fel är det nödvändigt att kunna kryptera förvalda klartexter på nyckeln vi vill återställa (den så kallade "valda klartextattacken"). I början av "nyckelöppningen"-proceduren genereras ett antal par klartexter slumpmässigt, som skiljer sig åt i samma fasta positioner. Alla texter är krypterade med ett "fullständigt" chiffer. De resulterande chiffertextparen används för att återställa de nyckelbitar som användes i den senaste omvandlingen, enligt följande. Genom att använda något slumpmässigt utvalt värde av de önskade nyckelbitarna, appliceras en transformation invers till den sista omgångstransformationen på alla chiffertexter. Faktum är att om vi gissade det önskade värdet på nyckelbitarna, kommer vi att få resultatet av ett "avkortat" chiffer, och om vi inte gissade kommer vi faktiskt att "kryptera data ännu mer", vilket bara kommer att minska beroende mellan block som noterats ovan (skillnaden är i vissa fasta positioner). Med andra ord, om det bland resultaten av sådan "ytterligare bearbetning" av chiffertexter fanns ganska många par som skiljer sig åt i de fasta positioner som vi känner till, betyder det att vi har gissat de nödvändiga nyckelbitarna. Annars blir det betydligt färre sådana par. Eftersom endast en del av nyckeln används i varje omgång, finns det inte lika många sökta bitar (det vill säga nyckelbitarna som användes i den senaste omgången) som det finns bitar i i full nyckel och du kan helt enkelt sortera igenom dem genom att upprepa stegen ovan. I det här fallet kommer vi definitivt att snubbla över den korrekta betydelsen en dag.
Av ovanstående beskrivning följer att det viktigaste i differentialanalysmetoden är numren på just dessa positioner i klartext och chiffertext, vars skillnader spelar en nyckelroll för att återställa nyckelbitarna. Den grundläggande närvaron av dessa positioner, såväl som uppsättningen av deras nummer, beror direkt på egenskaperna hos de olinjära transformationer som används i alla blockchiffer (vanligtvis är all "olinjäritet" koncentrerad i de så kallade S-boxarna eller ersättningsnoder).
Courtois använder en något modifierad version av differentialmetoden. Låt oss omedelbart notera att Courtois gör sin analys för S-boxar som skiljer sig från de nuvarande och de som föreslagits i ISO. Verket ger differentiella egenskaper (de siffror där blocken ska skilja sig åt) för ett litet antal omgångar. Motiveringen för att utöka egenskaperna för fler omgångar är som vanligt baserad på ”fakta”. Courtois uttrycker, återigen, utan någonting annat än sin auktoritet, ett ounderbyggt antagande att byte av S-boxarna inte kommer att påverka motståndet hos GOST 28147-89 mot hans attack (medan S-boxarna av okända orsaker från det 1:a arbetsutkastet till tillägget till standarden ISO/IEC 18033-3 beaktades inte). Analysen som utfördes av artikelförfattarna visar att även om vi tar Courtois ogrundade "fakta" om tro och analyserar GOST 28147-89 med andra S-block, visar attacken sig återigen inte vara bättre än en fullständig sökning.
En detaljerad analys av Courtois verk med en detaljerad belägg för grundlösheten i alla påståenden om minskningen av motståndet hos den ryska standarden utfördes i verken [,].
Samtidigt medger även Courtois själv den absoluta bristen på noggrannhet i beräkningarna! Följande bild är hämtad från Courtois presentation på FSE 2012 kortvariga avsnitt.
Det bör noteras att Courtois arbete också upprepade gånger har kritiserats av utländska forskare. Till exempel innehöll hans arbete med att konstruera attacker på AES-blockkrypteringsalgoritmen med XSL-metoden samma grundläggande brister som arbetet med analysen av den ryska standarden: de flesta av aförekommer i texten helt ogrundade och ogrundade - detaljerade kritik finns till exempel i arbetet. Dessutom erkänner Courtois själv att han har vägrat att publicera sitt arbete vid stora kryptografikonferenser och i etablerade peer-reviewade tidskrifter, vilket ofta lämnar honom bara möjligheten att tala i avsnittet med korta tillkännagivanden. Detta kan du till exempel läsa om i avsnitt 3 i arbetet. Här är några citat från Courtois själv angående hans arbete:
- "Jag tror att publiken på Asiacrypt inte kommer att känna att det är intressant." Asiacrypt 2011 granskare.
- "... det finns ett stort, stort, stort problem: denna attack, som är tidningens huvudsakliga bidrag har redan publicerats på FSE'11 (det var till och med den bästa tidningen), ...". Recensent för Crypto 2011.
Således betraktar den professionella delen av det internationella kryptografiska samfundet kvaliteten på Courtois arbete med inte mindre tvivel än, låt säga, uttalanden från vissa ryska specialister om deras förmåga att knäcka AES för 2 100, som inte bekräftas av några konsekventa beräkningar, eller senaste "beviset" för en tvåsidig hypotes om ojämlikheten i komplexitetsklasserna P och NP.
Attacker av Isobe och Dinur-Dankelman-Shamir
Den allmänna idén med Isobe () och Dinur-Dankelman-Shamir-attackerna (hädanefter: DDS-attacken) () är att för en viss (nyckelberoende) smal uppsättning klartexter konstruera en likvärdig transformation på denna uppsättning, som har en struktur enklare än själva krypteringstransformationen. I fallet med Isobe-metoden är detta uppsättningen av 64-bitars block x så att F 8 -1 (Swap(F 8 (z))) = z, där z = F 16 (x), till F 8 ( x) och F 16 ( x) indikerar de första 8 och första 16 omgångarna av GOST 28147-89-kryptering, respektive genom Swap - operationen att byta halvor av ett 64-byte ord. Om klartexten ingår i denna uppsättning, sammanfaller resultatet av den fullständiga 32-omvandlingen av GOST 28147-89 med resultatet av den 16-runda, vilket är vad författaren till attacken utnyttjar. I fallet med DDS-metoden är detta mängden x så att F8(x) = x (fixpunkt för transformationen F8). För alla klartexter från denna uppsättning fungerar GOST 28147-89-transformationen exakt likadant som de senaste 8 omgångarna, vilket förenklar analysen.
Komplexiteten i Isobe-attacken är 2 224 krypteringsoperationer, DDS-attacken är 2 192. Alla frågor om huruvida Isobe- och DDS-attackerna inför nya begränsningar för villkoren för att använda vår algoritm tas dock bort genom att man bedömer kraven på den mängd material som krävs för att utföra var och en av attackerna: Isobe-metoden kräver 2 32 par klartext och chiffertext, och för DDS-metoden - 2 64. Att bearbeta sådana materialvolymer utan att ändra nyckeln är a priori oacceptabelt för alla blockchiffer med en blocklängd på 64: på material med volym 2 32 , med hänsyn till problemet med födelsedagar (se till exempel ), sannolikheten för att det inträffar av upprepade block är nära 1/2, vilket ger angriparen möjlighet att dra vissa slutsatser om klartexter från chiffertexterna utan att bestämma nyckeln. Närvaron av 2 64 par vanliga och krypterade texter som erhållits på en nyckel tillåter faktiskt fienden att utföra krypterings- och dekrypteringsoperationer utan att känna till denna nyckel alls. Detta beror på en rent kombinatorisk egenskap: fienden har i detta fall hela krypteringstabellen. Denna situation är absolut oacceptabel under alla rimliga driftsförhållanden. Till exempel i CryptoPro CSP Det finns en teknisk begränsning på volymen krypterat material (utan nyckelkonvertering) på 4 MB (se). Således är ett strikt förbud mot att använda en nyckel på material med sådan volym inneboende i alla blockchiffer med en blocklängd på 64 bitar, och därför begränsar Isobe- och DDS-attacker inte på något sätt användningsområdet för GOST 28147-89-algoritmen samtidigt som maximal styrka på 2 256 bibehålls.
Naturligtvis bör det noteras att forskare (Isobe och Dinur-Dankelman-Shamir) har visat att vissa egenskaper hos GOST 28147-89-algoritmen gör det möjligt att hitta analysvägar som inte togs i beaktande av skaparna av algoritmen. Den enkla formen av nyckelschemat, som avsevärt förenklar uppgiften att konstruera effektiva implementeringar, tillåter också några sällsynta fall av nycklar och klartexter för att konstruera fler enkla beskrivningar transformationer som utförs av algoritmen.
Arbetet visar att denna negativa egenskap hos algoritmen lätt kan elimineras med fullt bevarande av operativa egenskaper, men tyvärr är den en integrerad del av algoritmen i dess vanliga form.
Observera att viss försumlighet i uppskattningarna av den genomsnittliga arbetsintensiteten också förekommer i Dinur, Dunkelmans och Shamirs arbete. Sålunda, när man konstruerar en attack, ägnas inte vederbörlig uppmärksamhet åt följande punkt: för en betydande del av nycklar är uppsättningen klartext x, så att F 8 (x) = x, tom: det kan helt enkelt inte finnas några fasta punkter för 8 omgångar av transformation. Förekomsten av fasta punkter beror också på valet av ersättningsnoder. Därför är attacken endast tillämplig för vissa ersättningsnoder och nycklar.
Det är också värt att nämna ytterligare ett arbete med en attack på GOST 28147-89. I februari 2012 dök det internationella kryptografiska förbundets ePrint elektroniska arkiv upp uppdaterad version artikel (daterad november 2011), som innehöll en ny attack mot GOST 28147-89. Egenskaperna för den presenterade attacken är följande: materialvolymen är 2 32 (som Isobe) och arbetsintensiteten är 2 192 (som DDS). Således förbättrade denna attack den tidsrekorda DDS-attacken vad gäller materialvolym från 2 64 till 2 32. Vi noterar separat att författarna ärligt presenterade alla beräkningar med motivering för materialets komplexitet och volym. Efter 9 månader hittades ett grundläggande fel i ovanstående beräkningar, och sedan november 2012 innehåller den uppdaterade versionen av artikeln i det elektroniska arkivet inte längre några resultat angående den inhemska algoritmen.
Attacker förutsatt att angriparen vet "något" om nycklarna
Slutligen noterar vi att det i litteraturen också finns ett antal verk (se till exempel och ) som ägnas åt attacker mot GOST 28147-89 i den så kallade länkade nyckelmodellen. Den här modellen innehåller i grunden antagandet att en angripare kan få tillgång för analys inte bara till par av klartext och krypterad med den önskade nyckeln, utan också till par av klartext och chiffertext som erhålls med (också okända) nycklar som skiljer sig från den sökta i en känd vanlig sätt (till exempel vid fasta bitpositioner). I den här modellen är det verkligen möjligt att få intressanta resultat om GOST 28147-89, men i denna modell kan inte mindre starka resultat erhållas om till exempel vilken som används mest i moderna nätverk allmänt bruk AES-standard (se till exempel). Observera att förutsättningarna för att utföra denna typ av attack uppstår när ett chiffer används i ett visst protokoll. Det bör noteras att resultat av detta slag, även om de är av otvivelaktigt akademiskt intresse ur synvinkeln att studera egenskaperna hos kryptografiska transformationer, faktiskt inte är relevanta för praktiken. Till exempel uppfyller alla verktyg för krypteringsinformationsskydd certifierade av Rysslands FSB de strängaste kraven för system för generering av krypteringsnyckel (se till exempel). Som indikeras i resultaten av analysen, om det finns 18 associerade nycklar och 2 10 par klartext- och chiffertextblock, är komplexiteten i att helt öppna den privata nyckeln, med en sannolikhet för framgång på 1-10 -4, faktiskt 2 26 . Men om de ovan nämnda kraven för utveckling av nyckelmaterial uppfylls är sannolikheten att hitta sådana nycklar 2 -4352, det vill säga 24096 gånger mindre än om man helt enkelt försöker gissa den hemliga nyckeln vid första försöket.
Verk relaterade till modellen med länkade nycklar inkluderar också arbete, som 2010 orsakade mycket brus i ryska elektroniska publikationer, som inte lider av vanan att noggrant kontrollera materialet i kapplöpningen för sensationer. Resultaten som presenterades i den stöddes inte av någon rigorös motivering, men de innehöll högljudda uttalanden om möjligheten att hacka den statliga standarden Ryska Federationen på en svag bärbar dator på några sekunder - i allmänhet skrevs artikeln i Nicolas Courtois bästa traditioner. Men trots den absolut uppenbara grundlösheten i artikeln för den läsare som är mer eller mindre insatt i de vetenskapliga publikationernas grundläggande principer, var det just för att lugna den ryska allmänheten efter arbetet som Rudsky skrev en detaljerad och grundlig text innehållande en omfattande analys av denna brist. Artikeln med den självförklarande rubriken "Om verkets noll praktiska betydelse "Key recovery attack on full GOST block cipher with noll time and memory"" motiverar att den genomsnittliga komplexiteten för metoden som ges i är inte mindre än komplexiteten av en fullständig sökning.
Torra rester: vad är hållbarhet i praktiken?
Sammanfattningsvis presenterar vi en tabell som innehåller data om alla resultat av strikt beskrivna och motiverade attacker på GOST 28147-89 kända för det internationella kryptografiska samfundet. Observera att komplexiteten ges i krypteringsoperationerna för GOST 28147-89-algoritmen, och minnet och materialet indikeras i algoritmblock (64 bitar = 8 byte).
| Ge sig på | Arbetsintensitet | Minne | Nödvändigt material |
| Isobe | 2 224 | 2 64 | 2 32 |
| Dinur-Dankelman-Shamir, FP, 2DMitM | 2 192 | 2 36 | 2 64 |
| Dinur-Dankelman-Shamir, FP, svagt minne | 2 204 | 2 19 | 2 64 |
| 2 224 | 2 36 | 2 32 | |
| Dinur-Dankelman-Shamir, Reflektion, 2DMitM | 2 236 | 2 19 | 2 32 |
| Slutför sökningen | 2 256 | 1 | 4 |
| Antal nanosekunder sedan universums skapelse | 2 89 |
Trots en ganska storskalig forskningscykel inom stabilitetsområdet för GOST 28147-89-algoritmen, det här ögonblicket Det finns inte en enda attack känd som skulle kunna uppnås under operativa krav på en 64-bitars blocklängd. Restriktionerna för volymen av material som kan bearbetas på en nyckel till följd av chifferparametrarna (nyckelbitlängd, blockbitlängd) är betydligt strängare än den minimivolym som krävs för att utföra en för närvarande känd attack. Följaktligen, när de uppfyller befintliga operativa krav, tillåter ingen av de kryptoanalysmetoder som hittills föreslagits GOST 28147-89 att bestämma en nyckel med en arbetsintensitet som är mindre än uttömmande sökning.
