S-boîte - S-box
En cryptographie , une S-box ( substitution-box ) est un composant de base des algorithmes à clé symétrique qui effectue la substitution. Dans les chiffrements par blocs , ils sont généralement utilisés pour masquer la relation entre la clé et le texte chiffré , garantissant ainsi la propriété de confusion de Shannon . Mathématiquement, une S-box est une fonction booléenne vectorielle .
En général, une S-box prend un certain nombre de bits d' entrée , m , et les transforme en un certain nombre de bits de sortie, n , où n n'est pas nécessairement égal à m . Une boîte S m × n peut être implémentée en tant que table de consultation avec 2 m mots de n bits chacun. Des tables fixes sont normalement utilisées, comme dans le Data Encryption Standard (DES), mais dans certains chiffrements, les tables sont générées dynamiquement à partir de la clé (par exemple, les algorithmes de chiffrement Blowfish et Twofish ).
Exemple
Un bon exemple de table fixe est la S-box de DES (S 5 ), mappant une entrée 6 bits en une sortie 4 bits :
S 5 | Milieu 4 bits d'entrée | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 | ||
Embouts extérieurs | 00 | 0010 | 1100 | 0100 | 0001 | 0111 | 1010 | 1011 | 0110 | 1000 | 0101 | 0011 | 1111 | 1101 | 0000 | 1110 | 1001 |
01 | 1110 | 1011 | 0010 | 1100 | 0100 | 0111 | 1101 | 0001 | 0101 | 0000 | 1111 | 1010 | 0011 | 1001 | 1000 | 0110 | |
dix | 0100 | 0010 | 0001 | 1011 | 1010 | 1101 | 0111 | 1000 | 1111 | 1001 | 1100 | 0101 | 0110 | 0011 | 0000 | 1110 | |
11 | 1011 | 1000 | 1100 | 0111 | 0001 | 1110 | 0010 | 1101 | 0110 | 1111 | 0000 | 1001 | 1010 | 0100 | 0101 | 0011 |
Étant donné une entrée de 6 bits, la sortie de 4 bits est trouvée en sélectionnant la ligne en utilisant les deux bits externes (le premier et le dernier bits) et la colonne en utilisant les quatre bits internes. Par exemple, une entrée " 0 1101 1 " a des bits externes " 01 " et des bits internes " 1101 " ; la sortie correspondante serait "1001".
Les huit S-box de DES ont fait l'objet d'une étude intensive pendant de nombreuses années, craignant qu'une porte dérobée (une vulnérabilité connue uniquement de ses concepteurs) n'ait été implantée dans le chiffrement. Les critères de conception de la S-box ont finalement été publiés (dans Coppersmith 1994 ) après la redécouverte publique de la cryptanalyse différentielle , montrant qu'ils avaient été soigneusement réglés pour augmenter la résistance contre cette attaque spécifique. Biham et Shamir ont découvert que même de petites modifications apportées à une boîte S pouvaient considérablement affaiblir le DES.
Analyse et propriétés
Il y a eu beaucoup de recherches sur la conception de bonnes boîtes S, et on en sait beaucoup plus sur leur utilisation dans les chiffrements par blocs que lorsque DES a été publié.
Toute S-box où toute combinaison linéaire de bits de sortie est produite par une fonction courbée des bits d'entrée est appelée une S-box parfaite .
Les boîtes S peuvent être analysées à l'aide d' une cryptanalyse linéaire et d' une cryptanalyse différentielle sous la forme d'une table d'approximation linéaire (LAT) ou d'une transformation de Walsh et d'une table de distribution des différences (DDT) ou d'une table et d'un spectre d'autocorrélation. Sa force peut se résumer par la non - linéarité (pliée, presque courbée) et l' uniformité différentielle (parfaitement non linéaire, presque parfaitement non linéaire).
Voir également
- Bijection, injection et surjection
- Fonction booléenne
- Numéro rien dans ma manche
- Boîte de permutation (P-box)
- Chiffre de permutation
- Rijndael S-box
- Chiffre de substitution
Les références
Lectures complémentaires
- Kaisa Nyberg (1991). Boîtes S non linéaires parfaites (PDF) . Avancées en cryptologie - EUROCRYPT '91. Brighton . p. 378-386 . Récupéré le 2007-02-20 .
- Chaudronnier, Don (1994). « La norme de chiffrement des données (DES) et sa force contre les attaques ». Revue IBM de recherche et développement . 38 (3) : 243-250. doi : 10.1147/rd.383.0243 .
- S. Monsieur et C. Adams (1996). Pratique S-box design . Atelier sur des domaines sélectionnés en cryptographie (SAC '96) Dossier d'atelier. Université Queen's . p. 61-76. CiteSeerX 10.1.1.40.7715 .
- Schneier, Bruce (1996). Cryptographie appliquée, deuxième édition . John Wiley & Fils . pages 296 à 298, 349. ISBN 978-0-471-11709-4.
- Chuck Easttom (2018). « Une méthodologie généralisée pour la conception d'éléments non linéaires dans des primitives cryptographiques symétriques ». 2018 IEEE 8th Annual Computing and Communication Workshop and Conference (CCWC) . Atelier et conférence sur l'informatique et la communication de l'IEEE (CCWC), 2018 IEEE 8th Annual. IEEE . p. 444-449. doi : 10.1109/CCWC.2018.8301643 . ISBN 978-1-5386-4649-6. S2CID 3659645 .