Über GOSTs Code, Grasshopper, seine SBox und verlorene Samen

Hallo% Benutzername%!



Wir sind kürzlich von der EuroCrypt 2019-Konferenz zurückgekehrt, bei der wir äußerst kluge Leute getroffen und gleichzeitig neue, äußerst anstößige Fakten über GOST SBox erfahren haben.

Dies ist also der zweite Ansatz für das Projektil. Korrigiert und ergänzt.

Dieses Mal wird es keine unverständlichen rot-blauen Folien geben, aber es wird Originaldokumente des ISO-Komitees mit Erklärungen der Autoren von Grasshopper geben.

Und sogar die Herausforderung am Ende!

Lass uns gehen.

Erstes Bildungsprogramm. Im vorherigen Artikel war es nicht, diesmal korrigiere ich.

Ausgewählter Plaintext Attack (CPA)

Wir beginnen mit dem grundlegenden Angriffsmodell für Blockchiffren.

In diesem Modell weiß der Angreifer alles über das Kryptosystem außer dem Verschlüsselungsschlüssel. Er kann beliebige Klartexte erstellen, die entsprechenden Chiffretexte abrufen und seine Aufgabe ist es, den Schlüssel zu berechnen, weil Dies ist die einzige Variable.

Die Blockverschlüsselung kann in dieser Situation als pseudozufällige Substitution betrachtet werden. Eine Funktion, die einen Klartextblock einem Chiffretextblock so zuordnet, dass die Beziehung zwischen ihnen nicht bestimmt werden kann.

Eine ideale Blockchiffre kann man sich als große Tabelle vorstellen, in der horizontal alle möglichen Schlüssel von 000 ... 000 bis 111 ... 111 vertikal vorhanden sind - alle möglichen offenen Texte auch von 000 ... 000 bis 111 ... 111 und an der Stelle ihrer Schnittmenge - zufällig erzeugte Chiffretexte, die ein Paar von "Schlüssel - Klartext" eindeutig zuordnen würden. Das Erstellen einer solchen Tabelle im wirklichen Leben ist aufgrund ihrer Größe nicht möglich, daher wird sie unter Verwendung verschiedener Blockverschlüsselungsalgorithmen emuliert.

Der Angriff auf die Blockverschlüsselung kann als erfolgreich bezeichnet werden, wenn wir die „Zufälligkeit“ bestimmen können, mit der der Algorithmus Chiffretexte auswählt, die Klartexten entsprechen. Diese Zufälligkeit ermöglicht es im schlimmsten Fall, den Verschlüsselungsschlüssel zu berechnen.

(Nicht-) Linearität

Der Verschlüsselungsprozess in der Blockverschlüsselung kann durch eine einfache Formel dargestellt werden
C = M x K.
Dabei ist C Chiffretext, M Klartext, K der Verschlüsselungsschlüssel und x die Blockchiffre.

Diese Formel ähnelt visuell der Schulformel der linearen Gleichung y = kx + b, deren Graph eine gerade Linie ist.

Jede gerade Linie kann in nur zwei Punkten wiederhergestellt werden. Gleichzeitig möchten wir wirklich nicht, dass Sie in zwei Paaren von Klartext - Chiffretext - den Verschlüsselungsschlüssel wiederherstellen können. Zu diesem Zweck werden den Verschlüsselungsalgorithmen spezielle Schichten hinzugefügt, die für die Nichtlinearität verantwortlich sind. Diese Ebenen sollen verhindern, dass die Beziehung zwischen Klartext, Chiffretext und Schlüssel berechnet werden kann.

Ihre Qualität ist entscheidend für die Sicherheit des Algorithmus.

Was ist SBox?

Dies ist dieselbe nichtlineare Schicht. Eine Funktion, die im Fall von Grasshopper und einigen anderen Chiffren ein Byte eindeutig einem anderen Byte zuordnet.

Sehr oft wird es durch eine einfache Korrespondenztabelle festgelegt, zum Beispiel



Weil es sonst nicht beschrieben werden kann. Auf den ersten Blick.

Warum ist SBox wichtig?

Weil es die einzige nichtlineare Funktion in der gesamten Chiffre ist. Ohne sie ist das Brechen einer Chiffre nicht einfach, aber sehr einfach, da sie als lineares Gleichungssystem dargestellt wird. Daher hat die Substitutionsfunktion so viel Aufmerksamkeit. Es gibt sogar praktische Übungen zum Hacken von AES mit linearer SBox.

Warum können Sie überhaupt keine sichere SBox erstellen?

Das Problem ist, dass Kryptographie keine exakte Wissenschaft ist. Der einzige nachweislich starke Verschlüsselungsalgorithmus ist ein einmaliges Pad . Der Rest sind schüchterne Versuche, sich in das uns zur Verfügung stehende Wissensspektrum einzufügen, dessen Menge nicht so groß ist.
Wir wissen nicht genau, ob RSA- oder AES- oder elliptische Kurven resistent sind, aber wir wissen, dass solche und solche Dinge definitiv nicht möglich sind . Alles dazwischen ist Kreativität.

Daher die ständige Paranoia über die verschiedenen „magischen Konstanten“ und andere Punkte, die die Autoren der Algorithmen als sicher präsentieren, aber nicht beweisen können .

Wie erstelle ich SBox?

Die verschiedenen SBox-Varianten sind 256!, Was ungefähr 2 ^{1684 entspricht} . Die Auswahl ist groß und im Laufe der Jahre der Kryptoanalyse wurden Metriken und Eigenschaften entwickelt, die SBox besitzen sollte und die gegen die heute bekannten Angriffe resistent sind. Natürlich denken die Schöpfer der Tabellen über Jahre hinweg nach und versuchen, Substitutionen zu schaffen, die selbst gegen Angriffe, die in 5-10 Jahren erfunden wurden, resistent sind. Dies ist jedoch mehr aus der Kategorie Magie und Schamanismus.

Es gibt zwei grundlegend unterschiedliche Ansätze zur Erstellung von SBox.

Die erste ist eine zufällige Suche. Entwickler generieren zufällige Tabellen, überprüfen ihre Eigenschaften und filtern diejenigen heraus, die nicht geeignet sind. Dies geht so lange weiter, bis die Entwickler mit dem, was sie gefunden haben, zufrieden sind.

In der zivilisierten Welt geschieht dies beispielsweise wie folgt:

1. Ein Anfangswert ist beispielsweise ein Zitat aus einem Buch oder die ersten Ziffern von Pi
2. Läuft durch einen Hash
3. Das Hash-Ergebnis wird als Daten zur Bildung der SBox verwendet.
4. Wenn SBox nicht passt, nehmen Sie den aktuellen Hash und kehren Sie zu Schritt 2 zurück

So kann jeder diesen Prozess reproduzieren und sicherstellen, dass mindestens die Mindestanforderungen für die pseudozufällige Suche erfüllt sind.

Wissen Sie, wohin die Samen des wichtigsten symmetrischen Algorithmus des Landes gehen? Verloren ! Ich dachte, sie hätten es ihnen nicht ausdrücklich verraten, das Geheimnis ist da oder so, aber russische Kollegen von EuroCrypt sagten, dass während der Entwicklung des Algorithmus im Jahr 2007 aus irgendeinem Grund niemand dachte, dass es notwendig wäre, das Design der Nachschlagetabelle zu rechtfertigen, und dass die Werte, aus denen es hervorging, für immer waren verloren. Die Geschichte ist wunderschön, vergessen Sie nur nicht, dass der Algorithmus nicht in der Schule in einer Pause erstellt wurde, sondern im Darm des FSB.

Die zweite Möglichkeit besteht darin, die SBox selbst zu erstellen, wobei Sie sich an den verfügbaren mathematischen Geräten orientieren. Das haben die Autoren von AES getan, und sie haben es ziemlich gut gemacht. Wenn wir die Nichtlinearität von SBox AES, SM4 (chinesischer Standard) und Grasshopper (es verwendet dieselbe SBox wie der Stribog-Hash) vergleichen, wird das Ergebnis nicht für letztere sprechen

AES-Nichtlinearität (min, max) = (112,0, 112,0)
SM4-Nichtlinearität (min, max) = (112,0, 112,0)
Streebog-Nichtlinearität (min, max) = (102,0, 110,0)

Der Nichtlinearitätsberechnungscode verwendet die Walsh-Transformation und ist hier verfügbar .

Docs

Ich habe zwei Dokumente von ISO erhalten. Im ersten Teil erklären Grasshopper-Designer, wie sie SBox erstellt haben, im anderen Fall erörtert das Komitee ihre Argumente.



Ab dem ersten Dokument interessieren uns zwei Zitate:



und



Ich hoffe, das Thema mit „Leo Perrin selbst kam auf die Idee, dass die Autoren zufällig nach SBox gesucht haben“ ist jetzt geschlossen.

Aus den Erklärungen der Designer folgt daraus

1. Sie haben die SBox wirklich pseudozufällig gesucht (gegebene Sicherheitskriterien)
2. Es wurde angeblich keine versteckte Struktur hineingelegt.

Und an diesem Ort haben sie es gründlich vermasselt.

Was ist eine Struktur?

Eine Struktur, wie sie auf eine Nachschlagetabelle angewendet wird, ist ein Algorithmus, der diese Tabelle beschreibt.

Das Dokument erwähnte AES. Die Nachschlagetabelle für AES wurde jedoch ursprünglich nicht durch zufällige Suche erstellt, sondern mithilfe mehrerer mathematischer Techniken, mit denen wir eine nichtlineare Ebene mit mehreren Formeln beschreiben konnten . Dies ist übrigens die Einzigartigkeit von AES.

Im Gegenteil, wenn Sie zufällig nach SBox suchen, sollte es keine solchen Strukturen geben, und das Problem bei Grasshopper SBox ist, dass sich die Wörter der Algorithmus-Designer stark von den Fakten unterscheiden. Ich habe in einem früheren Artikel über die Struktur einer Heuschrecke namens TKLog geschrieben. Dieses Mal wollen wir über Strukturen im Allgemeinen sprechen.

Kolmogorov Komplexität

Dies ist das Ergebnis von Untersuchungen aus Leo Perrins neuestem Artikel über die Heuschrecke.

Das Hauptgegenargument zu Artikeln über Strukturen in Grasshopper SBox ist, dass "in fast jeder SBox eine Struktur gefunden werden kann, wenn Sie möchten". Und "obwohl die Wahrscheinlichkeit, die von Leo gefundene Struktur zu finden, vernachlässigbar ist, würde es eine andere SBox geben, wenn es eine andere SBox gäbe, auch mit einer unbedeutenden Wahrscheinlichkeit."

Nehmen wir an, das ist so. Aber. Wie sich herausstellte, ist es möglich, einen bestimmten „Grad an Strukturiertheit“ von SBox abzuleiten, der nicht von der Wahrscheinlichkeit abhängt, in die eine oder andere Struktur zu fallen.

Dies hängt jedoch von der Größe des Algorithmus ab, der zur Generierung dieser SBox benötigt wird!

Dies nennt man die Kolmogorov-Komplexität.

Wenn Sie sich SBox als eine Zeichenfolge von Bytes vorstellen, sollte es im Fall einer zufälligen Zeichenfolge keinen Algorithmus geben, der diese Zeichenfolge generiert und gleichzeitig kleiner als diese Zeichenfolge ist.

Für eine Heuschrecke

Die Größe von SBox beträgt also 256 Bytes. Hier ist eine lesbare Version des Autorencodes von Leo Perrin, der die Grasshopper-Tabelle implementiert. Am Eingang befindet sich das Quellbyte, am Ausgang das entsprechende Byte von der Grasshopper SBox. Die Hauptbedingung für einen solchen Algorithmus ist ein Verbot der Verwendung von Sprach- oder Plattformstrukturen, die die Größe des Programms betrügerisch reduzieren. Wenn sich beispielsweise irgendwo in der Standardbibliothek eine Konstante befindet, die die Hälfte von SBox enthält, können Sie sie nicht verwenden.

Herausforderung - Schreiben Sie ein Programm, das kleiner als SBox ist.

unsigned char p(unsigned char x){
    unsigned char
        s[]={1,221,146,79,147,153,11,68,214,215,78,220,152,10,69},
        k[]={0,32,50,6,20,4,22,34,48,16,2,54,36,52,38,18,0};    
    if(x) {
        unsigned char l=1, a=2;
        while(a!=x) {
            a=(a<<1)^(a>>7)*29;
            l++;
        }
        if (l%17) return 252^k[l%17]^s[l/17];
        else return 252^k[l/17];
    }
    else return 252;
}

, SBox «» , , SBox. 416 , .

, :

p(x){
  unsigned char
      *t="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8",
      a=2,l=0,b=17;
  while(x && (l++,a^x)) a=2*a^a/128*29;
  return l%b ? t[l%b]^t[b+l/b]^b : t[l/b]^188;
}

196 , 23% SBox. . , :

p(x){char*k="@`rFTDVbpPBvdtfR@\xacp?\xe2>4\xa6\xe9{z\xe3q5\xa7\xe8";int l=256,b=17;while(--l*x^l)x=2*x^x/128*285;return l%b?k[l%b]^k[b+l/b]^b:k[l/b]^188;}

SBox :

int main() {
   for(int i = 0; i < 256; i++){
       if (i % 16 == 0){
           printf("\n");
       }
    printf("%d, ", (unsigned char)p(i));    
   }
}

, SBox .
153 . — ANSI, 7 , 8. 1071 ~134 . , .

, Cortex-M4 80 ( ).

, 64 .

, ?

, , .

, 4 Sbox, SBox , .

. , « » AES (60 , GolfScript), .

— . , — .

— SBox. , . , .

( ), , 4 , SBox. , — , . 4 , , , . , , , 11 , , . , side project ¯\_(ツ)_/¯.

ISO . . .

, , , SBox . . , , .

Curve25519 Daniel J. Bernstein Tanja Lange, ISO . , , , SBox. . .

, .

, . ISO, , EuroCrypt.

, ( SBox), RFC 7801, .

, SBox, (, ). , , , . V2 .

. , « , ».

, ? , AES - .

, , , , . .

Challenge!

SBox , , . , 256 . . . — , .

— 58 Stax. « » SBox.

.