✝️ 👩🏽‍🏫 🥦 À propos du code de GOST, Grasshopper, son SBox et les graines perdues 👨‍✈️ 🌀 🛀🏻

Salut% username%!

Nous sommes récemment revenus de la conférence EuroCrypt 2019, où nous avons rencontré des gens extrêmement intelligents et en même temps appris de nouveaux faits extrêmement offensants sur GOST SBox.

C'est donc la deuxième approche du projectile. Corrigé et complété.

Cette fois, il n'y aura pas de diapositives rouge-bleu incompréhensibles, mais il y aura des documents originaux du comité ISO avec des explications des auteurs de Grasshopper.

Et même le défi à la fin!

Allons-y.

Premier programme éducatif. Dans l'article précédent, ce n'était pas le cas, cette fois je corrige.

Attaque Plaintext choisie (CPA)

Nous commençons avec le modèle d'attaque de base sur les chiffres de bloc.

Dans ce modèle, l'attaquant sait tout sur le cryptosystème, à l'exception de la clé de chiffrement. Il peut créer n'importe quel texte en clair, obtenir les textes chiffrés correspondants et sa tâche consiste à calculer la clé, car c'est la seule variable.

Le chiffrement par bloc dans cette situation peut être considéré comme une substitution pseudo-aléatoire. Une fonction qui fait correspondre un bloc de texte en clair à un bloc de texte chiffré de telle manière qu'il est impossible de déterminer la relation entre eux.

Un chiffrement de bloc idéal peut être imaginé comme une grande table, où horizontalement il y aura toutes les clés possibles de 000 ... 000 à 111 ... 111, verticalement - tous les textes ouverts possibles également de 000 ... 000 à 111 ... 111 , et à l 'endroit de leur intersection - des textes chiffrés générés aléatoirement qui associeraient de façon unique une paire de "clé - texte en clair". La création d'une telle table dans la vie réelle n'est pas possible en raison de sa taille, elle est donc émulée à l'aide de divers algorithmes de chiffrement par blocs.

L'attaque contre le chiffrement par bloc peut être qualifiée de réussie si nous pouvons déterminer le «caractère aléatoire» avec lequel l'algorithme sélectionne les textes chiffrés qui correspondent au texte en clair. Ce caractère aléatoire permet dans les pires cas de calculer la clé de chiffrement.

(Non) linéarité

Le processus de chiffrement en chiffrement par blocs peut être représenté par une formule simple
C = M x K
où C est un texte chiffré, M est un texte en clair, K est la clé de chiffrement et x est le chiffrement par bloc.

Cette formule est visuellement similaire à la formule de l'école de l'équation linéaire y = kx + b, dont le graphique est une ligne droite.

Toute ligne droite peut être restaurée en seulement deux points. Et en même temps, nous ne voulons vraiment pas que dans deux paires de texte en clair - texte chiffré, vous puissiez restaurer la clé de chiffrement. Pour cela, des couches spéciales sont ajoutées aux algorithmes de chiffrement qui sont responsables de la non- linéarité. Ces couches sont conçues pour empêcher la possibilité de calculer la relation entre le texte en clair, le texte chiffré et la clé.

Leur qualité est essentielle à la sécurité de l'algorithme.

Qu'est-ce que SBox?

Il s'agit de la même couche non linéaire. Une fonction qui, dans le cas de Grasshopper et de certains autres chiffrements, mappe de manière unique un octet à un autre octet.

Très souvent, il est défini par une simple table de correspondance, par exemple ceci:

Sinon, cela ne peut pas être décrit. À première vue.

Pourquoi SBox est-il important?

Parce que c'est la seule fonction non linéaire de tout le chiffre. Sans lui, casser un chiffre ne sera pas facile, mais très simple, le présentant comme un système d'équations linéaires. Par conséquent, la fonction de substitution a tellement d'attention. Il existe même des exercices pratiques pour pirater AES avec SBox linéaire.

Pourquoi ne pouvez-vous pas du tout créer un SBox sûr?

Le problème est que la cryptographie n'est pas une science exacte. Le seul algorithme de chiffrement prouvablement fort est un tampon à usage unique . Tout le reste n'est que de timides tentatives de s'inscrire dans l'éventail des connaissances dont nous disposons, dont l'ensemble n'est pas si grand.
Nous ne savons pas avec certitude si RSA ou AES ou les courbes elliptiques sont résistantes, mais nous savons que telle ou telle chose n'est certainement pas possible . Entre les deux, il y a la créativité.

D'où la paranoïa constante des différentes «constantes magiques» et d'autres points que les auteurs des algorithmes présentent comme sûrs, mais ne peuvent pas le prouver .

Comment créer SBox?

Les différentes variantes de SBox sont 256!, Soit environ 2 ¹⁶⁸⁴ . Le choix est vaste et au fil des années de cryptanalyse, des métriques et des caractéristiques ont été développées que SBox devrait avoir, résistant aux attaques connues d'aujourd'hui. Bien sûr, les créateurs des tables réfléchissent pour les années à venir et tentent de créer des substitutions qui résistent même aux attaques inventées en 5-10 ans. Mais c'est plus de la catégorie de la magie et du chamanisme.

Il existe deux approches fondamentalement différentes pour créer SBox.

Le premier est une recherche aléatoire. Les développeurs génèrent des tableaux aléatoires, examinent leurs caractéristiques et filtrent ceux qui ne conviennent pas. Cela continue jusqu'à ce que les développeurs soient satisfaits de ce qu'ils ont trouvé.

Dans le monde civilisé, cela se produit, par exemple, comme suit:

Une valeur initiale est prise, par exemple, une citation d'un livre ou les premiers chiffres de Pi
Traverse un hachage
Le résultat de hachage est utilisé comme données pour former le SBox.
Si SBox ne correspond pas, prenez le hachage actuel et revenez à l'étape 2

Ainsi, n'importe qui peut reproduire ce processus et s'assurer qu'au moins les exigences minimales pour la recherche pseudo-aléatoire sont remplies.

Savez-vous où vont les graines de l'algorithme symétrique principal du pays? Perdu ! Je pensais qu'ils ne le leur avaient pas spécifiquement dit, le secret est là ou quelque chose, mais des collègues russes d'EuroCrypt ont dit que lors du développement de l'algorithme en 2007, pour une raison quelconque, personne ne pensait qu'il serait nécessaire de justifier la conception de la table de recherche, et les valeurs dont il est sorti étaient éternelles perdu. L'histoire est belle, n'oubliez pas que l'algorithme a été créé non pas à l'école à la pause, mais dans les entrailles du FSB.

La deuxième façon consiste à créer vous-même le SBox, guidé par l'appareil mathématique disponible. C'est ce que les auteurs d'AES ont fait, et ils s'en sont plutôt bien sortis. Si nous comparons la non-linéarité de SBox AES, SM4 (standard chinois) et Grasshopper (il utilise le même SBox que le hachage Stribog), alors le résultat ne sera pas en faveur de ce dernier

Non-linéarité AES (min, max) = (112,0, 112,0)
Non-linéarité SM4 (min, max) = (112,0, 112,0)
Non-linéarité Streebog (min, max) = (102,0, 110,0)

Le code de calcul de non-linéarité utilise la transformation de Walsh et est disponible ici.

Documents

J'ai reçu deux documents de l'ISO. Dans le premier, les concepteurs de Grasshopper expliquent comment ils ont créé SBox, dans un autre, le comité discute de leurs arguments.

du premier document nous sommes intéressés par deux citations:

J'espère que le sujet avec «Leo Perrin lui-même est venu avec l'idée que les auteurs ont recherché SBox au hasard» est maintenant fermé.

D'après les explications des concepteurs, il s'ensuit que

Ils ont vraiment cherché le SBox de manière pseudo-aléatoire (compte tenu des critères de sécurité)
Aucune structure cachée n'y aurait été posée.

Et à cet endroit, ils ont complètement foiré.

Qu'est-ce qu'une structure?

Une structure telle qu'appliquée à une table de recherche est un algorithme qui décrit cette table.

Le document mentionne AES. Mais la table de substitution pour AES a été créée à l'origine non pas par recherche aléatoire, mais à l'aide de plusieurs techniques mathématiques qui ont permis de décrire la couche non linéaire par plusieurs formules . C'est d'ailleurs le caractère unique d'AES.

Au contraire, si vous recherchez SBox au hasard, il ne devrait pas y avoir de telles structures et le problème avec Grasshopper SBox est que les mots des concepteurs d'algorithmes sont très différents des faits. J'ai écrit sur la structure d'une sauterelle appelée TKLog dans un article précédent , cette fois parlons des structures en général.

Complexité de Kolmogorov

Ceci est le résultat de la recherche du dernier article de Leo Perrin sur le Grasshopper.

Le principal contre-argument aux articles sur les structures dans Grasshopper SBox est que "dans presque tous les SBox, vous pouvez trouver une structure si vous le souhaitez." Et "même si la probabilité de trouver la structure que Leo a trouvée est négligeable, s'il y avait un autre SBox, alors il y en aurait un autre, également avec une probabilité insignifiante."

Disons qu'il en est ainsi. Mais. Il s'est avéré qu'il est possible de dériver un certain «degré de structure» de SBox, qui ne dépend pas de la probabilité de tomber dans l'une ou l'autre structure.

Mais cela dépend de la taille de l'algorithme qui est nécessaire pour générer ce SBox!

C'est ce qu'on appelle la complexité de Kolmogorov.

Si vous imaginez SBox comme une chaîne d'octets, alors dans le cas d'une chaîne aléatoire, il ne devrait pas y avoir d'algorithme qui génère cette chaîne et en même temps est plus petit que cette chaîne.

Pour une sauterelle

Ainsi, la taille de SBox est de 256 octets. Voici une version lisible du code de paternité de Leo Perrin, qui implémente la table Grasshopper. À l'entrée se trouve l'octet source, à la sortie se trouve l'octet correspondant du Grasshopper SBox. La condition principale pour un tel algorithme est l'interdiction d'utiliser des structures de langage ou de plate-forme qui réduisent considérablement la taille du programme. Par exemple, si quelque part dans la bibliothèque standard il y a une constante contenant la moitié de SBox, vous ne pouvez pas l'utiliser.

Défi - écrivez un programme qui sera plus petit que SBox.

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.

.

À propos du code de GOST, Grasshopper, son SBox et les graines perdues