Khufu et Khafre
Khufu et Khafre sont deux algorithmes de chiffrement par bloc développés par Ralph Merkle en 1989 alors qu'il travaillait pour le compte de Xerox au centre de recherche de Palo Alto. Tout comme Snefru, une fonction de hachage cryptographique, ces chiffrements portent les noms des pharaons égyptiens Khéops (Khufu), Snéfrou (Snefru) (pÚre de Khéops) et Khéphren (fils de Khéops).
| Concepteur(s) | Ralph Merkle |
|---|---|
| PremiĂšre publication | 1990 |
| Dérivé de | Inconnu |
| Chiffrement(s) basé(s) sur cet algorithme | Inconnu |
| Taille(s) du bloc | 64 bits |
|---|---|
| Longueur(s) de la clé | 512 bits (Khufu), 64*n bits (Khafre) |
| Structure | réseau de Feistel |
| Nombre de tours | 16 (Khufu), 8*n bits (Khafre, selon la clé) |
Meilleure cryptanalyse
Xerox transmit volontairement Khufu et Khafre Ă la NSA avant de les diffuser. La NSA demanda Ă Xerox de ne pas publier les algorithmes pour des raisons de sĂ©curitĂ© nationale. Xerox, travaillant souvent avec le gouvernement, accĂ©da Ă cette requĂȘte. Toutefois, une des personnes chargĂ©es de relire les spĂ©cifications, John Gilmore, envoya le document sur sci.crypt contre la volontĂ© de Merkle. L'algorithme fut de ce fait officiellement publiĂ© en 1990 Ă la confĂ©rence CRYPTO.
Khufu et Khafre ont été brevetés par Xerox le . Les deux algorithmes ont été optimisés pour du 32 bits
Khufu
Khufu utilise un bloc de 64 bits et une clĂ© de 512 bits ce qui fait de lui une exception dans ce domaine (la plupart des chiffrements, mĂȘme les plus rĂ©cents comme AES, utilisent 128 ou 256 bits). La majoritĂ© du contenu de la clĂ© permet de remplir les S-Boxes utilisĂ©es par le chiffrement pour les substitutions. Cette gĂ©nĂ©ration de tables est lourde et Khufu n'est pas destinĂ© au chiffrement de petits volumes de donnĂ©es.
Khufu est basé sur un réseau de Feistel avec 16 tours par défaut (le chiffrement accepte des multiples de 8 entre 8 et 64). Un groupe de 8 tours est nommé octet, à ne pas confondre avec l'unité informatique de 8 bits. Pour chaque octet, une autre table de substitution est utilisée. Dans un tour, les 8 bits de poids faible de la moitié du bloc (32 bits) sont transmis à la S-Box de 8x32 bits. La sortie de la boßte est ensuite combinée à l'aide d'un XOR avec l'autre moitié de 32 bits provenant du bloc. La moitié de gauche subit ensuite une rotation de 8 bits et les moitiés sont échangées. Au début et à la fin de l'algorithme, une partie de la clé est combinée via un XOR avec le bloc. Pour le reste du chiffrement, les données issues de la clé sont présentes dans les tables de substitution.
Cryptanalyse
Il existe une attaque diffĂ©rentielle de 16 tours contre Khufu qui permet de retrouver la clĂ© secrĂšte. La complexitĂ© de l'attaque en temps est de l'ordre de 243 et 243 textes clairs choisis sont nĂ©cessaires (Gilbert et Chauvaud, 1994). Il faut 232 textes clairs pour distinguer des donnĂ©es chiffrĂ©es d'un flot alĂ©atoire. Une attaque boomerang peut ĂȘtre employĂ©e dans le cadre d'une attaque adaptive avec des textes en clair/chiffrĂ© choisis. Il faut 218 requĂȘtes et une complexitĂ© en temps similaire pour mener cette attaque conçue par David Wagner. Khufu peut aussi ĂȘtre attaquĂ© grĂące Ă la cryptanalyse par diffĂ©rentielles impossibles, Eli Biham a montrĂ© comment casser 18 tours de la sorte en 1999.
Khafre
Khafre est similaire à Khufu mais utilise des S-Boxes prédéfinies et ne les calcule pas à partir de la clé. Ceci rÚgle le problÚme de Khufu dans le cadre des opérations de chiffrement fréquentes, il a une bonne "agilité de clés". Cependant, Khafre a besoin de plus de tours pour offrir un niveau de sécurité comparable à celui de Khufu ce qui le rend plus lent pour les gros volumes. Khafre utilise une clé dont la longueur est un multiple de 64 bits. Les substitutions ne dépendant pas de la clé, des sous-clés sont utilisées tous les huit tours.
Cryptanalyse
La cryptanalyse diffĂ©rentielle s'est avĂ©rĂ©e efficace contre Khafre : 16 tours peuvent ĂȘtre cassĂ©s si l'on dispose de 1500 textes clairs choisis ou 238 textes clairs connus. De maniĂšre similaire, 24 tours peuvent ĂȘtre attaquĂ©s avec 253 textes clairs choisis ou 259 textes clairs connus.
Références
- Eli Biham, Alex Biruykov, Adi Shamir « Miss in the middle attacks on IDEA, Khufu and Khafre », Fast Software Encryption '99, LNCS.
- Eli Biham, Adi Shamir: Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer. CRYPTO 1991: 156-171
- Henri Gilbert, Pascal Chauvaud: A Chosen Plaintext Attack of the 16-round Khufu Cryptosystem. CRYPTO 1994: 359-368
- R C Merkle, « Fast Software Encryption Functions », in Advances in Cryptology - Crypto'90, Lecture Notes in Computer Science, No 537, A J Menezes, S A Vanstone (eds), Springer-Verlag 1991, p. 476â501
- [B. Schneier and J. Kelsey, Unbalanced Feistel Networks and Block Cipher Design Fast Software Encryption, Third International Workshop Proceedings (February 1996), Springer-Verlag, 1996, pp. 121â144.
- David Wagner: The Boomerang Attack. Fast Software Encryption 1999: 156-170
Liens externes
- (en) Fast Software Encryption Functions papier original de Ralph Merkle (1990)