Khufu et khafre

Khufu et Khafre
La pyramide de Khéops (Khufu)
Résumé
Concepteur(s)	Ralph Merkle
Première publication	1990
Dérivé de	Inconnu
Chiffrement(s) basé(s) sur cet algorithme	Inconnu
Caractéristiques
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
cryptanalyse différentielle, attaque boomerang

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).

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 26 mars 1991. 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 2⁴³ et 2⁴³ textes clairs choisis sont nécessaires (Gilbert et Chauvaud, 1994). Il faut 2³² 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 2¹⁸ 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édifinies 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 2³⁸ textes clairs connus. De manière similaire, 24 tours peuvent être attaqués avec 2⁵³ textes clairs choisis ou 2⁵⁹ 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)

• Portail de la cryptologie