GOST 28147 89-algoritmen er. Innenlandsk datakrypteringsstandard. Variasjoner over temaet gjesten
I motsetning til den amerikanske DES, bruker den innenlandske standarden en lengre nøkkel - 256 biter. I tillegg foreslår den russiske standarden å bruke 32 runder med kryptering, mens DES bare krever 16.
Dermed er hovedparametrene til GOST 28147-89-algoritmen for kryptografisk datatransformasjon som følger: blokkstørrelse er 64 biter, nøkkelstørrelse er 256 biter, antall runder er 32.
Algoritmen er et klassisk Feishtel-nettverk. Den krypterte datablokken er delt inn i to identiske deler, høyre R og venstre L. Den høyre delen legges til den runde undernøkkelen og krypterer den venstre delen ved hjelp av en algoritme. Før neste runde byttes venstre og høyre del. Denne strukturen gjør at den samme algoritmen kan brukes til både kryptering og dekryptering av en blokk.
Krypteringsalgoritmen bruker følgende operasjoner:
- tillegg av ord modulo 2 32;
- syklisk skift ordet til venstre med det angitte antallet biter;
- bitvis addisjon modulo 2;
- utskifting i henhold til tabellen.
Ved forskjellige trinn i GOST-algoritmer blir dataene de opererer på tolket og brukt på forskjellige måter. I noen tilfeller behandles dataelementer som arrays av uavhengige biter, i andre tilfeller som et heltall uten fortegn, i andre som har en struktur komplekst element, bestående av flere enklere elementer.
Rund struktur GOST 28147-89
Strukturen til en runde med GOST 28147-89 er vist i fig. 5.1.
Den krypterte datablokken deles i to deler, som deretter behandles som separate 32-biters usignerte heltall. Først blir høyre halvdel av blokken og undernøkkelen til runden lagt til modulo 2 32. Deretter utføres blokk-for-blokk substitusjon. 32-bits verdien oppnådd i forrige trinn (la oss kalle det S) tolkes som en matrise med åtte 4-bits kodeblokker: S=(S0,S1,S2,S3,S4,S5,S6,S7). Deretter erstattes verdien av hver av de åtte blokkene med en ny, som velges fra erstatningstabellen som følger: verdien av blokken Si erstattes av det S i-te elementet i rekkefølge (nummerering fra null) av den i-te erstatningsnoden (dvs. de i-te raderstatningstabellene, nummerering også fra bunnen av). Med andre ord, et element med et radnummer lik nummeret på blokken som erstattes og et kolonnenummer lik verdien av blokken som erstattes som et 4-bits ikke-negativt heltall velges som erstatning for verdien av blokken. Hver linje i erstatningstabellen inneholder tall fra 0 til 15 i tilfeldig rekkefølge uten repetisjon. Verdiene til substitusjonstabellelementene er tatt fra 0 til 15, siden de fire bitene som erstattes kan inneholde et heltall uten fortegn i området fra 0 til 15. For eksempel kan den første raden i en S-boks inneholde følgende verdier: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . I dette tilfellet vil verdien av blokken S0 (de fire minst signifikante bitene av 32-bits nummeret S) erstattes med tallet på posisjonen hvis nummer er lik verdien til blokken som erstattes. Hvis S 0 = 0, vil den bli erstattet med 5, hvis S 0 = 1, vil den bli erstattet med 8, osv.
Ris. 5.1.
Etter at substitusjon er utført, blir alle 4-bits blokker sammenkoblet igjen til et enkelt 32-bits ord, som deretter roteres 11 biter til venstre. Til slutt bruker du den bitvise operasjonen "sum modulo 2" resultatet kombineres med venstre halvdel, noe som resulterer i en ny høyre halvdel av R i . Den nye venstresiden Li tas lik den lave delen av den konverterte blokken: Li = R i-1 .
Den resulterende verdien av den konverterte blokken betraktes som resultatet av én runde med krypteringsalgoritmen.
Kryptering og dekrypteringsprosedyrer
GOST 28147-89 er derfor et blokkchiffer datakonvertering utføres i blokker i den såkalte grunnleggende sykluser. Grunnsløyfer består av gjentatt utførelse av hovedrunden vi diskuterte tidligere for en datablokk, ved bruk av forskjellige nøkkelelementer og skiller seg fra hverandre i rekkefølgen nøkkelelementene brukes. Hver runde bruker en av åtte mulige 32-bits undernøkler.
La oss se på prosessen med å lage runde undernøkler. I GOST er denne prosedyren veldig enkel, spesielt sammenlignet med DES. 256-bits nøkkelen K er delt inn i åtte 32-biters undernøkler, betegnet K0, K1, K2,K3, K4, K5, K6, K7. Algoritmen inkluderer 32 runder, så hver undernøkkel under kryptering brukes i fire runder i sekvensen presentert i tabell 5.1.
| Rund | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Full konstruksjon | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Rund | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| Full konstruksjon | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Rund | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
| Full konstruksjon | K 0 | K 1 | K2 | K 3 | K 4 | K5 | K 6 | K 7 |
| Rund | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
| Full konstruksjon | K 7 | K 6 | K5 | K 4 | K 3 | K2 | K 1 | K 0 |
Dekrypteringsprosessen utføres ved hjelp av samme algoritme som kryptering. Den eneste forskjellen er rekkefølgen som K i-undernøklene brukes i. Ved dekryptering må undernøklene brukes i omvendt rekkefølge, nemlig som angitt i
Denne algoritmen er obligatorisk for bruk som en krypteringsalgoritme i regjeringsorganisasjoner i Den russiske føderasjonen og en rekke kommersielle.
Beskrivelse av algoritmen
Algoritmediagrammet er vist i fig. 3.1. Som du kan se, er utformingen av denne algoritmen ganske enkel, noe som tydelig forenkler implementeringen av programvare eller maskinvare.
GOST 28147-89-algoritmen krypterer informasjon i blokker på 64 biter, som er delt inn i to underblokker på 32 biter (N1 og N2). Underblokk N1 behandles på en bestemt måte, hvoretter verdien legges sammen
med verdien av underblokk N2 (tillegg utføres modulo 2), så byttes underblokkene. Denne transformasjonen utføres i et visst antall runder: 16 eller 32, avhengig av driftsmodusen til algoritmen (beskrevet nedenfor). I hver runde utføres følgende operasjoner:
1. Nøkkelapplikasjon. Innholdet i /VI-underblokken legges til modulo 2 32 med en del av Kx-nøkkelen.
Krypteringsnøkkelen til GOST 28147-89-algoritmen har en dimensjon på 256 biter, og Kx er dens 32-bits del, det vil si at 256-bits krypteringsnøkkel er representert som en sammenkobling av 32-bits undernøkler (fig. 3.2):
Shch ATI, AG2, Yu, AG4, K5, Kb, K7.
Under krypteringsprosessen brukes en av disse undernøklene, avhengig av det runde tallet og driftsmodusen til algoritmen.
Ris. 3.1. Algoritmediagram GOST 28147-
Ris. 3.2. Krypteringsnøkkelen til GOST 28147-89-algoritmen
2. Bordbytte. Etter inntasting deles /VI-delblokken inn i 8 deler av 4 biter, verdien av hver av dem erstattes individuelt i samsvar med erstatningstabellen for denne delen av underblokken. Tabellerstatninger (Substitusjonsboks, S-boks) brukes ofte i moderne krypteringsalgoritmer, så det er verdt å vurdere dem mer detaljert.
Tabellerstatning brukes på denne måten: en blokk med data av en viss størrelse (i dette tilfellet 4-bit) leveres til inngangen, hvis numeriske representasjon bestemmer nummeret på utgangsverdien. For eksempel har vi en S-boks med følgende form:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
La 4-bits blokken "0100" komme til inngangen, dvs. verdien 4. I følge tabellen vil utgangsverdien være lik 15, dvs. "1111" (0 erstattes av 4, 1 med 11, verdien av 2 forblir uendret, osv.).
Som du kan se, er algoritmedesignet veldig enkelt, noe som betyr at den største byrden med datakryptering faller på erstatningstabellene. Dessverre har algoritmen egenskapen at det er "svake" erstatningstabeller, ved hjelp av hvilke algoritmen kan løses med kryptoanalytiske metoder. Svake inkluderer for eksempel en tabell der utgangen er lik inngangen:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Bitvis syklisk forskyvning til venstre med 11 biter.
Algoritmedriftsmoduser
GOST 28147-89-algoritmen har 4 driftsmoduser:
□ enkel erstatningsmodus;
□ gammamodus;
P gammamodus med tilbakemelding;
□ modus for utvikling av imitasjonsvedlegg.
Disse modusene er noe forskjellige fra de generelt aksepterte (beskrevet i avsnitt 1.4), så det er verdt å vurdere dem mer detaljert.
Disse modusene har ulike formål, men bruk den samme krypteringstransformasjonen som beskrevet ovenfor.
Enkel utskiftingsmodus
I enkel erstatningsmodus krypteres hver 64-bits blokk med informasjon ganske enkelt ved å bruke de 32 rundene beskrevet ovenfor. 32-bits undernøkler brukes i følgende rekkefølge:
□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI, etc. - i runde 1 til 24;
□ K1, Kb, K5, K4, KZ, K2, K\, KO - i runder fra 25 til 32.
Dekryptering i enkel erstatningsmodus utføres på nøyaktig samme måte, men med en litt annen sekvens av bruk av undernøkler:
□ KO, K\, K2, KZ, K4, K5, Kb, KP - i runde 1 til 8;
□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb osv. - i runder fra 9 til 32.
I likhet med standard ECB-modus, på grunn av den separate krypteringen av blokker, er den enkle erstatningsmodusen strengt tatt ikke anbefalt for kryptering av selve dataene; den skal bare brukes til å kryptere andre krypteringsnøkler i flernøkkelskjemaer.
Gamma-modus
I gammamodus (fig. 3.3) blir hver klartekstblokk lagt til bit for bit modulo 2 til en 64-bits chiffer gammablokk. Gamma-chifferet er en spesiell sekvens som genereres ved hjelp av transformasjonene beskrevet ovenfor som følger:
1. Den første fyllingen deres skrives til registrene N1 og N2 - en 64-bits verdi kalt "synkroniseringsmeldingen" (synkroniseringsmeldingen er praktisk talt en analog av initialiseringsvektoren i CBC-, CFB- og OFB-modusene).
2. Innholdet i /VI- og N2-registrene er kryptert (i i dette tilfellet- synkronisering av meldinger) i enkel erstatningsmodus.
3. Innholdet i N1 legges til modulo (2 32 – 1) med konstanten CI = 2 24 + 2 16 + 2 8 + 4, resultatet av addisjonen skrives til /VI-registeret.
4. Innholdet i N2 legges til modulo 2 med konstanten C2 = 2 24 + 2 16 + 2 8 +1, resultatet av addisjonen skrives til register N2.
5. Innholdet i /VI- og N2-registrene sendes ut som en 64-bits chiffergammablokk (dvs. i dette tilfellet danner /VI og N2 den første gammablokken).
6. Hvis neste gammablokk er nødvendig (dvs. ytterligere kryptering eller dekryptering må gjøres), gå tilbake til trinn 2.
For dekryptering genereres gamma på lignende måte, deretter blir chifferteksten og gammabitene igjen XORed.
For å generere samme chifferområde, må brukeren som dekrypterer kryptogrammet ha samme nøkkel og samme synkroniseringsmeldingsverdi som ble brukt ved kryptering av informasjonen. Ellers vil det ikke være mulig å få tak i originalteksten fra den krypterte.
I de fleste implementeringer av GOST 28147-89-algoritmen er ikke synkroniseringsmeldingen et hemmelig element, men synkroniseringsmeldingen kan være like hemmelig som krypteringsnøkkelen. I dette tilfellet kan vi vurdere at den effektive nøkkellengden til algoritmen (256 biter) øker med ytterligere 64 biter av synkroniseringsmeldingen, som kan betraktes som et ekstra nøkkelelement.
Gamma-modus med tilbakemelding
I gammamodus med tilbakemelding brukes resultatet av kryptering av forrige blokk med klartekst til å fylle /VI- og L/2-registrene, med start fra den andre blokken, ikke den forrige gammablokken, men resultatet av kryptering av den forrige klartekstblokken (Fig. 3.4). Den første blokken inn denne modusen genereres helt på samme måte som den forrige.
Ris. 3.4. Generering av et chiffergamma i gammamodus med tilbakemelding
Imitert vedleggsgenereringsmodus
Et prefiks er en kryptografisk kontrollsum beregnet ved hjelp av en krypteringsnøkkel og designet for å verifisere integriteten til meldinger. For å beregne det er det en spesiell modus for GOST 28147-89-algoritmen.
Generering av et imitasjonsprefiks utføres som følger:
1. Den første 64-bits blokken med informasjon som imitasjonsprefikset beregnes for, skrives til registrene N1 og N2 og krypteres i den reduserte enkle erstatningsmodusen, der de første 16 rundene av 32 utføres.
2. Det oppnådde resultatet summeres modulo 2 med neste informasjonsblokk, og lagrer resultatet i N1 og N2.
3. M og N2 krypteres igjen i den forkortede enkle erstatningsmodusen osv. frem til siste informasjonsblokk.
Imitasjonsprefikset anses å være det 64-bits resulterende innholdet i registrene N1 og N2 eller deler av disse. Oftest brukes et 32-bits imitativt prefiks, det vil si halvparten av innholdet i registrene. Dette er nok, siden, som enhver kontrollsum, er imitasjonsvedlegget først og fremst ment å beskytte mot utilsiktet forvrengning av informasjon. For å beskytte mot forsettlig modifikasjon av data, brukes andre kryptografiske metoder – primært elektroniske digital signatur(se avsnitt 1.1).
Imitasjonsprefikset brukes som følger:
1. Ved kryptering av informasjon beregnes klartekst-imitasjonsprefikset og sendes sammen med chifferteksten.
2. Etter dekryptering blir imitasjonsprefikset igjen beregnet og sammenlignet med det som ble sendt.
3. Hvis de beregnede og sendte imitasjonsprefiksene ikke stemmer overens, ble chifferteksten forvrengt under overføring eller feil nøkler ble brukt under dekryptering.
Imitasjonsprefikset er spesielt nyttig for å sjekke riktig dekryptering av nøkkelinformasjon ved bruk av flernøkkelskjemaer.
Imitasjonsprefikset er en analog av MAC-meldingsautentiseringskoden, beregnet i CBC-modus; Forskjellen er at når man beregner imitasjonsprefikset, brukes ikke synkroniseringsmeldingen, mens initialiseringsvektoren brukes ved beregning av MAC.
Algoritme kryptografisk styrke
I 1994 ble beskrivelsen av GOST 28147-89-algoritmen oversatt til engelsk og publisert; det var etter dette at resultatene av analysen, utført av utenlandske spesialister, begynte å dukke opp; Det ble imidlertid ikke funnet noen angrep som nærmet seg gjennomførbarhet på lang tid.
□ stor nøkkellengde - 256 biter; sammen med den hemmelige synkroniseringsmeldingen øker den effektive nøkkellengden til 320 biter;
□ 32 runder med transformasjoner; allerede etter 8 runder oppnås den fulle effekten av spredning av inngangsdataene: endring av én bit av klartekstblokken vil påvirke alle biter av chiffertekstblokken, og omvendt, det vil si at det er en margin med flere styrker.
La oss vurdere resultatene av kryptoanalyse av GOST 28147-89-algoritmen.
Analyse av substitusjonstabeller
Siden erstatningstabeller ikke er gitt i standarden, antyder en rekke arbeider (for eksempel i) at en "kompetent organisasjon" kan utstede både "gode" og "dårlige" erstatningstabeller. Imidlertid kaller den berømte eksperten Bruce Schneier slike antakelser "rykter". Det er klart at den kryptografiske styrken til algoritmen i stor grad avhenger av egenskapene til erstatningstabellene som brukes, følgelig er det svake erstatningstabeller (se eksempel ovenfor), hvis bruk kan forenkle angrepet av algoritmen. Likevel virker muligheten for å bruke forskjellige erstatningstabeller som en veldig verdig idé, til fordel for hvilken følgende to fakta fra historien til DES-krypteringsstandarden kan siteres (for detaljer, se avsnitt 3.15):
□ angrep ved bruk av både lineær og differensiell kryptoanalyse av DES-algoritmen bruker spesifikke funksjoner for erstatningstabeller; når du bruker andre tabeller, må kryptoanalyse starte på nytt;
□ Det er gjort forsøk på å styrke DES mot lineær og differensiell kryptoanalyse ved å bruke mer robuste substitusjonstabeller; slike tabeller, som faktisk er mer robuste, ble foreslått, for eksempel i s 5 DES-algoritmen; men dessverre var det umulig å erstatte DES med s 5 DES, siden erstatningstabellene er strengt definert i standarden, og følgelig støtter implementeringer av algoritmen sannsynligvis ikke muligheten til å endre tabeller til andre.
En rekke arbeider (for eksempel , og ) konkluderer feilaktig at de hemmelige erstatningstabellene til GOST 28147-89-algoritmen kan være en del av nøkkelen og øke dens effektive lengde (noe som ikke er signifikant, siden algoritmen har en veldig stor 256 -bit nøkkel). Arbeidet beviser imidlertid at hemmelige erstatningstabeller kan beregnes ved å bruke følgende angrep, som praktisk talt kan brukes:
1. Nulltasten settes og søket etter "nullvektoren" utføres, dvs. verdien z = /(0), hvor /() er den runde funksjonen til algoritmen. Dette stadiet tar ca. 2 krypteringsoperasjoner.
2. Ved å bruke nullvektoren beregnes verdiene til erstatningstabellene, som ikke tar mer enn 2 11 operasjoner.
Algoritmemodifikasjoner og deres analyse
Arbeidet utførte en kryptoanalyse av modifikasjoner av GOST 28147-89-algoritmen:
□ GOST-H-algoritme, der, i forhold til den opprinnelige algoritmen, rekkefølgen for bruk av undernøkler er endret, nemlig i runder fra 25 til 32 undernøkler brukes i direkte rekkefølge, dvs. nøyaktig det samme som i tidligere runder av algoritmen;
□ 20-runders GOST®-algoritme, der en runde bruker XOR i stedet for modulo-2 addisjon for å overlegge nøkkelen.
Basert på resultatene av analysen ble det konkludert med at GOST-H og GOST© er svakere enn den originale GOST 28147-89-algoritmen, siden begge har klasser med svake nøkler. Det er verdt å merke seg at når det gjelder GOST©-krypteringsanalyse, gjentar verket ord for ord delen som er viet til kryptoanalysen av GOST 28147-89-algoritmen, et velkjent verk publisert i 2000 (uten noen referanser til originalen). Dette setter spørsmålstegn ved profesjonaliteten til forfatterne av verket og dets øvrige resultater.
En veldig interessant modifikasjon av algoritmen ble foreslått i arbeidet: tabeller S\...Ss må nødvendigvis være forskjellige; i hver runde av algoritmen må de omorganiseres i henhold til en bestemt lov. Denne permutasjonen kan være avhengig av krypteringsnøkkelen, eller den kan også være hemmelig (dvs. være en del av en større krypteringsnøkkel enn den opprinnelige 256-bits nøkkelen). Begge disse alternativene, ifølge deres forfattere, øker motstanden til algoritmen betydelig mot lineær og differensiell kryptoanalyse.
Og enda en modifikasjon knyttet til substitusjonstabeller er gitt i arbeidet, hvor en av mulige metoder beregning av erstatningstabeller basert på krypteringsnøkkelen. Forfatterne av arbeidet konkluderte med at en slik avhengighet svekker algoritmen, siden den fører til tilstedeværelsen av svake nøkler og til noen potensielle sårbarheter i algoritmen.
Helrunde algoritmeanalyse
Det er også angrep på full-round GOST 28147-89 uten noen modifikasjoner. En av de første åpne verk, der en analyse av algoritmen ble utført, et velkjent verk, er viet angrep som utnytter svakhetene ved nøkkelutvidelsesprosedyren til en rekke kjente krypteringsalgoritmer. Spesielt kan hele GOST 28147-89-algoritmen brytes ved hjelp av differensiell kryptoanalyse på relaterte nøkler, men bare hvis svake erstatningstabeller brukes. 24-runders versjonen av algoritmen (hvor de første 8 rundene mangler) åpnes på lignende måte med eventuelle erstatningstabeller, men sterke erstatningstabeller (for eksempel den som er gitt inn) gjør et slikt angrep helt upraktisk.
Innenlandske forskere A.G. Rostovtsev og E.B. Makhovenko i 2001 foreslo i sitt arbeid ny metode kryptanalyse (i følge forfatterne, betydelig mer effektiv enn lineær og differensiell kryptoanalyse) ved å danne en objektiv funksjon fra en kjent klartekst, den tilsvarende chifferteksten og den ønskede nøkkelverdien og finne dens ekstremum tilsvarende nøkkelens sanne verdi. De fant også en stor klasse med svake nøkler til GOST 28147-89-algoritmen, som gjør det mulig å åpne algoritmen ved å bruke bare 4 utvalgte klartekster og de tilsvarende chiffertekstene med en ganske lav kompleksitet. Krypteringsanalyse av algoritmen fortsetter i arbeidet.
I 2004 foreslo en gruppe spesialister fra Korea et angrep som ved hjelp av differensiell kryptoanalyse på relaterte nøkler kan få 12 biter av den hemmelige nøkkelen med en sannsynlighet på 91,7 %. Angrepet krever 2 35 utvalgte klartekster og 2 36 krypteringsoperasjoner. Som du kan se, er dette angrepet praktisk talt ubrukelig for å faktisk bryte algoritmen.
). Samtidig, i russiske medier og blogger til russiske brukere, øker antallet notater om denne algoritmen: både dekker resultatene av angrep på den russiske standarden med ulik grad av pålitelighet, og inneholder meninger om dens operasjonelle egenskaper. Forfatterne (og følgelig leserne) av disse notatene får ofte inntrykk av at den innenlandske krypteringsalgoritmen er utdatert, treg og har sårbarheter som gjør den betydelig mer utsatt for angrep enn utenlandske krypteringsalgoritmer med tilsvarende nøkkellengde. Med denne noteserien vil vi gjerne tilgjengelig form snakke om den nåværende situasjonen med den russiske standarden. Den første delen vil dekke alle angrep på GOST 28147-89 kjent for det internasjonale kryptografiske samfunnet og nåværende vurderinger av dens styrke. I fremtidige publikasjoner vil vi også se nærmere på egenskapene til standarden med tanke på evnen til å bygge effektive implementeringer.
Nicolas Courtois - "den store og forferdelige"
La oss starte med en historie om aktivitetene til Nicolas Courtois, som er forfatteren av en hel serie verk viet til den russiske blokkkrypteringsstandarden ().
I oktober 2010 begynte prosessen med å vurdere inkludering av GOST 28147-89-algoritmen i den internasjonale standarden ISO/IEC 18033-3. Allerede i mai 2011 dukket en artikkel av den berømte kryptografen Nicolas Courtois opp på ePrint elektroniske arkiv, preget av en svært tvetydig holdning til ham fra verdens kryptografiske miljø. Courtois' publikasjoner er et trist eksempel på manipulasjon av konsepter, som ikke avslører noen nye egenskaper ved det aktuelle objektet, men med krav på sensasjon provoserer ut spredning av feilaktige meninger om dets faktiske egenskaper i et inkompetent miljø.
Algebraisk metode
Courtois resonnement er bygget rundt to klasser av kryptoanalysemetoder: algebraiske metoder og differensielle metoder. La oss se på den første klassen av metoder.
På en forenklet måte kan metoden for algebraisk kryptoanalyse beskrives som kompilering og løsning av et stort system av ligninger, hvor hver av løsningene tilsvarer målet til kryptoanalytikeren (for eksempel hvis et system er kompilert ved bruk av ett par av klartekst og chiffertekst, så tilsvarer alle løsninger av dette systemet nøklene som denne klarteksten konverteres til denne er kryptert). Det vil si at når det gjelder problemet med kryptoanalyse av et blokkchiffer, er essensen av den algebraiske metoden for kryptoanalyse at nøkkelen blir funnet som et resultat av å løse et system med polynomlikninger. Den største vanskeligheten er å kunne komponere så mange som mulig, med tanke på egenskapene til et bestemt chiffer. enkelt system slik at prosessen med å løse det tar så kort tid som mulig. Her spilles nøkkelrollen av funksjonene til hvert spesifikt chiffer som analyseres.
Den algebraiske metoden brukt av Courtois kan kort beskrives som følger. I det første trinnet brukes slike egenskaper til GOST 28147-89 som eksistensen av et fast punkt for en del av krypteringstransformasjonen, så vel som det såkalte refleksjonspunktet. Takket være disse egenskapene velges flere par fra et tilstrekkelig stort antall klartekst-siffertekst-par, som gjør det mulig å vurdere transformasjoner ikke ved 32, men bare ved 8 runder. Det andre trinnet er at basert på resultatene av 8 runde transformasjoner oppnådd i det første trinnet, konstrueres et system med ikke-lineære ligninger, der nøkkelbitene er ukjente. Deretter er dette systemet løst (dette høres enkelt ut, men er i realiteten den mest tidkrevende delen av metoden, siden systemet består av ikke-lineære ligninger).
Som nevnt ovenfor, er det ingen steder i arbeidet Detaljert beskrivelse og analyse av kompleksiteten til det andre og hovedstadiet for å bestemme nøkkelen. Det er kompleksiteten til det andre trinnet som bestemmer kompleksiteten til hele metoden som helhet. I stedet gir forfatteren de beryktede "fakta" som han gjør anslag på arbeidsintensiteten på grunnlag av. Disse "fakta" sies å være basert på eksperimentelle resultater. En analyse av "fakta" fra Courtois' verk som helhet er gitt i arbeidet til innenlandske forfattere. Forfatterne av dette arbeidet bemerker at mange av Courtois "fakta" presentert uten bevis ble funnet å være falske under eksperimentell testing. Forfatterne av artikkelen gikk videre og utførte i etterkant av Courtois en analyse av kompleksiteten til det andre trinnet ved hjelp av velfunderte algoritmer og estimater. De resulterende kompleksitetsestimatene viser den fullstendige uanvendeligheten til det presenterte angrepet. I tillegg til hjemlige forfattere, ble også de store problemene Courtois har med vurderinger og begrunnelse av sine metoder bemerket i verket.
Differensiell metode
La oss vurdere den andre Courtois-metoden, som er basert på differensiell kryptoanalyse.
Den generelle metoden for differensiell kryptoanalyse er basert på utnyttelse av egenskapene til ikke-lineære kartlegginger som brukes i kryptografiske primitiver, assosiert med påvirkningen av nøkkelverdien på avhengighetene mellom forskjellene mellom par av input og par av utgangsverdier for disse mappingene . La oss beskrive hovedideen til den differensielle metoden for kryptografisk analyse av et blokkchiffer. Vanligvis transformerer blokkchifre inndataene i trinn ved å bruke en rekke såkalte runde transformasjoner, og hver runde transformasjon bruker ikke hele nøkkelen, men bare en del av den. La oss vurdere en litt "avkortet" chiffer, som skiller seg fra den originale ved at den ikke har den siste runden. La oss anta at det har vært mulig å fastslå at kryptering av to klartekster som er forskjellige i enkelte faste posisjoner ved bruk av et slikt "avkortet" chiffer, mest sannsynlig vil resultere i chiffertekster som også er forskjellige i enkelte faste posisjoner. Denne egenskapen viser at en "avkortet" chiffer mest sannsynlig etterlater en avhengighet mellom noen klartekster og resultatene av kryptering. For å gjenopprette deler av nøkkelen ved å bruke denne åpenbare feilen, er det nødvendig å kunne kryptere forhåndsvalgte klartekster på nøkkelen vi ønsker å gjenopprette (det såkalte "valgte klartekstangrepet"). I begynnelsen av "nøkkelåpning"-prosedyren genereres et antall par klartekster tilfeldig, som er forskjellige i de samme faste posisjonene. Alle tekster er kryptert med en "full" chiffer. De resulterende chiffertekstparene brukes til å gjenopprette de nøkkelbitene som ble brukt i forrige runde transformasjon, som følger. Ved å bruke noen tilfeldig valgt verdi av de ønskede nøkkelbitene, blir en transformasjon invers til den siste runde transformasjonen brukt på alle chiffertekster. Faktisk, hvis vi gjettet ønsket verdi av nøkkelbitene, vil vi få resultatet av en "avkortet" chiffer, og hvis vi ikke gjettet, vil vi faktisk "kryptere dataene enda mer", noe som bare vil redusere avhengighet mellom blokker nevnt ovenfor (forskjellen er i noen faste posisjoner). Med andre ord, hvis det blant resultatene av en slik "tilleggsbehandling" av chiffertekster var ganske mange par som er forskjellige i de faste posisjonene som er kjent for oss, betyr dette at vi har gjettet de nødvendige nøkkelbitene. Ellers blir det betydelig færre slike par. Siden bare en del av nøkkelen brukes i hver runde, er det ikke så mange søkte biter (det vil si nøkkelbitene som ble brukt i siste runde) som det er biter i i full nøkkel og du kan ganske enkelt sortere gjennom dem ved å gjenta trinnene ovenfor. I dette tilfellet vil vi definitivt snuble over den riktige betydningen en dag.
Fra beskrivelsen ovenfor følger det at det viktigste i differensialanalysemetoden er tallene på de samme posisjonene i klartekster og chiffertekster, hvor forskjellene spiller en nøkkelrolle i å gjenopprette nøkkelbitene. Den grunnleggende tilstedeværelsen av disse posisjonene, så vel som settet med deres tall, avhenger direkte av egenskapene til de ikke-lineære transformasjonene som brukes i et hvilket som helst blokkchiffer (vanligvis er all "ikke-linearitet" konsentrert i de såkalte S-boksene eller erstatningsnoder).
Courtois bruker en litt modifisert versjon av differensialmetoden. La oss umiddelbart merke seg at Courtois utfører sin analyse for S-bokser som er forskjellige fra de nåværende og de som er foreslått i ISO. Arbeidet gir differensielle egenskaper (de tallene der blokkene skal være forskjellige) for et lite antall runder. Begrunnelsen for å utvide egenskapene for flere runder er som vanlig basert på «fakta». Courtois uttrykker, igjen, uten annet enn sin autoritet, en ustøttet antakelse om at endring av S-boksene ikke vil påvirke motstanden til GOST 28147-89 mot hans angrep (mens av ukjente grunner, S-boksene fra det første arbeidsutkastet til tillegget til standarden ISO/IEC 18033-3 ble ikke vurdert). Analysen utført av forfatterne av artikkelen viser at selv om vi tar Courtois ubegrunnede "fakta" om tro og analyserer GOST 28147-89 med andre S-blokker, viser angrepet seg igjen å ikke være bedre enn et fullstendig søk.
En detaljert analyse av Courtois' verk med en detaljert underbyggelse av grunnløsheten til alle utsagn om nedgangen i motstanden til den russiske standarden ble utført i verkene [,].
Samtidig innrømmer selv Courtois selv den absolutte mangelen på nøyaktighet i beregningene! Følgende lysbilde er hentet fra Courtois' presentasjon på FSE 2012 kortvarig seksjon.
Det skal bemerkes at Courtois arbeid også har blitt kritisert gjentatte ganger av utenlandske forskere. For eksempel inneholdt hans arbeid med å konstruere angrep på AES-blokkkrypteringsalgoritmen ved bruk av XSL-metoden de samme grunnleggende feilene som arbeidet med analysen av den russiske standarden: de fleste arbeidsintensitetsestimatene vises i teksten helt ubegrunnede og udokumenterte - detaljert kritikk finnes for eksempel i arbeid. I tillegg innrømmer Courtois selv utbredt avslag på å publisere arbeidet sitt på store kryptografikonferanser og i etablerte fagfellevurderte tidsskrifter, noe som ofte gir ham bare muligheten til å snakke i den korte kunngjøringsdelen. Dette kan du for eksempel lese om i avsnitt 3 i arbeidet. Her er noen sitater fra Courtois selv relatert til arbeidet hans:
- "Jeg tror at publikum til Asiacrypt ikke vil føle at det er interessant." Asiacrypt 2011 anmelder.
- "... det er et stort, stort, stort problem: dette angrepet, som er hovedbidraget til avisen, har allerede blitt publisert på FSE'11 (det var til og med den beste avisen), ...". Anmelder for Crypto 2011.
Den profesjonelle delen av det internasjonale kryptografiske samfunnet ser på kvaliteten på Courtois' arbeid med ikke mindre tvil enn for eksempel uttalelsene fra noen russiske spesialister om deres evne til å knekke AES for 2100, som ikke er bekreftet av noen konsistente beregninger, eller siste "bevis" på en to-siders hypotese om ulikheten i kompleksitetsklassene P og NP.
Angrep fra Isobe og Dinur-Dankelman-Shamir
Den generelle ideen med Isobe () og Dinur-Dankelman-Shamir-angrepene (heretter: DDS-angrep) () er å konstruere for et visst (nøkkelavhengig) smalt sett med klartekster en ekvivalent transformasjon på dette settet, som har en struktur enklere enn selve krypteringstransformasjonen. Når det gjelder Isobe-metoden, er dette settet med 64-bits blokker x slik at F 8 -1 (Swap(F 8 (z))) = z, hvor z = F 16 (x), til og med F 8 ( x) og F 16 ( x) indikerer henholdsvis de første 8 og første 16 rundene med GOST 28147-89-kryptering gjennom Swap - operasjonen for å bytte halvdeler av et 64-byte ord. Hvis klarteksten er inkludert i dette settet, faller resultatet av den fullstendige 32-runders transformasjonen av GOST 28147-89 sammen med resultatet av 16-runden, som er hva forfatteren av angrepet utnytter. I tilfellet med DDS-metoden er dette settet av x slik at F 8 (x) = x (fast punkt for transformasjonen F 8). For enhver klartekst fra dette settet fungerer GOST 28147-89-transformasjonen nøyaktig det samme som de siste 8 rundene, noe som forenkler analysen.
Kompleksiteten til Isobe-angrepet er 2224 krypteringsoperasjoner, DDS-angrepet er 2192. Alle spørsmål om hvorvidt Isobe- og DDS-angrepene introduserer nye restriksjoner på betingelsene for bruk av algoritmen vår fjernes imidlertid ved å vurdere kravene til mengden materiale som kreves for å utføre hvert av angrepene: Isobe-metoden krever 2 32 par klartekst og chiffertekst, og for DDS-metoden - 2 64. Å behandle slike mengder materiale uten å endre nøkkelen er a priori uakseptabelt for ethvert blokkchiffer med en blokklengde på 64: på materiale med volum 2 32 , tatt i betraktning problemet med fødselsdager (se for eksempel ), sannsynligheten for forekomst av gjentatte blokker er nær 1/2, noe som vil gi angriperen er i stand til å trekke visse konklusjoner om klartekstene fra chiffertekstene uten å bestemme nøkkelen. Tilstedeværelsen av 2 64 par ren og kryptert tekst oppnådd på én nøkkel lar faktisk fienden utføre krypterings- og dekrypteringsoperasjoner uten å kjenne denne nøkkelen i det hele tatt. Dette skyldes en rent kombinatorisk egenskap: fienden har i dette tilfellet hele krypteringstabellen. Denne situasjonen er absolutt uakseptabel under alle rimelige driftsforhold. For eksempel i CryptoPro CSP Det er en teknisk begrensning på volumet av kryptert materiale (uten nøkkelkonvertering) på 4 MB (se). Dermed er et strengt forbud mot å bruke en nøkkel på materiale med et slikt volum iboende i ethvert blokkchiffer med en blokklengde på 64 biter, og derfor begrenser Isobe- og DDS-angrep på ingen måte omfanget av bruken av GOST 28147-89-algoritmen samtidig som maksimal styrke på 2256 opprettholdes.
Selvfølgelig skal det bemerkes at forskere (Isobe og Dinur-Dankelman-Shamir) har vist at noen egenskaper til GOST 28147-89-algoritmen gjør det mulig å finne analyseveier som ikke ble tatt i betraktning av skaperne av algoritmen. Den enkle formen til nøkkelplanen, som betydelig forenkler oppgaven med å konstruere effektive implementeringer, tillater også noen sjeldne tilfeller av nøkler og klartekster for å konstruere flere enkle beskrivelser transformasjoner utført av algoritmen.
Arbeidet viser at denne negative egenskapen til algoritmen lett kan elimineres med full bevaring av operasjonelle egenskaper, men dessverre er den en integrert del av algoritmen i sin ofte brukte form.
Merk at viss uaktsomhet i estimatene for gjennomsnittlig arbeidsintensitet også er til stede i arbeidet til Dinur, Dunkelman og Shamir. Når du konstruerer et angrep, blir det derfor ikke tatt hensyn til følgende punkt: for en betydelig andel nøkler er settet med klartekst x, slik at F 8 (x) = x, tomt: det kan ganske enkelt ikke være noen faste punkter for 8 runder med transformasjon. Eksistensen av faste punkter avhenger også av valget av erstatningsnoder. Dermed er angrepet kun aktuelt for visse erstatningsnoder og nøkler.
Det er også verdt å nevne ett arbeid til med et angrep på GOST 28147-89. I februar 2012 dukket det elektroniske ePrint-arkivet til den internasjonale kryptografiske foreningen opp oppdatert versjon artikkel (datert november 2011), som inneholdt et nytt angrep på GOST 28147-89. Egenskapene til det presenterte angrepet er som følger: volumet av materiale er 2 32 (som Isobe), og arbeidsintensiteten er 2 192 (som DDS). Dermed forbedret dette angrepet tidsrekord-DDS-angrepet når det gjelder materialvolum fra 2 64 til 2 32. Vi bemerker separat at forfatterne ærlig presenterte alle beregningene med begrunnelse for kompleksiteten og volumet til materialet. Etter 9 måneder ble det funnet en grunnleggende feil i beregningene ovenfor, og siden november 2012 inneholder ikke lenger den oppdaterte versjonen av artikkelen i det elektroniske arkivet noen resultater angående den innenlandske algoritmen.
Angrep forutsatt at angriperen vet "noe" om nøklene
Til slutt bemerker vi at det i litteraturen også er en rekke verk (se for eksempel og ) viet angrep på GOST 28147-89 i den såkalte koblede nøkkelmodellen. Denne modellen inneholder i utgangspunktet antakelsen om at en angriper kan få tilgang for analyse, ikke bare til par med ren tekst og kryptert ved hjelp av ønsket nøkkel, men også til par med ren tekst og chiffertekst oppnådd ved bruk av (også ukjente) nøkler som er forskjellige fra den ettersøkte i en kjent vanlig måte (for eksempel ved faste bitposisjoner). I denne modellen er det virkelig mulig å oppnå interessante resultater om GOST 28147-89, men i denne modellen kan ikke mindre sterke resultater oppnås om for eksempel som er mest brukt i moderne nettverk vanlig bruk AES-standard (se for eksempel). Merk at betingelsene for å utføre denne typen angrep oppstår ved bruk av et chiffer i en bestemt protokoll. Det skal bemerkes at resultater av denne typen, selv om de er av utvilsomt akademisk interesse med tanke på å studere egenskapene til kryptografiske transformasjoner, faktisk ikke er relevante for praksis. For eksempel oppfyller alle kryptografiske informasjonsbeskyttelsesverktøy sertifisert av FSB i Russland de strengeste kravene til krypteringsnøkkelgenerering (se for eksempel). Som angitt i resultatene av analysen, hvis det er 18 assosierte nøkler og 2 10 par klartekst- og chiffertekstblokker, er kompleksiteten ved å åpne den private nøkkelen fullstendig, med en sannsynlighet for suksess på 1-10 -4, faktisk 2 26 . Men dersom de ovennevnte kravene til utvikling av nøkkelmateriale er oppfylt, er sannsynligheten for å finne slike nøkler 2 -4352, det vil si 24096 ganger mindre enn om du bare prøver å gjette den hemmelige nøkkelen på første forsøk.
Verk relatert til modellen med koblede nøkler inkluderer også arbeid, som i 2010 forårsaket mye støy i russiske elektroniske publikasjoner, som ikke lider av vanen med å nøye sjekke materialet i løpet av sensasjoner. Resultatene presentert i den ble ikke støttet av noen streng begrunnelse, men de inneholdt høylytte uttalelser om muligheten for å hacke statsstandarden Den russiske føderasjonen på en svak bærbar datamaskin i løpet av sekunder - generelt ble artikkelen skrevet i de beste tradisjonene til Nicolas Courtois. Men til tross for artikkelens helt åpenbare grunnløshet for leseren som er mer eller mindre kjent med de grunnleggende prinsippene for vitenskapelige publikasjoner, var det nettopp for å berolige den russiske offentligheten etter arbeidet at Rudsky skrev en detaljert og grundig tekst som inneholdt en omfattende analyse av denne mangelen. Artikkelen med den selvforklarende tittelen "Om null praktisk betydning av arbeidet "Nøkkelgjenopprettingsangrep på full GOST-blokkchiffer med null tid og minne"" gir begrunnelse for at den gjennomsnittlige kompleksiteten til metoden gitt i er ikke mindre enn kompleksiteten av et fullstendig søk.
Tørre rester: hva er holdbarhet i praksis?
Avslutningsvis presenterer vi en tabell som inneholder data om alle resultatene av strengt beskrevne og berettigede angrep på GOST 28147-89 kjent for det internasjonale kryptografiske samfunnet. Merk at kompleksiteten er gitt i krypteringsoperasjonene til GOST 28147-89-algoritmen, og minnet og materialet er angitt i algoritmeblokker (64 biter = 8 byte).
| Angrep | Arbeidsintensitet | Hukommelse | Nødvendig materiale |
| Isobe | 2 224 | 2 64 | 2 32 |
| Dinur-Dankelman-Shamir, FP, 2DMitM | 2 192 | 2 36 | 2 64 |
| Dinur-Dankelman-Shamir, FP, lite minne | 2 204 | 2 19 | 2 64 |
| 2 224 | 2 36 | 2 32 | |
| Dinur-Dankelman-Shamir, Refleksjon, 2DMitM | 2 236 | 2 19 | 2 32 |
| Fullfør søk | 2 256 | 1 | 4 |
| Antall nanosekunder siden skapelsen av universet | 2 89 |
Til tross for en ganske storskala forskningssyklus innen stabiliteten til GOST 28147-89-algoritmen, dette øyeblikket Det er ikke et eneste angrep kjent som ville være oppnåelig under de operasjonelle kravene til en 64-bits blokklengde. Restriksjonene på volumet av materiale som kan behandles på én nøkkel som følge av chifferparametrene (nøkkelbitlengde, blokkbitlengde) er betydelig strengere enn minimumsvolumet som kreves for å utføre et hvilket som helst kjent angrep. Følgelig, når de oppfyller eksisterende driftskrav, tillater ingen av kryptoanalysemetodene som er foreslått til dags dato GOST 28147-89 å bestemme en nøkkel med en arbeidsintensitet som er mindre enn uttømmende søk.
