title: Khufu et Khafre
text: # 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).
  
  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^{43}$ et $2^{43}$ textes clairs choisis sont nécessaires (Gilbert et Chauvaud, 1994). Il faut $2^{32}$ 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^{18}$ 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 $2^{38}$ textes clairs connus. De manière similaire, 24 tours peuvent être attaqués avec $2^{53}$ textes clairs choisis ou $2^{59}$ textes clairs connus.
  
  