De in de volksmond bekende term ‘processorprestaties’ is een objectieve, berekende parameter die wordt gemeten in flops. De meeste mensen meten het echter in gigahertz, omdat ze naïef geloven dat dit hetzelfde is. Niemand kent de term ‘codeprestaties’, en ik zal meteen uitleggen waarom.

De reden is dat ik er pas onlangs op bedacht ben en er nog niemand over heb verteld. Codeprestaties hebben echter, net als processorprestaties, objectieve kenmerken die kunnen worden gemeten. Dit artikel gaat specifiek over de prestaties van code die door de processorkern wordt uitgevoerd.

Hoe worden codeprestaties gemeten? Omdat ik de eerste was die hierover sprak, zal ik het rechts van de ontdekker in RTT-eenheden meten;).

Nu serieus. In moderne processors zijn de belangrijkste transformaties bewerkingen op 32-bits getallen; al het andere is over het algemeen exotisch. Daarom zullen we rekening houden met het belangrijkste: bewerkingen met 32-bits getallen. Hoeveel 32-bits bewerkingen denk je dat een moderne processorkern tegelijkertijd kan uitvoeren?

De student zal antwoorden - één, zijn leraar zal denken en zeggen dat er vier zijn, de professional - dat er tot nu toe slechts twaalf operaties zijn.

Een programmacode die alle processoruitvoeringseenheden tegelijkertijd laadt gedurende de gehele uitvoeringstijd van de code, zal dus een prestatie hebben van 12 RTT's. Maximaal! Eerlijk gezegd heb ik nog nooit zo'n code geschreven, maar in dit artikel zal ik proberen mijn best te doen.

Ik zal bewijzen dat code met gelijktijdige uitvoering van twaalf 32-bits bewerkingen mogelijk is

Programmacode die één actuator in de processorkern gebruikt, heeft uiteraard een prestatie van 1 RTT. Programma's die zijn gegenereerd door taalcompilers op hoog niveau en tolken van virtuele machines kunnen bogen op dergelijke codeprestaties. Het is niet nodig om aan te nemen dat de processorbelastingsindicator, die te zien is in de taakbeheerder van het besturingssysteem, kan dienen als een objectief criterium voor de efficiëntie van de code. De processorkernbelasting kan 100% zijn, maar de programmacode gebruikt daarin één uitvoeringseenheid (prestatie 1 RTT). In dit geval zal de processorkern bij 100% belasting op 1/12 van zijn maximale prestaties werken. Met andere woorden: wanneer Windows Taakbeheer de maximale processorbelasting weergeeft, kunnen de werkelijke prestaties variëren van 1 tot 12 RTT. Als u in het prestatievenster een belasting van 100% op een processorkern ziet, is het verkeerd om aan te nemen dat alle actuatoren in deze kern werken, en dat is helemaal niet het geval!

Het enige criterium voor het indirect beoordelen van de werking van een processorkern bij maximale prestaties kan het energieverbruik zijn en, als gevolg daarvan, het geluid van de koeler. Als de koeler luidruchtig is, dan is de belasting inderdaad maximaal. Het is echter tijd om af te ronden met algemene concepten en verder te gaan met de harde praktijk.

Traditionele implementatie van GOST 28147-89

Ik ben geen professional op het gebied van informatiebeveiliging, maar ik ben nog steeds bekend met het onderwerp encryptie. Ik werd geïnspireerd om symmetrische stroomversleuteling te bestuderen, specifiek door gesprekken met een professionele cryptograaf die ik diep respecteer. En nadat ik dit onderwerp had behandeld, probeerde ik het goed te doen, en niet alleen goed, maar ook snel, door het maximale aantal bewerkingen per tijdseenheid uit te voeren. Met andere woorden, ik stond voor de taak om programmacode te schrijven met de maximale RTT-waarde.

Cryptografische transformatie in overeenstemming met GOST 28147-89 wordt gebruikt voor stroomcodering van informatie in communicatiekanalen en op schijfstations.

Momenteel wordt de software-implementatie van deze GOST op de RON van de centrale processor veel gebruikt. Bij bekende implementatiemethoden van GOST bevindt alle geheime informatie (coderingssleutels, vervangingsblokken) zich in RAM. Dit vermindert de betrouwbaarheid van de encryptie, omdat het hebben van een RAM-dump alle geheime elementen van de crypto-transformatie volledig kan onthullen. Bovendien heeft de methode prestatiebeperkingen vanwege de locatie van de belangrijkste cryptoconversieobjecten in het OP en het onvolledig laden van de uitvoerende eenheden van de ALU. Moderne processors, die de cryptoprocedure implementeren met behulp van een bekende methode, kunnen encryptiesnelheden van 40-60 megabytes per seconde bieden. En als we het echt tot het einde toe begrijpen, is de reden voor de lage prestaties en zwakke beveiliging van cryptoconversie de software-implementatie van het substitutieblok. Voor de beschrijving in GOST, zie Fig. 1.

Volgens clausule 1.2 van GOST implementeert dit blok tetrads (vier bits) permutaties in een 32-bits woord, maar de x86/64 processorarchitectuur en het bijbehorende instructiesysteem zijn niet in staat om tetrads effectief te manipuleren.

Voor de software-implementatie van het substitutieblok worden speciale tabellen in RAM gebruikt, opgesteld in de fase van initialisatie van de cryptofunctie. Deze tabellen combineren de vervangende knooppunten van aangrenzende tetrads in bytetabellen van 8 x 8 bits, waardoor vier tabellen van 256 bytes in RAM worden geplaatst.

In meer geavanceerde implementaties zijn deze tabellen 1024 bytes groot (256 woorden van vier bytes). Dit werd gedaan om in de tabellen een extra cyclische verschuiving met 11 posities te implementeren van het 32-bits woord verkregen als resultaat van substitutie (de volgende bewerking van het conversiealgoritme volgens GOST). Een voorbeeld van GOST-implementatie met behulp van deze methode wordt getoond in bijlage 1 (op schijf).

De informatie van het substitutieblok is een geheim onderdeel van de cryptofunctie (zoals geformuleerd in GOST, zie figuur 2).

Het plaatsen van deze tabellen met de sleutels van het substitutieblok in het OP is in tegenspraak met de vereisten van GOST (clausule 1.7), aangezien geheime informatie beschikbaar komt voor programma's van derden die op de computerinstallatie draaien. De FSB, die volgens GOST ook software-implementaties van encryptie certificeert, bekijkt deze overtreding, op zijn zachtst gezegd, neerbuigend. Als de FSB, om sleutels in de OP te plaatsen, nog steeds een "vijgenblad" nodig heeft - het maskeren van de sleutels met behulp van de XOR-bewerking, dan is er niets nodig voor vervangende blokken in de OP; ze worden in duidelijke vorm opgeslagen.

Kortom, de FSB laat dergelijke software-implementaties van cryptoprocedures passeren, ondanks de duidelijke afname van de veiligheid van een dergelijke oplossing en een directe schending van zijn eigen vereisten volgens GOST (clausule 1.7). En dit ondanks de bekende methoden om cijfers te kraken door een geheugendump te maken...

We komen later terug op de kwestie van het opslaan van sleutels en vervangende blokken in de interne registers van de processor (er is een mooie en snelle oplossing), maar voorlopig slaan we alleen encryptiesleutels op in MMX-registers, dit is betrouwbaarder.

Maar genoeg over de teksten, wat belangrijk is voor het onderwerp in kwestie is dat deze programmacode een prestatie heeft van 1 RTT. Laten we nu code schrijven met de prestaties van 2 RTT's.

Multithreaded implementatie van GOST 28147-89

De enige manier om cryptoprocedures in het bekende algoritme te versnellen is door multithreading te introduceren. Het doel van deze verandering in de implementatie van het algoritme is om verschillende gegevensblokken parallel te berekenen.

De meeste programmeurs bedoelen met parallelle verwerking uitsluitend het werk van verschillende processorkernen, gesynchroniseerd via interrupts en semaforen in het geheugen.

Er is echter nog een andere optie voor parallelle gegevensverwerking op één processorkern. Laat me dit niet voor de hand liggende idee uitleggen.

Moderne processors bevatten minstens twee en zelfs drie tot zes rekenkundig-logische eenheden. Deze ALU's (FPU's, adresrekeneenheden, enzovoort) kunnen onafhankelijk van elkaar werken; de enige voorwaarde voor hun parallelle werking is dat de softwareobjecten waarop ze werken onsamenhangend zijn. Met andere woorden, in instructies die gelijktijdig een ALU uitvoeren, moeten de geheugenadressen en registernummers verschillend zijn. Of er mogen geen schrijfbewerkingen worden uitgevoerd naar gedeelde registers en geheugenadressen waartoe verschillende processoruitvoeringseenheden toegang hebben.

De werklast van alle ALU's wordt geregeld door een speciale hardware-eenheid in de processorkern: de planner, die de uitvoerbare code vooruit scant, tot een diepte van 32-64 bytes. Als de planner instructies ontdekt die zonder conflicten op de ALU kunnen worden uitgevoerd, voert hij deze tegelijkertijd uit op verschillende uitvoeringsapparaten. In dit geval geeft de teller van uitgevoerde commando's het uitvoerende commando aan (er zijn er meerdere in een dergelijk schema), waarna alle commando's al zijn uitgevoerd.

De meeste programmareeksen die automatisch (door compilers) worden gegenereerd, kunnen niet alle ALU's en FPU's in de processorkern laden. In dit geval is de processorhardware inactief, wat de resulterende prestaties aanzienlijk vermindert. Processorontwikkelaars begrijpen dit en introduceren modi om de kernfrequentie te verhogen wanneer de hardware niet volledig wordt benut. Dit is ook waar hypertradingsystemen voor zijn ontworpen, en ik zal dit systeem gebruiken om de code in de toekomst maximaal te ‘persen’.

Compilers, zelfs de meest geoptimaliseerde, en nog meer virtuele machine-engines, kunnen geen geoptimaliseerde code genereren in termen van prestaties. Alleen een programmeur met technische kennis kan dergelijke geoptimaliseerde code schrijven, en het hulpmiddel om deze te schrijven is uitsluitend assembler.

Een typisch voorbeeld van de mogelijkheid om meerdere onafhankelijke programmathreads op één processorkern uit te voeren is de GOST-implementatie, uitgevoerd in twee threads op één processorkern. Het idee van de code is simpel: er zijn twee datablokken om te coderen/decoderen, maar één processorkern die de conversie zal uitvoeren. Het is mogelijk om de conversie op deze twee datablokken opeenvolgend uit te voeren, en dit wordt tot op de dag van vandaag gedaan. In dit geval verdubbelt de tijd die nodig is om de transformaties te voltooien.

Maar je kunt het ook anders doen: alternatieve opdrachten gerelateerd aan de verwerking van verschillende datablokken. Deze opties worden grafisch weergegeven in Fig. 3.

In de afbeelding toont het bovenste voorbeeld de gebruikelijke volgorde van verwerking van twee onafhankelijke gegevensblokken. Het eerste blok wordt eerst verwerkt, waarna de processor verdergaat met het verwerken van het tweede blok. Uiteraard is de resulterende tijd gelijk aan tweemaal de tijd die nodig is om één blok te verwerken, en zijn de actuatoren van de processorkern niet volledig belast.

Het volgende is een voorbeeld van het interleaven van opdrachten uit verschillende verwerkingsthreads. In dit geval worden opdrachten die verband houden met verschillende datablokken tussengevoegd. De planner selecteert instructies die onafhankelijk van elkaar zijn en verzendt deze ter uitvoering naar ALU1 en ALU2. Het groeperen van commando's van de eerste en tweede threads op deze ALU's wordt automatisch uitgevoerd, aangezien het bedieningsalgoritme van de planner een groep commando's omvat die zijn gekoppeld aan gemeenschappelijke gegevens op hetzelfde uitvoerende apparaat.

Om dergelijke programmacode te laten werken zonder ALU-downtime, is het noodzakelijk dat elke programmathread met zijn eigen set registers werkt. De cache in dit schema wordt een knelpunt (deze heeft slechts twee gegevensuitvoerpoorten), dus slaan we de sleutels op in MMX-registers. Omdat in dit geval de vervangende (en verschuivende) knooppunten in het geheugen alleen worden gelezen, kunnen ze gemeenschappelijk zijn voor beide programmathreads.

Dit is natuurlijk een zeer vereenvoudigde uitleg van het principe van parallelle uitvoering van programmathreads op een enkele kern; in werkelijkheid is alles veel gecompliceerder. In de praktijk moet je rekening houden met de pijplijnarchitectuur van actuatoren, beperkingen op gelijktijdige toegang tot de cache en het RON-registerblok, de aanwezigheid van adresberekeningsknooppunten, schakelaars en nog veel meer... Dit is dus een onderwerp voor professionals, die op de vingers van één hand te tellen is.

De parallelle coderingsmethode wordt alleen effectief geïmplementeerd voor de bedrijfsmodus van de 64-bits processor, omdat er in deze modus voldoende RON is (maar liefst 16 stuks!). Een voorbeeld van GOST-implementatie met behulp van deze methode wordt getoond in bijlage 2 (op schijf).

Het is duidelijk dat deze GOST-implementatie een codeprestatie heeft van 2 RTT-codes. Laten we nu eens kijken hoe dit de uitvoeringstijd beïnvloedt.

De versleutelingscyclus voor één stream (bijlage 1) bedraagt ​​352 klokcycli, en gedurende deze tijd worden 8 bytes aan gegevens berekend; voor een implementatie met twee threads van GOST (bijlage 2) zijn 416 processorcycli vereist, maar er worden 16 bytes berekend. De resulterende conversiesnelheid neemt dus toe van 80 naar 144 megabytes voor een 3,6 GHz-processor.

Er ontstaat een interessant beeld: de code bevat precies twee keer zoveel opdrachten en wordt slechts 15% langer uitgevoerd, maar ik denk dat de lezers de reden voor dit fenomeen al hebben begrepen...

Theoretisch zou de code uit het tweede voorbeeld in hetzelfde aantal klokcycli moeten worden uitgevoerd als de code uit het eerste voorbeeld, maar het plannerknooppunt is ontwikkeld door Intel-ingenieurs, maar ook zij zijn menselijk, en we zijn allemaal verre van perfect. Het is dus mogelijk om de effectiviteit van hun creatie te evalueren. Deze code werkt ook op een AMD-processor en u kunt de resultaten ervan vergelijken.

Als iemand mij niet op mijn woord gelooft, dan zijn er voor zulke niet-gelovigen testprogramma's met kloktellers op de schijf opgenomen. De programma's zijn in de broncode, uiteraard in assembler, dus er is een mogelijkheid om mijn woorden te controleren en tegelijkertijd enkele trucs van professionele codering te zien.

Gebruik van SSE-registers en AVX-opdrachten van moderne processors om GOST 28147-89 te implementeren

Moderne processors van de x86/64-architectuur omvatten een reeks SSE-registers van 16 bytes groot en gespecialiseerde FPU's (minstens twee) om verschillende bewerkingen op deze registers uit te voeren. Het is mogelijk om GOST op deze apparatuur te implementeren, en in dit geval kunnen vervangende knooppunten niet in de vorm van tabellen in RAM worden geplaatst, maar rechtstreeks op speciale SSE-registers.

Eén SSE-register kan twee tabellen van 16 rijen tegelijk bevatten. Vier SSE-registers zullen dus alle vervangingstabellen volledig kunnen huisvesten. De enige voorwaarde voor een dergelijke plaatsing is de interleaving-vereiste, volgens welke tetrads van dezelfde byte in verschillende SSE-registers moeten worden geplaatst. Bovendien is het raadzaam om respectievelijk de lage en hoge tetrads van de invoerbytes in de lage en hoge tetrads van de bytes van de SSE-registers te plaatsen.

Deze vereisten worden bepaald door optimalisatie voor de bestaande set AVX-opdrachten. Elke byte van het SSE-register zal dus twee tetrads bevatten die overeenkomen met verschillende bytes van het invoerregister van het substitutieblok, terwijl de positie van de byte in het SSE-register op unieke wijze overeenkomt met de index in de substitutietabel van het substitutieblok.

Een diagram van een van de mogelijke plaatsingen van vervangende knooppunten op SSE-registers wordt getoond in Fig. 4.

Het plaatsen van geheime informatie van vervangende knooppunten op SSE-registers verhoogt de veiligheid van de cryptoprocedure, maar volledige isolatie van deze geheime informatie is mogelijk als aan de volgende voorwaarden wordt voldaan:

• De processorkern wordt overgeschakeld naar de hypervisor-hostmodus en het interruptblok (APIC) wordt daarin met geweld uitgeschakeld. In dit geval is de processorkern volledig geïsoleerd van het besturingssysteem en de applicaties die op de computerinstallatie draaien.
• SSE-registers worden geladen en de computerkern wordt geïsoleerd voordat het besturingssysteem start; het is optimaal om deze procedures uit te voeren vanaf de vertrouwde opstartmodule (TLM).
• Programma's voor cryptoprocedures in overeenstemming met GOST bevinden zich in een niet-wijzigbaar geheugengebied van de computerinstallatie (BIOS of in flash-geheugen van de MDZ).

Naleving van deze vereisten garandeert volledige isolatie en onveranderlijkheid van de programmacode van cryptoprocedures en de daarin gebruikte geheime informatie.

Voor efficiënte bemonstering van tetrad SSE-registers worden de byteschakelaars met meerdere ingangen in de FPU-blokken gebruikt. Deze schakelaars maken overdrachten mogelijk van elke bronbyte naar elke bestemmingsbyte, met behulp van indices die zich in een speciaal SSE-indexregister bevinden. Bovendien wordt de overdracht parallel uitgevoerd voor alle 16 bytes van het SSE-ontvangerregister.

Met vervangingsopslagknooppunten op SSE-registers en een schakelaar met meerdere ingangen in FPU-blokken is het mogelijk om de volgende transformatie in het vervangingsblok te organiseren (Fig. 5).

In dit schema specificeert het ingangsregister in elke tetrad het adres voor de corresponderende schakelaar, die informatie van de aandrijvingen van de vervangende knooppunten via de databus naar het uitgangsregister verzendt. Dit schema kan op drie manieren worden georganiseerd:

• Maak een passend chipontwerp, maar voor ons is dit fantastisch.
• Het herprogrammeren van de microcode en het creëren van uw eigen processoropdracht om deze functie op bestaande processors te implementeren is niet langer een fantasie, maar is onder de huidige omstandigheden helaas onrealistisch.
• Schrijf een programma met behulp van officiële AVX-opdrachten. De optie is misschien niet erg effectief, maar kan ‘hier en nu’ worden geïmplementeerd. Dus dat is wat we hierna gaan doen.

De werking van schakelaars wordt geregeld door een speciaal commando met drie adressen AVX VPSHUFB. De eerste operand is de ontvanger van informatie van de schakelaars, de tweede is de bron waarmee de ingangen van de schakelaars zijn verbonden. De derde operand is een besturingsregister voor schakelaars, waarvan elke byte is geassocieerd met een overeenkomstige schakelaar; de waarde daarin specificeert het nummer van de richting waaruit de schakelaar informatie leest. Voor een beschrijving van deze opdracht uit de officiële Intel-documentatie, zie Fig. 5. Op afb. Figuur 6 toont een diagram van hoe dit commando werkt - slechts de helft van de SSE-registers wordt getoond, voor de tweede helft is alles vergelijkbaar.

De schakelaar gebruikt alleen de laagste vier bits om de richting van de commutatie te bepalen, de laatste bit van elke byte wordt gebruikt om de corresponderende ontvangerbyte naar nul te dwingen, maar deze schakelfunctie is in ons geval nog niet in trek.

Er is een programma geschreven voor het bemonsteren van tetrads via FPU-schakelaars, maar ik heb het niet eens in de applicatie gestopt - het is te zielig. Het hebben van een 128-bits register en het gebruik van slechts 32 bits is onprofessioneel.

Zoals ze zeggen: "Onze eindstreep is de horizon", dus knijp hem eruit, knijp hem eruit... wij drukken hem in en stoppen hem in zakken!

Dit is geen woordspeling, maar een harde FPU-realiteit: SSE-registers kunnen in gelijke delen worden verdeeld en dezelfde transformaties kunnen op deze delen worden uitgevoerd met één commando. Om de processor dit te laten begrijpen, is er een magische letter "P" - een pakket dat vóór de commando-ezelsbruggetjes wordt geplaatst, en niet minder magische letters "Q", "D", "W", "B", die worden aan het einde geplaatst en declareren. In welke delen zijn de SSE-registers in deze opdracht verdeeld?

We zijn geïnteresseerd in de batchmodus waarbij het SSE-register is verdeeld in vier blokken van 32 bits; dienovereenkomstig worden alle opdrachten voorafgegaan door “P” en aan het einde door het symbool “D”. Dit maakt het mogelijk om vier 32-bits blokken parallel te verwerken met één processoropdracht, dat wil zeggen vier datablokken parallel te berekenen.

Het programma dat deze methode implementeert, is beschikbaar in bijlage 3, met alle uitleg daarin.

Druk echter zo veel! Moderne processors hebben minimaal twee FPU's en twee onafhankelijke instructiethreads kunnen worden gebruikt om ze volledig te laden. Als u opdrachten van onafhankelijke threads correct afwisselt, kunt u beide FPU-eenheden volledig met werk belasten en acht parallel verwerkte gegevensstromen tegelijk verkrijgen. Zo'n programma is geschreven en kan worden bekeken in bijlage 4, maar je moet het goed in de gaten houden - je kunt gek worden. Dit is wat men noemt “de code is niet voor iedereen...”.

Prijs kwestie

Het gebruik van SSE-registers om vervangende knooppunten op te slaan is begrijpelijk - het biedt enige garantie voor isolatie van geheime informatie, maar de betekenis van het berekenen van de cryptofunctie zelf op de FPU is niet duidelijk. Daarom werd de uitvoeringstijd van standaardprocedures gemeten met behulp van de directe vervangingsmethode in overeenstemming met GOST voor vier en acht threads.

Voor vier threads werd een uitvoeringssnelheid van 472 processorcycli bereikt. Voor een processor met een frequentie van 3,6 GHz wordt dus één thread berekend met een snelheid van respectievelijk 59 megabytes per seconde en vier threads met een snelheid van 236 megabytes per seconde.

Voor acht threads werd een uitvoeringssnelheid van 580 processorcycli bereikt. Voor een 3,6 GHz-processor telt één thread dus bij 49 megabytes per seconde, en acht threads bij 392 megabytes per seconde.

Zoals de lezer kan zien, heeft de code in voorbeeld #3 een prestatie van 4 RTT, en de code in voorbeeld #4 heeft een prestatie van 8 RTT. In deze voorbeelden op SSE-registers zijn de patronen hetzelfde als bij het gebruik van RON, alleen heeft de planner zijn efficiëntie verminderd. Momenteel biedt het een verlenging van de duur met 20% en een verdubbeling van de codelengte.

Bovendien werden deze resultaten verkregen met behulp van universele AVX-opdrachten die beschikbaar zijn in zowel Intel- als AMD-processors. Als je optimaliseert voor een AMD-processor, zal het resultaat veel beter zijn. Het klinkt in strijd met de trend, maar het is niettemin waar, en dit is de reden: AMD-processors hebben een extra set instructies, de zogenaamde XOP-extensie, en in deze aanvullende set instructies zijn er instructies die de implementatie van de GOST-algoritme.

Dit verwijst naar de commando's voor logische burst-byteverschuiving en burst-cyclische verschuiving van dubbele woorden. In de voorbeelden in de bijlagen 3 en 4 worden reeksen universele commando's gebruikt die de noodzakelijke transformatie implementeren: in het eerste geval één “extra” commando, en in het andere geval vier extra commando's tegelijk. Er zijn dus optimalisatiereserves, en aanzienlijke.

Als het gaat om verdere optimalisatie, is het de moeite waard om de aanwezigheid van 256-bit registers (YMM-registers) te onthouden, waarmee je theoretisch de snelheid van berekeningen kunt verdubbelen. Maar voorlopig is dit slechts een vooruitzicht; op dit moment vertragen processors erg veel bij het uitvoeren van 256-bits instructies (FPU's hebben een padbreedte van 128 bits). Experimenten hebben aangetoond dat het tellen van 16 threads op YMM-registers op moderne processors geen enkel voordeel oplevert. Maar dit is slechts voor nu; op nieuwe processormodellen zullen de prestaties van 256-bits instructies ongetwijfeld worden verhoogd, en dan zal het gebruik van 16 parallelle threads raadzaam worden en tot een nog grotere toename van de snelheid van de cryptoprocedure leiden. .

Theoretisch kun je rekenen op een snelheid van 600-700 megabytes per seconde als de processor twee FPU's heeft met elk een werkpadbreedte van 256 bits. In dit geval kunnen we praten over het schrijven van code met een efficiëntie van 16 RTT, en dit is geen fantasie, maar de nabije toekomst.

Gemengde modus

Opnieuw rijst de vraag naar het aantal registers; er zijn er niet genoeg om een ​​dergelijk algoritme te promoten. Maar de hypertrading-modus zal ons helpen. De processorkern heeft een tweede set registers die beschikbaar zijn in de logische processormodus. Daarom zullen we dezelfde code tegelijkertijd op twee logische processors uitvoeren. In deze modus hebben we uiteraard niet meer actuatoren, maar door afwisseling kunnen we alle actuatoren volledig belasten.

Je kunt hier niet rekenen op een toename van 50%; het knelpunt is het cachegeheugen waar de technologische maskers worden opgeslagen, maar je kunt nog steeds een toename van 100 extra megabytes krijgen. Deze optie wordt niet weergegeven in de bijlagen (de macro's zijn vergelijkbaar met die gebruikt in de 8 RTT-code), maar is wel beschikbaar in de programmabestanden. Dus als iemand niet gelooft in de mogelijkheid van codering met een snelheid van 500 megabytes per seconde op een enkele processorkern, laat hem dan testbestanden uitvoeren. Er staan ​​ook teksten met commentaar zodat niemand denkt dat ik lieg.

Deze focus is alleen mogelijk op Intel-processors; AMD heeft slechts twee FPU-eenheden per twee processormodules (analoog aan de hypertrading-modus). Maar er zijn nog vier ALU's waarvan het zonde zou zijn om ze niet te gebruiken.

U kunt de Bulldozer-processormodules in een modus zetten die vergelijkbaar is met de hypertrading-modus, maar de conversie naar RON uitvoeren op verschillende modules in één thread, en op SSE-registers in een andere thread, en dezelfde 12 RTT's krijgen. Ik heb deze optie niet getest, maar ik denk dat 12 RTT-code efficiënter zal werken op AMD. Geïnteresseerden kunnen het proberen; testprogramma's kunnen vrij eenvoudig worden aangepast om op “Bulldozers” te werken.

Wie heeft het nodig?

Een serieuze vraag, maar met een eenvoudig antwoord: iedereen heeft dit nodig. Binnenkort zullen we allemaal verslaafd zijn aan de wolken, we zullen daar zowel gegevens als programma's opslaan, en daar, oh, wat willen we ons eigen, privéhoekje creëren. Om dit te doen, moet je het verkeer versleutelen, en de snelheid van crypto-conversie zal de belangrijkste bepalende factor zijn voor comfortabel werken in de cloud. Onze keuze voor het versleutelingsalgoritme is klein: GOST of AES.

Bovendien blijkt vreemd genoeg het in processors ingebouwde AES-coderingsalgoritme veel langzamer te zijn; tests tonen snelheden aan van 100-150 megabytes per seconde, en dit is met een hardware-implementatie van het algoritme! Het probleem ligt in de single-threaded telling en het vervangingsblok, dat werkt op bytes (een tabel van 256 rijen). Dus GOST blijkt effectiever te zijn wanneer het wordt geïmplementeerd op x86/64-architectuur, wie had dat ooit gedacht...

Dit is als we het hebben over het bereikte niveau van coderingssnelheid. En als we theoretische verfijningen op het gebied van het vergroten van de code-efficiëntie in gedachten houden, dan heeft waarschijnlijk niemand dit nodig. Er zijn vrijwel geen specialisten op het 3-6 RTT-niveau, compilers genereren over het algemeen code op het 1-2,5 RTT-niveau, en de meerderheid van de programmeurs kent assembler niet, en zelfs als ze de spelling ervan kennen, begrijpen ze het ontwerp van een moderne processor. En zonder deze kennis maakt het niet uit of het een assembler is of een soort SI-sharp.

Maar niet alles is zo triest: het komt erop neer na een week van slapeloze nachten een nieuw algoritme voor de implementatie van GOST, wat zonde zou zijn om niet te patenteren. En patentaanvragen (drie in totaal) zijn al voltooid en ingediend, dus heren, zakenlieden, in de rij - vrouwen en kinderen krijgen korting.

). Tegelijkertijd groeit in de Russische media en blogs van Russische gebruikers het aantal opmerkingen over dit algoritme: zowel met betrekking tot de resultaten van aanvallen op de Russische standaard met verschillende mate van betrouwbaarheid, als met meningen over de operationele kenmerken ervan. De auteurs (en dus de lezers) van deze aantekeningen krijgen vaak de indruk dat het binnenlandse versleutelingsalgoritme verouderd en traag is en kwetsbaarheden bevat die het aanzienlijk gevoeliger maken voor aanvallen dan buitenlandse versleutelingsalgoritmen met een vergelijkbare sleutellengte. Met deze reeks aantekeningen willen wij u in toegankelijke vorm vertellen over de huidige stand van zaken met de Russische standaard. Het eerste deel behandelt alle aanvallen op GOST 28147-89 die bekend zijn bij de internationale cryptografische gemeenschap en de huidige beoordelingen van de kracht ervan. In toekomstige publicaties zullen we de eigenschappen van de standaard ook nader bekijken vanuit het oogpunt van het vermogen om effectieve implementaties te bouwen.

Nicolas Courtois - "de grote en verschrikkelijke"

Laten we beginnen met een verhaal over de activiteiten van Nicolas Courtois, de auteur van een hele reeks werken gewijd aan de Russische blokcoderingsstandaard ().

In oktober 2010 begon het proces van het overwegen van de opname van het GOST 28147-89-algoritme in de internationale standaard ISO/IEC 18033-3. Al in mei 2011 verscheen een artikel van de beroemde cryptograaf Nicolas Courtois in het elektronische archief van ePrint, gekenmerkt door een zeer dubbelzinnige houding jegens hem vanuit de cryptografische wereldgemeenschap. De publicaties van Courtois zijn een droevig voorbeeld van de manipulatie van concepten, die geen nieuwe eigenschappen van het object in kwestie onthult, maar met een aanspraak op sensatie de verspreiding van onjuiste meningen over de werkelijke eigenschappen ervan in een incompetente omgeving uitlokt.

Algebraïsche methode

De redenering van Courtois is opgebouwd rond twee klassen van cryptanalysemethoden: algebraïsche methoden en differentiële methoden. Laten we eens kijken naar de eerste klasse methoden.

Op een vereenvoudigde manier kan de methode van algebraïsche cryptanalyse worden omschreven als de compilatie en oplossing van een groot systeem van vergelijkingen, waarvan elk van de oplossingen overeenkomt met het doel van de cryptanalyticus (bijvoorbeeld als een systeem wordt samengesteld met behulp van één paar van leesbare tekst en cijfertekst, dan komen alle oplossingen van dit systeem overeen met de sleutels waarmee deze leesbare tekst wordt omgezet in deze gecodeerd). Dat wil zeggen, in het geval van het probleem van de cryptanalyse van een blokcijfer, is de essentie van de algebraïsche methode van cryptanalyse dat de sleutel wordt gevonden als resultaat van het oplossen van een systeem van polynoomvergelijkingen. De grootste moeilijkheid is om een ​​zo eenvoudig mogelijk systeem te kunnen creëren, rekening houdend met de kenmerken van een bepaald cijfer, zodat het oplossingsproces ervan zo min mogelijk tijd kost. Hier wordt de sleutelrol gespeeld door de kenmerken van elk specifiek cijfer dat wordt geanalyseerd.

De door Courtois gebruikte algebraïsche methode kan als volgt kort worden beschreven. In de eerste fase worden dergelijke eigenschappen van GOST 28147-89 gebruikt als het bestaan ​​van een vast punt voor een deel van de encryptietransformatie, evenals het zogenaamde reflectiepunt. Dankzij deze eigenschappen worden verschillende paren geselecteerd uit een voldoende groot aantal leesbare tekst-cijfertekstparen, waardoor het mogelijk is om transformaties niet in 32, maar alleen in 8 ronden te overwegen. De tweede fase is dat, gebaseerd op de resultaten van acht ronde transformaties verkregen in de eerste fase, een systeem van niet-lineaire vergelijkingen wordt geconstrueerd, waarin de sleutelbits onbekend zijn. Vervolgens wordt dit systeem opgelost (dit klinkt eenvoudig, maar is in werkelijkheid het meest tijdrovende deel van de methode, aangezien het systeem uit niet-lineaire vergelijkingen bestaat).

Zoals hierboven opgemerkt, is er nergens in het werk een gedetailleerde beschrijving en analyse van de complexiteit van de tweede en belangrijkste fase van het bepalen van de sleutel. Het is de complexiteit van de tweede fase die de complexiteit van de hele methode als geheel bepaalt. In plaats daarvan geeft de auteur de beruchte ‘feiten’ op basis waarvan hij schattingen maakt van de arbeidsintensiteit. Deze ‘feiten’ zouden gebaseerd zijn op experimentele resultaten. Een analyse van de ‘feiten’ uit het werk van Courtois als geheel wordt gegeven in het werk van binnenlandse auteurs. De auteurs van dit werk merken op dat veel van Courtois’ ‘feiten’, gepresenteerd zonder enig bewijs, tijdens experimentele tests vals bleken te zijn. De auteurs van het artikel gingen verder en voerden, in navolging van Courtois, een analyse uit van de complexiteit van de tweede fase met behulp van goed onderbouwde algoritmen en schattingen. De hieruit resulterende complexiteitsschattingen tonen de volledige ontoepassing van de gepresenteerde aanval aan. Naast binnenlandse auteurs werden bijvoorbeeld ook de grote problemen die Courtois heeft met de beoordeling en rechtvaardiging van zijn methoden in het werk opgemerkt.

Differentiële methode

Laten we eens kijken naar de tweede Courtois-methode, die is gebaseerd op differentiële cryptanalyse.

De algemene methode van differentiële cryptanalyse is gebaseerd op de exploitatie van de eigenschappen van niet-lineaire afbeeldingen die worden gebruikt in cryptografische primitieven, geassocieerd met de invloed van de sleutelwaarde op de afhankelijkheden tussen de verschillen tussen paren invoer- en uitvoerwaarden van deze afbeeldingen. . Laten we het hoofdidee van de differentiële methode van cryptografische analyse van een blokcijfer beschrijven. Normaal gesproken transformeren blokcijfers de invoergegevens in fasen met behulp van een aantal zogenaamde ronde transformaties, en elke ronde transformatie gebruikt niet de hele sleutel, maar slechts een deel ervan. Laten we een enigszins "ingekort" cijfer bekijken, dat verschilt van het origineel doordat het niet de laatste ronde heeft. Laten we aannemen dat het mogelijk is gebleken om vast te stellen dat het versleutelen van twee leesbare teksten die op bepaalde vaste posities verschillen met behulp van een dergelijk “afgeknot” cijfer hoogstwaarschijnlijk zal resulteren in cijferteksten die ook op bepaalde vaste posities verschillen. Deze eigenschap laat zien dat een “afgeknot” cijfer hoogstwaarschijnlijk een afhankelijkheid achterlaat tussen sommige leesbare teksten en de resultaten van hun codering. Om een ​​deel van de sleutel te herstellen met behulp van deze voor de hand liggende fout, is het noodzakelijk om vooraf geselecteerde platte tekst te kunnen coderen op de sleutel die we willen herstellen (de zogenaamde “gekozen platte tekstaanval”). Aan het begin van de “sleutelopening”-procedure worden willekeurig een aantal paren leesbare teksten gegenereerd, die op dezelfde vaste posities verschillen. Alle teksten worden gecodeerd met een “volledig” cijfer. De resulterende cijfertekstparen worden als volgt gebruikt om de sleutelbits te herstellen die in de laatste ronde-transformatie zijn gebruikt. Met behulp van een willekeurig geselecteerde waarde van de gewenste sleutelbits wordt op alle cijferteksten een transformatie toegepast die omgekeerd is aan de transformatie van de laatste ronde. Als we de gewenste waarde van de sleutelbits raden, krijgen we het resultaat van een “afgekapt” cijfer, en als we het niet raden, zullen we feitelijk “de gegevens nog verder versleutelen”, wat de kans alleen maar zal verminderen. afhankelijkheid tussen de hierboven genoemde blokken (het verschil zit in een aantal vaste posities). Met andere woorden, als er onder de resultaten van een dergelijke "aanvullende verwerking" van cijferteksten nogal wat paren waren die verschillen in de ons bekende vaste posities, dan betekent dit dat we de vereiste sleutelbits hebben geraden. Anders zullen er aanzienlijk minder van dergelijke paren zijn. Omdat in elke ronde slechts een deel van de sleutel wordt gebruikt, zijn de gezochte bits (dat wil zeggen de sleutelbits die in de laatste ronde zijn gebruikt) niet zo talrijk als de bits in de volledige sleutel en kunnen ze eenvoudigweg worden herhaald door de bovenstaande stappen te herhalen . In dit geval zullen we ooit zeker de juiste betekenis tegenkomen.

Uit de bovenstaande beschrijving volgt dat het belangrijkste bij de differentiële analysemethode de aantallen van die posities in platte teksten en cijferteksten zijn, waarbij de verschillen een sleutelrol spelen bij het terugvinden van de sleutelbits. De fundamentele aanwezigheid van deze posities, evenals de reeks van hun getallen, hangt rechtstreeks af van de eigenschappen van die niet-lineaire transformaties die in elk blokcijfer worden gebruikt (meestal is alle ‘niet-lineariteit’ geconcentreerd in de zogenaamde S-boxen of vervangende knooppunten).

Courtois gebruikt een licht gewijzigde versie van de differentiële methode. Laten we meteen opmerken dat Courtois zijn analyse uitvoert voor S-boxen die verschillen van de huidige en van die voorgesteld in ISO. Het werk biedt differentiële kenmerken (de getallen waarin de blokken moeten verschillen) voor een klein aantal rondes. De rechtvaardiging voor het uitbreiden van de kenmerken voor meer rondes is, zoals gebruikelijk, gebaseerd op “feiten”. Courtois drukt, opnieuw, met niets anders dan zijn autoriteit, een niet-ondersteunde veronderstelling uit dat het veranderen van de S-boxen de weerstand van GOST 28147-89 tegen zijn aanval niet zal beïnvloeden (terwijl om onbekende redenen de S-boxen uit de eerste werkversie van de aanvulling op de norm ISO/IEC 18033-3 werd niet in overweging genomen). De analyse van de auteurs van het artikel laat zien dat zelfs als we de ongefundeerde ‘feiten’ van Courtois over geloof nemen en GOST 28147-89 analyseren met andere S-blokken, de aanval opnieuw niet beter blijkt te zijn dan een volledige zoektocht.

Een gedetailleerde analyse van de werken van Courtois met een gedetailleerde onderbouwing van de ongegrondheid van alle uitspraken over de afname van de weerstand van de Russische standaard werd uitgevoerd in de werken [,].

Tegelijkertijd geeft zelfs Courtois zelf het absolute gebrek aan nauwkeurigheid in de berekeningen toe! De volgende dia is afkomstig uit de presentatie van Courtois tijdens de kortetermijnsectie van FSE 2012.

Opgemerkt moet worden dat het werk van Courtois ook herhaaldelijk is bekritiseerd door buitenlandse onderzoekers. Zijn werk aan het construeren van aanvallen op het AES-blokversleutelingsalgoritme met behulp van de XSL-methode bevatte bijvoorbeeld dezelfde fundamentele tekortkomingen als het werk aan de analyse van de Russische standaard: de meeste schattingen van de arbeidsintensiteit verschijnen in de tekst volledig ongefundeerd en ongefundeerd - gedetailleerd kritiek vind je bijvoorbeeld op het werk. Bovendien geeft Courtois zelf toe dat hij wijdverbreid wordt geweigerd om zijn werk te publiceren op grote cryptografieconferenties en in gevestigde peer-reviewed tijdschriften, waardoor hij vaak alleen de kans krijgt om te spreken in de korte aankondigingssectie. Hierover kunt u bijvoorbeeld lezen in hoofdstuk 3 van het werk. Hier zijn enkele citaten van Courtois zelf met betrekking tot zijn werk:

• “Ik denk dat het publiek van Asiacrypt het niet interessant zal vinden.” Asiacrypt 2011-recensent.
• “… er is een groot, groot, groot probleem: deze aanval, die de belangrijkste bijdrage van het artikel is, is al gepubliceerd op FSE’11 (het was zelfs het beste artikel), …”. Recensent voor Crypto 2011.

Het professionele deel van de internationale cryptografische gemeenschap beschouwt de kwaliteit van het werk van Courtois dus met niet minder twijfel dan bijvoorbeeld de uitspraken van sommige Russische specialisten over hun vermogen om AES voor 2.100 te kraken, die niet worden bevestigd door consistente berekeningen, of de laatste ‘bewijs’ van een hypothese van twee pagina’s over de ongelijkheid van complexiteitsklassen P en NP.

Aanvallen door Isobe en Dinur-Dankelman-Shamir

Het algemene idee van de Isobe () en Dinur-Dankelman-Shamir-aanvallen (hierna: DDS-aanval) () is om voor een bepaalde (sleutelafhankelijke) smalle set platte teksten een gelijkwaardige transformatie op deze set te construeren, die een structuur eenvoudiger dan de encryptietransformatie zelf. In het geval van de Isobe-methode is dit de set van 64-bits blokken x zodat F 8 -1 (Swap(F 8 (z))) = z, waarbij z = F 16 (x), tot en met F 8 ( x) en F 16 (x) geven respectievelijk de eerste 8 en eerste 16 ronden van GOST 28147-89-codering aan, via Swap - de bewerking waarbij de helften van een woord van 64 bytes worden verwisseld. Als de leesbare tekst in deze set is opgenomen, valt het resultaat van de volledige transformatie van 32 ronden van GOST 28147-89 samen met het resultaat van de transformatie van 16 ronden, wat de auteur van de aanval exploiteert. In het geval van de DDS-methode is dit de verzameling van x zodanig dat F 8 (x) = x (vast punt van de transformatie F 8). Voor elke leesbare tekst uit deze set werkt de GOST 28147-89-transformatie precies hetzelfde als de laatste 8 ronden, wat de analyse vereenvoudigt.

De complexiteit van de Isobe-aanval bedraagt ​​2.224 encryptie-operaties, de DDS-aanval is 2.192. Alle vragen over de vraag of de Isobe- en DDS-aanvallen nieuwe beperkingen introduceren op de voorwaarden voor het gebruik van ons algoritme worden echter weggenomen door de vereisten te beoordelen voor de hoeveelheid materiaal die nodig is om elk van de aanvallen uit te voeren: de Isobe-methode vereist 2 32 paar platte tekst en cijfertekst, en voor de DDS-methode - 2 64. Het verwerken van dergelijke hoeveelheden materiaal zonder de sleutel te veranderen is a priori onaanvaardbaar voor elk blokcijfer met een bloklengte van 64: op materiaal van volume 2 32 , rekening houdend met het probleem van verjaardagen (zie bijvoorbeeld ), de waarschijnlijkheid van voorkomen van herhaalde blokken is bijna 1/2, wat ervoor zorgt dat de aanvaller bepaalde conclusies over de leesbare teksten uit de cijferteksten kan trekken zonder de sleutel te bepalen. De aanwezigheid van 264 paren gewone en gecodeerde teksten die op één sleutel zijn verkregen, stelt de vijand in feite in staat versleutelings- en decoderingsoperaties uit te voeren zonder deze sleutel überhaupt te kennen. Dit komt door een puur combinatorische eigenschap: de vijand heeft in dit geval de volledige encryptieconversietabel. Deze situatie is onder alle redelijke bedrijfsomstandigheden absoluut onaanvaardbaar. In CryptoPro CSP is er bijvoorbeeld een technische beperking op het volume van gecodeerd materiaal (zonder sleutelconversie) van 4 MB (zie). Een strikt verbod op het gebruik van een sleutel op materiaal met een dergelijk volume is dus inherent aan elk blokcijfer met een bloklengte van 64 bits, en daarom beperken Isobe- en DDS-aanvallen op geen enkele manier de reikwijdte van het gebruik van het GOST 28147-89-algoritme. met behoud van de maximaal mogelijke sterkte van 2.256.

Natuurlijk moet worden opgemerkt dat onderzoekers (Isobe en Dinur-Dankelman-Shamir) hebben aangetoond dat sommige eigenschappen van het GOST 28147-89-algoritme het mogelijk maken om analysepaden te vinden waarmee de makers van het algoritme geen rekening hebben gehouden. De eenvoudige vorm van het sleutelschema, die de taak van het construeren van effectieve implementaties aanzienlijk vereenvoudigt, maakt het ook mogelijk dat in zeldzame gevallen sleutels en platte teksten eenvoudiger beschrijvingen construeren van de transformaties die door het algoritme worden geproduceerd.

Het werk toont aan dat deze negatieve eigenschap van het algoritme gemakkelijk kan worden geëlimineerd met volledig behoud van operationele kenmerken, maar helaas is het een integraal onderdeel van het algoritme in zijn algemeen gebruikte vorm.

Merk op dat een zekere nalatigheid bij het schatten van de gemiddelde arbeidsintensiteit ook aanwezig is in het werk van Dinur, Dunkelman en Shamir. Bij het construeren van een aanval wordt dus niet de nodige aandacht besteed aan het volgende punt: voor een aanzienlijk deel van de sleutels is de set leesbare teksten x, zodat F 8 (x) = x, leeg: er kunnen eenvoudigweg geen vaste punten zijn voor 8 transformatierondes. Het bestaan ​​van vaste punten hangt ook af van de keuze van vervangende knooppunten. De aanval is dus alleen van toepassing op bepaalde vervangende knooppunten en sleutels.

Het is ook de moeite waard om nog een werk te vermelden met een aanval op GOST 28147-89. In februari 2012 verscheen een bijgewerkte versie van het artikel (gedateerd november 2011) in het elektronische archief ePrint van de internationale cryptografische vereniging, die een nieuwe aanval op GOST 28147-89 bevatte. De kenmerken van de gepresenteerde aanval zijn als volgt: het materiaalvolume is 2 32 (zoals Isobe) en de arbeidsintensiteit is 2 192 (zoals DDS). Deze aanval verbeterde dus de tijdrecord DDS-aanval in termen van materieel volume van 2 64 naar 2 32. We merken afzonderlijk op dat de auteurs alle berekeningen eerlijk hebben gepresenteerd met rechtvaardiging voor de complexiteit en het volume van het materiaal. Na 9 maanden werd een fundamentele fout gevonden in bovenstaande berekeningen en sinds november 2012 bevat de bijgewerkte versie van het artikel in het elektronische archief geen resultaten meer met betrekking tot het binnenlandse algoritme.

Aanvallen waarbij wordt aangenomen dat de aanvaller "iets" weet over de sleutels

Ten slotte merken we op dat er in de literatuur ook een aantal werken zijn (zie bijvoorbeeld en ) gewijd aan aanvallen op GOST 28147-89 in het zogenaamde gekoppelde sleutelmodel. Dit model gaat in principe uit van de aanname dat een aanvaller voor analyse niet alleen toegang kan krijgen tot paren open teksten en versleuteld met de gewenste sleutel, maar ook tot paren open en versleutelde teksten verkregen met (ook onbekende) sleutels die verschillen van de gewenste sleutel. op bekende reguliere wijze (bijvoorbeeld in vaste bitposities). In dit model is het inderdaad mogelijk om interessante resultaten te verkrijgen over GOST 28147-89, maar in dit model is het mogelijk om niet minder sterke resultaten te verkrijgen over bijvoorbeeld de AES-standaard, die het meest wordt gebruikt in moderne openbare netwerken ( zie bijvoorbeeld). Merk op dat de voorwaarden voor het uitvoeren van dit soort aanvallen ontstaan ​​bij het gebruik van een cijfer in een bepaald protocol. Opgemerkt moet worden dat dit soort resultaten, hoewel ze van onbetwist academisch belang zijn vanuit het oogpunt van het bestuderen van de eigenschappen van cryptografische transformaties, feitelijk niet relevant zijn voor de praktijk. Alle tools voor de bescherming van cryptografische informatie die zijn gecertificeerd door de FSB van Rusland voldoen bijvoorbeeld aan de strengste eisen voor het genereren van coderingssleutels (zie bijvoorbeeld). Zoals aangegeven in de resultaten van de analyse, is de complexiteit van het volledig openen van de privésleutel, met een kans op succes van 1-10-4, feitelijk 2 26 als er 18 bijbehorende sleutels en 2 10 paren platte tekst- en cijfertekstblokken zijn. . Als echter aan de bovengenoemde vereisten voor de ontwikkeling van sleutelmateriaal wordt voldaan, is de kans op het vinden van dergelijke sleutels 2 -4352, dat wil zeggen 24096 keer minder dan wanneer u eenvoudigweg bij de eerste poging de geheime sleutel probeert te raden.

Werken gerelateerd aan het model met gekoppelde sleutels omvatten ook werk dat in 2010 veel ophef veroorzaakte in Russische elektronische publicaties, die niet de gewoonte hebben om het materiaal in de race op sensaties zorgvuldig te controleren. De daarin gepresenteerde resultaten werden niet ondersteund door enige rigoureuze rechtvaardiging, maar bevatten luide uitspraken over het vermogen om binnen enkele seconden de staatsnorm van de Russische Federatie op een zwakke laptop te hacken - over het algemeen is het artikel in de beste tradities geschreven van Nicolas Courtois. Maar ondanks de absoluut duidelijke ongegrondheid van het artikel voor de lezer die min of meer bekend is met de basisprincipes van wetenschappelijke publicaties, was het juist om het Russische publiek na het werk gerust te stellen dat Rudsky een gedetailleerde en grondige tekst schreef met daarin een uitgebreide analyse. van deze tekortkoming. Het artikel met de voor zichzelf sprekende titel “Over de nul-praktische betekenis van het werk “Key recovery aanval op volledige GOST-blokcodering met nul tijd en geheugen”” rechtvaardigt dat de gemiddelde complexiteit van de gegeven methode niet minder is dan de complexiteit van een volledige zoektocht.

Droogresten: wat is duurzaamheid in de praktijk?

Concluderend presenteren we een tabel met gegevens over alle resultaten van strikt beschreven en gerechtvaardigde aanvallen op GOST 28147-89 die bekend zijn bij de internationale cryptografische gemeenschap. Merk op dat de complexiteit wordt gegeven in de versleutelingsbewerkingen van het GOST 28147-89-algoritme, en dat het geheugen en het materiaal worden aangegeven in algoritmeblokken (64 bits = 8 bytes).

Aanval	Arbeidsintensiteit	Geheugen	Benodigd materiaal
Isobe	2 224	2 64	2 32
Dinur-Dankelman-Shamir, FP, 2DMitM	2 192	2 36	2 64
Dinur-Dankelman-Shamir, FP, weinig geheugen	2 204	2 19	2 64
	2 224	2 36	2 32
Dinur-Dankelman-Shamir, Reflectie, 2DMitM	2 236	2 19	2 32
Volledige zoekopdracht	2 256	1	4
Aantal nanoseconden sinds de schepping van het heelal	2 89

Ondanks een vrij grootschalige onderzoekscyclus op het gebied van de weerstand van het GOST 28147-89-algoritme, is er op dit moment geen enkele aanval bekend waarvan de voorwaarden voor de implementatie haalbaar zouden zijn met de bijbehorende operationele vereisten voor een bloklengte van 64 bits. De beperkingen op de hoeveelheid materiaal die op één sleutel kan worden verwerkt als gevolg van de coderingsparameters (sleutelbitlengte, blokbitlengte) zijn aanzienlijk strenger dan het minimale volume dat nodig is om een ​​op dit moment bekende aanval uit te voeren. Bijgevolg maakt geen van de tot nu toe voorgestelde cryptanalysemethoden in GOST 28147-89 het mogelijk om een ​​sleutel te bepalen met een arbeidsintensiteit die minder is dan uitputtend zoeken, wanneer wordt voldaan aan de bestaande operationele vereisten.

In ons land is een uniform algoritme voor cryptografische weergave van gegevens vastgesteld voor informatieverwerkingssystemen in computernetwerken, individuele computersystemen en computers, dat wordt bepaald GOST 28147-89.

Dit cryptografische dataconversie-algoritme is een 64-bits blokalgoritme met een 256-bits sleutel, ontworpen voor hardware- en software-implementatie, voldoet aan cryptografische eisen en legt geen beperkingen op aan de mate van geheimhouding van de beschermde informatie.

Bij het beschrijven van het algoritme wordt de volgende notatie gebruikt:

L en R - bitreeksen;
LR is een aaneenschakeling van reeksen L en R, waarbij de bits van de reeks R de bits van de reeks L volgen;
(+) - bitsgewijze optelling modulo 2 ("exclusieve OF"-bewerking);
[+] - toevoeging van 32-bits getallen modulo 2 32;
(+) - toevoeging van 32-bits getallen modulo 2 32 -1.

De getallen worden opgeteld volgens de volgende regel:

A [+] B = A + B als A + B< 2 32 ,
A [+] B = A + B - 2 32 als A + B >= 2 32 . A (+) B = A + B als A + B< 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

Het algoritme biedt vier bedrijfsmodi:

In ieder geval wordt een 256-bits sleutel K gebruikt om gegevens te coderen, die wordt weergegeven als acht 32-bits subsleutels K i:

K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .

Decodering wordt uitgevoerd met dezelfde sleutel als codering, maar het proces is het omgekeerde van het gegevenscoderingsproces.

Eenvoudige vervangingsmodus

De eerste en gemakkelijkste modus is vervanging. De te versleutelen gegevens worden verdeeld in blokken van 64 bits. De versleutelingsprocedure voor een blok open data To omvat 32 cycli (j=1...32).

Blok To is verdeeld in twee reeksen van 32 bits: B(0)A(0), waarbij B(0) de bits van de linker- of hogere orde zijn, en A(0) de bits van de rechter- of lage-orde zijn.

Deze reeksen worden vóór het begin van de eerste encryptiecyclus in de schijven N1 en N2 ingevoerd.

De eerste cyclus (j=1) van de coderingsprocedure voor een 64-bits datablok wordt beschreven door de volgende formules:

Hier geeft i het iteratienummer aan (i = 1, 2,..., 32).

De functie f wordt de encryptiefunctie genoemd. Het argument is de som, modulo 2, van 32 getallen A(i), verkregen bij de vorige iteratiestap, en het sleutelgetal X(j) (de dimensie van elk van deze getallen is 32 cijfers).

De coderingsfunctie omvat twee bewerkingen op de resulterende 32-bits som. De eerste operatie heet substitutie K. Het substitutieblok K bestaat uit 8 substitutieknooppunten K(1) ... K(8) met elk een geheugen van 64 bits. De 32-bits vector die aankomt bij het substitutieblok wordt verdeeld in 8 opeenvolgende 4-bits vectoren, die elk worden omgezet in een 4-bits vector door het overeenkomstige vervangingsknooppunt, dat een tabel is met 16 gehele getallen in het bereik 0.. .15.

De invoervector specificeert het adres van een rij in de tabel, waarvan een getal de uitvoervector is. De 4-bits uitgangsvectoren worden vervolgens opeenvolgend samengevoegd tot een 32-bits vector. De vervangingsbloktabel K bevat sleutelelementen die gemeenschappelijk zijn voor het computernetwerk en zelden worden gewijzigd.

De tweede bewerking is een cyclische verschuiving naar links van de 32-bits vector die wordt verkregen als resultaat van de vervanging van K. Het 64-bits blok van gecodeerde gegevens Tsh wordt weergegeven als Tsh = A (32) B (32).

De resterende blokken open data in de eenvoudige vervangingsmodus worden op dezelfde manier gecodeerd.

Houd er rekening mee dat de eenvoudige vervangingsmodus slechts in beperkte gevallen kan worden gebruikt om gegevens te coderen. Deze gevallen omvatten de ontwikkeling van een sleutel en de codering ervan met het bieden van imitatiebescherming (bescherming tegen het opleggen van valse gegevens) voor verzending via communicatiekanalen of opslag in computergeheugen.

Gamma-modus

Open data, verdeeld in 64-bits blokken T(i) (i=1, 2,..., m, waarbij m wordt bepaald door het volume aan gecodeerde data), wordt gecodeerd in de gammamodus door bitsgewijze optelling modulo 2 met het gammacijfer Гш, dat wordt geproduceerd in blokken van 64 bits, dat wil zeggen Гш = (Г(1),Г(2),...,Г(i),...,Г(m)).

De gegevenscoderingsvergelijking in de gammamodus kan als volgt worden weergegeven:

Ø(i) = A (Y(i-1) [+] C2, Z(i-1) (+) C1) (+) T(i) = Г(i) (+) T(i) .
Hier is Ø(i) een 64-bits blok cijfertekst,
A - coderingsfunctie in eenvoudige vervangingsmodus (de argumenten van deze functie zijn twee 32-bits getallen),
C1 en C2 zijn constanten gespecificeerd in GOST 28147-89,
Y(i) en Z(i) zijn grootheden die iteratief worden bepaald terwijl de gamma als volgt wordt gevormd:
(Y(0), Z(0)) = A(S), waarbij S een binaire reeks van 64 bits is (synchronisatiebericht);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) (+) C1) voor i = 1, 2,...,m.

Het decoderen van gegevens is alleen mogelijk in de aanwezigheid van een synchronisatiebericht, dat geen geheim onderdeel van het cijfer is en kan worden opgeslagen in het computergeheugen of samen met gecodeerde gegevens via communicatiekanalen kunnen worden verzonden.

Gammamodus met feedback

Modus gokken met feedback lijkt sterk op de gammamodus. Net als in de gammamodus worden open data, verdeeld in 64-bits blokken T(i) (i=1, 2,..., m, waarbij m wordt bepaald door het volume aan gecodeerde data), gecodeerd door bitsgewijze optelling modulo 2 met het gammacijfer Г sh, dat wordt geproduceerd in blokken van 64 bits:

Gw = (G(1),G(2),...,G(i),...,G(m)).

Het aantal binaire cijfers in het T(m)-blok kan kleiner zijn dan 64, terwijl het deel van het codegamma dat niet wordt gebruikt voor encryptie uit het G(m)-blok wordt weggegooid.

De gegevenscoderingsvergelijking in de gesloten-lus-gammamodus kan als volgt worden weergegeven:

Hier is Ø(i) een 64-bits blok cijfertekst,
A - coderingsfunctie in eenvoudige vervangingsmodus. Het functieargument bij de eerste stap van het iteratieve algoritme is een 64-bits synchronisatiebericht, en bij alle volgende stappen is het het vorige blok met gecodeerde gegevens Ø(i-1).

Ontwikkelingen van imitatie-inzetstukken

Productieproces imitovstaki is uniform voor elk van de gegevensversleutelingsmodi.

Imitatie-invoeging is een blok van p bits (imitatie-invoeging Ir), dat wordt gegenereerd voordat het volledige bericht wordt gecodeerd, of parallel aan blok-voor-blok-codering. De eerste blokken open data die deelnemen aan het genereren van de imitatieve invoeging kunnen dienstinformatie bevatten (bijvoorbeeld het adresgedeelte, de tijd, het synchronisatiebericht) en zijn niet gecodeerd. De waarde van de parameter p (het aantal binaire bits in de simulatie-insert) wordt bepaald door cryptografische vereisten, rekening houdend met het feit dat de waarschijnlijkheid van het opleggen van valse interferentie gelijk is aan 1/2^p.

Om een ​​gesimuleerde invoeging te verkrijgen, worden open data gepresenteerd in de vorm van 64-bits blokken T(i) (i = 1, 2,..., m, waarbij m wordt bepaald door het volume aan gecodeerde data). Het eerste blok met gewone gegevens T(1) ondergaat een transformatie die overeenkomt met de eerste 16 cycli van het versleutelingsalgoritme in de eenvoudige vervangingsmodus. Bovendien wordt de sleutel die wordt gebruikt om de gegevens te coderen gebruikt als een sleutel om de imitatie-invoeging te genereren.

Het 64-bits getal verkregen na 16 werkingscycli wordt modulo 2 opgeteld met het tweede blok open data T(2). Het resultaat van de optelling wordt opnieuw onderworpen aan een transformatie die overeenkomt met de eerste 16 cycli van het versleutelingsalgoritme in de eenvoudige vervangingsmodus. Het resulterende 64-bits getal wordt modulo 2 opgeteld bij het derde blok open data T(3), enz. Het laatste blok T(m), indien nodig opgevuld tot een volledig 64-bits blok met nullen, wordt modulo 2 opgeteld met het resultaat van het werk in stap m-1, waarna het wordt gecodeerd in eenvoudige vervangingsmodus over de eerste 16 cycli van het algoritme. Uit het resulterende 64-bits getal wordt een segment Ir met een lengte p bits geselecteerd.

De imitatieve invoeging Ir wordt na de gecodeerde gegevens via een communicatiekanaal of in het computergeheugen verzonden. De ontvangen gecodeerde gegevens worden gedecodeerd, en uit de ontvangen blokken open gegevens T(i) wordt een gesimuleerde invoeging Ir gegenereerd, die vervolgens wordt vergeleken met een gesimuleerde invoeging Ir ontvangen van het communicatiekanaal of uit het computergeheugen. invoegingen komen niet overeen, alle gedecodeerde gegevens worden als vals beschouwd.

GOST 28147-89-coderingsalgoritme, het gebruik ervan en de software-implementatie voor computers op het Intel x86-platform.

Andrej Vinokurov

Beschrijving van het algoritme.

Termen en benamingen.

Een beschrijving van de encryptiestandaard van de Russische Federatie is opgenomen in een zeer interessant document met de titel “Cryptografisch conversie-algoritme GOST 28147-89”. Het feit dat er in de naam in plaats van de term ‘encryptie’ een algemener concept voorkomt “ cryptografische conversie ”, is helemaal niet toevallig. Naast verschillende nauw verwante versleutelingsprocedures beschrijft het document één algoritme voor het genereren imitatie inzetstukken . Dit laatste is niets meer dan een cryptografische controlecombinatie, dat wil zeggen een code die wordt gegenereerd op basis van de originele gegevens met behulp van een geheime sleutel met als doel imitatie bescherming of het beschermen van gegevens tegen ongeoorloofde wijzigingen.

Bij verschillende stappen van GOST-algoritmen worden de gegevens waarmee ze werken op verschillende manieren geïnterpreteerd en gebruikt. In sommige gevallen worden data-elementen behandeld als reeksen van onafhankelijke bits, in andere gevallen als een geheel getal zonder teken, in andere gevallen als een gestructureerd complex element dat uit verschillende eenvoudiger elementen bestaat. Om verwarring te voorkomen is het daarom belangrijk om overeenstemming te bereiken over de gebruikte notatie.

Gegevenselementen in dit artikel worden aangegeven met hoofdletters en cursief (bijvoorbeeld X). Via | X| geeft de grootte van het data-element aan X in stukjes. Dus als we het data-element interpreteren X Als een niet-negatief geheel getal kunnen we de volgende ongelijkheid schrijven:

Als een data-element uit meerdere kleinere elementen bestaat, wordt dit feit als volgt aangegeven: X=(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n-1. Het proces waarbij verschillende gegevenselementen tot één worden gecombineerd, wordt genoemd aaneenschakeling gegevens en wordt aangegeven door het symbool “||”. Voor de grootte van data-elementen moet uiteraard aan de volgende relatie worden voldaan: | X|=|X 0 |+|X 1 |+…+|X n-1 |. Bij het specificeren van complexe data-elementen en de aaneenschakelingsbewerking worden de samenstellende data-elementen weergegeven in oplopende volgorde van prioriteit. Met andere woorden, als we het samengestelde element en al zijn data-elementen interpreteren als gehele getallen zonder teken, kunnen we de volgende gelijkheid schrijven:

In het algoritme kan een data-element worden geïnterpreteerd als een array van individuele bits, in welk geval de bits worden aangegeven met dezelfde letter als de array, maar in kleine letters, zoals weergegeven in het volgende voorbeeld:

X=(X 0 ,X 1 ,…,x n –1)=X 0 +2 1 · X 1 +…+2 N-1 · x n –1 .

Dus, als je het gemerkt hebt, is de zogenaamde GOST aangenomen. “little-endian” nummering van cijfers, d.w.z. Binnen datawoorden met meerdere bits zijn individuele bits en groepen bits met een lager nummer minder significant. Dit staat direct vermeld in paragraaf 1.3 van de standaard: “Bij het toevoegen en cyclisch verschuiven van binaire vectoren worden de meest significante bits beschouwd als de bits van schijven met grote getallen.” Verder vereisen clausules van de standaard 1.4, 2.1.1 en andere dat het beginnen met het vullen van de opslagregisters van het virtuele versleutelingsapparaat met gegevens uit de laagste, d.w.z. minder belangrijke categorieën. Precies dezelfde nummeringsvolgorde wordt aangenomen in de Intel x86-microprocessorarchitectuur. Daarom zijn er bij het implementeren van een cijfer in software op deze architectuur geen extra permutaties van bits binnen datawoorden vereist.

Als een bewerking met een logische betekenis wordt uitgevoerd op data-elementen, wordt aangenomen dat deze bewerking wordt uitgevoerd op de overeenkomstige bits van de elementen. Met andere woorden A B=(A 0 B 0 ,A 1 B 1 ,…,een –1 b n–1), waar N=|A|=|B|, en het symbool “ ” geeft een willekeurige binaire logische bewerking aan; in de regel betekent dit een operatie exclusief of , wat ook de werking is van sommatie modulo 2:

De logica van het construeren van een cijfer en de structuur van GOST-sleutelinformatie.

Als je de originele GOST 28147–89 zorgvuldig bestudeert, zul je merken dat deze een beschrijving van algoritmen op verschillende niveaus bevat. Helemaal bovenaan staan ​​praktische algoritmen die zijn ontworpen om data-arrays te coderen en er imitatieve inserts voor te ontwikkelen. Ze zijn allemaal gebaseerd op drie algoritmen op laag niveau, genoemd in de GOST-tekst cycli . Deze fundamentele algoritmen worden in dit artikel aangeduid als basiscycli om ze te onderscheiden van alle andere cycli. Ze hebben de volgende namen en symbolen, deze staan ​​tussen haakjes en hun betekenis zal later worden uitgelegd:

• versleutelingscyclus (32-З);
• decoderingscyclus (32-P);
• productiecyclus van imitatie-inzetstuk (16-Z).

Op zijn beurt is elk van de basiscycli een meervoudige herhaling van één enkele procedure, die verder in dit werk om duidelijkheid vraagt de belangrijkste stap van crypto-conversie .

Om GOST te begrijpen, moet je dus de volgende drie dingen begrijpen:

• wat is er gebeurd fundamentele stap crypto-conversies;
• hoe basiscycli worden gevormd uit basisstappen;
• vanaf drie basiscycli alle praktische GOST-algoritmen worden opgeteld.

Voordat we verder gaan met het bestuderen van deze kwesties, moeten we het hebben over de belangrijkste informatie die door GOST-algoritmen wordt gebruikt. In overeenstemming met het principe van Kirchhoff, waaraan alle moderne cijfers die bij het grote publiek bekend zijn, voldoen, is het de geheimhouding ervan die de geheimhouding van het gecodeerde bericht garandeert. In GOST bestaat sleutelinformatie uit twee datastructuren. Naast de feitelijke sleutel , noodzakelijk voor alle cijfers, bevat het ook vervangingstabel . Hieronder staan ​​​​de belangrijkste kenmerken van de belangrijkste structuren van GOST.

De belangrijkste stap van crypto-conversie.

De basisstap voor cryptoconversie is in wezen een instructie die de conversie van een 64-bits gegevensblok specificeert. Een extra parameter van deze operator is een 32-bits blok, dat als sleutelelement wordt gebruikt. Het algoritmediagram van de hoofdstap wordt getoond in Figuur 1.

Figuur 1. Schema van de hoofdstap van crypto-conversie van het GOST 28147-89-algoritme.

Hieronder vindt u uitleg van het hoofdstapalgoritme:

Stap 0

• N– een geconverteerd 64-bit datablok, tijdens de uitvoering van de stap zijn ondergeschikte ( N 1) en senioren ( N 2) de delen worden behandeld als afzonderlijke 32-bit gehele getallen zonder teken. Zo kunnen we schrijven N=(N 1 ,N 2).
• X– 32-bit sleutelelement;

Stap 1

Toevoeging met een sleutel. De onderste helft van het geconverteerde blok wordt modulo 2 32 toegevoegd met het sleutelelement dat bij de stap wordt gebruikt, het resultaat wordt overgedragen naar de volgende stap;

Stap 2

Vervanging van blokken. De 32-bits waarde die in de vorige stap is verkregen, wordt geïnterpreteerd als een array van acht 4-bits codeblokken: S=(S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), en S 0 bevat de 4 jongsten, en S 7 – 4 meest significante bits S.

Vervolgens wordt de waarde van elk van de acht blokken vervangen door een nieuwe, die als volgt uit de vervangingstabel wordt geselecteerd: blokwaarde S ik veranderd naar S ik-de element in volgorde (nummering vanaf nul) i-dat vervangende knooppunt (d.w.z. i-de regel van de vervangingstabel, nummering ook helemaal opnieuw). Met andere woorden, een element uit de vervangingstabel met een rijnummer dat gelijk is aan het nummer van het blok dat wordt vervangen en een kolomnummer dat gelijk is aan de waarde van het blok dat wordt vervangen als een 4-bits niet-negatief geheel getal, wordt als vervanging geselecteerd. voor de waarde van het blok. Dit maakt de grootte van de vervangingstabel duidelijk: het aantal rijen daarin is gelijk aan het aantal 4-bits elementen in een 32-bits datablok, dat wil zeggen acht, en het aantal kolommen is gelijk aan het aantal verschillende waarden van een 4-bit datablok, waarvan bekend is dat het 2 4, zestien is.

Stap 3

Draai 11 bits naar links. Het resultaat van de vorige stap wordt cyclisch met 11 bits verschoven naar de meest significante bits en verzonden naar de volgende stap. In het algoritmediagram geeft het symbool de functie aan van het cyclisch verschuiven van zijn argument 11 bits naar links, d.w.z. richting de hogere rangen.

Stap 4

Bitsgewijze optelling: De in stap 3 verkregen waarde wordt bitsgewijze modulo 2 opgeteld, waarbij de hogere helft van het blok wordt geconverteerd.

Stap 5

Verschuiving langs de keten: het onderste deel van het geconverteerde blok wordt verschoven naar de plaats van het oudere blok en het resultaat van de vorige stap wordt op zijn plaats geplaatst.

Stap 6

De resulterende waarde van het geconverteerde blok wordt geretourneerd als resultaat van het uitvoeren van het algoritme van de belangrijkste cryptoconversiestap.

Basiscycli van cryptografische transformaties.

Zoals opgemerkt aan het begin van dit artikel, behoort GOST tot de klasse van blokcijfers, dat wil zeggen dat de eenheid van informatieverwerking daarin een datablok is. Daarom is het heel logisch om te verwachten dat het algoritmen zal definiëren voor cryptografische transformaties, dat wil zeggen voor het coderen, decoderen en ‘verrekenen’ van een besturingscombinatie van één gegevensblok. Deze algoritmen worden genoemd basiscycli GOST, die hun fundamentele belang voor de constructie van dit cijfer benadrukt.

Basislussen zijn opgebouwd uit belangrijkste stappen cryptografische transformatie besproken in de vorige sectie. Tijdens de hoofdstap wordt slechts één 32-bits sleutelelement gebruikt, terwijl de GOST-sleutel acht van dergelijke elementen bevat. Om de sleutel volledig te kunnen gebruiken, moet daarom elk van de basislussen herhaaldelijk de hoofdstap met zijn verschillende elementen uitvoeren. Tegelijkertijd lijkt het heel natuurlijk dat in elke basiscyclus alle sleutelelementen hetzelfde aantal keren moeten worden gebruikt; om redenen van codeersterkte zou dit aantal meer dan één moeten zijn.

Alle hierboven gemaakte aannames, eenvoudigweg gebaseerd op gezond verstand, bleken correct te zijn. Basislussen bestaan ​​uit herhaalde uitvoering belangrijkste stap gebruiken verschillende sleutelelementen en verschillen alleen van elkaar in het aantal stapherhalingen en de volgorde waarin de sleutelelementen worden gebruikt. Hieronder vindt u deze volgorde voor verschillende cycli.

Versleutelingscyclus 32-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Figuur 2a. Versleutelingscyclusschema 32-З

Decoderingscyclus 32-P:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Figuur 2b. Schema van de 32-P-decoderingscyclus

Productiecyclus van imitatie inzetstuk 16-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 .

Figuur 2c. Schema van de productiecyclus van imitatie-inzetstuk 16-Z.

Elk van de cycli heeft zijn eigen alfanumerieke aanduiding die overeenkomt met het patroon " n-X", waarbij het eerste element van de aanduiding ( N), specificeert het aantal herhalingen van de hoofdstap in de cyclus, en het tweede aanduidingselement ( X), letter, specificeert de volgorde van codering (“Z”) of decodering (“P”) bij het gebruik van sleutelelementen. Deze bestelling heeft verdere uitleg nodig:

De decryptiecyclus moet het omgekeerde zijn van de encryptiecyclus, dat wil zeggen dat de opeenvolgende toepassing van deze twee cycli op een willekeurig blok uiteindelijk het originele blok moet opleveren, wat wordt weerspiegeld in de volgende relatie: C 32-Р ( C 32-З ( T))=T, Waar T– willekeurig 64-bit datablok, C X ( T) – het resultaat van de lusuitvoering X boven het datablok T. Om aan deze voorwaarde te voldoen voor algoritmen vergelijkbaar met GOST, is het noodzakelijk en voldoende dat de volgorde van gebruik van sleutelelementen door de overeenkomstige cycli onderling omgekeerd is. Het is gemakkelijk om de geldigheid van de schriftelijke voorwaarde voor het onderhavige geval te verifiëren door de bovenstaande reeksen voor cycli 32-З en 32-Р te vergelijken. Uit het bovenstaande volgt één interessante consequentie: de eigenschap dat een cyclus omgekeerd is aan een andere cyclus, is wederkerig, dat wil zeggen dat de 32-Z-cyclus omgekeerd is aan de 32-P-cyclus. Met andere woorden, het coderen van een gegevensblok kan theoretisch worden uitgevoerd met behulp van een decoderingscyclus, in welk geval de decodering van een gegevensblok moet worden uitgevoerd door een encryptiecyclus. Van de twee onderling omgekeerde cycli kan er één worden gebruikt voor codering, waarna de tweede moet worden gebruikt om gegevens te decoderen. De GOST 28147-89-standaard wijst echter rollen toe aan cycli en geeft de gebruiker niet het recht om in deze kwestie te kiezen .

De cyclus voor het produceren van een imitatie-insert is half zo lang als de encryptiecycli. De volgorde van het gebruik van sleutelelementen daarin is dezelfde als in de eerste 16 stappen van de encryptiecyclus, wat gemakkelijk te verifiëren is door de bovenstaande reeksen te beschouwen. deze volgorde in de aanduiding van de cyclus wordt gecodeerd door dezelfde letter “Z”.

Schema's van basiscycli worden getoond in figuren 2a-c. Elk van hen neemt als argument en retourneert als resultaat een 64-bits gegevensblok, aangegeven in de diagrammen N. Symbool Stap( N,X) geeft de uitvoering aan van de belangrijkste crypto-transformatiestap voor een datablok N sleutelelement gebruiken X. Er is nog een verschil tussen de berekeningscycli voor encryptie en imitatieve invoeging, hierboven niet vermeld: aan het einde van de basiscoderingscycli worden de hoge en lage delen van het resultaatblok verwisseld, dit is nodig voor hun wederzijdse omkeerbaarheid.

Basisversleutelingsmodi.

GOST 28147-89 biedt de volgende drie gegevenscoderingsmodi:

• eenvoudige vervanging,
• gokken,
• gamen met feedback,

en een extra modus voor het genereren van imitatie-inzetstukken.

In elk van deze modi worden gegevens verwerkt in blokken van 64 bits, waarin de array wordt verdeeld en onderworpen aan cryptografische transformatie. Daarom verwijst GOST naar blokcijfers. In twee gammamodi is het echter mogelijk om een ​​onvolledig gegevensblok van minder dan 8 bytes te verwerken, wat essentieel is bij het coderen van data-arrays van willekeurige grootte, die geen veelvoud van 8 bytes mogen zijn.

Voordat we overgaan tot een bespreking van specifieke algoritmen voor cryptografische transformatie, is het noodzakelijk om de notatie te verduidelijken die wordt gebruikt in de diagrammen in de volgende secties:

T O, T w – respectievelijk arrays van open en gecodeerde gegevens;

, – i- opeenvolgende 64-bits blokken met respectievelijk open en gecodeerde gegevens: , , het laatste blok is mogelijk onvolledig: ;

N– aantal 64-bits blokken in de data-array;

C X – functie voor het converteren van een 64-bit datablok met behulp van het basiscyclus “X” -algoritme.

Nu zullen we de belangrijkste coderingsmodi beschrijven:

Gemakkelijke vervanging.

Codering in deze modus bestaat uit het toepassen van cyclus 32-З op blokken met open data, en decryptie - cyclus 32-Р op blokken met gecodeerde data. Dit is de eenvoudigste van de modi; 64-bits datablokken worden onafhankelijk van elkaar verwerkt. Schema's van versleutelings- en decoderingsalgoritmen in de eenvoudige vervangingsmodus worden respectievelijk weergegeven in figuren 3a en b; ze zijn triviaal en behoeven geen commentaar.

Tekening. 3a. Algoritme voor gegevenscodering in eenvoudige vervangingsmodus

Tekening. 3b. Algoritme voor gegevensdecodering in eenvoudige vervangingsmodus

De grootte van de reeks open of gecodeerde gegevens, die respectievelijk worden gecodeerd of gedecodeerd, moet een veelvoud van 64 bits zijn: | T o |=| T w |=64· N Na het uitvoeren van de bewerking verandert de grootte van de resulterende gegevensarray niet.

De eenvoudige vervangende coderingsmodus heeft de volgende kenmerken:

• Omdat datablokken onafhankelijk van elkaar en hun positie in de data-array worden gecodeerd, resulteert het coderen van twee identieke leesbare tekstblokken in identieke cijfertekstblokken en omgekeerd. De genoemde eigenschap zal de cryptanalyticus in staat stellen een conclusie te trekken over de identiteit van de originele datablokken als hij identieke blokken tegenkomt in de gecodeerde data-array, wat onaanvaardbaar is voor een serieus cijfer.
• Als de lengte van de gecodeerde data-array geen veelvoud is van 8 bytes of 64 bits, ontstaat het probleem hoe en hoe het laatste onvolledige datablok van de array moet worden aangevuld tot de volledige 64 bits. Deze taak is niet zo eenvoudig als het op het eerste gezicht lijkt. Voor de hand liggende oplossingen zoals “een onvolledig blok aanvullen met nul bits” of, algemener, “een onvolledig blok aanvullen met een vaste combinatie van nul en één bits” kunnen de cryptanalyticus onder bepaalde omstandigheden de mogelijkheid geven om brute force-methoden te gebruiken om te bepalen de inhoud van dit zeer onvolledige blok, en dit feit betekent een afname van het beveiligingscijfer. Bovendien zal de lengte van de cijfertekst veranderen, oplopend tot het dichtstbijzijnde gehele veelvoud van 64 bits, wat vaak ongewenst is.

Op het eerste gezicht maken de bovenstaande kenmerken het bijna onmogelijk om de eenvoudige vervangingsmodus te gebruiken, omdat deze alleen kan worden gebruikt om data-arrays te coderen met een grootte die een veelvoud is van 64 bits en geen herhalende 64-bits blokken bevat. Het lijkt erop dat het voor echte gegevens onmogelijk is om de vervulling van deze voorwaarden te garanderen. Dit is bijna waar, maar er is één heel belangrijke uitzondering: onthoud dat de sleutelgrootte 32 bytes is en de grootte van de vervangende tabel 64 bytes. Bovendien zal de aanwezigheid van herhaalde blokken van 8 bytes in een sleutel- of vervangingstabel wijzen op de zeer slechte kwaliteit ervan, zodat een dergelijke herhaling niet kan bestaan ​​in echte sleutelelementen. We ontdekten dus dat de eenvoudige vervangingsmodus redelijk geschikt is voor het coderen van sleutelinformatie, vooral omdat andere modi minder handig zijn voor dit doel, omdat ze een extra synchroniserend gegevenselement vereisen: een synchronisatiebericht (zie de volgende sectie). Onze inschatting is juist; GOST schrijft het gebruik van de eenvoudige vervangingsmodus exclusief voor voor het coderen van sleutelgegevens.

Gommen.

Hoe kunt u de tekortkomingen van de eenvoudige vervangingsmodus wegnemen? Om dit te doen is het noodzakelijk om het mogelijk te maken blokken met een grootte van minder dan 64 bits te coderen en ervoor te zorgen dat het cijfertekstblok afhankelijk is van het aantal ervan, met andere woorden: willekeurig maken encryptie proces. In GOST wordt dit op twee verschillende manieren bereikt in twee coderingsmodi: gokken . Gommen - dit is het opleggen (verwijderen) van een cryptografische schaal aan open (gecodeerde) gegevens, dat wil zeggen een reeks gegevenselementen die zijn gegenereerd met behulp van een cryptografisch algoritme om gecodeerde (open) gegevens te verkrijgen. Om gamma toe te passen tijdens het coderen en het te verwijderen tijdens het decoderen, moeten onderling inverse binaire bewerkingen worden gebruikt, bijvoorbeeld optellen en aftrekken modulo 2 64 voor 64-bits datablokken. In GOST wordt voor dit doel de werking van bitsgewijze optelling modulo 2 gebruikt, omdat deze het omgekeerde van zichzelf is en bovendien het eenvoudigst in hardware is geïmplementeerd. Gamma lost beide genoemde problemen op: ten eerste zijn alle gamma-elementen verschillend voor echte gecodeerde arrays en daarom zal het resultaat van het coderen van zelfs twee identieke blokken in één data-array verschillend zijn. Ten tweede kan, hoewel de gamma-elementen in gelijke delen van 64 bits worden gegenereerd, een deel van een dergelijk blok met een grootte gelijk aan de grootte van het gecodeerde blok worden gebruikt.

Laten we nu direct naar de beschrijving van de gammamodus gaan. Het gamma voor deze modus wordt als volgt verkregen: met behulp van een algoritmische terugkerende nummerreeksgenerator (RNGN) worden 64-bits datablokken gegenereerd, die vervolgens worden geconverteerd met behulp van de 32-3-cyclus, dat wil zeggen gecodeerd in de eenvoudige vervangingsmodus, resulterend in gammablokken. Vanwege het feit dat gamma-toepassing en -verwijdering worden uitgevoerd met behulp van dezelfde bitsgewijze exclusieve of bewerking, zijn de coderings- en decoderingsalgoritmen in de gammamodus identiek; hun algemene schema wordt weergegeven in figuur 4.

De RGPG die wordt gebruikt om de schaal te genereren is een terugkerende functie: – elementen van de terugkerende reeks, F– transformatiefunctie. Daarom rijst onvermijdelijk de vraag over de initialisatie ervan, dat wil zeggen over het element. In feite is dit data-element een algoritmeparameter voor gammamodi; in de diagrammen wordt het aangeduid als S, en wordt in de cryptografie genoemd synchronisatie verzenden , en in onze GOST – initiële vulling een van de encoderregisters. Om bepaalde redenen besloten de ontwikkelaars van GOST om niet het synchronisatiebericht rechtstreeks te gebruiken om de RGFC te initialiseren, maar het resultaat van de conversie volgens de 32-Z-cyclus: . De reeks elementen die door het RGHR wordt gegenereerd, hangt volledig af van de initiële vulling ervan, dat wil zeggen dat de elementen van deze reeks een functie zijn van hun aantal en de initiële vulling van het RGHR: waar f ik(X)=F(f ik –1 (X)), F 0 (X)=X. Rekening houdend met de transformatie met behulp van het eenvoudige vervangingsalgoritme, wordt ook een afhankelijkheid van de sleutel toegevoegd:

Waar Г ik– i-de element van de schaal, K- sleutel.

De volgorde van de in de gammamodus te gebruiken gamma-elementen wordt dus op unieke wijze bepaald door de sleutelgegevens en het synchronisatiebericht. Om de versleutelingsprocedure omkeerbaar te maken, moet uiteraard hetzelfde synchronisatiebericht worden gebruikt in de versleutelings- en ontsleutelingsprocessen. Uit de eis van uniciteit van de gamma, waarvan het niet naleven ervan leidt tot een catastrofale afname van de sterkte van het cijfer, volgt dat om twee verschillende data-arrays op dezelfde sleutel te coderen, het noodzakelijk is om het gebruik van verschillende synchronisatieberichten. Dit leidt tot de noodzaak om het synchronisatiebericht samen met de gecodeerde gegevens op te slaan of te verzenden langs communicatiekanalen, hoewel het in sommige speciale gevallen vooraf kan worden bepaald of op een speciale manier kan worden berekend als het coderen van twee arrays met dezelfde sleutel is uitgesloten.

Laten we nu eens nader kijken naar de RGPC die in GOST wordt gebruikt om gamma-elementen te genereren. Allereerst moet worden opgemerkt dat het niet vereist is om statistische kenmerken van de gegenereerde getallenreeks te verstrekken. De RGHR is ontworpen door de ontwikkelaars van GOST op basis van de noodzaak om aan de volgende voorwaarden te voldoen:

• de herhalingsperiode van de door de RGPC gegenereerde reeks getallen mag niet veel verschillen (in procentuele termen) van de maximaal mogelijke waarde voor een gegeven blokgrootte van 2 64;
• aangrenzende waarden geproduceerd door de RGPG moeten in elke byte van elkaar verschillen, anders wordt de taak van de cryptanalist vereenvoudigd;
• De RGPC zou redelijk eenvoudig te implementeren moeten zijn, zowel in hardware als in software, op de meest voorkomende typen processors, waarvan bekend is dat de meeste 32-bits zijn.

Op basis van de genoemde principes hebben de makers van GOST een zeer succesvolle RGHR ontworpen, die de volgende kenmerken heeft:

Waar C 0 =1010101 16 ;

Waar C 1 =1010104 16 ;

Het subscript in een getal geeft het getalsysteem aan, dus de constanten die in deze stap worden gebruikt, worden in hexadecimaal geschreven.

De tweede uitdrukking heeft commentaar nodig, omdat de tekst van GOST iets anders bevat: , met dezelfde waarde als de constante C 1. Maar verderop in de tekst van de standaard wordt opgemerkt dat, onder de bewerking van het nemen van de rest modulo 2 32 –1 daar wordt niet op dezelfde manier begrepen als in de wiskunde. Het verschil is dat volgens GOST (2 32 –1) mod(2 32 –1)=(2 32 –1), niet 0. In feite vereenvoudigt dit de implementatie van de formule, en de wiskundig correcte uitdrukking ervoor wordt hierboven gegeven.

• de herhalingsperiode van de reeks voor het onderste deel is 2 32, voor het oudere deel 2 32 –1, voor de hele reeks is de periode 2 32 (2 32 –1), het bewijs van dit feit is heel eenvoudig, snap het jezelf. De eerste van de twee formules wordt geïmplementeerd in één commando, de tweede, ondanks zijn schijnbare omslachtigheid, in twee commando's op alle moderne 32-bits processors - het eerste commando voert de gebruikelijke optelling modulo 2 32 uit met het opslaan van de carry-bit, en de tweede commando voegt de carry-bit toe aan de resulterende betekenis.

Het diagram van het versleutelingsalgoritme in de gammamodus wordt weergegeven in Figuur 4; hieronder vindt u uitleg voor het schema:

Figuur 4. Algoritme voor het coderen (decoderen) van gegevens in gammamodus.

Stap 0

Definieert de invoergegevens voor de belangrijkste crypto-conversiestap:

• T o(w) – een array van open (gecodeerde) gegevens van willekeurige grootte, onderworpen aan een coderings- (decoderings)procedure; tijdens de procedure wordt de array geconverteerd in gedeelten van 64 bits;
• S – bericht synchroniseren , een 64-bits data-element dat nodig is om de gammagenerator te initialiseren;

Stap 1

De initiële transformatie van het synchronisatiebericht, uitgevoerd om het te "randomiseren", dat wil zeggen om de daarin aanwezige statistische patronen te elimineren, het resultaat wordt gebruikt als de initiële vulling van de RGPC;

Stap 2

Eén stap van de RGPC-operatie, waarbij het terugkerende algoritme wordt geïmplementeerd. Tijdens deze stap wordt de oudste ( S 1) en junior ( S 0) delen van de datareeks worden onafhankelijk van elkaar gegenereerd;

Stap 3

Gommen. Het volgende 64-bits element dat door de RGPC wordt gegenereerd, wordt onderworpen aan een versleutelingsprocedure met behulp van cyclus 32-3. Het resultaat wordt gebruikt als een gamma-element om het volgende blok open (gecodeerde) gegevens van dezelfde grootte te versleutelen (ontsleutelen).

Stap 4

Het resultaat van het algoritme is een gecodeerde (gedecodeerde) data-array.

Hieronder volgen de kenmerken van gamma als coderingsmodus:

1. Identieke blokken in een open data-array zullen bij versleuteling verschillende cijfertekstblokken opleveren, wat het mogelijk maakt om het feit van hun identiteit te verbergen.
2. Omdat gamma-overlay bitsgewijs wordt uitgevoerd, kan het coderen van een gedeeltelijk gegevensblok eenvoudig worden bereikt door de bits van dat gedeeltelijke blok te coderen door gebruik te maken van de overeenkomstige bits van het gammablok. Om een ​​onvolledig blok van 1 bit te versleutelen, moet dus volgens de standaard de minst significante bit uit het gammablok worden gebruikt.
3. Het synchronisatiebericht dat voor de codering wordt gebruikt, moet op een of andere manier worden verzonden voor gebruik bij decodering. Dit kan op de volgende manieren worden bereikt:

• een synchronisatiebericht opslaan of verzenden samen met een gecodeerde data-array, wat zal leiden tot een toename van de omvang van de data-array wanneer deze wordt gecodeerd met de grootte van het synchronisatiebericht, dat wil zeggen met 8 bytes;
• een vooraf bepaalde waarde van het synchronisatiebericht gebruiken of dit synchroon genereren door de bron en de ontvanger volgens een bepaalde wet, in dit geval is er geen verandering in de grootte van de verzonden of opgeslagen datareeks;

Beide methoden vullen elkaar aan, en in de zeldzame gevallen waarin de eerste, meest voorkomende methode niet werkt, kan de tweede, meer exotische methode worden gebruikt. De tweede methode heeft veel minder toepassing, omdat het alleen mogelijk is om een ​​vooraf bepaald synchronisatiebericht te maken als niet meer dan één data-array is gecodeerd op een gegeven set sleutelinformatie, wat niet erg vaak gebeurt. Ook is het niet altijd mogelijk om synchroon een synchronisatiebericht te genereren bij de bron en ontvanger van een data-array, omdat hiervoor een strikte verbinding met iets in het systeem vereist is. Een ogenschijnlijk goed idee om het nummer van het verzonden bericht te gebruiken als synchronisatiebericht in een systeem voor het verzenden van gecodeerde berichten is dus niet geschikt, omdat het bericht verloren kan gaan en de ontvanger niet kan bereiken, in welk geval de coderingssystemen van de bron en de ontvanger raakt gedesynchroniseerd. Daarom is er in het beschouwde geval geen alternatief voor het samen met het gecodeerde bericht verzenden van het synchronisatiebericht.

Aan de andere kant kan het tegenovergestelde voorbeeld worden gegeven. Laten we zeggen dat gegevensversleuteling wordt gebruikt om informatie op de schijf te beschermen en dat deze op een laag niveau wordt geïmplementeerd; om onafhankelijke toegang te garanderen, worden de gegevens per sector versleuteld. In dit geval is het onmogelijk om het synchronisatiebericht samen met de gecodeerde gegevens op te slaan, omdat de sectorgrootte niet kan worden gewijzigd, maar kan worden berekend als een functie van het schijfleeskopnummer, het tracknummer (cilindernummer) en het sectornummer. Op de rails. In dit geval is het synchronisatiebericht gekoppeld aan de positie van de sector op de schijf, die waarschijnlijk niet zal veranderen zonder de schijf opnieuw te formatteren, dat wil zeggen zonder de gegevens erop te vernietigen.

De gammamodus heeft nog een interessante feature. In deze modus worden de bits van de data-array onafhankelijk van elkaar gecodeerd. Elke bit van de cijfertekst hangt dus af van de overeenkomstige bit van de leesbare tekst en uiteraard van het volgnummer van de bit in de array: . Dit impliceert dat het veranderen van een cijfertekstbit naar de tegenovergestelde waarde zal resulteren in een soortgelijke verandering van de tegenovergestelde waarde van een leesbare tekstbit:

waarbij staat voor omgekeerd ten opzichte van T bitwaarde().

Deze eigenschap geeft een aanvaller de mogelijkheid om, door de cijfertekstbits te beïnvloeden, voorspelbare en zelfs doelgerichte wijzigingen aan te brengen in de overeenkomstige leesbare tekst die na decodering wordt verkregen, zonder dat hij over de geheime sleutel beschikt. Dit illustreert het bekende feit in de cryptologie dat geheimhouding en authenticiteit zijn verschillende eigenschappen cryptografische systemen . Met andere woorden: de eigenschappen van een cryptosysteem om bescherming te bieden tegen ongeoorloofde toegang tot de inhoud van een bericht en tegen ongeoorloofde wijzigingen aan een bericht zijn onafhankelijk en kunnen elkaar slechts in bepaalde gevallen overlappen. Dit betekent dat er cryptografische algoritmen zijn die een zekere geheimhouding van gecodeerde gegevens bieden en tegelijkertijd op geen enkele manier beschermen tegen veranderingen, en omgekeerd, waardoor de authenticiteit van de gegevens wordt gegarandeerd en op geen enkele manier de mogelijkheid wordt beperkt om zich ermee vertrouwd te maken hen. Om deze reden mag de beschouwde eigenschap van de gammamodus niet als een nadeel worden beschouwd.

Gamma met feedback.

Deze modus lijkt sterk op de gammamodus en verschilt er alleen van in de manier waarop de gamma-elementen worden gegenereerd - het volgende gamma-element wordt gegenereerd als resultaat van de transformatie van 32-3 cycli van het vorige blok met gecodeerde gegevens, en om te coderen In het eerste blok van de data-array wordt het gamma-element gegenereerd als resultaat van dezelfdes. Hierdoor wordt blokketening bereikt: elk cijfertekstblok in deze modus is afhankelijk van de overeenkomstige en alle voorgaande leesbare tekstblokken. Daarom wordt deze modus soms genoemd gamen met in elkaar grijpende blokken . Het feit dat blokken aan elkaar gekoppeld zijn, heeft geen invloed op de sterkte van het cijfer.

Het diagram van de coderings- en decoderingsalgoritmen in de gammamodus met feedback wordt getoond in figuur 5 en behoeft vanwege zijn eenvoud geen commentaar.

Figuur 5. Algoritme voor het coderen (decoderen) van gegevens in gammamodus met feedback.

Gamma-encryptie met gesloten lus heeft dezelfde kenmerken als gewone gamma-encryptie, behalve het effect van cijfertekstcorruptie op de overeenkomstige leesbare tekst. Laten we ter vergelijking de blokdecoderingsfuncties voor beide genoemde modi opschrijven:

Gommen;

Gamma met feedback;

Als in de reguliere gammamodus veranderingen in bepaalde bits van de cijfertekst alleen de overeenkomstige bits van de leesbare tekst beïnvloeden, dan is het beeld in de feedbackgammamodus iets gecompliceerder. Zoals uit de overeenkomstige vergelijking blijkt, hangt het open datablok bij het decoderen van een datablok in de gesloten-lus-gammamodus af van de overeenkomstige en eerdere gecodeerde datablokken. Als u daarom vervormingen in een gecodeerd blok introduceert, zullen na decodering twee blokken met open gegevens worden vervormd - de overeenkomstige en de daaropvolgende, en de vervormingen in het eerste geval zullen van dezelfde aard zijn als in de gammamodus , en in het tweede geval - zoals bij de gemakkelijke vervanging. Met andere woorden: in het corresponderende blok met open data zullen dezelfde bits beschadigd raken als in het blok met gecodeerde data, en in het volgende blok met open data zijn alle bits onafhankelijk van elkaar met waarschijnlijkheid 1. / 2 zullen hun waarden veranderen.

Ontwikkeling van een gesimuleerde insert voor de data-array.

In eerdere secties hebben we de impact van corruptie van gecodeerde gegevens op de overeenkomstige gewone gegevens besproken. We hebben vastgesteld dat bij het decoderen in de eenvoudige vervangingsmodus het overeenkomstige blok met open gegevens op een onvoorspelbare manier vervormd blijkt te zijn, en bij het decoderen van een blok in de gammamodus zijn de veranderingen voorspelbaar. In de gesloten-lus-gammamodus raken twee blokken vervormd, de ene op een voorspelbare manier en de andere op een onvoorspelbare manier. Betekent dit dat vanuit het oogpunt van bescherming tegen het opleggen van valse gegevens de gammamodus slecht is en de eenvoudige vervangings- en feedbackgammamodi goed zijn? - In geen geval. Bij het analyseren van deze situatie moet er rekening mee worden gehouden dat onvoorspelbare veranderingen in een gedecodeerd datablok alleen kunnen worden gedetecteerd als dezelfde gegevens redundant zijn, en hoe groter de mate van redundantie, hoe waarschijnlijker de detectie van vervorming. Er treedt bijvoorbeeld een zeer grote redundantie op bij teksten in natuurlijke en kunstmatige talen; in dit geval wordt het feit van vervorming vrijwel onvermijdelijk gedetecteerd. In andere gevallen, bijvoorbeeld wanneer gecomprimeerde gedigitaliseerde geluidsbeelden worden vervormd, krijgen we echter eenvoudigweg een ander beeld dat ons oor kan waarnemen. De vervorming blijft in dit geval onopgemerkt, tenzij er uiteraard a priori informatie is over de aard van het geluid. De conclusie hier is deze: aangezien het vermogen van sommige versleutelingsmodi om vervormingen te detecteren die in versleutelde gegevens zijn geïntroduceerd, aanzienlijk afhangt van de aanwezigheid en mate van redundantie van de versleutelde gegevens, is dit vermogen geen inherente eigenschap van de overeenkomstige modi en kan het niet worden beschouwd als hun voordeel.

Om het probleem van het detecteren van vervormingen in een gecodeerde data-array met een bepaalde waarschijnlijkheid op te lossen, voorziet GOST in een extra manier van cryptografische transformatie: de ontwikkeling van imitatieve invoeging. Imitatie-insert is een besturingscombinatie die afhankelijk is van open data en geheime sleutelinformatie. Het doel van het gebruik van imitatieve invoeging is om alle toevallige of opzettelijke veranderingen in de informatiearray te detecteren. Het in de vorige paragraaf beschreven probleem kan met succes worden opgelost door imitatieve invoegingen aan de gecodeerde gegevens toe te voegen. Voor een potentiële aanvaller zijn de volgende twee taken vrijwel onmogelijk op te lossen als hij de sleutel niet heeft:

• berekening van imitatieve invoeging voor een gegeven open reeks informatie;
• selectie van open data voor een gegeven simulatie-insert;

Het diagram van het algoritme voor het ontwikkelen van een gesimuleerde insert wordt getoond in Figuur 6.

Figuur 6. Algoritme voor het ontwikkelen van een gesimuleerde insert voor een data-array.

Een deel van het blok dat aan de uitgang wordt ontvangen, wordt als gesimuleerde invoeging genomen, meestal de 32 minst significante bits. Bij het kiezen van de grootte van een nep-insert moet er rekening mee worden gehouden dat de kans op het succesvol invoeren van valse gegevens gelijk is aan 2 –| I | per selectiepoging, als de aanvaller niet over een effectievere selectiemethode beschikt dan eenvoudig raden. Bij gebruik van een 32-bits gesimuleerde invoeging is deze waarschijnlijkheid gelijk aan

Bespreking van cryptografische algoritmen van GOST.

Cryptografische kracht van GOST.

Bij het kiezen van een cryptografisch algoritme voor gebruik in een bepaalde ontwikkeling is een van de bepalende factoren de kracht ervan, dat wil zeggen de weerstand tegen pogingen van tegenstanders om het te onthullen. De vraag naar de sterkte van een cijfer komt bij nader onderzoek neer op twee onderling verbonden vragen:

• Is het überhaupt mogelijk om dit cijfer te kraken?
• zo ja, hoe moeilijk is dit praktisch uitvoerbaar;

Cijfers die helemaal niet kunnen worden verbroken, worden absoluut of theoretisch sterk genoemd. Het bestaan ​​van dergelijke cijfers wordt bewezen door de stelling van Shannon, maar de prijs voor deze kracht is de noodzaak om voor het coderen van elk bericht een sleutel te gebruiken die niet kleiner is dan het bericht zelf. In alle gevallen, met uitzondering van een aantal bijzondere, is deze prijs buitensporig hoog, waardoor in de praktijk vooral gebruik wordt gemaakt van niet absoluut veilige cijfers. De meest voorkomende versleutelingsschema's kunnen dus in een eindige tijd worden verbroken, of preciezer gezegd in een eindig aantal stappen, die elk een bewerking op getallen zijn. Voor hen is het belangrijkste concept praktische volharding, wat de praktische moeilijkheid van hun ontdekking uitdrukt. Een kwantitatieve maatstaf voor deze moeilijkheid kan het aantal elementaire rekenkundige en logische bewerkingen zijn dat moet worden uitgevoerd om het cijfer te openen, dat wil zeggen om de overeenkomstige leesbare tekst voor een gegeven cijfertekst te bepalen met een waarschijnlijkheid van niet minder dan een bepaalde waarde. Tegelijkertijd kan de cryptanalyticus, naast de gedecodeerde data-array, beschikken over blokken open data en bijbehorende gecodeerde gegevens, of zelfs over de mogelijkheid om overeenkomstige gecodeerde gegevens te verkrijgen voor elke open data die hij kiest - afhankelijk van de vermelde en vele andere niet-gespecificeerde gegevens. omstandigheden worden afzonderlijke typen cryptanalyse onderscheiden.

Alle moderne cryptosystemen zijn gebouwd op het Kirchhoff-principe, dat wil zeggen dat de geheimhouding van gecodeerde berichten wordt bepaald door de geheimhouding van de sleutel. Dit betekent dat zelfs als het versleutelingsalgoritme zelf bekend is bij de cryptanalyticus, hij niettemin niet in staat is het bericht te ontsleutelen als hij niet over de juiste sleutel beschikt. Een cijfer wordt als goed ontworpen beschouwd als er geen manier is om het efficiënter te ontcijferen dan door brute kracht over de gehele sleutelruimte, d.w.z. over alle mogelijke sleutelwaarden. GOST komt waarschijnlijk overeen met dit principe - door de jaren heen van intensief onderzoek is er geen enkele effectieve methode voor de cryptanalyse ervan voorgesteld. In termen van kracht is het vele ordes van grootte superieur aan de vorige Amerikaanse encryptiestandaard, DES.

GOST gebruikt een sleutel van 256 bits en het volume van de sleutelruimte is 2.256. Geen van de elektronische apparaten die momenteel bestaan ​​of die naar verwachting in de nabije toekomst zullen worden geïmplementeerd, kunnen worden gebruikt om binnen een tijdsbestek van minder dan vele honderden jaren een sleutel op te pakken. Deze waarde is tegenwoordig de de facto standaard voor sleutelgrootte voor symmetrische cryptografische algoritmen geworden, en de nieuwe Amerikaanse encryptiestandaard ondersteunt deze ook. De voormalige Amerikaanse standaard DES, met zijn werkelijke sleutelgrootte van 56 bits en het sleutelvolume van slechts 2 56 bits, is niet langer voldoende stabiel in het licht van de mogelijkheden van moderne computerhulpmiddelen. Dit werd eind jaren negentig aangetoond door verschillende succesvolle brute force-pogingen om DES te doorbreken. Bovendien was DES vatbaar voor speciale cryptanalysetechnieken zoals differentieel en lineair. In dit opzicht kan DES eerder van onderzoeks- of wetenschappelijk belang zijn dan van praktisch belang. In 1998 werd de cryptografische zwakte ervan officieel erkend: het Amerikaanse National Institute of Standards adviseerde het gebruik van drievoudige DES-codering. En eind 2001 werd een nieuwe Amerikaanse encryptiestandaard, AES, officieel goedgekeurd, gebaseerd op andere principes en vrij van de tekortkomingen van zijn voorganger.

Opmerkingen over GOST-architectuur.

Het is bekend dat de binnenlandse encryptiestandaard representatief is voor een hele familie van codes die op dezelfde principes zijn gebouwd. Het bekendste ‘familielid’ is de voormalige Amerikaanse encryptiestandaard, het DES-algoritme. Al deze cijfers bevatten, net als GOST, algoritmen op drie niveaus. In de kern is er altijd een bepaalde “basisstap”, op basis waarvan “basiscycli” op een vergelijkbare manier worden gebouwd, en op basis daarvan worden praktische procedures voor codering en de ontwikkeling van imitatieve inserts gebouwd. De specificiteit van elk van de cijfers van deze familie ligt dus precies in de belangrijkste stap, of liever zelfs in zijn deel. Hoewel de architectuur van klassieke blokcijfers, waarnaar GOST verwijst, ver buiten het bestek van dit artikel ligt, is het toch de moeite waard er een paar woorden over te zeggen.

De algoritmen voor de “belangrijkste stappen van crypto-transformatie” voor cijfers zoals GOST zijn op identieke wijze gebouwd, en deze architectuur wordt genoemd uitgebalanceerd Feistel-netwerk (evenwichtig Feistel-netwerk) achter de naam van de persoon die het als eerste heeft voorgesteld. Gegevensconversieschema in één cyclus, of, zoals het gewoonlijk wordt genoemd, ronde , wordt weergegeven in Figuur 7.

Figuur 7. Inhoud van de hoofdstap van crypto-transformatie voor blokcijfers vergelijkbaar met GOST.

Aan de ingang van de hoofdstap wordt een blok van gelijke grootte toegevoerd, waarvan de bovenste en onderste helft afzonderlijk van elkaar worden verwerkt. Tijdens de conversie wordt de onderste helft van het blok op de plaats van de oudere helft geplaatst en wordt de oudere helft gecombineerd met behulp van de bitsgewijze bewerking exclusief of ” met het resultaat van het berekenen van een bepaalde functie, in plaats van de jongste. Deze functie neemt als argument de onderste helft van het blok en het sleutelinformatie-element ( X), is het inhoudsgedeelte van het cijfer en wordt genoemd encryptie functie . Om verschillende redenen bleek het voordelig om het gecodeerde blok in twee delen van gelijke grootte te verdelen: | N 1 |=|N 2 | – dit feit wordt weerspiegeld door het woord ‘evenwichtig’ in de naam van de architectuur. Er wordt echter ook van tijd tot tijd gebruik gemaakt van het versleutelen van onevenwichtige netwerken, hoewel niet zo vaak als gebalanceerde netwerken. Bovendien vereisen overwegingen van codeersterkte dat de grootte van het sleutelelement niet kleiner mag zijn dan de grootte van de helft van het blok: in GOST zijn alle drie de grootten gelijk aan 32 bits .

Als we het bovenstaande toepassen op het diagram van de hoofdstap van het GOST-algoritme, zal het duidelijk worden dat blokken 1,2,3 van het algoritme (zie figuur 1) de berekening van de encryptiefunctie bepalen, en blokken 4 en 5 specificeer de vorming van het uitvoerblok van de hoofdstap op basis van de inhoud van het invoerblok en de waarden van de versleutelingsfunctie. Meer details over de architecturen van moderne blokcijfers met een geheime sleutel zijn te vinden in klassieke werken, of, in aangepaste vorm, in mijn werken.

In de vorige sectie hebben we DES en GOST al vergeleken op het gebied van duurzaamheid, nu zullen we ze vergelijken op het gebied van functionele inhoud en implementatiegemak. In GOST-coderingscycli wordt de hoofdstap 32 keer herhaald, voor DES is deze waarde 16. De GOST-coderingsfunctie zelf is echter veel eenvoudiger dan de vergelijkbare DES-functie, die veel onregelmatige bitpermutaties bevat. Deze bewerkingen zijn uiterst inefficiënt op moderne, niet-gespecialiseerde processors. GOST bevat dergelijke bewerkingen niet, dus het is veel handiger voor software-implementatie.

Geen van de door de auteur beoordeelde DES-implementaties voor het Intel x86-platform bereikt zelfs maar de helft van de prestaties van de GOST-implementatie die in dit artikel wordt voorgesteld, ondanks de twee keer kortere cyclus. Al het bovenstaande geeft aan dat de ontwikkelaars van GOST zowel de positieve als de negatieve aspecten van DES in aanmerking hebben genomen, en ook de huidige en toekomstige mogelijkheden van cryptanalyse realistischer hebben beoordeeld. Het is echter niet langer relevant om DES als basis te nemen bij het vergelijken van de prestaties van coderingsimplementaties. De nieuwe Amerikaanse coderingsstandaard doet het veel beter op het gebied van efficiëntie - met dezelfde sleutelgrootte als GOST (256 bits) werkt AES ongeveer 14% sneller - dit wordt vergeleken in termen van het aantal "elementaire bewerkingen". Bovendien kan GOST praktisch niet worden geparallelliseerd, terwijl AES in dit opzicht veel meer mogelijkheden heeft. Op sommige architecturen kan dit voordeel van AES kleiner zijn, op andere kan het groter zijn. Op een Intel Pentium-processor bereikt dit dus 28%. Details zijn te vinden in.

Eisen aan de kwaliteit van sleutelinformatie en sleutelbronnen.

Niet alle sleutels en vervangingstabellen bieden maximale codeersterkte. Elk versleutelingsalgoritme heeft zijn eigen criteria voor het evalueren van sleutelinformatie. Voor het DES-algoritme is het dus bekend dat er zogenaamde “ zwakke toetsen "Bij gebruik wordt de verbinding tussen open en gecodeerde gegevens niet voldoende gemaskeerd en wordt de code relatief gemakkelijk verbroken.

Als een alomvattend antwoord op de vraag over de kwaliteitscriteria van GOST-sleutels en vervangingstabellen überhaupt ergens kan worden verkregen, kan dit alleen van de ontwikkelaars van het algoritme zijn. De relevante gegevens zijn niet in de openbare pers gepubliceerd. Volgens de vastgestelde procedure moeten voor het versleutelen van geheime informatie echter sleutelgegevens worden gebruikt die zijn ontvangen van een geautoriseerde organisatie. Indirect kan dit duiden op de aanwezigheid van methoden om sleutelgegevens op luizen te controleren. Als de aanwezigheid van zwakke sleutels in GOST een discutabel probleem is, dan staat de aanwezigheid van zwakke vervangende eenheden buiten twijfel. Het is duidelijk dat de "triviale" vervangingstabel, volgens welke elke waarde door zichzelf wordt vervangen, zo zwak is dat bij gebruik ervan het cijfer eenvoudig kan worden gekraakt, ongeacht wat de sleutel is.

Zoals hierboven opgemerkt, zijn er geen criteria beschikbaar voor het beoordelen van belangrijke informatie, maar kunnen er toch enkele algemene overwegingen over worden gemaakt.

Sleutel

De sleutel moet een array zijn van statistisch onafhankelijke bits die met gelijke waarschijnlijkheid de waarden 0 en 1 aannemen. Het kan niet volledig worden uitgesloten dat sommige specifieke sleutelwaarden ‘zwak’ blijken te zijn, dat wil zeggen de cipher biedt mogelijk niet het opgegeven sterkteniveau als het wordt gebruikt. Vermoedelijk is het aandeel van dergelijke waarden in de totale massa van alle mogelijke sleutels echter verwaarloosbaar klein. In ieder geval heeft intensief onderzoek naar het cijfer nog geen enkele dergelijke sleutel aan het licht gebracht voor een van de bekende (dat wil zeggen, voorgesteld door FAPSI) substitutietabellen. Daarom zullen sleutels die worden gegenereerd met behulp van een werkelijk willekeurige getallensensor van hoge kwaliteit zijn met een waarschijnlijkheid die verwaarloosbaar klein verschilt van de eenheid. Als de sleutels worden gegenereerd met behulp van een generator van pseudo-willekeurige getallen, moet de gebruikte generator de bovengenoemde statistische kenmerken bieden en bovendien een hoge cryptografische kracht hebben - niet minder dan die van GOST zelf. Met andere woorden, de taak van het bepalen van de ontbrekende leden van de reeks elementen die door de generator wordt gegenereerd, mag niet eenvoudiger zijn dan de taak van het ontcijferen van het cijfer. Bovendien kunnen verschillende statistische criteria worden gebruikt om sleutels met slechte statistische kenmerken te weigeren. In de praktijk zijn meestal twee criteria voldoende: om de gelijkwaardige verdeling van sleutelbits tussen de waarden 0 en 1 te controleren, wordt meestal de Pearson-test (chi kwadraat) gebruikt, en om de onafhankelijkheid van sleutelbits te controleren, wordt de run-test gebruikt. . U kunt over de genoemde criteria lezen in leerboeken of naslagwerken over wiskundige statistiek.

De beste aanpak voor het genereren van sleutels zou het gebruik van hardware-middenbereiksensoren zijn, maar dit is om economische redenen niet altijd acceptabel. Bij het genereren van een kleine reeks sleutelinformatie is een redelijk alternatief voor het gebruik van een dergelijke sensor de ‘elektronische roulette’-methode, die in de praktijk veel wordt gebruikt, waarbij het volgende gegenereerde deel van willekeurige bits afhangt van het moment waarop de operator op een knop drukt. bepaalde toets op het toetsenbord van de computer. In dit schema is de bron van willekeurige gegevens de computergebruiker, of preciezer gezegd, de tijdskenmerken van zijn reactie. In dit geval kunnen slechts een paar bits aan willekeurige gegevens per toetsaanslag worden gegenereerd, dus de algehele snelheid voor het genereren van sleutelinformatie is laag: tot enkele bits per seconde. Het is duidelijk dat deze aanpak niet geschikt is voor het verkrijgen van grote reeksen sleutels.

In het geval dat het nodig is om een ​​grote reeks sleutelinformatie te genereren, is het gebruik van verschillende softwarematige pseudo-willekeurige getalsensoren mogelijk en zeer wijdverbreid. Omdat een dergelijke sensor een hoge mate van cryptografische sterkte vereist, is het normaal om de gammagenerator van het cijfer zelf te gebruiken - we "knippen" eenvoudigweg het door het cijfer gegenereerde gamma in "stukken" van de vereiste grootte, voor GOST - 32 bytes. Voor deze aanpak hebben we uiteraard een ‘hoofdsleutel’ nodig, die we kunnen verkrijgen met behulp van de hierboven beschreven elektronische roulettemethode, en met zijn hulp verkrijgen we, met behulp van een code in de gammageneratormodus, een reeks sleutelinformatie van de grootte wij hebben nodig. Deze twee methoden voor het genereren van sleutels – ‘handmatig’ en ‘algoritmisch’ – werken dus samen en vullen elkaar aan. Sleutelgeneratieschema's in "low-budget" cryptografische beveiligingssystemen voor informatie zijn bijna altijd op dit principe gebaseerd.

Vervangingstabel

De vervangingstabel is een sleutelelement voor de lange termijn, dat wil zeggen dat deze veel langer geldig is dan een enkele sleutel. Er wordt aangenomen dat dit gemeenschappelijk is voor alle encryptieknooppunten binnen hetzelfde cryptografische beveiligingssysteem. Zelfs als de vertrouwelijkheid van de vervangingstabel wordt geschonden, blijft de sterkte van het cijfer extreem hoog en daalt niet onder de toegestane limiet. Daarom is er geen specifieke noodzaak om de tabel geheim te houden, en in de meeste commerciële toepassingen van GOST wordt dit wel gedaan. Aan de andere kant is de vervangingstabel een cruciaal element om de sterkte van het gehele cijfer te garanderen. Als u de verkeerde tabel kiest, kan dit ertoe leiden dat het cijfer gemakkelijk kan worden verbroken door bekende cryptanalysetechnieken. De criteria voor het ontwikkelen van vervangende eenheden zijn een goed bewaard geheim en het is onwaarschijnlijk dat FAPSI dit in de nabije toekomst met het publiek zal delen. Uiteindelijk vergt het bepalen of een bepaalde vervangingstabel goed of slecht is een enorme hoeveelheid werk: vele duizenden man- en machine-uren. Eenmaal geselecteerd en gebruikt, moet een tabel worden vervangen als en alleen als het gebruikte cijfer kwetsbaar blijkt te zijn voor een of ander type cryptanalyse. Daarom zou de beste keuze voor de gemiddelde coderingsgebruiker zijn om een ​​van de verschillende tabellen te gebruiken die openbaar zijn geworden. Bijvoorbeeld uit de standaard voor de hashfunctie, ook wel de ‘central banking’-functie genoemd; informatie over deze tabellen is te vinden in de open pers en zelfs op internet, als je goed zoekt.

Voor degenen die niet gewend zijn om de gemakkelijke route te nemen, vindt u hieronder een algemeen schema voor het verkrijgen van tafels van hoge kwaliteit:

1. Met behulp van een of andere techniek ontwikkel je een set van acht vervangende eenheden met gegarandeerde niet-lineariteitskenmerken. Er zijn verschillende van dergelijke technieken, een daarvan is het gebruik van zogenaamde gebogen functies.
2. U controleert of aan de eenvoudigste “kwaliteitscriteria” wordt voldaan, bijvoorbeeld de criteria die zijn gepubliceerd voor DES-vervangingsknooppunten. Hier volgen nog enkele algemene overwegingen in dit verband: Elk substitutieknooppunt kan worden beschreven door vier logische functies op basis van vier logische argumenten. Als deze functies zijn geschreven in minimale vorm(d.w.z. met de minimaal mogelijke expressielengte) niet complex genoeg zal zijn, wordt een dergelijk vervangend knooppunt afgewezen. Bovendien moeten de afzonderlijke functies binnen de gehele vervangingstabel voldoende van elkaar verschillen. In dit stadium worden veel tafels van duidelijk lage kwaliteit geëlimineerd.
3. Voor een cijfer met tabellen naar keuze bouwt u verschillende ronde modellen die overeenkomen met verschillende soorten cryptanalyse en meet u de bijbehorende ‘profiel’-kenmerken. Bouw dus voor lineaire cryptanalyse een lineair statistisch analoog van de coderingsronde en bereken het 'profiel'-kenmerk - een indicator van niet-lineariteit. Als dit onvoldoende is, wordt de vervangende tafel afgewezen.
4. Ten slotte onderwerpt u, met behulp van de resultaten uit de vorige paragraaf, het cijfer met de door u gekozen tabel aan intensief onderzoek - een poging tot cryptanalyse met behulp van alle bekende methoden. Deze fase is het moeilijkst en meest tijdrovend. Maar als het van hoge kwaliteit is gemaakt, kan met een hoge mate van waarschijnlijkheid worden gesteld dat het cijfer met de door u gekozen tabellen niet door gewone stervelingen zal worden gekraakt, en dat het mogelijk is dat het te moeilijk zal zijn voor de intelligentie. Diensten.

U kunt het echter veel eenvoudiger doen. Het punt is dat hoe meer rondes er in een cijfer zitten, hoe minder invloed de sterkte-eigenschappen van één ronde hebben op de sterkte van het hele cijfer. GOST heeft maar liefst 32 ronden - meer dan in bijna alle cijfers met een vergelijkbare architectuur. Daarom is het voor de meeste huishoudelijke en commerciële toepassingen voldoende om vervangingsknooppunten te verkrijgen als onafhankelijke willekeurige permutaties van getallen van 0 tot 15. Dit kan praktisch worden geïmplementeerd, bijvoorbeeld door een kaartspel van zestien kaarten te schudden, aan elk waarvan één van de volgende wordt toegewezen. de waarden van het opgegeven bereik.

Wat de vervangingstabel betreft, moet nog een interessant feit worden opgemerkt. Voor de omkeerbaarheid van de coderingscycli “32-З” en “32-Р” is het niet vereist dat de vervangende knooppunten permutaties zijn van getallen van 0 tot 15. Alles werkt, zelfs als het vervangende knooppunt dubbele elementen heeft en de vervangende knooppunten bepaald door een dergelijk knooppunt, is onomkeerbaar, maar in dit geval wordt de sterkte van het cijfer verminderd. Waarom dit precies zo is, wordt in dit artikel niet besproken, maar het is niet moeilijk om het feit zelf te verifiëren. Om dit te doen, volstaat het om eerst te proberen een gegevensblok te coderen en vervolgens te decoderen met behulp van een dergelijke "onvolledige" vervangingstabel, waarvan de knooppunten dubbele waarden bevatten.

Variaties op het thema van GOST

Voor gebruik in een cryptografisch gegevensbeschermingssysteem is heel vaak een algoritme met een hogere implementatiesnelheid dan GOST vereist, en een dergelijke hoge cryptografische sterkte is niet vereist. Een typisch voorbeeld van dergelijke taken zijn verschillende soorten elektronische aandelenhandelsystemen die handelssessies in realtime beheren. Hier zijn de gebruikte versleutelingsalgoritmen nodig om het onmogelijk te maken om de operationele gegevens van het systeem tijdens de sessie te ontsleutelen (gegevens over ingediende bestellingen, afgesloten transacties, enz.). Na het verstrijken ervan zijn deze gegevens in de regel niet langer nutteloos voor aanvallers. Met andere woorden, er is een gegarandeerde duurzaamheid van slechts een paar uur vereist - dit is de typische duur van een handelssessie. Het is duidelijk dat het gebruik van een volwaardige GOST in deze situatie mussen met een kanon zou neerschieten.

Wat te doen in deze en soortgelijke gevallen om de coderingssnelheid te verhogen? Het antwoord ligt aan de oppervlakte: gebruik een wijziging van het cijfer met minder hoofdstappen (rondes) in de basiscycli. De keren dat we het aantal encryptierondes verminderen, nemen de prestaties met hetzelfde bedrag toe. Deze verandering kan op twee manieren worden bereikt: door de lengte van de sleutel te verkleinen en door het aantal “beoordelingscycli” van de sleutel te verminderen. Bedenk dat het aantal basisstappen in basiscoderingscycli gelijk is aan: N=n·m, Waar N– aantal 32-bits elementen in de sleutel, M– aantal gebruikscycli van sleutelelementen in de standaard N=8, M=4. U kunt elk van deze getallen verkleinen, maar de eenvoudigste optie is om de lengte van de sleutel te verkleinen zonder de manier waarop deze wordt gebruikt te beïnvloeden.

Het is duidelijk dat de prijs voor het versnellen van het werk een afname van de sterkte van het cijfer zal zijn. De grootste moeilijkheid is dat het vrij moeilijk is om de omvang van deze reductie min of meer nauwkeurig in te schatten. Uiteraard is de enige mogelijke manier om dit te doen het uitvoeren van een grootschalig onderzoek naar codevarianten met kortere cryptografische conversiecycli. Het is duidelijk dat dit ten eerste het gebruik van geheime informatie vereist, die alleen eigendom is van de ontwikkelaars van GOST, en ten tweede dat het zeer arbeidsintensief is. Daarom zullen we nu proberen een zeer, zeer ruwe beoordeling te geven, uitsluitend gebaseerd op algemene patronen.

Wat betreft de weerstand van het cijfer tegen kraken door ‘uitgebreide’ methoden, dat wil zeggen tegen een ‘brute force’-aanval, is alles hier min of meer duidelijk: een sleutel van 64 bits staat ergens op het punt toegankelijk te zijn voor dit type van een aanval is een cijfer met een sleutel van 96 bits of hoger (onthoud dat de sleutel een geheel aantal 32-bits elementen moet bevatten) er behoorlijk resistent tegen. Enkele jaren geleden werd de vorige Amerikaanse encryptiestandaard, DES, herhaaldelijk gehackt met brute force-methoden - eerst door een computernetwerk georganiseerd op basis van het mondiale internet, en vervolgens door een gespecialiseerd netwerk, d.w.z. een computer die speciaal voor dit doel is ontworpen. Laten we aannemen dat de standaardversie van GOST, wanneer geïmplementeerd in software op moderne processors, vier keer sneller werkt dan DES. Dan zal de 8-ronde "verminderde GOST" 16 keer sneller werken dan DES. Laten we ook aannemen dat in de tijd sinds de DES-hack de computerprestaties zijn verviervoudigd volgens de wet van Moore. Het resultaat is dat het controleren van één 64-bits sleutel op de “gereduceerde GOST” met acht cycli nu 64 keer sneller is dan het controleren van één DES-sleutel tegelijk. Het voordeel van deze versie van GOST ten opzichte van DES in termen van de complexiteit van een brute-force-aanval is dus teruggebracht van 2 64–56 = 2 8 = 256 naar 256 / 64 = 4 keer. Mee eens, dit is een heel illusoir verschil, bijna niets.

Het is veel moeilijker om de weerstand van verzwakte GOST-modificaties tegen “intensieve” methoden van cryptanalyse te beoordelen. Maar ook hier is een algemeen patroon te ontdekken. Feit is dat de ‘profiel’-kenmerken van veel van de krachtigste vormen van cryptanalyse van vandaag exponentieel afhankelijk zijn van het aantal coderingsrondes. Voor lineaire cryptanalyse (LCA) zal dit dus een lineariteitskenmerk zijn L :

Waar C en zijn constanten, R is het aantal ronden. Een soortgelijke relatie bestaat voor differentiële cryptanalyse. In hun ‘fysieke betekenis’ zijn alle kenmerken van dit soort waarschijnlijkheden. Normaal gesproken zijn de hoeveelheid initiële gegevens die nodig zijn voor cryptanalyse en de complexiteit ervan omgekeerd evenredig met dergelijke kenmerken. Hieruit volgt dat deze arbeidsintensiteitsindicatoren exponentieel groeien met het aantal basisversleutelingsstappen. Daarom zal, wanneer het aantal rondes verschillende keren wordt verminderd, de complexiteit van de meest bekende soorten analyses veranderen als, zeer bij benadering en grofweg, de wortel van deze macht uit de oorspronkelijke grootheid. Dit is een zeer grote daling in duurzaamheid.

Aan de andere kant is GOST ontworpen met een grote veiligheidsmarge en is het tegenwoordig bestand tegen alle bekende soorten cryptanalyse, inclusief differentiële en lineaire. Met betrekking tot LCA betekent dit dat voor de succesvolle implementatie ervan meer “open blok-gecodeerde blok”-paren nodig zijn dan “in de natuur bestaat”, dat wil zeggen meer dan 2 64 . Rekening houdend met het bovenstaande betekent dit dat voor een succesvolle LCA van een GOST met 16 ronden ten minste blokken van 2 35 bytes of 32 GB aan gegevens vereist zullen zijn, en voor een LCA van 8 ronden ten minste blokken of 2 19 bytes of 0,5 MB.

De conclusies uit al het bovenstaande worden weergegeven in de volgende tabel, die de kenmerken van de gereduceerde versies van GOST samenvat.

Aantal rondes	Sleutelgrootte, bits	Prestatie-index	Waarschijnlijke kenmerken van het cijfer (zeer ruwe schatting)
24	192	1,33	Resistent tegen de meeste bekende soorten CA, of staat op de rand van resistentie. De praktische implementatie van CA is onmogelijk vanwege de hoge eisen aan initiële gegevens en arbeidsintensiteit.
16	128	2	Theoretisch is het onstabiel voor sommige soorten cryptanalyse, maar de praktische implementatie ervan is in de meeste gevallen moeilijk vanwege de hoge eisen aan de brongegevens en de arbeidsintensiteit.
12	95	2,67	Het is niet bestand tegen sommige bekende vormen van cryptanalyse, maar is geschikt om de geheimhouding van kleine hoeveelheden gegevens (tot tientallen of honderden kilobytes) voor een korte periode te garanderen.
8	64	4	Het is niet bestand tegen sommige bekende vormen van cryptanalyse, maar is geschikt om de geheimhouding van kleine hoeveelheden gegevens (tot tientallen kilobytes) voor een korte periode te garanderen.

De laatste twee opties, met 12 en 8 ronden, kunnen een zeer, zeer beperkte tijdbescherming bieden. Het gebruik ervan is alleen gerechtvaardigd bij taken waarbij slechts kortetermijngeheimhouding van de beschermde gegevens vereist is, in de orde van enkele uren. Een mogelijk toepassingsgebied voor deze zwakke cijfervarianten is het blokkeren van UDP-verkeer van elektronische beurshandelssystemen. In dit geval wordt elk datapakket (datagram, de middelste “D” van de afkorting UDP) gecodeerd met een afzonderlijke 64-bits sleutel, en wordt de sleutel zelf gecodeerd met een sessiesleutel (een sleutel waarvan de reikwijdte één communicatiesessie tussen twee computers) en wordt samen met de gegevens verzonden.

Voordat ik eindig met de gereduceerde versies van GOST, zal ik zeggen dat alle bovenstaande overwegingen zeer speculatief zijn. De standaard biedt duurzaamheid voor slechts één variant met 32 ​​schoten. En niemand kan u garanderen dat de weerstand van gereduceerde versies van het cijfer tegen kraken op de hierboven aangegeven manier zal veranderen. Als u toch besluit ze bij uw ontwikkelingen te gebruiken, bedenk dan dat u op zeer wankele grond bent beland, die elk moment onder uw voeten vandaan kan glippen. Omdat de coderingssnelheid voor u van cruciaal belang is, kunt u misschien overwegen een snellere code of een krachtigere computer te gebruiken? Een andere overweging waarom dit de moeite waard is, is dat verzwakte versies van GOST het meest gevoelig zullen zijn voor de kwaliteit van de gebruikte vervangende eenheden.

Het onderhavige probleem heeft ook een keerzijde. Wat als de coderingssnelheid niet kritisch is, maar de sterkte-eisen zeer streng zijn? De weerstand van GOST kan op twee manieren worden vergroot – laten we ze ‘extensief’ en ‘intensief’ noemen. De eerste daarvan is niets meer dan een simpele verhoging van het aantal encryptierondes. Het is mij niet helemaal duidelijk waarom dit eigenlijk nodig zou kunnen zijn, aangezien de binnenlandse standaard zonder dit al de nodige duurzaamheid biedt. Als je echter meer aan paranoia lijdt dan het vereiste niveau (en alle “informatieverdedigers” zijn eenvoudigweg verplicht hieraan te lijden, dit is een voorwaarde voor professionele geschiktheid, de enige vraag is de ernst van de zaak :)), zal dit helpen je wordt wat rustiger. Als u niet zeker bent van dit KGB-cijfer of de vervangingstabel die u gebruikt, kunt u eenvoudigweg verdubbelen, verviervoudigen, enz. aantal rondes – selecteer het aantal op basis van de ernst van uw zaak. Met deze aanpak kun je de sterkte van het cijfer echt vergroten - als eerdere cryptanalyse eenvoudigweg onmogelijk was, is het nu onmogelijk in het kwadraat!

Een lastigere en interessantere vraag is of het mogelijk is om de sterkte van het cijfer te vergroten zonder het aantal en de structuur van de belangrijkste versleutelingsstappen te veranderen. Verrassend genoeg is het antwoord hierop positief, ook al betreden we opnieuw het wankele terrein van de speculatie. Feit is dat het in GOST bij de hoofdconversiestap 4 bij 4 bits zou moeten vervangen, maar in de praktijk (we zullen hier later over praten) voeren alle software-implementaties de vervanging byte voor byte uit, d.w.z. 8 bij 8 bits - dit wordt gedaan om redenen van efficiëntie. Als we zo’n vervanger meteen als 8-bit ontwerpen, verbeteren we de prestaties van één ronde aanzienlijk. Ten eerste zal het “diffusie”-kenmerk of de “lawine”-indicator toenemen: één bit van de brongegevens en/of sleutel zal een groter aantal bits van het resultaat beïnvloeden. Ten tweede kunnen voor grotere vervangingsknooppunten lagere differentiële en lineaire kenmerken worden verkregen, waardoor de gevoeligheid van het cijfer voor vergelijkbare soorten cryptanalyse wordt verminderd. Dit geldt met name voor verminderde GOST-cycli, en voor opties met 8 en 12 ronden is een dergelijke stap eenvoudigweg noodzakelijk. Dit zal het verlies aan duurzaamheid enigszins compenseren als gevolg van de vermindering van het aantal rondes. Wat het gebruik van deze techniek moeilijk maakt, is dat je dergelijke “vergrote” vervangingseenheden zelf zult moeten ontwerpen. En ook het feit dat grotere eenheden over het algemeen veel moeilijker te bouwen zijn dan kleinere.

Niet-standaard gebruik van de standaard.

Het belangrijkste doel van de cryptografische algoritmen van GOST is natuurlijk encryptie en gegevensbescherming. Ze kunnen echter ook andere toepassingen vinden die uiteraard verband houden met informatiebeveiliging. Laten we er kort over praten:

1. Voor codering in gammamodus voorziet GOST in de ontwikkeling van een cryptografisch gamma - een reeks bits met goede statistische kenmerken en hoge cryptografische sterkte. Dit gamma wordt vervolgens gebruikt om open data aan te passen, wat resulteert in gecodeerde gegevens. Dit is echter niet de enige mogelijke toepassing van het cryptografische gamma. Feit is dat het algoritme voor het genereren ervan een pseudo-willekeurige nummerreeksgenerator (PRNG) is met uitstekende eigenschappen. Het gebruik van zo'n PRNG waarbij alleen de statistische kenmerken van de gegenereerde reeks vereist zijn, maar cryptografische kracht niet nodig is, is natuurlijk niet erg redelijk - voor deze gevallen zijn er veel efficiëntere generatoren. Maar voor verschillende toepassingen die verband houden met informatiebeveiliging zal een dergelijke bron zeer nuttig zijn:

• Zoals hierboven opgemerkt, kan gamma worden gebruikt als “grondstof” voor het genereren van sleutels. Om dit te doen, hoeft u alleen maar een gammasegment van de vereiste lengte te verkrijgen: 32 bytes. Op deze manier kunnen sleutels naar behoefte worden gemaakt en hoeven ze niet te worden opgeslagen. Als zo'n sleutel opnieuw nodig is, is het vrij eenvoudig om deze opnieuw te genereren. U hoeft alleen maar te onthouden op welke sleutel deze oorspronkelijk is gegenereerd, welk synchronisatiebericht is gebruikt en met welke byte van de gegenereerde gamma de sleutel is begonnen. Alle informatie behalve de gebruikte sleutel is niet-geclassificeerd. Deze aanpak maakt het gemakkelijk om een ​​tamelijk complex en vertakt sleutelsysteem te besturen met slechts één “hoofdsleutel”.
• Net als de vorige kan gamma worden gebruikt als de initiële “grondstof” voor het genereren van wachtwoorden. Hier kan de vraag rijzen: waarom is het überhaupt nodig om ze te genereren? Is het niet eenvoudiger om ze eenvoudigweg uit te vinden als dat nodig is? Het falen van deze aanpak werd duidelijk aangetoond door een reeks incidenten in computernetwerken, waarvan de grootste de dagelijkse verlamming van het internet in november 1988 was, veroorzaakt door de Morris-worm. Een van de manieren waarop een kwaadaardig programma een computer binnendrong, was door wachtwoorden te raden: het programma probeerde het systeem binnen te dringen door achtereenvolgens wachtwoorden uit de interne lijst van honderden te proberen, en in een aanzienlijk deel van de gevallen slaagde dat. De menselijke verbeeldingskracht voor het bedenken van wachtwoorden bleek erg slecht. Dat is de reden dat in organisaties waar beveiliging de nodige aandacht krijgt, wachtwoorden door de systeembeveiligingsbeheerder worden gegenereerd en onder de gebruikers worden gedistribueerd. Het genereren van wachtwoorden is iets ingewikkelder dan het genereren van sleutels, omdat in dit geval het ‘ruwe’ binaire gamma moet worden omgezet in een symbolische vorm, en niet simpelweg in stukken moet worden ‘geknipt’. Bovendien moeten individuele waarden mogelijk worden weggegooid om ervoor te zorgen dat alle alfabetische tekens even waarschijnlijk in het wachtwoord voorkomen.
• Een andere manier om het cryptografische gamma te gebruiken is het gegarandeerd wissen van gegevens op magnetische media. Het is een feit dat zelfs wanneer informatie op een magnetisch medium wordt herschreven, er sporen van eerdere gegevens achterblijven, die door passend onderzoek kunnen worden hersteld. Om deze sporen te vernietigen, moet een dergelijke overschrijving vele malen worden uitgevoerd. Het bleek dat het minder vaak nodig zou zijn om informatie op de media te herschrijven als een dergelijke procedure gebruik zou maken van willekeurige of pseudo-willekeurige gegevens die onbekend zouden blijven voor deskundigen die probeerden de gewiste informatie te herstellen. Het gammacijfer zal hier van pas komen.

2. Niet alleen het cryptografische gamma, maar ook de cryptografische transformatie zelf kan worden gebruikt voor behoeften die niet direct verband houden met encryptie:

• We weten dat een van deze opties voor het gebruik van GOST de ontwikkeling is van gesimuleerde inserts voor data-arrays. Op basis van elk blokcijfer, inclusief GOST, is het echter vrij eenvoudig om een ​​schema te construeren voor het berekenen van een eenrichtings-hashfunctie, in de literatuur ook wel MDC genoemd, wat in verschillende bronnen staat voor detectiecode wijzigen / manipulatie (M wijziging/ M animatie D etectie C ode) of berichtoverzicht (M essay D ige C ode). De eerste decodering verscheen veel eerder in de literatuur, de tweede, kortere, denk ik, werd uitgevonden door degenen die zich de eerste niet konden herinneren :), - het was een grap. MDC kan direct worden gebruikt in imitatiebeschermingssystemen als analoog van imitatie-invoeging, die echter niet afhankelijk is van de geheime sleutel. Bovendien wordt MDC veel gebruikt in schema's voor elektronische digitale handtekeningen (EDS), omdat de meeste van dergelijke schema's zo zijn ontworpen dat het handig is om een ​​datablok van een vaste grootte te ondertekenen. Zoals u weet, werd op basis van de besproken GOST 28147-89-standaard de Russische Federatie-standaard voor het berekenen van de eenrichtings-hash-functie GOST R34.11-94 gebouwd.
• Het is minder bekend dat op basis van elk blokcijfer, inclusief GOST, een volledig functioneel digitaal handtekeningschema kan worden gebouwd, met een geheime handtekeningsleutel en een open verificatiecombinatie. Om een ​​aantal redenen heeft dit systeem geen brede praktische verspreiding gekregen, maar in sommige gevallen kan het nog steeds worden beschouwd als een zeer aantrekkelijk alternatief voor de “wiskundige” digitale handtekeningsystemen die momenteel dominant zijn in de wereld.

Literatuur

Informatieverwerkingssystemen. Cryptografische bescherming. Cryptografisch transformatie-algoritme GOST 28147-89. Staat Com. USSR volgens normen, M., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Shannon Claude. Wiskundige theorie van geheime systemen. In de collectie “Works on information theory and cybernetics”, M., IL, 1963, p. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Aankondiging van goedkeuring van Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Vol. 66, Nee. 235 / Donderdag 6 december 2001 / Mededelingen, pp 63369–63371. http://csrc.nist.gov/encryption/aes/
Feistel Horst. Cryptografie en computerbeveiliging. Vertaling door A. Vinokurov volgens de publicatie Horst Feistel. Cryptography and Computer Privacy, Scientific American, mei 1973, Vol. 228, nr. 5, blz. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Schneier Bruce. Toegepaste cryptografie. 2e druk. Protocollen, algoritmen en bronteksten in C-taal., M., “Triumph”, 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Handboek voor toegepaste cryptografie. ttp://www.cacr.math.uwaterloo.ca/hac/
Vinokurov Andrej. Hoe werkt een blokcijfer? Manuscript. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Vinokurov Andrej. Uitgaven over cryptografie voor het elektronische tijdschrift iNFUSED BYTES online. http://www.enlight.ru/crypto/articles/ib/ib.htm
Vinokurov Andrej, Primenko Eduard. Tekst van het rapport “Over de software-implementatie van encryptiestandaarden in de Russische Federatie en de VS”, conferentie over informatisering, Moskou, MEPhI, 28-29 januari 2001. Gepubliceerd in congresverslagen.
Informatie Technologie. Beveiliging van cryptografische informatie. Hash-functie GOST R34.11-94, State Standard van de Russische Federatie, M., 1994.

Dit algoritme is verplicht voor gebruik als versleutelingsalgoritme in overheidsorganisaties van de Russische Federatie en een aantal commerciële organisaties.

Beschrijving van het algoritme

Het algoritmediagram wordt getoond in Fig. 3.1. Zoals u kunt zien, is het ontwerp van dit algoritme vrij eenvoudig, wat de software- of hardware-implementatie ervan duidelijk vereenvoudigt.

Het GOST 28147-89-algoritme codeert informatie in blokken van 64 bits, die zijn verdeeld in twee subblokken van 32 bits (N1 en N2). Deelblok N1 wordt op een bepaalde manier bewerkt, waarna de waarde ervan wordt opgeteld

met de waarde van subblok N2 (optelling wordt modulo 2 uitgevoerd), dan worden de subblokken verwisseld. Deze transformatie wordt uitgevoerd in een bepaald aantal ronden: 16 of 32, afhankelijk van de werkingsmodus van het algoritme (hieronder beschreven). In elke ronde worden de volgende bewerkingen uitgevoerd:

1. Sleutelapplicatie. De inhoud van het /VI-subblok wordt modulo 2 32 toegevoegd met een deel van de Kx-sleutel.

De encryptiesleutel van het GOST 28147-89-algoritme heeft een afmeting van 256 bits, en Kx is het 32-bits deel ervan, d.w.z. de 256-bits encryptiesleutel wordt weergegeven als een aaneenschakeling van 32-bits subsleutels (Fig. 3.2):

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

Tijdens het versleutelingsproces wordt één van deze subsleutels gebruikt, afhankelijk van het ronde getal en de werkingsmodus van het algoritme.

Rijst. 3.1. Algoritmediagram GOST 28147-

Rijst. 3.2. Coderingssleutel van het GOST 28147-89-algoritme

2. Vervanging van de tafel. Na het intoetsen wordt het /VI-subblok verdeeld in 8 delen van 4 bits, waarvan de waarde individueel wordt vervangen in overeenstemming met de vervangingstabel voor dit deel van het subblok. Tabelvervangingen (substitutiebox, S-box) worden vaak gebruikt in moderne versleutelingsalgoritmen, dus het is de moeite waard om ze in meer detail te bekijken.

Tabelvervanging wordt op deze manier gebruikt: een gegevensblok van een bepaalde grootte (in dit geval 4 bits) wordt aan de invoer geleverd, waarvan de numerieke weergave het nummer van de uitvoerwaarde bepaalt. We hebben bijvoorbeeld een S-box met de volgende vorm:

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

Laat het 4-bits blok “0100” naar de ingang komen, d.w.z. de waarde 4. Volgens de tabel zal de uitgangswaarde gelijk zijn aan 15, d.w.z. “1111” (0 wordt vervangen door 4, 1 door 11, de waarde van 2 blijft ongewijzigd, enz.).

Zoals u kunt zien, is het ontwerp van het algoritme heel eenvoudig, wat betekent dat de grootste last van gegevensversleuteling op de vervangende tabellen valt. Helaas heeft het algoritme de eigenschap dat er ‘zwakke’ vervangingstabellen zijn, waarmee het algoritme kan worden opgelost door cryptanalytische methoden. Zwakke voorbeelden zijn bijvoorbeeld een tabel waarin de uitvoer gelijk is aan de invoer:

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

3. Bitsgewijze cyclische verschuiving naar links met 11 bits.

Algoritme werkingsmodi

Het GOST 28147-89-algoritme heeft 4 bedrijfsmodi:

□ eenvoudige vervangingsmodus;

□ gammamodus;

P-gammamodus met feedback;

□ wijze van ontwikkeling van imitatie-gehechtheden.

Deze modi verschillen enigszins van de algemeen aanvaarde modi (beschreven in paragraaf 1.4), dus het is de moeite waard om ze in meer detail te bekijken.

Deze modi hebben verschillende doeleinden, maar gebruiken dezelfde encryptietransformatie die hierboven is beschreven.

Eenvoudige vervangingsmodus

In de eenvoudige vervangingsmodus wordt elk 64-bits informatieblok eenvoudigweg gecodeerd met behulp van de 32 hierboven beschreven ronden. 32-bits subsleutels worden in de volgende volgorde gebruikt:

□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI, enz. - in rondes 1 tot en met 24;

□ K1, Kb, K5, K4, KZ, K2, K\, KO - in rondes van 25 tot 32.

Decodering in de eenvoudige vervangingsmodus wordt op precies dezelfde manier uitgevoerd, maar met een iets andere volgorde van het gebruik van subsleutels:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - in rondes 1 tot en met 8;

□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb, enz. - in rondes van 9 tot 32.

Net als bij de standaard ECB-modus wordt, vanwege de afzonderlijke versleuteling van blokken, de eenvoudige vervangingsmodus ten strengste afgeraden voor het versleutelen van de gegevens zelf; het mag alleen worden gebruikt om andere encryptiesleutels in meersleutelschema's te coderen.

Gamma-modus

In de gammamodus (Fig. 3.3) wordt elk leesbare tekstblok bit voor bit modulo 2 toegevoegd aan een 64-bit gecodeerd gammablok. Het gammacijfer is een speciale reeks die als volgt wordt gegenereerd met behulp van de hierboven beschreven transformaties:

1. Hun initiële vulling wordt naar de registers N1 en N2 geschreven - een 64-bits waarde die het "synchronisatiebericht" wordt genoemd (het synchronisatiebericht is praktisch analoog aan de initialisatievector in de CBC-, CFB- en OFB-modi).

2. De inhoud van de /VI- en N2-registers (in dit geval synchronisatieberichten) wordt gecodeerd in de eenvoudige vervangingsmodus.

3. De inhoud van N1 wordt modulo (2 32 – 1) opgeteld met de constante CI = 2 24 + 2 16 + 2 8 + 4, het resultaat van de optelling wordt naar het /VI-register geschreven.

4. De inhoud van N2 wordt modulo 2 opgeteld met de constante C2 = 2 24 + 2 16 + 2 8 +1, het resultaat van de optelling wordt naar register N2 geschreven.

5. De inhoud van de /VI- en N2-registers wordt uitgevoerd als een 64-bit gecodeerd gammablok (d.w.z. in dit geval vormen /VI en N2 het eerste gammablok).

6. Als het volgende gammablok nodig is (d.w.z. er moet verdere codering of decodering worden uitgevoerd), ga dan terug naar stap 2.

Voor decodering wordt gamma op een vergelijkbare manier gegenereerd, waarna de cijfertekst en gammabits opnieuw worden XORed.

Om hetzelfde cijferbereik te genereren, moet de gebruiker die het cryptogram ontsleutelt, dezelfde sleutel en dezelfde synchronisatieberichtwaarde hebben die werden gebruikt bij het versleutelen van de informatie. Anders is het niet mogelijk om de originele tekst uit de gecodeerde tekst te halen.

In de meeste implementaties van het GOST 28147-89-algoritme is het synchronisatiebericht geen geheim element, maar het synchronisatiebericht kan net zo geheim zijn als de coderingssleutel. In dit geval kunnen we ervan uitgaan dat de effectieve sleutellengte van het algoritme (256 bits) met nog eens 64 bits van het synchronisatiebericht toeneemt, wat als een extra sleutelelement kan worden beschouwd.

Gammamodus met feedback

In de gammamodus met feedback wordt het resultaat van het coderen van het vorige blok platte tekst gebruikt om de /VI- en L/2-registers te vullen, beginnend bij het tweede blok, niet het vorige gammablok, maar het resultaat van het coderen van het vorige blok platte tekst (Afb. 3.4). Het eerste blok in deze modus wordt volledig op dezelfde manier gegenereerd als het vorige.

Rijst. 3.4. Het genereren van een cipher-gamma in de gamma-modus met feedback

Modus voor het genereren van imitatiebijlagen

Een voorvoegsel is een cryptografische controlesom die wordt berekend met behulp van een coderingssleutel en is ontworpen om de integriteit van berichten te verifiëren. Om het te berekenen, is er een speciale modus van het GOST 28147-89-algoritme.

Het genereren van een imitatievoorvoegsel gaat als volgt:

1. Het eerste 64-bits informatieblok waarvoor het imitatievoorvoegsel wordt berekend, wordt naar de registers N1 en N2 geschreven en gecodeerd in de gereduceerde eenvoudige vervangingsmodus, waarin de eerste 16 van de 32 ronden worden uitgevoerd.

2. Het verkregen resultaat wordt modulo 2 opgeteld bij het volgende informatieblok, waarbij het resultaat wordt opgeslagen in N1 en N2.

3. M en N2 worden opnieuw gecodeerd in de verkorte eenvoudige vervangingsmodus, enz. tot het laatste informatieblok.

Het imitatievoorvoegsel wordt beschouwd als de 64-bits resulterende inhoud van de registers N1 en N2 of een deel daarvan. Meestal wordt een 32-bits imitatief voorvoegsel gebruikt, d.w.z. de helft van de inhoud van de registers. Dit is voldoende, omdat de imitatiebijlage, zoals elke controlesom, in de eerste plaats bedoeld is om te beschermen tegen onbedoelde vervorming van informatie. Ter bescherming tegen opzettelijke wijziging van gegevens worden andere cryptografische methoden gebruikt, voornamelijk een elektronische digitale handtekening (zie paragraaf 1.1).

Het imitatievoorvoegsel wordt als volgt gebruikt:

1. Bij het coderen van informatie wordt het imitatievoorvoegsel voor platte tekst berekend en samen met de cijfertekst verzonden.

2. Na decodering wordt het imitatievoorvoegsel opnieuw berekend en vergeleken met het verzonden voorvoegsel.

3. Als de berekende en verzonden imitatievoorvoegsels niet overeenkomen, is de cijfertekst tijdens de verzending vervormd of zijn tijdens de decodering onjuiste sleutels gebruikt.

Het imitatievoorvoegsel is vooral handig voor het controleren van de juiste decodering van sleutelinformatie bij gebruik van schema's met meerdere sleutels.

Het imitatievoorvoegsel is een analoog van de MAC-berichtauthenticatiecode, berekend in de CBC-modus; Het verschil is dat bij het berekenen van het imitatievoorvoegsel het synchronisatiebericht niet wordt gebruikt, terwijl bij het berekenen van de MAC de initialisatievector wordt gebruikt.

Cryptografische sterkte van het algoritme

In 1994 werd de beschrijving van het GOST 28147-89-algoritme in het Engels vertaald en gepubliceerd; het was daarna dat de resultaten van zijn analyse, uitgevoerd door buitenlandse specialisten, begonnen te verschijnen; Er werden echter geruime tijd geen aanvallen gevonden die de haalbaarheid benaderden.

□ grote sleutellengte - 256 bits; samen met het geheime synchronisatiebericht neemt de effectieve sleutellengte toe tot 320 bits;

□ 32 transformatieronden; al na 8 ronden wordt het volledige effect van verspreiding van de invoergegevens bereikt: het veranderen van één bit van het leesbare tekstblok heeft invloed op alle bits van het cijfertekstblok, en omgekeerd, d.w.z. er is een marge met meerdere sterktes.

Laten we eens kijken naar de resultaten van de cryptanalyse van het GOST 28147-89-algoritme.

Analyse van vervangingstabellen

Omdat vervangingstabellen niet in de standaard zijn opgenomen, suggereren een aantal werken (bijvoorbeeld in) dat een “competente organisatie” zowel “goede” als “slechte” vervangende tafels kan uitgeven. De beroemde deskundige Bruce Schneier noemt dergelijke aannames echter ‘geruchten’. Het is duidelijk dat de cryptografische kracht van het algoritme grotendeels afhangt van de eigenschappen van de gebruikte vervangingstabellen; dienovereenkomstig zijn er zwakke vervangingstabellen (zie voorbeeld hierboven), waarvan het gebruik de aanval op het algoritme kan vereenvoudigen. Niettemin lijkt de mogelijkheid om verschillende vervangingstabellen te gebruiken een zeer waardevol idee, waarvoor de volgende twee feiten uit de geschiedenis van de DES-encryptiestandaard kunnen worden aangehaald (voor details, zie paragraaf 3.15):

□ aanvallen die gebruik maken van zowel lineaire als differentiële cryptanalyse van het DES-algoritme maken gebruik van specifieke kenmerken van vervangende tabellen; bij gebruik van andere tabellen zal de cryptanalyse opnieuw moeten beginnen;

□ Er zijn pogingen ondernomen om DES te versterken tegen lineaire en differentiële cryptanalyse door gebruik te maken van robuustere substitutietabellen; dergelijke tabellen, die inderdaad robuuster zijn, werden bijvoorbeeld voorgesteld in het s 5 DES-algoritme; maar helaas was het onmogelijk om DES te vervangen door s 5 DES, aangezien de vervangingstabellen strikt gedefinieerd zijn in de standaard, en dienovereenkomstig ondersteunen implementaties van het algoritme waarschijnlijk niet de mogelijkheid om tabellen naar andere te veranderen.

Een aantal werken (bijvoorbeeld , en ) concluderen ten onrechte dat de geheime vervangingstabellen van het GOST 28147-89-algoritme deel kunnen uitmaken van de sleutel en de effectieve lengte ervan kunnen vergroten (wat niet significant is, aangezien het algoritme een zeer grote omvang heeft). -bit-sleutel). Het werk bewijst echter dat geheime vervangingstabellen kunnen worden berekend met behulp van de volgende aanval, die praktisch kan worden gebruikt:

1. De nulsleutel wordt ingesteld en er wordt gezocht naar de “nulvector”, d.w.z. de waarde z = /(0), waarbij /() de ronde functie van het algoritme is. Deze fase duurt ongeveer twee encryptiebewerkingen.

2. Met behulp van de nulvector worden de waarden van de vervangingstabellen berekend, wat niet meer dan 2 11 bewerkingen kost.

Algoritmewijzigingen en hun analyse

Het werk voerde een cryptanalyse uit van wijzigingen in het GOST 28147-89-algoritme:

□ GOST-H-algoritme, waarin, ten opzichte van het oorspronkelijke algoritme, de volgorde van het gebruik van subsleutels is gewijzigd, namelijk in rondes van 25 tot 32 subsleutels die in directe volgorde worden gebruikt, d.w.z. precies hetzelfde als in eerdere rondes van het algoritme;

□ GOST®-algoritme met 20 ronden, waarbij een ronde XOR gebruikt in plaats van modulo-2-optelling om de sleutel te overlappen.

Op basis van de resultaten van de analyse werd geconcludeerd dat GOST-H en GOST© zwakker zijn dan het oorspronkelijke GOST 28147-89-algoritme, omdat beide klassen van zwakke sleutels hebben. Het is vermeldenswaard dat in termen van GOST©-cryptanalyse het werk woord voor woord de sectie herhaalt die is gewijd aan de cryptanalyse van het GOST 28147-89-algoritme, een bekend werk gepubliceerd in 2000 (zonder enige verwijzing naar het origineel). Dit doet twijfels rijzen over de professionaliteit van de auteurs van het werk en de andere resultaten ervan.

In het werk werd een zeer interessante wijziging van het algoritme voorgesteld: tabellen S\…Ss moeten noodzakelijkerwijs verschillend zijn; in elke ronde van het algoritme moeten ze opnieuw worden gerangschikt volgens een bepaalde wet. Deze permutatie kan afhankelijk zijn van de encryptiesleutel, maar kan ook geheim zijn (d.w.z. deel uitmaken van een grotere encryptiesleutel dan de originele 256-bits sleutel). Beide opties verhogen volgens hun auteurs de weerstand van het algoritme tegen lineaire en differentiële cryptanalyse aanzienlijk.

En er wordt nog een wijziging met betrekking tot vervangingstabellen gegeven in het werk, waarin een van de mogelijke methoden voor het berekenen van vervangingstabellen wordt geanalyseerd op basis van de coderingssleutel. De auteurs van het werk concludeerden dat een dergelijke afhankelijkheid het algoritme verzwakt, omdat dit leidt tot de aanwezigheid van zwakke sleutels en tot enkele potentiële kwetsbaarheden van het algoritme.

Volledige algoritmeanalyse

Er zijn ook aanvallen op de volledige GOST 28147-89 zonder enige wijziging. Een van de eerste openbare werken waarin het algoritme wordt geanalyseerd, een bekend werk, is gewijd aan aanvallen die misbruik maken van zwakke punten in de sleuteluitbreidingsprocedure van een aantal bekende versleutelingsalgoritmen. In het bijzonder kan het volledige GOST 28147-89-algoritme worden verbroken met behulp van differentiële cryptanalyse op gerelateerde sleutels, maar alleen als er zwakke vervangingstabellen worden gebruikt. De 24-rondenversie van het algoritme (waarin de eerste 8 ronden ontbreken) wordt op een vergelijkbare manier geopend met eventuele vervangingstabellen, maar sterke vervangingstabellen (bijvoorbeeld de opgegeven) maken een dergelijke aanval volkomen onpraktisch.

Binnenlandse wetenschappers AG Rostovtsev en EB Makhovenko stelden in 2001 een fundamenteel nieuwe methode van cryptanalyse voor (volgens de auteurs aanzienlijk effectiever dan lineaire en differentiële cryptanalyse) door een objectieve functie te vormen uit een bekende leesbare tekst die overeenkomt met de cijfertekst en de gewenste sleutelwaarde en het vinden van het uiterste dat overeenkomt met de werkelijke sleutelwaarde. Ze vonden ook een grote klasse zwakke sleutels van het GOST 28147-89-algoritme, die het mogelijk maken om het algoritme te openen met slechts 4 geselecteerde leesbare teksten en de bijbehorende cijferteksten met een vrij lage complexiteit. De cryptoanalyse van het algoritme wordt voortgezet in het werk.

In 2004 stelde een groep specialisten uit Korea een aanval voor die, met behulp van differentiële cryptanalyse op gerelateerde sleutels, 12 bits van de geheime sleutel kan verkrijgen met een waarschijnlijkheid van 91,7%. Voor de aanval zijn 235 geselecteerde leesbare teksten en 236 encryptiebewerkingen nodig. Zoals u kunt zien, is deze aanval vrijwel nutteloos voor het daadwerkelijk breken van het algoritme.