PICSI

Les réseaux de substitution-permutation

Un réseau de substitutions-permutations est également un système de chiffrement itératif. A chaque étage, on applique au bloc d'entrée une substitution non linéaire puis une fonction généralement linéaire appelée abusivement permutation. Ces réseaux prennent au mot les deux concepts définis par Shannon. La substitution, en général représentée par une boîte S, garantit, si elle est bien choisie, une bonne confusion (faire disparaître les structures tant linéaires qu'algébriques du chiffrement) et la permutation garantit une bonne diffusion de l'information (faire en sorte que chaque bit de sortie soit influencé par le plus grand nombre possible de bits d'entrée). Précisons également que l'usage des mots substitution et permutation est abusif. On peut effectivement parler de substitution en ce qui concerne les boîtes S même si il peut y avoir confusion avec le terme de permutation mais le terme de permutation est beaucoup trop approximatif pour désigner l'application linéaire qui suit. Cependant, l'emploi de ces termes restent classique en cryptographie, nous continuerons donc à les utiliser dans la suite de ce paragraphe.

Ce réseau doit également vérifier ce qu'on appelle l'effet avalanche : les modifications du texte clair doivent être de plus en plus importantes au fur et à mesure que les données se propagent dans la structure de l'algorithme. De ce fait, en perturbant un seul bit en entrée, on obtient idéalement une sortie totalement différente, d'où le nom de ce phénomène. Si la diffusion des modifications des entrées sur les sorties n'est pas suffisamment grande, il sera possible d'établir des prédictions sur les entrées à partir de l'observation des sorties et donc d'obtenir un biais statistique. Le critère d'avalanche stricte a été introduit en cryptographie par Webster et Tavares en 1985 [1] comme une propriété des fonctions booléennes utilisées qui doit être vérifiée. Une fonction qui satisfait ce critère est telle que tout changement d'un bit d'entrée a une chance sur deux de modifier un bit de sortie ce qui permet d'uniformiser les sorties.
Deux exemples d'algorithmes de chiffrement utilisant des réseaux de substitutions-permutations sont la famille SAFER et l'AES.

 

Références

[1]

A. F. Webster and Stafford E. Tavares. On the design of s-boxes. In CRYPTO, volume 218 of Lecture Notes in Computer Science, pages 523-534, 1985.