GOST fut en quelque sorte l'équivalent soviétique du standard américain DES. Les deux algorithmes sont relativement similaires avec l'utilisation d'un réseau de Feistel.
Fonctionnement
GOST utilise un bloc de 64 bits et une clé de 256 bits. Ses S-Boxes (boîtes de substitution) peuvent être secrètes et contiennent environ protégés ce qui permet d'avoir une clé effective de 610 bits. Le réseau de Feistel possède 32 tours, chaque stage est simple :
addition d'une sous-clé de 32 bits (modulo 232)
passage du résultat dans une série de substitutions via les S-Boxes
rotation du résultat vers la gauche de 11 bits
Après rotation, on obtient la sortie de la fonction présente à chaque tour. Le key schedule est également simple :
diviser la clé de 256 bits en 8 sous-clés de 32 bits
utiliser quatre fois chaque clé dans l'algorithme
Les S-Boxes acceptent des entrées de 4 bits et produisent une sortie de 4 bits. La substitution à chaque tour comprend huit boîtes de 4x4 éléments.
Ces substitutions dépendent de l'implémentation et de la sécurité désirée (S-Boxes secrètes ou non). Les valeurs des S-Boxes n'étaient pas fournies dans les spécifications ce qui laissa supposer que le gouvernement avait volontairement distribué des valeurs vulnérables. Bruce Schneier rapporta qu'un constructeur de circuits intégrés dédiés à GOST avait généré les S-Boxes lui-même à l'aide d'un générateur de nombres pseudo-aléatoires.
Cryptanalyse
Par rapport à DES, la structure de chaque tour dans GOST est très simple. Cependant, les concepteurs de GOST ont tenté de compenser cette simplicité en intégrant 32 tours dans l'algorithme et la possibilité d'avoir des S-Boxes secrètes.
L'effet avalanche est plus lent à apparaître dans GOST que dans DES. Le standard soviétique utilise une rotation en lieu et place d'une permutation. Cela est encore une fois compensé par l'augmentation du nombre de tours.
Il y a eu relativement peu de cryptanalyse de GOST par rapport à DES mais malgré sa simplicité, il est relativement robuste. Le grand nombre de tours et les boîtes secrètes rendent la cryptanalyse différentielle ou linéaire plus difficiles. Même si l'effet avalanche est plus lent à se déclencher, il s'avère être efficace au terme des 32 tours.
En 1996, Bruce Schneier, Niels Ferguson et David Wagner ont cryptanalysé le key schedule de GOST. Même si leur attaque n'est pas praticable, elle a montré que l'utilisation d'un générateur aléatoire pour remplir les boîtes de substitution n'était pas une bonne idée.
Pour plus d'informations, il est aussi conseillé de lire Further Comments on Soviet Encryption Algorithm de Zhang, Pieprzyk et al.
