1 Blockdiagramm des kryptografischen Transformationsalgorithmus 1

2 Einfacher Austauschmodus 4

3 Gammamodus 8

4 Gamma-Modus mit Rückmeldung 11

5 Simulationseinfügungsgenerierungsmodus 14

Anhang 1 In dieser Norm verwendete Begriffe und ihre Definitionen 16

Anhang 2 Werte der Konstanten C1, C2 18

Anhang 3 Schemata Softwareimplementierung kryptografischer Algorithmus

Transformationen. 19

Anhang 4 Regeln für die Summation Modulo 2 32 und Modulo (2 32 -I) 25

STAATLICHER STANDARD

Union der UdSSR

INFORMATIONSVERARBEITUNGSSYSTEME. KRYPTOGRAPHISCHE SICHERHEIT

Kryptografischer Konvertierungsalgorithmus

Datum der Einführung 01.07.90

Dieser Standard legt einen einheitlichen kryptografischen Transformationsalgorithmus für Informationsverarbeitungssysteme in Netzwerken elektronischer Computer (Computer), einzelner Computersysteme und Computer fest, der die Regeln für die Datenverschlüsselung und die Entwicklung von Nachahmungen definiert.

Der kryptografische Transformationsalgorithmus ist für die Hardware- oder Softwareimplementierung konzipiert, erfüllt kryptografische Anforderungen und schränkt in seinen Fähigkeiten den Grad der Geheimhaltung der geschützten Informationen nicht ein.

Der Standard ist für Organisationen, Unternehmen und Institutionen, die ihn nutzen, verbindlich kryptografischer Schutz Daten, die in Computernetzwerken, in separaten Computersystemen oder in Computern gespeichert und übertragen werden.

Die in dieser Norm verwendeten Begriffe und ihre Definitionen sind in Anhang 1 aufgeführt.

I. BLOCKDIAGRAMM DES KRYPTOGRAPHISCHEN TRANSFORMATIONSALGORITHMUS

1.1. Das Blockdiagramm des kryptografischen Transformationsalgorithmus (Kryptoschema) enthält (siehe Abbildung 1):

Offizielle Veröffentlichung ★

ein 256-Bit-Schlüsselspeichergerät (KSD), bestehend aus acht 32-Bit-Laufwerken (X0, Xt. X2, A3 L4, X$, X6, Xu); vier 32-Bit-Laufwerke (/V (, N 2, Nj, /V 4);

Die Vervielfältigung ist verboten

© Standards Publishing House, 1989 © IPK Standards Publishing House, 1996

zwei 32-Bit-Laufwerke L/$,) mit darin aufgezeichneten permanenten Füllungen C 2, C\\

zwei 32-Bit-Modulo-2-32-Addierer (SM|, SL/3);

32-Bit-Addierer mit bitweiser Summierung Modulo 2 (SL/2);

32-Bit-Modulo-Addierer (2 32 - 1) (SL/ 4);

Modulo 2(SL/5)-Addierer, es gibt keine Einschränkung hinsichtlich der Kapazität des SL/$-Addierers;

Substitutionsblock (A);

zyklisches Schieberegister elf Schritte zur höchstwertigen Ziffer (R).

1.2. Der Substitutionsblock A" besteht aus acht Substitutionsknoten A'j,

A 2, A“z, K 4, A5, A7, A 8 mit jeweils 64-Bit-Speicher. Post

Ein auf einen Substitutionsblock angewendeter 32-Bit-Vektor wird in acht aufeinanderfolgende 4-Bit-Vektoren aufgeteilt, von denen jeder durch den entsprechenden Substitutionsknoten in einen 4-Bit-Vektor umgewandelt wird, bei dem es sich um eine Tabelle mit sechzehn Zeilen mit vier Füllbits pro Zeile handelt . Der Eingabevektor bestimmt die Adresse einer Zeile in der Tabelle, die Füllung dieser Zeile ist der Ausgabevektor. Die 4-Bit-Ausgabevektoren werden dann sequentiell zu einem 32-Bit-Vektor verkettet.

1.3. Beim Addieren und zyklischen Verschieben binärer Vektoren gelten als höchstwertige Bits die Bits der Speichergeräte mit großen Zahlen.

1.4. Beim Schreiben des Schlüssels (I", W 2 ..., W q e (0,1), d = N256, in

Der RCU-Wert W\ wird in die i-te Stelle des Laufwerks Xq eingetragen, der Wert W 2 wird in die 2. Stelle des Laufwerks L# eingetragen, ..., der Wert W^ 2 wird in die 32. Stelle von eingetragen das Laufwerk Xq; der Wert W33 wird in die 1. Stelle des Laufwerks X\ y eingetragen, der Wert wird in die 2. Stelle des Laufwerks X\ y... eingetragen, der Wert W M wird in die 32. Stelle des Laufwerks X\\ the eingetragen Der Wert W 6 5 wird in die 1. Stelle des Laufwerks X 2 usw. eingetragen, der Wert 1U 2 5b wird in das 32. Bit des Laufwerks Xy eingetragen.

1.5. Beim Umschreiben von Informationen wird der Inhalt der p-ten Stelle eines Laufwerks (Addierers) in die p-te Stelle eines anderen Laufwerks (Addierers) umgeschrieben.

1.6. Die Werte der konstanten Füllungen Cj, C 2 (Konstanten) der Speichergeräte /V 6, /V5 sind in Anhang 2 angegeben.

1.7. Die Schlüssel, die die Füllung der KZU und Tabellen des Substitutionsblocks K bestimmen, sind geheime Elemente und werden in der vorgeschriebenen Weise bereitgestellt.

Das Füllen der Tabellen des Substitutionsblocks K ist ein langfristiges Schlüsselelement, das dem Computernetzwerk gemeinsam ist.

Organisation verschiedene Arten Die Kommunikation wird durch den Aufbau eines geeigneten Schlüsselsystems erreicht. In diesem Fall kann die Möglichkeit genutzt werden, Schlüssel im einfachen Ersetzungsmodus zu generieren (das KZU zu füllen) und im einfachen Ersetzungsmodus zu verschlüsseln und gleichzeitig einen imitierenden Schutz für die Übertragung über Kommunikationskanäle oder die Speicherung im Computerspeicher bereitzustellen.

1.8. Das Kryptoschema sieht vier Arten von Arbeiten vor: Verschlüsselung (Entschlüsselung) von Daten im einfachen Ersetzungsmodus; Verschlüsselung (Entschlüsselung) von Daten im Gammamodus;

Verschlüsselung (Entschlüsselung) von Daten im Gammamodus mit Rückmeldung;

Simulations-Insert-Generierungsmodus.

Schemata zur Softwareimplementierung des kryptografischen Transformationsalgorithmus sind in Anhang 3 aufgeführt.

2. EINFACHER ÄNDERUNGSMODUS

2.1. Verschlüsseln klarer Daten im einfachen Ersetzungsmodus

2.1.1. Das Kryptoschema, das den Verschlüsselungsalgorithmus im einfachen Ersetzungsmodus implementiert, sollte die in Abbildung 2 dargestellte Form haben.

Die zu verschlüsselnden offenen Daten werden in Blöcke zu je 64 Bit aufgeteilt. Eingabe eines beliebigen Blocks T () = (D|(0), ^(O), ..., d 3 1(0), i 32 (0), £|(0), b 2 (0) y. . . , Z> 32 (0)) von binären Informationen in die Laufwerke N\ und N 2 erfolgt so, dass der Wert D|(0) in das 1. Bit von N| eingetragen wird, der Wert a 2 (0) ist in das 2. Bit eingetragen / Vj usw., der Wert i 32 (0) wird in die 32. Stelle iVj eingetragen; Der Wert />|(0) wird eingegeben

1. Ziffer L/ 2, der Wert b 2 (0) wird in die 2. Ziffer N 2 eingetragen, usw., der Wert >> 32 (0) wird in die 32. Ziffer N 2 eingetragen. Als Ergebnis erhält man den Zustand (i 32 (0), i 3 |(0), ... und 2 (0) y<7|(0)) накопителя yVj и состояние (/>32 (0), b 2 1(0), ... , />|(0)) Speichereinheit N 2.

2.1.2. 256 Bit des Schlüssels werden in die RCU eingegeben. Der Inhalt von acht 32-Bit-Laufwerken Aq, X\ t ..., Xj hat die Form:

^0 = (^32^3.....

*1 =(^64^63, . ^34^33)

*7 = (^56> ^255. ... , I/ 226, ^ 225)

2.1.3. Der Verschlüsselungsalgorithmus für einen 64-Bit-Block einfacher Daten im einfachen Ersetzungsmodus besteht aus 32 Zyklen.

Im ersten Zyklus wird die Anfangsfüllung des Speichers modulo 2 32 im Addierer CM\ mit der Füllung des Speichers Xq summiert, während die Füllung des Speichers Nj beibehalten wird.

Das Ergebnis der Summation wird im Substitutionsblock K umgewandelt und der resultierende Vektor an den Eingang des Registers /? gesendet, wo er zyklisch um elf Schritte in Richtung der höchstwertigen Bits verschoben wird. Das Ergebnis der Verschiebung wird im Addierer CM 2 mit 32-Bit-Füllung des Antriebs yV 2 bitweise Modulo 2 aufsummiert. Das in CM 2 erhaltene Ergebnis wird in N\% geschrieben, mit der alten Füllung N| umgeschrieben in N 2. Der erste Zyklus endet.

Nachfolgende Zyklen werden ähnlich durchgeführt, mit

Im 2. Zyklus wird die Füllung X\ von der RCU gelesen, im 3. Zyklus von der RCU

die Füllung X2 wird gelesen usw., im 8. Zyklus wird die Füllung Xj von der RCU gelesen. In den Zyklen 9 bis 16 sowie in den Zyklen 17 bis 24 werden Füllungen aus der RCU in der gleichen Reihenfolge gelesen:

In den letzten acht Zyklen vom 25. bis zum 32. ist die Reihenfolge des Lesens der RCD-Füllungen umgekehrt:

Hölle, Hölle, Hölle, Hölle.

Somit wird bei der Verschlüsselung in 32 Zyklen die folgende Reihenfolge der Auswahl der Speicherfüllungen durchgeführt:

Hölle, ^2,^),^4>^5,^6"^7, Hölle, ^2,^3"^4,^5,-^6,^7, Hölle, Hölle, Hölle, Hölle, Hölle ,Hölle, Hölle, Hölle.

Im 32. Zyklus wird das Ergebnis des Addierers SL/2 in das Laufwerk CU 2 eingegeben und die alte Füllung im Laufwerk N\ gespeichert.

Erhalten nach dem 32. Verschlüsselungszyklus zum Ausfüllen des N| und N2 sind der verschlüsselte Datenblock, der dem einfachen Datenblock entspricht.

2.1 4 Verschlüsselungsgleichungen im einfachen Ersetzungsmodus haben die Form:

J*Cr> "(

I b(/) = a(/~ I)

bei y = I -24;

G"

\bO) - a O - O at / 8* 25 -g 31; a(32) = a(31)

A (32) = (d (31) ffl X 0)KRG> b (31)

wobei d(0) = (a 32 (0), «з|(0), ... , Ä|(0)) die anfängliche Füllung von N\ vor dem ersten Verschlüsselungszyklus ist;

6(0) = (632(0), 63j(0), ... , 6j(0)) – anfängliche Füllung /U 2 vor dem ersten Verschlüsselungszyklus;

a(j) = (032(7), 0з|(/) e... , 0|(/)) – Füllung der Steuereinheit, nach dem y-ten Verschlüsselungszyklus;

b(j) = (6з 2 (/), 63j(/"), ... , 6|(/)) - Füllung von /V 2 nach dem y-ten Verschlüsselungszyklus, y = 032.

Das Vorzeichen φ bedeutet die bitweise Summation von 32-Bit-Vektoren Modulo 2.

Das Vorzeichen Ш bedeutet die Summation von 32-Bit-Vektoren Modulo 2 32. Die Regeln für die Summation Modulo 2 32 sind im Anhang 4 aufgeführt;

/? - der Vorgang einer zyklischen Verschiebung von elf Schritten zu den höchsten Ziffern, d.h.

^(g 32"O|>g 30>g 29>g 28>g 27>g 26"g 25>g 24>g 23'G 22"G 2b G 20>"g 2* g |)~

= (g 21" g 20> - "g 2* g 1 * G 32>G31 *GzO" g 29* g 28*, 27e"26e/"25>, 24>G23", 22)*

2.1.5. Der 64-Bit-Block verschlüsselter Daten Tsh wird von den Laufwerken L^, VU 2 in der folgenden Reihenfolge ausgegeben: vom 1., 2., ..., 32. Bit des Laufwerks L7|, dann vom 1., 2., ... , 32. Bit des Speichers W 2, d.h.

t w - (a,<32),0 2 (32),0 32 (32), 6,(32), 6 2 <32),6 32 <32».

Die verbleibenden Blöcke offener Daten im einfachen Ersetzungsmodus werden auf die gleiche Weise verschlüsselt.

2.2. Entschlüsseln verschlüsselter Daten im einfachen Ersetzungsmodus

2.2.1. Das Kryptoschema, das den Entschlüsselungsalgorithmus im einfachen Ersetzungsmodus implementiert, hat die gleiche Form (siehe Kapitel 2) wie für die Verschlüsselung. In die RCU werden 256 Bit des gleichen Schlüssels eingegeben, der auch zur Verschlüsselung verwendet wird. Die zu entschlüsselnden verschlüsselten Daten werden in Blöcke zu je 64 Bit aufgeteilt. Geben Sie einen beliebigen Block ein

T w - (0,(32),o 2 (32), ..., 0 32 (32), 6,(32), 6 2 (32), ..., 6 32 (32))

in die Akkumulatoren L' und N 2 werden so erzeugt, dass der Wert dj(32) in die 1. Stelle /V eingetragen wird, der Wert o 2 (32) in die 2. Stelle /V usw., der Wert a 32 (32) wird in die 32. Ziffer /V, eingetragen; der Wert 6,(32) wird in die 1. Stelle von N2 eingetragen usw., der Wert 6 32 (32) wird in die 32. Stelle von N2 eingetragen.

2.2.2. Die Entschlüsselung erfolgt nach dem gleichen Algorithmus wie die Verschlüsselung offener Daten, mit dem Unterschied, dass die Füllungen der Laufwerke Xq, X\y..., Xj in Entschlüsselungszyklen in folgender Reihenfolge aus der RCU gelesen werden:

Hölle, Hölle 3, Hölle, Hölle, Hölle, Hölle, Hölle, Hölle 0,

Hölle 6, Hölle 4, Hölle 2, Hölle, Hölle, Hölle, Hölle 2, Hölle.

2.2.3. Die Entschlüsselungsgleichungen sehen so aus:

G d (32 - /) = (d (32 - / + 1) SHLG,.,) *LF6(32 - / + 1) b (32 - /) = d (32 - / + 1) at, / = 1+8;

I o(32- /) = (a(32-/M)SHDG (32 _ /)(tod8))KLFL(32./M) |6(32-/) = d (32 - / + 1)

bei /= 9 + 31;

b(0) = (a (1) ШДГо) ОФй(1)

2.2.4. Die nach 32 Betriebszyklen erhaltenen W- und N2-Laufwerke bilden einen Block offener Daten.

Dann = (fli(O), a 2 (0), ... , Az 2 (0)" 6, (0), 6 2 (0), ... , 6 32 (0)), entsprechend dem Block verschlüsselter Daten, während der Wert o,(0) von Block 7о dem Inhalt des 1. Bits yV entspricht, entspricht der Wert 02(0).

S. 8 GOST 28147-89

entspricht dem Inhalt des 2. Bits N\ usw., der Wert Dz2(0) entspricht dem Inhalt des 32. Bits N\; der Wert 6j(0) entspricht dem Inhalt des 1. Bits; der Wert ^(0) entspricht dem Inhalt des 2. Bits N2 usw., der Wert £зг(0) entspricht dem Inhalt des 32. Bits N2 -

Die übrigen Blöcke verschlüsselter Daten werden auf die gleiche Weise entschlüsselt.

2.3. Der Verschlüsselungsalgorithmus im Modus des einfachen Ersetzens des 64-Bit-Blocks G 0 wird mit A y bezeichnet, d.h.

A (T 0) = A (a (0), b (0)) = (a (32), b (32)) = T w.

2.4. Der einfache Ersetzungsmodus kann zum Verschlüsseln (Entschlüsseln) von Daten nur in den in Abschnitt 1.7 genannten Fällen verwendet werden.

3. SPIELMODUS

3.1. Offene Daten im Gammamodus verschlüsseln

3.1.1. Das Kryptoschema, das den Verschlüsselungsalgorithmus im Gammamodus implementiert, hat die in Abbildung 3 dargestellte Form.

Offene Daten, unterteilt in 64-Bit-Blöcke T\)\ 7), 2) ..., 7)) m“, 1 7[) M), werden im Gammamodus durch bitweise Summation Modulo 2 im Addierer SL/ verschlüsselt. 5 mit der Chiffre Gamma Гш, die in Blöcken zu 64 Bit erstellt wird, d.h.

G _/L1) R2) Lm-1) LM)\

"ill V 1 w e * w * » " Sh » " * * * " 111 /»

wobei M durch das Volumen der verschlüsselten Daten bestimmt wird.

Tjj) - Yth 64-Bit-Block, /“ die Anzahl der Binärziffern in Block 7J) M) kann kleiner als 64 sein, während der Teil des Chiffrierumfangs, der nicht für die Verschlüsselung aus Block Г\^] verwendet wird, verworfen wird.

3.1.2. 256 Bit des Schlüssels werden in die RCU eingegeben. In die Laufwerke iVj, N 2 wird eine 64-Bit-Binärsequenz (Sync-Nachricht) S = (5*1, S 2, ..., 5^4) eingeführt, die die Erstbefüllung dieser Laufwerke für die nachfolgende Generation darstellt von M-Blöcken der Chiffre Gamma. Die Sync-Nachricht wird in jV| eingetragen und L^so dass der Wert 5[ in die 1. Ziffer von VU eingetragen wird), der Wert S 2 in die 2. Ziffer N\ usw. eingetragen wird, der Wert ^ in die 32. Ziffer 7V| eingetragen wird; der Wert S33 wird in die 1. Stelle N2 eingetragen, der Wert 4S34 wird in die 2. Stelle N2 eingetragen usw., der Wert wird in die 32. Stelle N2 eingetragen.

3.1.3. Die Erstbefüllung der Laufwerke /Vj und N 2 (Sync-Nachricht.5) erfolgt verschlüsselt im einfachen Ersetzungsmodus gemäß

Ein bekannter Forscher, der Begründer der algebraischen Kryptoanalyse, Nicolas Courtois, behauptet, dass die GOST-Blockchiffre, die bald zum internationalen Standard werden sollte, tatsächlich geknackt wurde und erwartet in Zukunft viele Veröffentlichungen, die seine Vorstellungen über die Instabilität weiterentwickeln sollten dieses Algorithmus.

Im Folgenden finden Sie kurze Auszüge aus dieser Arbeit, die als alarmierender Angriff inmitten der internationalen Standardisierung angesehen werden kann (der Autor war für ähnliche Übertreibungen in Bezug auf AES bekannt, seine Arbeit hatte damals jedoch großen theoretischen Einfluss auf die Kryptoanalyse, hat sie aber nicht vorangetrieben). zu praktischen Angriffen auf AES selbst). Aber vielleicht ist dies eine echte Warnung vor dem Beginn der Phase des „abstürzenden Flugzeugs“, die mit dem Zusammenbruch des nationalen Verschlüsselungsstandards enden könnte, wie es beim SHA-1-Hashing-Algorithmus und beim „de facto“ MD5 der Fall war Hashing-Algorithmus.

GOST 28147-89 wurde 1989 standardisiert und wurde zum ersten offiziellen Standard zum Schutz vertraulicher Informationen, die Verschlüsselungsspezifikation blieb jedoch geschlossen. 1994 wurde der Standard freigegeben, veröffentlicht und ins Englische übersetzt. Analog zu AES (und im Gegensatz zu DES) darf GOST vertrauliche Informationen ohne Einschränkungen gemäß den Vorgaben des russischen Standards schützen. Das. GOST ist kein Analogon von DES, sondern ein Konkurrent von 3-DES mit drei unabhängigen Schlüsseln oder AES-256. Es ist offensichtlich, dass es sich bei GOST um eine ziemlich seriöse Chiffre handelt, die militärische Kriterien erfüllt und für die anspruchsvollsten Anwendungen entwickelt wurde. Basierend auf Anwendungen russischer Banken wurden mindestens zwei Sätze von GOST-S-Boxen identifiziert. Diese Banken müssen geheime Kommunikation mit Hunderten von Filialen führen und Milliarden von Dollar vor betrügerischen Diebstählen schützen.

GOST ist eine Blockchiffre mit einfacher Feistel-Struktur, mit einer Blockgröße von 64 Bit, einem 256-Bit-Schlüssel und 32 Runden. Jede Runde enthält eine Modulo-2^32-Schlüsseladdition, einen Satz von acht 4-Bit-S-Boxen und eine einfache 11-Bit-Rundenverschiebung. Ein Merkmal von GOST ist die Möglichkeit, S-Blöcke geheim zu speichern, die als zweiter Schlüssel betrachtet werden können, wodurch das effektive Schlüsselmaterial auf 610 Bit erhöht wird. Ein Satz S-Boxen wurde 1994 als Teil der Hash-Funktionsspezifikation GOST-R 34.11-94 veröffentlicht und, wie Schneier schrieb, von der Zentralbank der Russischen Föderation verwendet. Es wurde auch in den RFC4357-Standard im Teil „id-GostR3411-94-CryptoProParamSet“ aufgenommen. Es gab einen Fehler im Quellcode am Ende von Schneiers Buch (in der S-Box-Reihenfolge). Die genaueste Referenzimplementierung ursprünglich russischen Ursprungs ist jetzt in der OpenSSL-Bibliothek zu finden. Wenn irgendwo geheime S-Boxen verwendet werden, dann können sie aus Softwareimplementierungen und aus Mikroschaltkreisen extrahiert werden, auf denen entsprechende Werke veröffentlicht wurden.

GOST ist ein ernstzunehmender Konkurrent

Zusätzlich zu seiner sehr großen Schlüsselgröße weist GOST im Vergleich zu AES und anderen ähnlichen Verschlüsselungssystemen deutlich geringere Ausführungskosten auf. Tatsächlich kostet es viel weniger als AES, das viermal so viele Hardware-Logikgatter für ein deutlich niedrigeres angegebenes Sicherheitsniveau erfordert.

Es ist nicht verwunderlich, dass GOST zu einem Internetstandard geworden ist, insbesondere ist es in vielen Krypto-Bibliotheken wie OpenSSL und Crypto++ enthalten und erfreut sich auch außerhalb seines Ursprungslandes immer größerer Beliebtheit. Im Jahr 2010 wurde GOST als weltweiter Verschlüsselungsstandard der ISO-Standardisierung vorgelegt. Eine äußerst kleine Anzahl von Algorithmen hat es geschafft, internationale Standards zu werden. ISO/IEC 18033-3:2010 beschreibt die folgenden Algorithmen: vier 64-Bit-Chiffren – TDEA, MISTY1, CAST-128, HIGHT – und drei 128-Bit-Chiffren – AES, Camellia, SEED. Es wird vorgeschlagen, GOST zum gleichen ISO/IEC 18033-3-Standard hinzuzufügen.

Zum ersten Mal in der Geschichte der industriellen Standardisierung haben wir es mit einem derart konkurrenzfähigen Algorithmus hinsichtlich der Optimalität zwischen Kosten und Sicherheitsniveau zu tun. GOST hat 20 Jahre an Versuchen zur Kryptoanalyse hinter sich, und bis vor Kurzem wurde seine militärische Sicherheit nicht in Frage gestellt.

Wie der Autor kürzlich durch private Korrespondenz erfahren hat, hat die Mehrheit der Länder bei der ISO-Abstimmung in Singapur gegen GOST gestimmt, die Ergebnisse dieser Abstimmung werden jedoch noch auf der ISO-SC27-Plenarsitzung berücksichtigt, sodass sich GOST noch im Prozess der Standardisierung befindet der Zeitpunkt der Veröffentlichung dieser Arbeit.

Expertenmeinungen zu GOST

Keine der verfügbaren Informationen und Literatur zu GOST gibt Anlass zu der Annahme, dass die Verschlüsselung unsicher sein könnte. Im Gegenteil, die große Schlüsselgröße und die große Anzahl an Patronen machen GOST auf den ersten Blick für den jahrzehntelangen Einsatz geeignet.

Jeder, der mit dem Mooreschen Gesetz vertraut ist, weiß, dass 256-Bit-Schlüssel theoretisch mindestens 200 Jahre lang sicher bleiben. GOST wurde umfassend von führenden Kryptographie-Experten untersucht, die auf dem Gebiet der Blockchiffrierungsanalyse bekannt sind, wie Schneier, Biryukov, Dunkelman, Wagner, vielen australischen, japanischen und russischen Wissenschaftlern, ISO-Kryptographie-Experten, und alle Forscher haben zum Ausdruck gebracht, dass es so aussieht dass es sicher sein kann oder sollte. Es ist zwar weithin bekannt, dass die GOST-Struktur selbst beispielsweise im Vergleich zu DES extrem schwach ist, insbesondere die Diffusion ist nicht so gut, aber das liegt schon immer daran, dass dies durch eine große Anzahl an Runden ausgeglichen werden muss (32) sowie zusätzliche Nichtlinearität und Diffusion durch Modulo-Addition.

Biryukov und Wagner schrieben: „Die große Anzahl an Runden (32) und die gut untersuchte Feistel-Konstruktion, kombiniert mit aufeinanderfolgenden Shannon-Permutationen, bilden eine solide Grundlage für die GOST-Sicherheit.“ Im selben Artikel lesen wir: „Nach erheblichem Zeit- und Arbeitsaufwand wurden in der offenen Literatur keine Fortschritte beim Kryptoanalysestandard erzielt.“ Daher gab es keine nennenswerten Angriffe, die in einem realistischen Szenario, in dem GOST bei der Verschlüsselung mit vielen verschiedenen Zufallsschlüsseln verwendet wird, eine Entschlüsselung oder Wiederherstellung des Schlüssels ermöglichen würden. Im Gegensatz dazu gibt es viele Arbeiten zu Angriffen auf schwache Schlüssel in GOST, Angriffen mit verknüpften Schlüsseln und Angriffen auf die Wiederherstellung geheimer S-Boxen. Auf der Crypto 2008 wurde ein Hack einer Hash-Funktion basierend auf dieser Chiffre vorgestellt. Bei allen Angriffen hat der Angreifer einen deutlich größeren Freiheitsgrad, als ihm normalerweise zugestanden wird. Bei traditionellen Anwendungen der Verschlüsselung mit zufällig ausgewählten Schlüsseln wurden bisher keine schwerwiegenden kryptografischen Angriffe auf GOST festgestellt, was 2010 mit dem zusammenfassenden Satz ausgedrückt wurde: „Trotz der erheblichen Bemühungen von Kryptoanalytikern in den letzten 20 Jahren war GOST noch nicht erfolgreich.“ geknackt“ (Axel Poschmann, San Ling und Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, S. 219-233, 2010).

Lineare und Differentialanalyse GOST

In Schneiers bekanntem Buch lesen wir: „Gegen differenzielle und lineare Kryptoanalyse ist GOST wahrscheinlich robuster als DES.“ Die Hauptbewertung der Sicherheit von GOST erfolgte im Jahr 2000 durch Gabidulin et al. Ihre Ergebnisse sind sehr beeindruckend: Bei der vorgesehenen Sicherheitsstufe von 2^256 reichen fünf Runden aus, um GOST vor linearer Kryptoanalyse zu schützen. Selbst wenn S-Blöcke durch identische ersetzt werden und die einzige nichtlineare Operation der Chiffre – Addition modulo 2^32 – erfolgt, ist die Chiffre nach 6 Runden von 32 immer noch resistent gegen lineare Kryptoanalyse. Die differenzielle GOST-Kryptanalyse sieht vergleichsweise einfacher und einfacher aus erregt mehr Aufmerksamkeit. Für die Sicherheitsstufe 2^128 gingen Forscher (Vitaly V. Shorin, Vadim V. Jelezniakov und Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint, eingereicht bei Elsevier Preprint, 4. April 2001) von ausreichendem Widerstand auf dieser Ebene aus von 7 Runden. Ihrer Meinung nach ist es „extrem schwierig“, GOST in mehr als fünf Runden zu hacken. Darüber hinaus zeigten zwei japanische Forscher, dass ein klassischer Vorwärtsdifferentialangriff mit einer Differentialcharakteristik eine äußerst geringe Wahrscheinlichkeit hat, eine große Anzahl von Runden zu überleben. Basierend auf der Tatsache, dass eine ziemlich „gute“ iterative Differentialcharakteristik für eine begrenzte Anzahl von Runden untersucht wird (die selbst eine Wahrscheinlichkeit hat, nicht besser als 2-11,4 pro Runde zu bestehen), sind die Werte des Satzes geeigneter Schlüssel geringer als die Hälfte. Bei einem Vollrunden-GOST funktioniert ein solcher Angriff mit einem einzigen Merkmal nur mit einem vernachlässigbaren Teil der Tasten in der Größenordnung von 2-62 (und selbst in diesem kleinen Teil besteht die Wahrscheinlichkeit, dass er nicht mehr als 2-62 durchläuft). 360).

Komplexere Angriffe beinhalten mehrere Differentiale, die bestimmten Mustern folgen, wie zum Beispiel die Verwendung einzelner S-Boxen, die Null-Differentiale haben, während andere Bits Einsen ungleich Null haben. Wir sprechen von diskriminierenden Angriffen, die auf den schlechten Diffusionseigenschaften von GOST basieren. Der beste dieser Angriffe funktioniert gegen 17 GOST-Runden, hängt vom Schlüssel ab und verfügt über einen äußerst schwachen Diskriminator von Zufallsdaten am Ausgang, sodass er irgendwie verwendet werden kann, um Informationen über den Schlüssel zu erhalten.

Gleitende und reflektierende Angriffe

Laut Biryukov und Wagner macht die Struktur von GOST, zu der auch die Umkehrung der Reihenfolge der Unterschlüssel in den letzten Runden gehört, GOST resistent gegen Gleitangriffe (auch „Gleitangriffe“ genannt). Aufgrund des hohen Maßes an Selbstähnlichkeit in der Chiffre sind jedoch Schlüsselinversionsangriffe auf Kombinationen aus Festpunkten und „Reflexions“-Eigenschaften (auch „Reflexionsangriffe“ genannt) für bestimmte schwache Schlüssel möglich. Die Komplexität dieses Angriffs beträgt 2^192 und 2^32 übereinstimmende Klartexte.

Aktuelle Ergebnisse

Auch neue Angriffe nutzen Reflektion und brachen tatsächlich GOST, das auf der FSE-Konferenz 2011 vorgestellt wurde. Diese Angriffe wurden auch unabhängig vom Autor dieser Arbeit entdeckt. Der Angriff erfordert 2^132 Bytes Speicher, was tatsächlich schlimmer ist als langsamere Angriffe mit geringerem Speicherbedarf.

Viele neue, auf Selbstähnlichkeit basierende Angriffe wirken gegen alle GOST-Schlüssel und ermöglichen es Ihnen, einen vollständigen GOST mit einem 256-Bit-Schlüssel zu knacken, und zwar nicht nur für schwache Schlüssel, wie es bisher der Fall war. Alle diese Angriffe benötigen deutlich weniger Speicher und sind deutlich schneller.

Diese neuen Angriffe können als Beispiele für ein neues allgemeines Paradigma für die Kryptoanalyse von Blockchiffren angesehen werden, das als „algebraische Komplexitätsreduktion“ bezeichnet wird und diese Angriffe auf viele Spezialfälle von Angriffen mit bekannten Fixpunkten, Slips, Involutionen und Zyklen verallgemeinert. Es ist wichtig, dass es in der Familie all dieser Angriffe solche gibt, die eine GOST-Kryptoanalyse ohne jegliche Reflexionen und ohne symmetrische Punkte ermöglichen, die während der Berechnungen auftreten. Ein Beispiel ist ein einfacher GOST-Hacking-Angriff, der in dieser Arbeit nicht berücksichtigt wird.

Algebraische Kryptoanalyse und Angriffe geringer Komplexität auf Chiffren mit reduzierter Rundenzahl

Algebraische Angriffe auf Block- und Stromchiffren können als das Problem dargestellt werden, ein großes System boolescher algebraischer Gleichungen zu lösen, das der Geometrie und Struktur eines proprietären kryptografischen Schemas folgt. Die Idee selbst geht auf Shannon zurück. In der Praxis wurde es für DES (erstmals vom Autor dieser Arbeit eingeführt) als formale Kodierungsmethode eingeführt und kann 6 Runden auf nur einem bekannten Klartext knacken. Die Manipulation mit Gleichungen erfolgt auf Basis von XL-Algorithmen, Gröbner-Basen, der ElimLin-Methode und SAT-Lösern.

In der Praxis wurden algebraische Angriffe gegen eine sehr kleine Anzahl von Runden von Blockchiffren durchgeführt, führten jedoch bereits zum Brechen von Stream-Chiffren, und es gab auch Erfolge beim Brechen ultraleichter Chiffren für Mikrohardware. Aufgrund von Schwierigkeiten beim Speicherplatz und bei der Schätzung der Rechenkosten werden sie mit anderen Angriffen kombiniert.

Wie hackt man GOST?

Ein algebraischer Angriff auf das vollständige GOST wird in der besprochenen Veröffentlichung ausführlicher vorgestellt. In einer früheren Arbeit hat der Autor bereits 20 algebraische Angriffe auf GOST skizziert und erwartet in naher Zukunft eine Vielzahl davon. Der in dieser Arbeit vorgeschlagene Angriff ist nicht der beste, aber er eröffnet einen einfachen (zumindest für Kryptografen verständlichen) Weg für spätere Entwicklungen, um eine spezifische Methodik zum Brechen von GOST zu entwickeln.

Das praktische Ergebnis ist immer noch bescheiden: 2^64 bekannte Klartexte und 2^64 Speicher zum Speichern von Klartext-/Chiffretext-Paaren ermöglichen es, GOST 2^8 schneller als mit einfacher Brute-Force zu knacken. Aber im Hinblick auf die Kryptoanalyse ist die Aussage, dass „GOST gehackt wurde“, völlig wahr.

Schlussfolgerungen

GOST soll ein militärisches Sicherheitsniveau für die nächsten 200 Jahre gewährleisten. Die meisten der führenden Experten, die GOST untersuchten, waren sich einig, dass „GOST trotz erheblicher kryptoanalytischer Bemühungen seit 20 Jahren noch nicht geknackt wurde“. Im Jahr 2010 wurde GOST als globaler Verschlüsselungsstandard zur ISO 18033 befördert.

Die Grundlage der Ideen zur algebraischen Kryptoanalyse entstand vor mehr als 60 Jahren. Doch erst in den letzten 10 Jahren wurden effiziente Softwaretools entwickelt, um eine Vielzahl NP-vollständiger Probleme (teilweise) zu lösen. Eine Reihe von Stream-Verschlüsselungen wurden gebrochen. Mit dieser Methode wurde nur eine Blockchiffre gebrochen – das schwache KeeLoq selbst. In dieser Arbeit knackt der Autor eine wichtige, tatsächlich verwendete GOST-Verschlüsselung. Er stellt fest, dass dies das erste Mal in der Geschichte ist, dass eine standardisierte Regierungschiffre durch algebraische Kryptoanalyse gebrochen wurde.

Ein einfacher „MITM with Reflection“-Angriff auf GOST wurde bereits auf der FSE 2011-Konferenz vorgestellt. In der in diesem Artikel besprochenen Arbeit wird ein weiterer Angriff nur vorgestellt, um zu veranschaulichen, wie viele Angriffe auf GOST mittlerweile bereits aufgetreten sind, viele davon die schneller sind, und ein algebraischer Angriff erfordert viel weniger Speicher und eröffnet einem Gegner einen nahezu unerschöpflichen Raum an Möglichkeiten, die Chiffre auf unterschiedliche Weise anzugreifen. Diese Arbeit zeigt auch, dass die Reflection-Eigenschaft nicht zum Hacken verwendet werden muss.

Der Autor stellt fest: Es ist offensichtlich, dass GOST gravierende Mängel aufweist und nicht mehr den von der ISO geforderten Widerstand bietet. Viele Angriffe auf GOST werden im Rahmen der Bestätigung des Paradigmas der algebraischen Komplexitätsreduktion vorgestellt.

Abschließend weist der Forscher insbesondere auf einige Fakten hin, die dem Leser noch nicht zur Verfügung stehen, ihm aber bekannt sind und die während des ISO-Standardisierungsprozesses wichtig sind. Bei diesem Angriff handelt es sich nicht nur um einen „Zertifizierungs“-Angriff auf GOST, der schneller ist als Brute-Force. Tatsächlich wäre es äußerst gefährlich und unverantwortlich, GOST jetzt zu standardisieren. Dies liegt daran, dass einige der Angriffe in der Praxis machbar sind. Einige GOST-Schlüssel können sogar in der Praxis entschlüsselt werden, seien es schwache Schlüssel oder Schlüssel aus bestimmten realen Anwendungen von GOST. In einer früheren Arbeit untersucht der Autor ausführlich Fälle, in denen praktische Angriffe möglich sind. Wichtig ist auch, dass „dies das erste Mal in der Geschichte ist, dass eine ernsthafte, standardisierte Blockchiffrierung, die zum Schutz militärischer Geheimnisse und zum Schutz von Regierungsgeheimnissen für Regierungen, Großbanken und andere Organisationen entwickelt wurde, durch einen mathematischen Angriff gebrochen wurde.“ ."

). Gleichzeitig wächst in den russischen Medien und Blogs russischer Benutzer die Zahl der Notizen zu diesem Algorithmus: Sie behandeln sowohl die Ergebnisse von Angriffen auf den russischen Standard mit unterschiedlichem Grad an Zuverlässigkeit als auch Meinungen zu seinen Betriebseigenschaften. Die Autoren (und damit auch die Leser) dieser Notizen haben oft den Eindruck, dass der inländische Verschlüsselungsalgorithmus veraltet und langsam ist und Schwachstellen aufweist, die ihn deutlich anfälliger für Angriffe machen als ausländische Verschlüsselungsalgorithmen mit ähnlicher Schlüssellänge. Mit dieser Notizreihe möchten wir Sie in verständlicher Form über den aktuellen Stand des russischen Standards informieren. Der erste Teil behandelt alle Angriffe auf GOST 28147-89, die der internationalen kryptografischen Gemeinschaft bekannt sind, und aktuelle Einschätzungen seiner Stärke. In zukünftigen Veröffentlichungen werden wir die Eigenschaften des Standards auch unter dem Gesichtspunkt der Fähigkeit, effektive Implementierungen zu erstellen, genauer betrachten.

Nicolas Courtois – „der Große und Schreckliche“

Beginnen wir mit einer Geschichte über die Aktivitäten von Nicolas Courtois, dem Autor einer ganzen Reihe von Werken zum russischen Blockverschlüsselungsstandard ().

Im Oktober 2010 begann der Prozess der Prüfung der Aufnahme des GOST 28147-89-Algorithmus in den internationalen Standard ISO/IEC 18033-3. Bereits im Mai 2011 erschien im elektronischen Archiv ePrint ein Artikel des berühmten Kryptographen Nicolas Courtois, der von einer sehr zweideutigen Haltung der weltweiten Kryptografiegemeinschaft gegenüber ihm geprägt war. Die Veröffentlichungen von Courtois sind ein trauriges Beispiel für die Manipulation von Begriffen, die keine neuen Eigenschaften des betreffenden Objekts offenbaren, sondern mit dem Anspruch auf Sensation die Verbreitung falscher Meinungen über seine tatsächlichen Eigenschaften in einem inkompetenten Umfeld provozieren.

Algebraische Methode

Courtois‘ Argumentation basiert auf zwei Klassen von Kryptoanalysemethoden: algebraischen Methoden und differenziellen Methoden. Schauen wir uns die erste Klasse von Methoden an.

Vereinfacht lässt sich die Methode der algebraischen Kryptoanalyse als Zusammenstellung und Lösung eines großen Gleichungssystems beschreiben, dessen Lösungen jeweils dem Ziel des Kryptoanalytikers entsprechen (z. B. wenn ein System anhand eines Paares zusammengestellt wird). von Klartext und Chiffretext, dann entsprechen alle Lösungen dieses Systems den Schlüsseln, mit denen dieser Klartext in diesen umgewandelt und verschlüsselt wird). Das heißt, im Fall des Problems der Kryptoanalyse einer Blockchiffre besteht der Kern der algebraischen Methode der Kryptoanalyse darin, dass der Schlüssel als Ergebnis der Lösung eines Systems polynomialer Gleichungen gefunden wird. Die Hauptschwierigkeit besteht darin, ein möglichst einfaches System unter Berücksichtigung der Eigenschaften einer bestimmten Chiffre zu erstellen, damit der Lösungsprozess möglichst wenig Zeit in Anspruch nimmt. Dabei spielen die Merkmale der einzelnen zu analysierenden Chiffren eine Schlüsselrolle.

Die von Courtois verwendete algebraische Methode kann wie folgt kurz beschrieben werden. In der ersten Stufe werden Eigenschaften von GOST 28147-89 wie das Vorhandensein eines Fixpunkts für einen Teil der Verschlüsselungstransformation sowie des sogenannten Reflexionspunkts genutzt. Dank dieser Eigenschaften werden aus einer ausreichend großen Anzahl von Klartext-Geheimtext-Paaren mehrere Paare ausgewählt, die es ermöglichen, Transformationen nicht bei 32, sondern nur bei 8 Runden zu berücksichtigen. Die zweite Stufe besteht darin, dass basierend auf den Ergebnissen von 8 Rundentransformationen, die in der ersten Stufe erhalten wurden, ein System nichtlinearer Gleichungen konstruiert wird, in dem die Schlüsselbits Unbekannte sind. Als nächstes wird dieses System gelöst (das klingt einfach, ist aber in Wirklichkeit der zeitaufwändigste Teil der Methode, da das System aus nichtlinearen Gleichungen besteht).

Wie oben erwähnt, gibt es in der Arbeit nirgendwo eine detaillierte Beschreibung und Analyse der Komplexität der zweiten und Hauptphase der Schlüsselbestimmung. Es ist die Komplexität der zweiten Stufe, die die Komplexität der gesamten Methode als Ganzes bestimmt. Stattdessen liefert der Autor die berüchtigten „Fakten“, auf deren Grundlage er Schätzungen zur Arbeitsintensität vornimmt. Diese „Fakten“ sollen auf experimentellen Ergebnissen beruhen. Eine Analyse der „Fakten“ aus Courtois‘ Gesamtwerk findet sich in den Werken einheimischer Autoren. Die Autoren dieser Arbeit stellen fest, dass sich viele der „Fakten“, die Courtois ohne jegliche Beweise vorlegte, bei experimentellen Tests als falsch herausstellten. Die Autoren des Artikels gingen noch einen Schritt weiter und führten in Anlehnung an Courtois eine Analyse der Komplexität der zweiten Stufe unter Verwendung fundierter Algorithmen und Schätzungen durch. Die resultierenden Komplexitätsschätzungen zeigen die völlige Unanwendbarkeit des vorgestellten Angriffs. Neben einheimischen Autoren wurden in dem Werk beispielsweise auch die großen Probleme angemerkt, die Courtois mit der Beurteilung und Begründung seiner Methoden hat.

Differentialmethode

Betrachten wir die zweite Courtois-Methode, die auf der differentiellen Kryptoanalyse basiert.

Die allgemeine Methode der differenziellen Kryptoanalyse basiert auf der Ausnutzung der Eigenschaften nichtlinearer Abbildungen, die in kryptografischen Grundelementen verwendet werden, verbunden mit dem Einfluss des Schlüsselwerts auf die Abhängigkeiten zwischen den Unterschieden zwischen Eingabe- und Ausgabewertpaaren dieser Abbildungen . Beschreiben wir die Grundidee der Differentialmethode der kryptografischen Analyse einer Blockchiffre. Typischerweise transformieren Blockchiffren die Eingabedaten schrittweise mithilfe einer Reihe sogenannter runder Transformationen, wobei bei jeder runden Transformation nicht der gesamte Schlüssel, sondern nur ein Teil davon verwendet wird. Betrachten wir eine leicht „abgeschnittene“ Chiffre, die sich vom Original dadurch unterscheidet, dass sie keine letzte Runde hat. Nehmen wir an, es konnte festgestellt werden, dass die Verschlüsselung zweier Klartexte, die sich in einigen festen Positionen unterscheiden, mit einer solchen „abgeschnittenen“ Chiffre höchstwahrscheinlich zu Chiffretexten führt, die sich auch in einigen festen Positionen unterscheiden. Diese Eigenschaft zeigt, dass eine „abgeschnittene“ Chiffre höchstwahrscheinlich eine Abhängigkeit zwischen einigen Klartexten und den Ergebnissen ihrer Verschlüsselung hinterlässt. Um einen Teil des Schlüssels mithilfe dieses offensichtlichen Fehlers wiederherzustellen, ist es notwendig, vorab ausgewählte Klartexte auf dem Schlüssel, den wir wiederherstellen möchten, zu verschlüsseln (der sogenannte „Chosen-Plaintext-Angriff“). Zu Beginn des „Schlüsselöffnungsvorgangs“ werden zufällig mehrere Paare von Klartexten generiert, die sich in denselben festen Positionen unterscheiden. Alle Texte werden mit einer „vollständigen“ Verschlüsselung verschlüsselt. Die resultierenden Chiffretextpaare werden wie folgt verwendet, um die Schlüsselbits wiederherzustellen, die in der letzten Transformationsrunde verwendet wurden. Unter Verwendung eines zufällig ausgewählten Werts der gewünschten Schlüsselbits wird auf alle Chiffretexte eine zur Transformation der letzten Runde umgekehrte Transformation angewendet. Tatsächlich erhalten wir, wenn wir den gewünschten Wert der Schlüsselbits erraten haben, das Ergebnis einer „abgeschnittenen“ Verschlüsselung, und wenn wir nicht erraten haben, werden wir die Daten tatsächlich „noch mehr verschlüsseln“, was nur zu einer Reduzierung führt oben erwähnte Abhängigkeit zwischen Blöcken (der Unterschied besteht in einigen festen Positionen). Mit anderen Worten: Wenn sich unter den Ergebnissen einer solchen „zusätzlichen Verarbeitung“ von Chiffretexten eine ganze Reihe von Paaren befanden, die sich in den uns bekannten festen Positionen unterscheiden, bedeutet dies, dass wir die erforderlichen Schlüsselbits erraten haben. Ansonsten wird es deutlich weniger solcher Paare geben. Da in jeder Runde nur ein Teil des Schlüssels verwendet wird, sind die gesuchten Bits (d. h. die in der letzten Runde verwendeten Schlüsselbits) nicht so zahlreich wie die Bits im vollständigen Schlüssel und können einfach durch Wiederholen der obigen Schritte wiederholt werden . In diesem Fall werden wir sicherlich eines Tages auf die richtige Bedeutung stoßen.

Aus der obigen Beschreibung folgt, dass das Wichtigste bei der Differentialanalysemethode die Anzahl genau jener Positionen in Klartexten und Chiffretexten ist, deren Unterschiede eine Schlüsselrolle bei der Wiederherstellung der Schlüsselbits spielen. Das grundsätzliche Vorhandensein dieser Positionen sowie die Menge ihrer Zahlen hängt direkt von den Eigenschaften der nichtlinearen Transformationen ab, die in jeder Blockchiffre verwendet werden (normalerweise ist die gesamte „Nichtlinearität“ in den sogenannten S-Boxen konzentriert). Ersatzknoten).

Courtois verwendet eine leicht modifizierte Version der Differentialmethode. Wir stellen sofort fest, dass Courtois seine Analyse für S-Boxen durchführt, die sich von den aktuellen und den in der ISO vorgeschlagenen unterscheiden. Die Arbeit liefert differenzielle Merkmale (die Zahlen, in denen sich die Blöcke unterscheiden sollten) für eine kleine Anzahl von Runden. Die Begründung für die Ausweitung der Eigenschaften auf weitere Runden basiert wie üblich auf „Fakten“. Courtois äußert wiederum, mit nichts anderem als seiner Autorität, eine unbestätigte Annahme, dass eine Änderung der S-Boxen die Widerstandsfähigkeit von GOST 28147-89 gegen seinen Angriff nicht beeinträchtigen wird (während aus unbekannten Gründen die S-Boxen aus dem 1. Arbeitsentwurf von die Ergänzung der Norm ISO/IEC 18033-3 wurde nicht berücksichtigt). Die von den Autoren des Artikels durchgeführte Analyse zeigt, dass selbst wenn wir Courtois‘ unbegründete „Fakten“ zum Glauben heranziehen und GOST 28147-89 mit anderen S-Blöcken analysieren, der Angriff wiederum nicht besser ist als eine vollständige Durchsuchung.

Eine detaillierte Analyse der Werke von Courtois mit einer detaillierten Begründung der Unbegründetheit aller Aussagen über die Abnahme des Widerstands des russischen Standards wurde in den Werken [,] durchgeführt.

Gleichzeitig gibt sogar Courtois selbst die absolute Ungenauigkeit der Berechnungen zu! Die folgende Folie stammt aus Courtois‘ Präsentation im Kurzmitteilungsteil der FSE 2012.

Anzumerken ist, dass die Arbeit von Courtois auch von ausländischen Forschern immer wieder kritisiert wurde. Beispielsweise enthielt seine Arbeit zur Konstruktion von Angriffen auf den AES-Blockverschlüsselungsalgorithmus mithilfe der XSL-Methode die gleichen grundlegenden Mängel wie die Arbeit zur Analyse des russischen Standards: Die meisten Schätzungen der Arbeitsintensität erscheinen im Text völlig unbegründet und unbegründet – detailliert Kritik findet sich beispielsweise in der Arbeit. Darüber hinaus gibt Courtois selbst zu, dass er sich weit verbreitet weigert, seine Arbeit auf großen Kryptographiekonferenzen und in etablierten Fachzeitschriften zu veröffentlichen, sodass ihm oft nur die Gelegenheit bleibt, im Abschnitt mit kurzen Ankündigungen zu sprechen. Dies können Sie beispielsweise im Abschnitt 3 der Arbeit nachlesen. Hier sind einige Zitate von Courtois selbst zu seiner Arbeit:

• „Ich denke, dass das Publikum von Asiacrypt es nicht interessant finden wird.“ Rezensent von Asiacrypt 2011.
• „… es gibt ein großes, großes, großes Problem: Dieser Angriff, der den Hauptbeitrag des Papiers darstellt, wurde bereits auf der FSE’11 veröffentlicht (es war sogar das beste Papier), …“. Rezensent für Crypto 2011.

Daher betrachtet der professionelle Teil der internationalen kryptografischen Gemeinschaft die Qualität von Courtois‘ Arbeit mit nicht weniger Zweifeln als beispielsweise die Aussagen einiger russischer Spezialisten über ihre Fähigkeit, AES für 2.100 zu knacken, die durch keine konsistenten Berechnungen bestätigt werden, oder die Neuester „Beweis“ einer zweiseitigen Hypothese zur Ungleichheit der Komplexitätsklassen P und NP.

Angriffe von Isobe und Dinur-Dankelman-Shamir

Die allgemeine Idee der Angriffe Isobe () und Dinur-Dankelman-Shamir (im Folgenden: DDS-Angriff) () besteht darin, für eine bestimmte (schlüsselabhängige) enge Menge von Klartexten eine äquivalente Transformation auf dieser Menge zu konstruieren, die eine hat Struktur einfacher als die Verschlüsselungstransformation selbst. Im Fall der Isobe-Methode ist dies die Menge der 64-Bit-Blöcke x, so dass F 8 -1 (Swap(F 8 (z))) = z, wobei z = F 16 (x), bis F 8 ( x) und F 16 ( x) geben die ersten 8 bzw. die ersten 16 Runden der GOST 28147-89-Verschlüsselung durch Swap an – den Vorgang des Vertauschens der Hälften eines 64-Byte-Wortes. Wenn der Klartext in diesem Satz enthalten ist, stimmt das Ergebnis der vollständigen 32-Runden-Transformation von GOST 28147-89 mit dem Ergebnis der 16-Runden-Transformation überein, was der Autor des Angriffs ausnutzt. Im Fall der DDS-Methode ist dies die Menge von x mit F 8 (x) = x (Fixpunkt der Transformation F 8). Für jeden Klartext aus diesem Satz funktioniert die GOST 28147-89-Transformation genauso wie die letzten 8 Runden, was die Analyse vereinfacht.

Die Komplexität des Isobe-Angriffs beträgt 2.224 Verschlüsselungsoperationen, der DDS-Angriff beträgt 2.192. Alle Fragen dazu, ob die Isobe- und DDS-Angriffe neue Einschränkungen für die Bedingungen für die Verwendung unseres Algorithmus mit sich bringen, werden jedoch durch die Bewertung der Anforderungen an das Materialvolumen beseitigt, das für die Durchführung jedes der Angriffe erforderlich ist: Die Isobe-Methode erfordert 2 32 Klartextpaare und Chiffretext und für die DDS-Methode - 2 64. Die Verarbeitung solcher Materialmengen ohne Änderung des Schlüssels ist für jede Blockchiffre mit einer Blocklänge von 64 von vornherein inakzeptabel: auf Material der Menge 2 32 , unter Berücksichtigung der Geburtstagsproblematik (siehe z. B. ), die Eintrittswahrscheinlichkeit Die Anzahl der wiederholten Blöcke beträgt nahezu 1/2, was es dem Angreifer ermöglicht, aus den Chiffretexten bestimmte Rückschlüsse auf die Klartexte zu ziehen, ohne den Schlüssel zu ermitteln. Das Vorhandensein von 2 64 Paaren unverschlüsselter und verschlüsselter Texte, die auf einem Schlüssel erhalten wurden, ermöglicht es dem Feind tatsächlich, Verschlüsselungs- und Entschlüsselungsvorgänge durchzuführen, ohne diesen Schlüssel überhaupt zu kennen. Dies ist auf eine rein kombinatorische Eigenschaft zurückzuführen: Der Feind verfügt in diesem Fall über die gesamte Verschlüsselungskonvertierungstabelle. Diese Situation ist unter vernünftigen Betriebsbedingungen absolut inakzeptabel. Beispielsweise gibt es in CryptoPro CSP eine technische Begrenzung des Volumens des verschlüsselten Materials (ohne Schlüsselkonvertierung) von 4 MB (siehe). Daher ist die Verwendung eines Schlüssels für Material dieses Umfangs in jeder Blockchiffre mit einer Blocklänge von 64 Bit strikt verboten, und daher schränken Isobe- und DDS-Angriffe den Anwendungsbereich des GOST 28147-89-Algorithmus in keiner Weise ein unter Beibehaltung der maximal möglichen Stärke von 2.256.

Natürlich ist zu beachten, dass Forscher (Isobe und Dinur-Dankelman-Shamir) gezeigt haben, dass einige Eigenschaften des GOST 28147-89-Algorithmus es ermöglichen, Analysepfade zu finden, die von den Erstellern des Algorithmus nicht berücksichtigt wurden. Die einfache Form des Schlüsselplans, die die Erstellung effektiver Implementierungen erheblich vereinfacht, ermöglicht in einigen seltenen Fällen von Schlüsseln und Klartexten auch die Erstellung einfacherer Beschreibungen der vom Algorithmus erzeugten Transformationen.

Die Arbeit zeigt, dass diese negative Eigenschaft des Algorithmus unter vollständiger Beibehaltung der Betriebseigenschaften leicht beseitigt werden kann, aber leider ist sie ein integraler Bestandteil des Algorithmus in seiner häufig verwendeten Form.

Beachten Sie, dass auch in der Arbeit von Dinur, Dunkelman und Shamir eine gewisse Nachlässigkeit bei den Schätzungen der durchschnittlichen Arbeitsintensität vorhanden ist. Daher wird bei der Konstruktion eines Angriffs folgender Punkt nicht gebührend berücksichtigt: Für einen erheblichen Teil der Schlüssel ist die Menge der Klartexte x, so dass F 8 (x) = x, leer: Es kann einfach keine Fixpunkte geben für 8 Transformationsrunden. Die Existenz von Fixpunkten hängt auch von der Wahl der Ersatzknoten ab. Daher ist der Angriff nur für bestimmte Ersatzknoten und -schlüssel anwendbar.

Erwähnenswert ist auch ein weiteres Werk mit einem Angriff auf GOST 28147-89. Im Februar 2012 erschien im elektronischen Archiv ePrint der International Cryptographic Association eine aktualisierte Version des Artikels (vom November 2011), die einen neuen Angriff auf GOST 28147-89 enthielt. Die Merkmale des vorgestellten Angriffs sind wie folgt: Das Materialvolumen beträgt 2 32 (wie bei Isobe) und die Arbeitsintensität beträgt 2 192 (wie bei DDS). Somit verbesserte dieser Angriff den Zeitrekord-DDS-Angriff hinsichtlich des Materialvolumens von 2,64 auf 2,32. Wir weisen gesondert darauf hin, dass die Autoren alle Berechnungen ehrlich dargelegt und die Komplexität und den Umfang des Materials begründet haben. Nach 9 Monaten wurde ein grundlegender Fehler in den oben genannten Berechnungen festgestellt und seit November 2012 enthält die aktualisierte Version des Artikels im elektronischen Archiv keine Ergebnisse mehr zum inländischen Algorithmus.

Angriffe gehen davon aus, dass der Angreifer „etwas“ über die Schlüssel weiß

Abschließend sei darauf hingewiesen, dass es in der Literatur auch eine Reihe von Arbeiten gibt (siehe zum Beispiel und ), die sich mit Angriffen auf GOST 28147-89 im sogenannten Linked-Key-Modell befassen. Dieses Modell geht grundsätzlich davon aus, dass ein Angreifer nicht nur Paare aus offenen Texten, die mit dem gewünschten Schlüssel verschlüsselt wurden, zur Analyse erhalten kann, sondern auch Paare aus offenen und verschlüsselten Texten, die er mit (ebenfalls unbekannten) Schlüsseln erhalten hat, die vom gewünschten Schlüssel abweichen auf bekannte reguläre Weise (z. B. in festen Bitpositionen). In diesem Modell ist es zwar möglich, interessante Ergebnisse zu GOST 28147-89 zu erhalten, aber in diesem Modell ist es möglich, nicht weniger starke Ergebnisse beispielsweise über den AES-Standard zu erhalten, der in modernen öffentlichen Netzwerken am weitesten verbreitet ist ( siehe zum Beispiel). Beachten Sie, dass die Bedingungen für die Durchführung dieser Art von Angriff entstehen, wenn eine Chiffre in einem bestimmten Protokoll verwendet wird. Es ist anzumerken, dass Ergebnisse dieser Art, obwohl sie im Hinblick auf die Untersuchung der Eigenschaften kryptografischer Transformationen zweifellos von akademischem Interesse sind, für die Praxis tatsächlich nicht relevant sind. Beispielsweise erfüllen alle vom FSB Russlands zertifizierten Tools zum Schutz kryptografischer Informationen die strengsten Anforderungen für Schemata zur Generierung von Verschlüsselungsschlüsseln (siehe beispielsweise). Wie aus den Ergebnissen der Analyse hervorgeht, beträgt die Komplexität des vollständigen Öffnens des privaten Schlüssels mit einer Erfolgswahrscheinlichkeit von 1-10 -4 bei 18 zugehörigen Schlüsseln und 2 10 Paaren aus Klartext- und Chiffretextblöcken tatsächlich 2 26 . Wenn jedoch die oben genannten Voraussetzungen für die Entwicklung von Schlüsselmaterial erfüllt sind, beträgt die Wahrscheinlichkeit, solche Schlüssel zu finden, 2 -4352, also 24096 Mal weniger, als wenn man einfach beim ersten Versuch versucht, den geheimen Schlüssel zu erraten.

Zu den Werken, die sich auf das Modell mit verknüpften Tasten beziehen, gehören auch Arbeiten, die 2010 in russischen elektronischen Publikationen für viel Aufsehen sorgten, die nicht unter der Angewohnheit leiden, das Material im Wettlauf um Sensationen sorgfältig zu prüfen. Die darin präsentierten Ergebnisse wurden nicht durch eine strenge Begründung gestützt, sondern enthielten laute Aussagen über die Fähigkeit, den Staatsstandard der Russischen Föderation in Sekundenschnelle auf einem schwachen Laptop zu hacken – im Allgemeinen wurde der Artikel in bester Tradition verfasst von Nicolas Courtois. Aber trotz der absolut offensichtlichen Unbegründetheit des Artikels für den Leser, der mit den Grundprinzipien wissenschaftlicher Veröffentlichungen mehr oder weniger vertraut ist, schrieb Rudsky gerade um die russische Öffentlichkeit nach der Arbeit zu beruhigen, einen detaillierten und gründlichen Text mit einer umfassenden Analyse von diesem Mangel. Der Artikel mit dem selbsterklärenden Titel „Über die praktische Nullbedeutung der Arbeit „Key Recovery Attack on Full GOST Block Cipher with Zero Time and Memory““ begründet, dass die durchschnittliche Komplexität der angegebenen Methode nicht geringer ist als die Komplexität einer vollständigen Suche.

Trockenrückstände: Was ist Haltbarkeit in der Praxis?

Abschließend präsentieren wir eine Tabelle mit Daten zu allen Ergebnissen streng beschriebener und gerechtfertigter Angriffe auf GOST 28147-89, die der internationalen kryptografischen Gemeinschaft bekannt sind. Beachten Sie, dass die Komplexität in den Verschlüsselungsoperationen des GOST 28147-89-Algorithmus angegeben ist und der Speicher und das Material in Algorithmusblöcken (64 Bit = 8 Byte) angegeben werden.

Trotz eines relativ umfangreichen Forschungszyklus im Bereich der Resistenz des GOST 28147-89-Algorithmus ist derzeit kein einziger Angriff bekannt, dessen Umsetzungsbedingungen mit den damit verbundenen betrieblichen Anforderungen für a erreichbar wären Blocklänge von 64 Bit. Die aus den Chiffrierparametern (Schlüsselbitlänge, Blockbitlänge) resultierenden Einschränkungen hinsichtlich der Menge an Material, die auf einem Schlüssel verarbeitet werden kann, sind deutlich strenger als das Mindestvolumen, das zur Durchführung eines derzeit bekannten Angriffs erforderlich ist. Folglich ermöglicht keine der bisher in GOST 28147-89 vorgeschlagenen Methoden der Kryptoanalyse die Bestimmung eines Schlüssels mit einem geringeren Arbeitsaufwand als einer erschöpfenden Suche, wenn die bestehenden betrieblichen Anforderungen erfüllt werden.

Der allgemein bekannte Begriff „Prozessorleistung“ ist ein objektiver, berechneter Parameter, der in Flops gemessen wird. Die meisten Menschen messen es jedoch in Gigahertz und glauben naiv, dass es sich dabei um dasselbe handelt. Niemand kennt den Begriff „Code-Performance“, und ich werde gleich erklären, warum.

Der Grund dafür ist, dass ich erst kürzlich darauf gekommen bin und noch niemandem davon erzählt habe. Allerdings verfügt die Codeleistung ebenso wie die Prozessorleistung über objektive Merkmale, die gemessen werden können. In diesem Artikel geht es speziell um die Leistung des vom Prozessorkern ausgeführten Codes.

Wie wird die Codeleistung gemessen? Da ich der Erste war, der darüber gesprochen hat, werde ich es im Namen des Entdeckers in RTT-Einheiten messen;).

Jetzt im Ernst. In modernen Prozessoren sind die wichtigsten Transformationen Operationen mit 32-Bit-Zahlen; alles andere ist im Großen und Ganzen exotisch. Daher berücksichtigen wir die Hauptsache – Operationen mit 32-Bit-Zahlen. Wie viele 32-Bit-Operationen kann ein moderner Prozessorkern Ihrer Meinung nach gleichzeitig ausführen?

Der Schüler wird antworten – eins, sein Lehrer wird denken und sagen, dass es vier sind, der Profi – dass es bisher nur zwölf Operationen gibt.

Ein Programmcode, der über die gesamte Ausführungszeit des Codes alle Prozessorausführungseinheiten gleichzeitig lädt, hat also eine Leistung von 12 RTTs. Maximal! Ehrlich gesagt habe ich noch nie einen solchen Code geschrieben, aber in diesem Artikel werde ich versuchen, mich darum zu bemühen.

Ich werde beweisen, dass Code mit gleichzeitiger Ausführung von zwölf 32-Bit-Operationen möglich ist

Programmcode, der einen Aktuator im Prozessorkern verwendet, hat natürlich eine Leistung von 1 RTT. Programme, die von Hochsprachen-Compilern und Interpretern virtueller Maschinen generiert wurden, können sich einer solchen Codeleistung rühmen. Es muss nicht davon ausgegangen werden, dass die Prozessorlastanzeige, die im Task-Manager des Betriebssystems angezeigt wird, als objektives Kriterium für die Effizienz des Codes dienen kann. Die Auslastung des Prozessorkerns kann 100 % betragen, der Programmcode verwendet jedoch eine Ausführungseinheit darin (Leistung 1 RTT). In diesem Fall arbeitet der Prozessorkern bei 100 % Auslastung mit 1/12 seiner maximalen Leistung. Mit anderen Worten: Wenn der Windows-Task-Manager die maximale Prozessorlast anzeigt, kann die tatsächliche Leistung zwischen 1 und 12 RTT variieren. Wenn Sie im Leistungsfenster eine 100-prozentige Auslastung eines Prozessorkerns sehen, ist es falsch anzunehmen, dass alle Aktoren in diesem Kern arbeiten, überhaupt nicht!

Das einzige Kriterium zur indirekten Beurteilung des Betriebs eines Prozessorkerns bei maximaler Leistung kann dessen Stromverbrauch und damit einhergehend die Geräuschentwicklung des Kühlers sein. Wenn der Kühler nun laut ist, dann ist die Belastung ja auf Maximum gestiegen. Es ist jedoch an der Zeit, mit den allgemeinen Konzepten abzuschließen und mit der harten Praxis fortzufahren.

Traditionelle Umsetzung von GOST 28147-89

Ich bin kein Profi auf dem Gebiet der Informationssicherheit, kenne mich aber dennoch mit dem Thema Verschlüsselung aus. Inspiriert wurde ich durch Gespräche mit einem professionellen Kryptographen, den ich zutiefst respektiere, zum Studium der symmetrischen Stream-Verschlüsselung. Und nachdem ich mich mit diesem Thema beschäftigt hatte, versuchte ich, es gut zu machen, und zwar nicht nur gut, sondern auch schnell, indem ich die maximale Anzahl an Operationen pro Zeiteinheit ausführte. Mit anderen Worten, ich stand vor der Aufgabe, Programmcode mit dem maximalen RTT-Wert zu schreiben.

Die kryptografische Transformation gemäß GOST 28147-89 wird zur Stream-Verschlüsselung von Informationen in Kommunikationskanälen und auf Festplatten verwendet.

Derzeit ist die Softwareimplementierung dieses GOST auf dem RON des Zentralprozessors weit verbreitet. Bei bekannten Methoden zur Implementierung von GOST befinden sich alle geheimen Informationen (Verschlüsselungsschlüssel, Ersatzblöcke) im RAM. Dies verringert die Zuverlässigkeit der Verschlüsselung, da ein RAM-Speicherauszug alle geheimen Elemente der Kryptotransformation vollständig offenlegen kann. Darüber hinaus weist die Methode Leistungseinschränkungen aufgrund der Position der wichtigsten Krypto-Konvertierungsobjekte im OP und des unvollständigen Ladens der ALU-Ausführungseinheiten auf. Moderne Prozessoren, die das Kryptoverfahren nach einem bekannten Verfahren umsetzen, können Verschlüsselungsgeschwindigkeiten von 40–60 Megabyte pro Sekunde ermöglichen. Und wenn wir es wirklich bis zum Ende verstehen, liegt der Grund für die geringe Leistung und schwache Sicherheit der Kryptokonvertierung in der Softwareimplementierung des Substitutionsblocks. Die Beschreibung in GOST finden Sie in Abb. 1.

Gemäß Abschnitt 1.2 von GOST implementiert dieser Block Tetraden-Permutationen (vier Bits) in einem 32-Bit-Wort, aber die x86/64-Prozessorarchitektur und ihr Befehlssystem sind nicht in der Lage, Tetraden effektiv zu manipulieren.

Für die Softwareimplementierung des Substitutionsblocks werden spezielle Tabellen im RAM verwendet, die in der Phase der Initialisierung der Kryptofunktion erstellt werden. Diese Tabellen kombinieren die Ersatzknoten benachbarter Tetraden in 8 × 8-Bit-Byte-Tabellen und platzieren so vier 256-Byte-Tabellen im RAM.

In fortgeschritteneren Implementierungen haben diese Tabellen eine Größe von 1024 Byte (256 Wörter à vier Byte). Dies geschah, um in den Tabellen eine zusätzliche zyklische Verschiebung um 11 Positionen des durch die Substitution erhaltenen 32-Bit-Wortes (die nächste Operation des Konvertierungsalgorithmus nach GOST) zu implementieren. Ein Beispiel für die GOST-Implementierung mit dieser Methode ist in Anhang 1 (auf Datenträger) dargestellt.

Die Informationen des Substitutionsblocks sind ein geheimer Bestandteil der Kryptofunktion (wie in GOST formuliert, siehe Abb. 2).

Die Platzierung dieser Tabellen mit den Schlüsseln des Substitutionsblocks im OP widerspricht den Anforderungen von GOST (Absatz 1.7), da geheime Informationen für Programme von Drittanbietern verfügbar werden, die auf der Computerinstallation ausgeführt werden. Der FSB, der auch Software-Implementierungen der Verschlüsselung nach GOST zertifiziert, betrachtet diesen Verstoß gelinde gesagt herablassend. Wenn der FSB zum Platzieren von Schlüsseln im OP noch ein „Feigenblatt“ benötigt – die Maskierung der Schlüssel mithilfe der XOR-Operation, dann ist für Ersatzblöcke im OP nichts erforderlich; sie werden in klarer Form gespeichert.

Kurz gesagt, der FSB lässt solche Softwareimplementierungen von Kryptoverfahren zu, trotz der offensichtlichen Verringerung der Sicherheit einer solchen Lösung und eines direkten Verstoßes gegen seine eigenen Anforderungen gemäß GOST (Absatz 1.7). Und das trotz der bekannten Methoden, Chiffren durch einen Speicherauszug zu knacken ...

Wir werden etwas später auf die Frage der Speicherung von Schlüsseln und Ersatzblöcken in internen Registern des Prozessors zurückkommen (es gibt eine schöne und schnelle Lösung), aber vorerst werden wir Verschlüsselungsschlüssel nur in MMX-Registern speichern, das ist zuverlässiger.

Aber genug der Texte, wichtig für das betrachtete Thema ist, dass dieser Programmcode eine Leistung von 1 RTT hat. Schreiben wir nun Code mit der Leistung von 2 RTTs.

Multithread-Implementierung von GOST 28147-89

Die einzige Möglichkeit, Kryptovorgänge im bekannten Algorithmus zu beschleunigen, ist die Einführung von Multithreading. Der Sinn dieser Änderung in der Implementierung des Algorithmus besteht darin, mehrere Datenblöcke parallel zu berechnen.

Unter Parallelverarbeitung verstehen die meisten Programmierer ausschließlich die Arbeit mehrerer Prozessorkerne, synchronisiert durch Interrupts und Semaphoren im Speicher.

Es gibt jedoch noch eine andere Möglichkeit der parallelen Datenverarbeitung auf einem einzelnen Prozessorkern. Lassen Sie mich diese nicht offensichtliche Idee erklären.

Moderne Prozessoren umfassen mindestens zwei, sogar drei bis sechs arithmetisch-logische Einheiten. Diese ALUs (FPUs, Adress-Recheneinheiten usw.) können unabhängig voneinander arbeiten; die einzige Bedingung für ihren parallelen Betrieb ist, dass die Softwareobjekte, auf denen sie arbeiten, disjunkt sind. Mit anderen Worten: Bei Befehlen, die gleichzeitig eine ALU ausführen, müssen die Speicheradressen und Registernummern unterschiedlich sein. Oder es sollten keine Schreibvorgänge in gemeinsam genutzte Register und Speicheradressen durchgeführt werden, auf die verschiedene Prozessorausführungseinheiten zugreifen.

Die Arbeitslast aller ALUs wird von einer speziellen Hardwareeinheit im Prozessorkern gesteuert – dem Scheduler, der den ausführbaren Code bis zu einer Tiefe von 32–64 Byte vorwärts scannt. Wenn der Scheduler Anweisungen erkennt, die ohne Konflikte auf der ALU ausgeführt werden können, führt er sie gleichzeitig auf verschiedenen Ausführungsgeräten aus. In diesem Fall zeigt der Zähler der ausgeführten Befehle den ausführenden Befehl an (in einem solchen Schema gibt es mehrere davon), wonach alle Befehle bereits ausgeführt wurden.

Die meisten automatisch (durch Compiler) generierten Programmabläufe können nicht alle im Prozessorkern befindlichen ALUs und FPUs laden. In diesem Fall befindet sich die Prozessorhardware im Leerlauf, was die resultierende Leistung deutlich reduziert. Prozessorentwickler sind sich dessen bewusst und führen Modi ein, um die Kernfrequenz zu erhöhen, wenn die Hardware nicht vollständig ausgelastet ist. Dafür sind auch Hypertrading-Systeme konzipiert, und ich werde dieses System in Zukunft nutzen, um den Code auf das Maximum zu „pressen“.

Compiler, selbst die am besten optimierten, und noch mehr virtuelle Maschinen-Engines können keinen hinsichtlich der Leistung optimierten Code generieren. Nur ein Programmierer mit technischen Kenntnissen kann solch optimierten Code schreiben, und das Werkzeug zum Schreiben ist ausschließlich Assembler.

Ein typisches Beispiel für die Möglichkeit, mehrere unabhängige Programmthreads auf einem Prozessorkern auszuführen, ist die GOST-Implementierung, die in zwei Threads auf einem einzigen Prozessorkern ausgeführt wird. Die Idee des Codes ist einfach: Es gibt zwei Datenblöcke zum Verschlüsseln/Entschlüsseln, aber einen Prozessorkern, der die Konvertierung durchführt. Es ist möglich, die Konvertierung dieser beiden Datenblöcke nacheinander durchzuführen, und dies wird bis heute durchgeführt. In diesem Fall verdoppelt sich die Zeit, die zum Abschluss der Transformationen benötigt wird.

Sie können es aber auch anders machen: alternative Befehle, die sich auf die Verarbeitung verschiedener Datenblöcke beziehen. Diese Möglichkeiten sind in Abb. grafisch dargestellt. 3.

In der Abbildung zeigt das obere Beispiel die übliche Reihenfolge der Verarbeitung zweier unabhängiger Datenblöcke. Zuerst wird der erste Block verarbeitet, dann fährt der Prozessor mit der Verarbeitung des zweiten Blocks fort. Natürlich entspricht die resultierende Zeit dem Doppelten der Zeit, die zur Verarbeitung eines Blocks benötigt wird, und die Aktuatoren des Prozessorkerns sind nicht vollständig ausgelastet.

Das Folgende ist ein Beispiel für die Verschachtelung von Befehlen aus verschiedenen Verarbeitungsthreads. In diesem Fall werden Befehle, die sich auf verschiedene Datenblöcke beziehen, verschachtelt. Der Scheduler wählt voneinander unabhängige Anweisungen aus und übermittelt sie zur Ausführung an ALU1 und ALU2. Die Gruppierung der Befehle des ersten und zweiten Threads auf diesen ALUs erfolgt automatisch, da der Betriebsalgorithmus des Schedulers eine Gruppierung von Befehlen umfasst, die mit gemeinsamen Daten auf demselben ausführenden Gerät verknüpft sind.

Damit ein solcher Programmcode ohne ALU-Ausfallzeit funktioniert, ist es notwendig, dass jeder Programmthread mit seinem eigenen Registersatz arbeitet. Der Cache wird in diesem Schema zu einem Engpass (er verfügt nur über zwei Datenausgabeports), daher speichern wir die Schlüssel in MMX-Registern. Da in diesem Fall die Ersetzungs- (und Verschiebungs-)Knoten im Speicher nur gelesen werden, können sie beiden Programm-Threads gemeinsam sein.

Dies ist natürlich eine sehr vereinfachte Erklärung des Prinzips der parallelen Ausführung von Programm-Threads auf einem einzelnen Kern; in Wirklichkeit ist alles viel komplizierter. In der Praxis müssen Sie die Pipeline-Architektur von Aktoren, Einschränkungen beim gleichzeitigen Zugriff auf den Cache und den RON-Registerblock, das Vorhandensein von Adressarithmetikknoten, Schaltern und vieles mehr berücksichtigen ... Dies ist also ein Thema für Profis, der sich an den Fingern einer Hand abzählen lässt.

Das parallele Verschlüsselungsverfahren wird effektiv nur für den 64-Bit-Prozessorbetriebsmodus implementiert, da in diesem Modus eine ausreichende Anzahl von RON vorhanden ist (bis zu 16 Stück!). Ein Beispiel für die GOST-Implementierung mit dieser Methode ist in Anhang 2 (auf Datenträger) dargestellt.

Es ist klar, dass diese GOST-Implementierung eine Codeleistung von 2 RTT-Codes hat. Sehen wir uns nun an, wie sich dies auf die Ausführungszeit auswirkt.

Der Verschlüsselungszyklus für einen Thread (Anhang 1) beträgt 352 Taktzyklen, und in dieser Zeit werden 8 Byte Daten berechnet; für eine Zwei-Thread-Implementierung von GOST (Anhang 2) sind 416 Prozessorzyklen erforderlich, es werden jedoch 16 Byte berechnet. Dadurch erhöht sich die resultierende Konvertierungsgeschwindigkeit von 80 auf 144 Megabyte bei einem 3,6-GHz-Prozessor.

Es ergibt sich ein interessantes Bild: Der Code enthält genau doppelt so viele Befehle und führt nur 15 % länger aus, aber ich denke, die Leser haben den Grund für dieses Phänomen bereits verstanden ...

Theoretisch sollte der Code aus dem zweiten Beispiel in der gleichen Anzahl von Zyklen ausgeführt werden wie der Code aus dem ersten Beispiel, aber der Scheduler-Knoten wurde von Intel-Ingenieuren entwickelt, aber sie sind auch Menschen und wir sind alle alles andere als perfekt. So ist es möglich, die Wirksamkeit ihrer Erstellung zu bewerten. Dieser Code läuft auch auf einem AMD-Prozessor und Sie können die Ergebnisse vergleichen.

Falls mir das jemand nicht glauben kann: Für solche Ungläubigen sind auf der Diskette Testprogramme mit Taktzählern enthalten. Die Programme liegen im Quellcode vor, natürlich in Assembler, so dass ich die Möglichkeit habe, meine Worte zu überprüfen und gleichzeitig einige Tricks des professionellen Programmierens kennenzulernen.

Verwendung von SSE-Registern und AVX-Befehlen moderner Prozessoren zur Implementierung von GOST 28147-89

Moderne Prozessoren der x86/64-Architektur umfassen einen Satz SSE-Register mit einer Größe von 16 Byte und spezialisierte FPUs (mindestens zwei), um verschiedene Operationen an diesen Registern durchzuführen. Es ist möglich, GOST auf diesem Gerät zu implementieren, und in diesem Fall können Ersatzknoten nicht in Form von Tabellen im RAM, sondern direkt in dedizierten SSE-Registern platziert werden.

Ein SSE-Register kann zwei Tabellen mit 16 Zeilen gleichzeitig aufnehmen. Somit werden vier SSE-Register alle Ersetzungstabellen vollständig aufnehmen. Die einzige Bedingung für eine solche Platzierung ist die Interleaving-Anforderung, wonach Tetraden desselben Bytes in verschiedenen SSE-Registern platziert werden müssen. Darüber hinaus empfiehlt es sich, die Low- und High-Tetraden der Eingangsbytes jeweils in den Low- und High-Tetraden der Bytes der SSE-Register zu platzieren.

Diese Anforderungen werden durch Optimierung für den vorhandenen Satz von AVX-Befehlen bestimmt. Somit enthält jedes Byte des SSE-Registers zwei Tetraden, die unterschiedlichen Bytes des Eingaberegisters des Substitutionsblocks entsprechen, während die Position des Bytes im SSE-Register eindeutig dem Index in der Substitutionsblock-Substitutionstabelle entspricht.

Ein Diagramm einer der möglichen Platzierungen von Ersatzknoten in SSE-Registern ist in Abb. dargestellt. 4.

Das Platzieren geheimer Informationen von Ersatzknoten in SSE-Registern erhöht die Sicherheit des Kryptoverfahrens, eine vollständige Isolierung dieser geheimen Informationen ist jedoch möglich, wenn die folgenden Bedingungen erfüllt sind:

• Der Prozessorkern wird in den Hypervisor-Host-Modus geschaltet und der Interrupt-Block (APIC) wird darin zwangsweise deaktiviert. In diesem Fall ist der Prozessorkern vollständig vom Betriebssystem und den Anwendungen isoliert, die auf der Computerinstallation ausgeführt werden.
• SSE-Register werden geladen und der Rechenkern wird vor dem Start des Betriebssystems isoliert; es ist optimal, diese Vorgänge vom Trusted Boot Module (TLM) aus durchzuführen.
• Programme für Kryptoverfahren nach GOST befinden sich in einem nicht veränderbaren Speicherbereich der Rechenanlage (entweder im BIOS oder im Flash-Speicher des MDZ).

Die Einhaltung dieser Anforderungen gewährleistet eine vollständige Isolierung und Unveränderlichkeit des Programmcodes von Kryptoverfahren und der darin verwendeten geheimen Informationen.

Für eine effiziente Abtastung von Tetrad-SSE-Registern werden die in den FPU-Blöcken enthaltenen Multi-Input-Byte-Schalter verwendet. Diese Schalter ermöglichen Übertragungen von jedem Quellbyte zu jedem Zielbyte unter Verwendung von Indizes, die sich in einem speziellen SSE-Indexregister befinden. Darüber hinaus erfolgt die Übertragung parallel für alle 16 Bytes des SSE-Empfängerregisters.

Mit Substitutionsspeicherknoten in SSE-Registern und einem Multi-Input-Switch in FPU-Blöcken ist es möglich, die folgende Transformation im Substitutionsblock zu organisieren (Abb. 5).

Bei diesem Schema gibt das Eingangsregister in jeder Tetrade die Adresse für den entsprechenden Schalter an, der Informationen von den Antrieben der Ersatzknoten über den Datenbus an das Ausgangsregister überträgt. Dieses Schema kann auf drei Arten organisiert werden:

• Erstellen Sie ein passendes Chip-Design, aber das ist fantastisch für uns.
• Den Mikrocode neu zu programmieren und einen eigenen Prozessorbefehl zu erstellen, um diese Funktion auf vorhandenen Prozessoren zu implementieren, ist keine Fantasie mehr, aber unter den gegenwärtigen Bedingungen leider unrealistisch.
• Schreiben Sie ein Programm mit offiziellen AVX-Befehlen. Die Option ist möglicherweise nicht sehr effektiv, kann aber „hier und jetzt“ umgesetzt werden. Das ist also, was wir als nächstes tun werden.

Der Betrieb von Schaltern wird durch einen speziellen Drei-Adressen-Befehl AVX VPSHUFB gesteuert. Sein erster Operand ist der Empfänger der Informationen von den Schaltern, der zweite ist die Quelle, mit der die Eingänge der Schalter verbunden sind. Der dritte Operand ist ein Steuerregister für Schalter, wobei jedes Byte einem entsprechenden Schalter zugeordnet ist; Der darin enthaltene Wert gibt die Nummer der Richtung an, aus der der Schalter Informationen liest. Eine Beschreibung dieses Befehls aus der offiziellen Intel-Dokumentation finden Sie in Abb. 5. In Abb. Abbildung 6 zeigt ein Diagramm, wie dieser Befehl funktioniert – nur die Hälfte der SSE-Register wird angezeigt, für die zweite Hälfte ist alles ähnlich.

Der Schalter verwendet nur die niedrigsten vier Bits, um die Kommutierungsrichtung zu bestimmen, das letzte Bit in jedem Byte wird verwendet, um das entsprechende Empfängerbyte auf Null zu zwingen, aber diese Schalterfunktion ist in unserem Fall noch nicht gefragt.

Es wurde ein Programm zum Abtasten von Tetraden über FPU-Schalter geschrieben, aber ich habe es nicht einmal in die Anwendung eingefügt – es ist zu erbärmlich. Ein 128-Bit-Register zu haben und darin nur 32 Bit zu verwenden, ist unprofessionell.

Wie sie sagen: „Unsere Ziellinie ist der Horizont“, also drücken Sie es aus, drücken Sie es aus ... wir drücken es aus und packen es in Tüten!

Dies ist kein Wortspiel, sondern eine harte FPU-Realität – SSE-Register können in gleiche Teile geteilt werden und die gleichen Transformationen können an diesen Teilen mit einem Befehl durchgeführt werden. Damit der Prozessor dies versteht, gibt es einen magischen Buchstaben „P“ – ein Paket, das vor der Befehlsmnemonik platziert wird, und nicht weniger magische Buchstaben „Q“, „D“, „W“, „B“, die werden am Ende platziert und deklarieren. In welche Teile werden die SSE-Register in diesem Befehl unterteilt?

Wir interessieren uns für den Batch-Modus, bei dem das SSE-Register in vier 32-Bit-Blöcke unterteilt ist; Dementsprechend wird allen Befehlen ein „P“ vorangestellt und am Ende das Symbol „D“. Dadurch ist es möglich, mit einem Prozessorbefehl vier 32-Bit-Blöcke parallel zu verarbeiten, also vier Datenblöcke parallel zu berechnen.

Das Programm, das diese Methode implementiert, finden Sie in Anhang 3 mit allen Erläuterungen dort.

Drücken Sie jedoch so viel! Moderne Prozessoren verfügen über mindestens zwei FPUs und können über zwei unabhängige Befehlsthreads vollständig geladen werden. Wenn Sie Befehle von unabhängigen Threads korrekt abwechseln, können Sie beide FPU-Blöcke vollständig mit Arbeit beladen und acht parallel verarbeitete Datenströme gleichzeitig erhalten. Ein solches Programm wurde geschrieben und kann in Anhang 4 eingesehen werden, aber Sie müssen es sorgfältig beobachten – Sie können verrückt werden. Das nennt man „Der Code ist nicht jedermanns Sache…“.

Preisproblem

Die Verwendung von SSE-Registern zum Speichern von Ersatzknoten ist verständlich – sie bietet eine gewisse Garantie für die Isolierung geheimer Informationen, aber die Bedeutung der Berechnung der Kryptofunktion selbst auf der FPU ist nicht offensichtlich. Daher wurde die Ausführungszeit von Standardprozeduren mit der direkten Ersetzungsmethode nach GOST für vier und acht Threads gemessen.

Für vier Threads wurde eine Ausführungsgeschwindigkeit von 472 Prozessorzyklen erreicht. Für einen Prozessor mit einer Frequenz von 3,6 GHz wird also ein Thread mit einer Geschwindigkeit von 59 Megabyte pro Sekunde berechnet, bzw. vier Threads mit einer Geschwindigkeit von 236 Megabyte pro Sekunde.

Für acht Threads wurde eine Ausführungsgeschwindigkeit von 580 Prozessorzyklen erreicht. Bei einem 3,6-GHz-Prozessor zählt also ein Thread mit 49 Megabyte pro Sekunde und acht Threads mit 392 Megabyte pro Sekunde.

Wie der Leser sehen kann, hat der Code in Beispiel Nr. 3 eine Leistung von 4 RTT und der Code in Beispiel Nr. 4 hat eine Leistung von 8 RTT. In diesen Beispielen für SSE-Register sind die Muster dieselben wie bei der Verwendung von RON, nur dass der Scheduler seine Effizienz verringert hat. Es bietet derzeit eine Verlängerung der Dauer um 20 % bei gleichzeitiger Verdoppelung der Codelänge.

Darüber hinaus wurden diese Ergebnisse mithilfe universeller AVX-Befehle erzielt, die sowohl in Intel- als auch in AMD-Prozessoren verfügbar sind. Wenn Sie für einen AMD-Prozessor optimieren, wird das Ergebnis deutlich besser sein. Das hört sich zwar gegen den Trend an, ist aber dennoch wahr, und zwar aus folgendem Grund: AMD-Prozessoren verfügen über einen zusätzlichen Befehlssatz, die sogenannte XOP-Erweiterung, und in diesem zusätzlichen Befehlssatz befinden sich solche, die die Implementierung deutlich vereinfachen GOST-Algorithmus.

Dies bezieht sich auf die Befehle zur logischen Burst-Byte-Verschiebung und zur Burst-zyklischen Verschiebung von Doppelwörtern. In den Beispielen in den Anhängen 3 und 4 werden Sequenzen universeller Befehle verwendet, die die notwendige Transformation implementieren: im ersten Fall ein „zusätzlicher“ Befehl und im anderen Fall vier zusätzliche Befehle gleichzeitig. Es gibt also Optimierungsreserven, und zwar erhebliche.

Bei der weiteren Optimierung ist an das Vorhandensein von 256-Bit-Registern (YMM-Registern) zu denken, mit denen sich die Berechnungsgeschwindigkeit theoretisch verdoppeln lässt. Doch das ist vorerst nur eine Prognose; derzeit werden Prozessoren bei der Ausführung von 256-Bit-Befehlen (FPUs haben eine Pfadbreite von 128 Bit) sehr langsam. Experimente haben gezeigt, dass das Zählen von 16 Threads in YMM-Registern auf modernen Prozessoren keinen Vorteil bringt. Aber das ist nur vorerst; auf neuen Prozessormodellen wird die Leistung von 256-Bit-Anweisungen zweifellos gesteigert, und dann wird die Verwendung von 16 parallelen Threads ratsam sein und zu einer noch stärkeren Steigerung der Geschwindigkeit des Kryptoverfahrens führen .

Theoretisch können Sie mit einer Geschwindigkeit von 600–700 Megabyte pro Sekunde rechnen, wenn der Prozessor über zwei FPUs mit einer Arbeitspfadbreite von jeweils 256 Bit verfügt. In diesem Fall können wir davon sprechen, Code mit einer Effizienz von 16 RTT zu schreiben, und das ist keine Fantasie, sondern die nahe Zukunft.

Mischform

Auch hier stellt sich die Frage nach der Anzahl der Register; es gibt nicht genügend davon, um einen solchen Algorithmus zu fördern. Aber der Hypertrading-Modus wird uns helfen. Der Prozessorkern verfügt über einen zweiten Satz Register, der im logischen Prozessormodus verfügbar ist. Daher führen wir denselben Code gleichzeitig auf zwei logischen Prozessoren aus. In diesem Modus werden wir natürlich nicht mehr Aktoren haben, aber durch den Wechsel können wir eine volle Auslastung aller Aktoren erreichen.

Mit einer Steigerung um 50 % kann man hier nicht rechnen; der Flaschenhals ist der Cache-Speicher, in dem die technologischen Masken gespeichert sind, man kann aber immer noch mit einer Steigerung um 100 zusätzliche Megabyte rechnen. Diese Option wird in den Anhängen nicht angezeigt (die Makros ähneln denen im 8 RTT-Code), ist aber in den Programmdateien verfügbar. Wenn also jemand nicht an die Möglichkeit einer Verschlüsselung mit einer Geschwindigkeit von 500 Megabyte pro Sekunde auf einem einzelnen Prozessorkern glaubt, lassen Sie ihn Testdateien ausführen. Es gibt auch Texte mit Kommentaren, damit niemand denkt, ich lüge.

Dieser Fokus ist nur auf Intel-Prozessoren möglich; AMD verfügt nur über zwei FPU-Einheiten pro zwei Prozessormodulen (analog zum Hypertrading-Modus). Aber es gibt noch vier weitere ALUs, deren Nichtbenutzung eine Sünde wäre.

Sie können die Bulldozer-Prozessormodule in einen Modus versetzen, der dem Hypertrading-Modus ähnelt, aber die Konvertierung in RON auf verschiedenen Modulen in einem Thread und auf SSE-Registern in einem anderen Thread ausführen und die gleichen 12 RTTs erhalten. Ich habe diese Option nicht getestet, aber ich denke, dass 12 RTT-Code auf AMD effizienter funktionieren wird. Interessierte können es ausprobieren; Testprogramme lassen sich ganz einfach an „Bulldozer“ anpassen.

Wer braucht es?

Eine ernste Frage, aber mit einer einfachen Antwort – das braucht jeder. Bald werden wir alle von den Clouds abhängig sein, wir werden dort sowohl Daten als auch Programme speichern und dort, oh, wie wollen wir unsere eigene, private Ecke schaffen. Dazu müssen Sie den Datenverkehr verschlüsseln, und die Geschwindigkeit der Kryptokonvertierung wird der wichtigste Faktor für komfortables Arbeiten in der Cloud sein. Unsere Auswahl an Verschlüsselungsalgorithmen ist klein – entweder GOST oder AES.

Darüber hinaus erweist sich der in Prozessoren integrierte AES-Verschlüsselungsalgorithmus seltsamerweise als viel langsamer; Tests zeigen Geschwindigkeiten von 100–150 Megabyte pro Sekunde, und das bei einer Hardware-Implementierung des Algorithmus! Das Problem liegt in der Single-Threaded-Zählung und dem Ersetzungsblock, der mit Bytes arbeitet (eine Tabelle mit 256 Zeilen). GOST erweist sich also als effektiver, wenn es auf einer x86/64-Architektur implementiert wird, wer hätte das gedacht ...

Dies ist der Fall, wenn wir über die erreichte Verschlüsselungsgeschwindigkeit sprechen. Und wenn wir theoretische Verfeinerungen im Bereich der Steigerung der Code-Effizienz im Auge behalten, dann braucht das höchstwahrscheinlich niemand. Es gibt praktisch keine Spezialisten auf der RTT-Ebene 3–6, Compiler generieren im Allgemeinen Code auf der RTT-Ebene 1–2,5, und die meisten Programmierer kennen sich mit Assembler nicht aus, und selbst wenn sie die Schreibweise kennen, verstehen sie das Design nicht ein moderner Prozessor. Und ohne dieses Wissen ist es egal, ob es sich um einen Assembler oder eine Art SI-Sharp handelt.

Aber nicht alles ist so traurig: Das Fazit nach einer Woche schlafloser Nächte ist ein neuer Algorithmus zur Umsetzung von GOST, den es nicht patentieren ließe, wäre eine Sünde. Und Patentanmeldungen (bis zu drei) sind bereits abgeschlossen und eingereicht, also, meine Herren, Geschäftsleute, stellt euch an – Frauen und Kinder erhalten einen Rabatt.

Die Geschichte dieser Chiffre ist viel älter. Der Algorithmus, der später die Grundlage des Standards bildete, wurde vermutlich in den Eingeweiden der Achten Hauptdirektion des KGB der UdSSR (heute innerhalb der Struktur des FSB) geboren, höchstwahrscheinlich in einer der geschlossenen Forschungen nachgeordneten Instituten vermutlich bereits in den 1970er Jahren im Rahmen von Projekten zur Erstellung von Software- und Hardware-Implementierungen der Chiffre für verschiedene Computerplattformen.

Seit der Veröffentlichung von GOST wurde es mit dem restriktiven Stempel „Für den offiziellen Gebrauch“ gekennzeichnet und offiziell wurde die Chiffre erst im Mai 1994 für „vollständig offen“ erklärt. Die Entstehungsgeschichte der Chiffre und die Kriterien der Entwickler wurden bis 2010 nicht veröffentlicht.

Beschreibung

GOST 28147-89 ist eine Blockchiffre mit einem 256-Bit-Schlüssel und 32 Konvertierungszyklen, die mit 64-Bit-Blöcken arbeitet. Die Grundlage des Verschlüsselungsalgorithmus ist das Feistel-Netzwerk. Gemäß GOST 28147-89 gibt es vier Betriebsarten:

• simulierter Einfügemodus.

Einfacher Austauschmodus

Um in diesem Modus zu verschlüsseln, wird der Klartext zunächst in zwei Hälften geteilt (die niedrigstwertigen Bits sind A, die höchstwertigen Bits sind B). Im i-ten Zyklus wird der Unterschlüssel K i verwendet:

( = binär „exklusiv oder“)

Um Unterschlüssel zu generieren, wird der ursprüngliche 256-Bit-Schlüssel in acht 32-Bit-Blöcke unterteilt: K 1 ... K 8 .

Die Tasten K 9 ... K 24 sind eine zyklische Wiederholung der Tasten K 1 ... K 8 (nummeriert vom niedrigstwertigen zum höchsten Bit). Die Tasten K 25...K 32 sind die Tasten K 8...K 1.

Nach Abschluss aller 32 Runden des Algorithmus werden die Blöcke A 33 und B 33 zusammengeklebt (beachten Sie, dass das höchstwertige Bit zu A 33 und das niedrigstwertige Bit zu B 33 wird) – das Ergebnis ist das Ergebnis des Algorithmus.

Die Entschlüsselung erfolgt auf die gleiche Weise wie die Verschlüsselung, jedoch ist die Reihenfolge der Unterschlüssel K i umgekehrt.

Funktion wird wie folgt berechnet:

A i und K i werden modulo 2 32 addiert.

Das Ergebnis wird in acht 4-Bit-Teilsequenzen unterteilt, von denen jede eine eigene Eingabe erhält Substitutionstabellenknoten(in aufsteigender Reihenfolge der Bitpriorität), unten aufgerufen S-Block. Die Gesamtzahl der GOST-S-Blöcke beträgt acht, also genauso viele wie Teilsequenzen. Jeden S-Block ist eine Permutation von Zahlen von 0 bis 15. Die erste 4-Bit-Teilsequenz geht an den Eingang der ersten S-Box, die zweite an den Eingang der zweiten usw.

Wenn S-Block sieht so aus:

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

und der Eingang des S-Blocks 0 ist, dann ist der Ausgang 1, wenn 4, dann ist der Ausgang 5, wenn der Eingang 12 ist, dann ist der Ausgang 6 usw.

Die Ausgänge aller acht S-Boxen werden zu einem 32-Bit-Wort zusammengefasst, dann wird das gesamte Wort zyklisch um 11 Bit nach links (in Richtung der höchstwertigen Bits) verschoben.

Der einfache Austauschmodus hat folgende Nachteile:

• Kann nur zum Verschlüsseln von Klartexten mit einer Länge verwendet werden, die ein Vielfaches von 64 Bit ist
• Durch die Verschlüsselung identischer Klartextblöcke werden identische Chiffretextblöcke erhalten, die einem Kryptoanalytiker bestimmte Informationen liefern können.

Im Text der Norm heißt es, dass die Bereitstellung von füllenden Ersatzknoten (S-Boxen) in der vorgeschriebenen Weise erfolgt, also durch den Entwickler des Algorithmus. Die Gemeinschaft russischer CIPF-Entwickler hat sich auf Ersatzknoten geeinigt, die im Internet verwendet werden, siehe RFC 4357.

Vorteile von GOST

• die Sinnlosigkeit eines Gewaltangriffs (XSL-Angriffe werden nicht berücksichtigt, da ihre Wirksamkeit noch nicht vollständig bewiesen ist);
• effiziente Implementierung und dementsprechend hohe Leistung auf modernen Computern.
• das Vorhandensein eines Schutzes gegen das Auferlegen falscher Daten (Entwicklung der nachahmenden Einfügung) und des gleichen Verschlüsselungszyklus in allen vier GOST-Algorithmen.

Kryptoanalyse

Es wird angenommen (siehe zum Beispiel Vitaly V. Shorin, Vadim V. Jelezniakov und Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST), dass GOST gegen so weit verbreitete Methoden wie die lineare und differentielle Kryptoanalyse resistent ist. Das Umkehren der Reihenfolge der Tasten in den letzten acht Runden bietet Schutz vor Slide-Angriffen und Reflexionsangriffen.

Im Mai 2011 bewies der berühmte Kryptoanalytiker Nicolas Courtois die Existenz eines Angriffs auf diese Chiffre, deren Komplexität 2,8 (256) Mal geringer ist als die Komplexität der direkten Suche nach Schlüsseln, vorausgesetzt, es gibt 2,64 Klartext/Klartext-Paare. Aufgrund des zu hohen Rechenaufwands ist dieser Angriff in der Praxis nicht durchführbar. Darüber hinaus ermöglicht Ihnen die Kenntnis von 2 64 Klartext/Privattext-Paaren offenbar, Chiffretexte zu lesen, ohne den Schlüssel zu berechnen. In den meisten anderen Werken werden auch Angriffe beschrieben, die nur unter bestimmten Voraussetzungen anwendbar sind, etwa einer bestimmten Art von Schlüsseln oder Ersatztabellen, einer Modifikation des ursprünglichen Algorithmus oder die immer noch unerreichbare Mengen an Speicher oder Rechenleistung erfordern. Offen bleibt die Frage, ob es praktische Angriffe gibt, ohne die Schwäche einzelner Schlüssel oder Ersatztabellen auszunutzen.

Kritik an GOST

Die Hauptprobleme von GOST hängen mit der Unvollständigkeit des Standards in Bezug auf die Generierung von Schlüsseln und Ersatztabellen zusammen. Es wird angenommen, dass GOST über „schwache“ Schlüssel und Ersatztabellen verfügt, der Standard beschreibt jedoch nicht die Kriterien für die Auswahl und Beseitigung „schwacher“ Schlüssel. Außerdem spezifiziert der Standard keinen Algorithmus zur Generierung einer Substitutionstabelle (S-Boxen). Einerseits kann es sich hierbei um weitere geheime Informationen (zusätzlich zum Schlüssel) handeln, andererseits wirft dies eine Reihe von Problemen auf:

• Es ist unmöglich, die kryptografische Stärke eines Algorithmus zu bestimmen, ohne die Substitutionstabelle im Voraus zu kennen.
• Implementierungen des Algorithmus von verschiedenen Herstellern verwenden möglicherweise unterschiedliche Ersatztabellen und sind möglicherweise nicht miteinander kompatibel.
• die Möglichkeit der absichtlichen Bereitstellung schwacher Ersatztabellen durch die Lizenzbehörden der Russischen Föderation;
• die Möglichkeit (kein Verbot im Standard), Substitutionstabellen zu verwenden, in denen die Knoten keine Permutationen sind, was zu einer extremen Verringerung der Stärke der Verschlüsselung führen kann.

Im Oktober 2010 wurde GOST auf der Sitzung des 1. Gemeinsamen Technischen Komitees der Internationalen Organisation für Normung (ISO/IEC JTC 1/SC 27) für die Aufnahme in den internationalen Blockverschlüsselungsstandard ISO/IEC 18033-3 nominiert. In diesem Zusammenhang wurden im Januar 2011 feste Sätze von Ersatzknoten gebildet und deren kryptografische Eigenschaften analysiert. Allerdings wurde GOST nicht als Standard übernommen und die entsprechenden Ersatztabellen wurden nicht veröffentlicht

Mögliche Anwendungen

Anmerkungen

siehe auch

Links

• GOST 28147-89 „Informationsverarbeitungssysteme. Kryptografischer Schutz. Kryptografischer Konvertierungsalgorithmus“
• Sergej Panasenko Verschlüsselungsstandard GOST 28147-89 (Russisch) (15. August 2007). Abgerufen am 3. August 2012.

• . - ein kryptografisches Projekt der Firma Cryptocom LLC zur Hinzufügung russischer kryptografischer Algorithmen zur OpenSSL-Bibliothek. Archiviert vom Original am 24. August 2011. Abgerufen am 16. November 2008.

Literatur

• Melnikov V.V. Schutz von Informationen in Computersystemen. - M.: Finanzen und Statistik, 1997.
• Romanets Yu. V., Timofeev P. A., Shangin V. F. Schutz von Informationen in Computersystemen und Netzwerken. - M.: Radio und Kommunikation, 1999.
• Kharin Yu. S., Bernik V. I., Matveev G. V. Mathematische Grundlagen der Kryptologie. - Mn. : BSU, 1999.
• Gerasimenko V. A., Malyuk A. A. Grundlagen der Informationssicherheit. - M.: MGIFI, 1997.
• Leonov A. P., Leonov K. P., Frolov G. V. Sicherheit automatisierter Bank- und Bürotechnologien. - Mn. : National Buch Kammer von Weißrussland, 1996.
• Winter V. M.. Moldovyan A. A., Moldovyan N. A. Computernetzwerke und Schutz übertragener Informationen. - St. Petersburg. : Staatliche Universität St. Petersburg, 1998.
• Schneider B. 14.1 Algorithmus GOST 28147-89 // Angewandte Kryptographie. Protokolle, Algorithmen, Quelltexte in C-Sprache = Angewandte Kryptographie. Protokolle, Algorithmen und Quellcode in C. - M.: Triumph, 2002. - S. 373-377. - 816 S. - 3000 Exemplare. - ISBN 5-89392-055-4
• Popov, V., Kurepkin, I. und S. Leontiev Zusätzliche kryptografische Algorithmen zur Verwendung mit den Algorithmen GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001 und GOST R 34.11-94 (Englisch) // RFC 4357. - IETF, Januar 2006.

Wikimedia-Stiftung. 2010.