Madryga
Madryga est un algorithme de chiffrement par bloc conçu en 1984 par W. E. Madryga. Destiné à une implémentation logicielle efficace et simple à mettre en œuvre, l'algorithme souffre cependant d'importantes faiblesses. Il a toutefois posé les bases algorithmiques et mathématiques concernant les rotations dépendantes des données. Celles-ci seront reprises dans d'autres chiffrements comme RC5 et RC6.
| Concepteur(s) | W. E. Madryga |
|---|---|
| Première publication | 1984 |
| Dérivé de | Aucun |
| Chiffrement(s) basé(s) sur cet algorithme | Aucun |
| Taille(s) du bloc | 24 bits |
|---|---|
| Longueur(s) de la clé | quelconque |
| Structure | série de rotations |
| Nombre de tours | variable (8 dans les spécifications) |
Meilleure cryptanalyse
Dans sa proposition, Madryga met en avant 12 objectifs qui doivent être considérés lors de la réalisation d'un bon chiffrement par bloc. DES remplissait 9 d'entre eux. Les 3 critères restants étaient :
- toute clé doit produire un chiffrement robuste (ie. pas de clés faibles)
- la longueur de la clé et du texte doivent être ajustables selon la sécurité désirée
- l'algorithme doit pouvoir être implémenté facilement sur les ordinateurs et la logique discrète (DES utilise des opérations sur les bits comme les permutations qui sont très inefficaces dans une implémentation logicielle).
Fonctionnement
Madryga a rempli ses objectifs d'efficacité dans une implémentation logicielle : les seules opérations utilisées sont des XOR et des rotations. Les deux travaillent sur des octets. Madryga a une clé de taille variable, sans limite supérieure.
La spécification de Madryga prévoit huit tours mais ce nombre peut être incrémenté pour plus de sécurité si nécessaire. Il utilise un bloc de 24 bits et procède à un XOR entre un octet de la clé et l'octet de poids faible du bloc. Les deux autres octets du bloc subissent une rotation. Celle-ci dépend de la sortie du XOR. Ensuite, l'algorithme effectue une rotation vers la droite de un octet. De cette façon si Madryga travaille sur les octets 2,3 et 4, il s'occuperait des octets 3,4 et 5 après avoir effectué les rotations et les XOR.
Le key schedule est très simple. Un XOR entre la clé et une constante aléatoire de la même taille est effectué. Une rotation vers la gauche de 3 bits est appliquée. Après chaque tour, cette rotation sur le résultat clé/constante est appliquée à nouveau. La clé intermédiaire de chaque tour est obtenue grâce à l'octet de poids faible de cette combinaison. Le chiffrement s'effectue ainsi via un XOR entre l'octet de poids faible du bloc et l'octet de poids faible du registre circulaire contenant la clé.
Le déchiffrement consiste simplement en une utilisation inverse des opérations. Ceci est rendu possible grâce aux propriétés d'inversibilité du XOR.
Cryptanalyse
À première vue, Madryga semble plus faible que DES. Toutes les opérations de Madryga sont linéaires. DES utilise au moins des S-Boxes, composants non-linéaires dans le chiffrement qui furent mis à mal par la cryptanalyse linéaire et différentielle. Malgré la présence de rotations qui dépendent en partie des données, Madryga est toujours linéaire.
Le plus gros problème de Madryga est l'absence d'un effet avalanche (une modification en entrée ne va pas influencer tous les bits à la sortie). Ce défaut est provoqué par une taille de bloc insuffisante.
Eli Biham a procédé à une analyse informelle de l'algorithme. Il a remarqué que la « parité de tous les bits du texte clair et du texte chiffré est une constante qui dépend seulement de la clé. De cette façon, étant donné un texte en clair, vous pouvez établir la parité du texte chiffré ». La parité correspond ici à un XOR entre tous les bits d'une séquence.,
En 1995, Ken Shirrif présente une attaque différentielle qui nécessite 5 000 textes clairs choisis. Biryukov et Kushilevitz publient en 1998 une attaque différentielle améliorée qui ne nécessite que 16 textes clairs choisis. Leur démonstration va plus loin et montre que l'attaque peut être convertie entre une attaque par texte chiffré avec 212 textes chiffrés, sous des hypothèses favorables (redondances, par exemple du texte en français). Ce type d'attaque anéantit définitivement Madryga.
Liens externes
Références
- Alex Biryukov, Eyal Kushilevitz: From Differential Cryptoanalysis to Ciphertext-Only Attacks. CRYPTO 1998: 72-88
- W. E. Madryga, « A High Performance Encryption Algorithm », Computer Security: À Global Challenge, Elsevier Science Publishers, 1984, p. 557-570.
- Ken Shirriff, Differential Cryptanalysis of Madryga, unpublished manuscript, October 1995.