Réseau SP
En cryptographie, un réseau SP, ou réseau de substitution-permutation (SPN), est une série d'opérations mathématiques liées utilisées dans les algorithmes de chiffrement par blocs tels que AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK et Square.
Un tel réseau prend un bloc de texte en clair et la clé comme entrées, et applique plusieurs "rondes" ou "couches" alternées de boîtes de substitution (boîtes S) et de permutation (boîtes P) pour produire le bloc de texte chiffré. Les boîtes S et les boîtes P transforment les (sous-)blocs de bits d'entrée en bits de sortie. Il est courant que ces transformations soient des opérations efficaces à effectuer dans le matériel, comme la rotation exclusive ou (XOR) et la rotation par bit. La clé est introduite à chaque tour, généralement sous la forme de "clés rondes" qui en sont dérivées. (Dans certaines conceptions, les S-boxes eux-mêmes dépendent de la clé).
Le décryptage se fait en inversant simplement le processus (en utilisant les inverses des boîtes S et P et en appliquant les clés rondes dans l'ordre inverse).
Une S-box remplace un petit bloc de bits (l'entrée de la S-box) par un autre bloc de bits (la sortie de la S-box). Cette substitution doit être de type un à un, pour assurer l'invertibilité (donc le décryptage). En particulier, la longueur de la sortie doit être la même que la longueur de l'entrée (l'image de droite montre des S-box avec 4 bits d'entrée et 4 bits de sortie), ce qui est différent des S-box en général qui peuvent également changer de longueur, comme dans DES (Data Encryption Standard), par exemple. Une S-box n'est généralement pas une simple permutation des bits. Au contraire, un bon S-box aura la propriété que le changement d'un bit d'entrée changera environ la moitié des bits de sortie (ou un effet d'avalanche). Elle aura également la propriété que chaque bit de sortie dépendra de chaque bit d'entrée.
Une P-box est une permutation de tous les bits : elle prend les sorties de toutes les S-box d'un tour, permute les bits et les introduit dans les S-box du tour suivant. Une bonne P-box a la propriété que les bits de sortie de n'importe quelle S-box sont distribués au plus grand nombre possible d'entrées de S-box.
À chaque tour, la clé de tour (obtenue à partir de la clé avec quelques opérations simples, par exemple, en utilisant des boîtes S et des boîtes P) est combinée en utilisant une opération de groupe, généralement XOR.
Une seule boîte S typique ou une seule boîte P n'a pas une grande force cryptographique : une boîte S peut être considérée comme un chiffre de substitution, tandis qu'une boîte P peut être considérée comme un chiffre de transposition. Cependant, un réseau SP bien conçu avec plusieurs séries alternées de boîtes S et P satisfait déjà les propriétés de confusion et de diffusion de Shannon :
- La raison de cette diffusion est la suivante : Si l'on modifie un bit du texte en clair, il est alors introduit dans une S-box, dont la sortie changera à plusieurs bits, puis tous ces changements sont répartis par la P-box entre plusieurs S-box, ce qui fait que les sorties de toutes ces S-box sont à nouveau modifiées à plusieurs bits, et ainsi de suite. En faisant plusieurs tours, chaque bit change plusieurs fois dans un sens et dans l'autre, donc, à la fin, le texte chiffré a complètement changé, de manière pseudo-aléatoire. En particulier, pour un bloc d'entrée choisi au hasard, si on retourne le i-ième bit, alors la probabilité que le j-ième bit de sortie change est d'environ la moitié, pour tout i et j, ce qui est le critère d'avalanche strict. Inversement, si l'on change un bit du texte chiffré, puis que l'on tente de le déchiffrer, le résultat est un message complètement différent du texte en clair original - les chiffres SP ne sont pas facilement malléables.
- La raison de la confusion est exactement la même que pour la diffusion : le changement d'un bit de la clé modifie plusieurs des clés rondes, et chaque changement de chaque clé ronde diffuse sur tous les bits, modifiant le cryptogramme de manière très complexe.
- Même si un attaquant obtient d'une manière ou d'une autre un texte en clair correspondant à un texte chiffré - une attaque de texte en clair connu ou, pire, une attaque de texte en clair choisi ou de texte chiffré choisi - la confusion et la diffusion rendent difficile pour l'attaquant de récupérer la clé.
Bien qu'un réseau Feistel qui utilise des S-box (comme DES) soit assez similaire aux réseaux SP, il y a quelques différences qui rendent ceci ou cela plus applicable dans certaines situations. Pour un certain degré de confusion et de diffusion, un réseau SP présente plus de "parallélisme inhérent" et peut donc - compte tenu d'un processeur comportant de nombreuses unités d'exécution - être calculé plus rapidement qu'un réseau Feistel. Les CPU ayant peu d'unités d'exécution - comme la plupart des cartes à puce - ne peuvent pas tirer parti de ce parallélisme inhérent. De même, les chiffrages SP exigent que les boîtes S soient inversibles (pour effectuer le décryptage) ; les fonctions internes de Feistel n'ont pas cette restriction et peuvent être construites comme des fonctions unidirectionnelles.
