RadioGatún

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

RadioGatún est une fonction de hachage cryptographique créée par Guido Bertoni, Joan Daemen, Michaël Peeters, et Gilles Van Assche. Elle a été présentée pour la première fois au second atelier du NIST sur la question (NIST Second Cryptographic Hash Workshop, à Santa Barbara en Californie, en août 2006, pour la compétition « NIST hash function competition ».

RadioGatún est construite à partir de la fonction Panama, une fonction de chiffrement de flux et d'empreinte cryptographique datant de la fin des années 1990 dont la fonction d'empreinte a été cassée, en en corrigeant les vulnérabilités.

RadioGatún est précisément une famille de 64 fonctions, qui se distinguent par un seul paramètre : la taille des mots - en bits (w), de 1 à 64. L'algorithme nécessite 58 mots de mémoire pour stocker son état interne, chacun de taille w. La version 32 bits nécessite donc 232 octets et la version 64 bits 464 octets.

Elle peut être utilisée comme fonction de hachage ou chiffrement de flux; elle peut générer une suite arbitrairement longue de nombres pseudo-aléatoires.

C'est l’ancêtre de la primitive cryptographique Keccak, gagnante du concours SHA-3[1].

Robustesse selon ses créateurs[modifier | modifier le code]

D'après les concepteurs, les premiers 19 × w bits (avec w la taille du mot paramétrés) de la sortie de RadioGatún's est une empreinte de qualité cryptographique. Autrement dit, les 608 et 1216 premiers bits pour les versions 32 et 64-bits respectivement peuvent être utilisés comme empreinte cryptographique.

En considérant l'attaque dite attaque des anniversaires (en référence au paradoxe des anniversaires), cela signifie que pour un mot de taille w, RadioGatún est conçue pour n'avoir pas d'attaque en dessous d'une complexité de 29.5w. Numériquement cela donne 2304 et 2608 pour les versions 32 et 64 bits respectivement.

Cryptanalyse[modifier | modifier le code]

Dmitry Khovratovich et Alex Biryukov ont trouvé deux attaques qui ne compromettent pas les affirmations des créateurs sur la sécurité de la fonction, l'une avec une complexité de 218w, l'autre avec une complexité de 223.1w[2]. Khovratovich aurait aussi trouvé [3] une attaque en 218w.

On recense aussi une attaque qui ne fonctionne que sur la version 1-bit, en 224.5 opérations[4]. Elle est moins efficace que les précédentes et n'est pas extensible aux autres tailles de mots.

La meilleure attaque connue (2015) est une attaque de complexité 211w[5]. La complexité est dans les bornes affirmées par les auteurs de la fonction.

Ceux-ci ont cependant affirmé que leurs expérimentations ne leur donnaient pas une grande confiance dans la solidité de la fonction[6].

Vecteurs de test[modifier | modifier le code]

Des vecteurs de tests pour les développeurs (des valeurs d'empreintes pour une entrée particulières) qui coderaient les fonctions sont disponibles pour les variantes 32 et 64-bit.

Ils sont constitués des 256 premiers bits de la sortie des fonctions (qui est arbitrairement long) : En 32 bits :

RadioGatun[32]("") =
F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117
RadioGatun[32]("The quick brown fox jumps over the lazy dog") = 
191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
RadioGatun[32]("The quick brown fox jumps over the lazy cog") = 
EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD 

En 64 bits :

RadioGatun[64]("") =
64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584
RadioGatun[64]("The quick brown fox jumps over the lazy dog") = 
6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
RadioGatun[64]("The quick brown fox jumps over the lazy cog") = 
C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5

Références[modifier | modifier le code]

  1. Bertoni, Guido ; Daemen, Joan ; Peeters, Michaël ; Van Assche, Gilles, « The Road from Panama to Keccak via RadioGatún » (consulté le 20 octobre 2009).
  2. Dmitry Khovratovich et Alex Biryukov, « Two attacks on RadioGatún »
  3. « Cryptanalysis of hash functions with structures »
  4. Charles Bouillaguet et Pierre-Alain Fouque, « Analysis of the Collision Resistance of RadioGatun using Algebraic Techniques »
  5. Thomas Fuhr et Thomas Peyrin, « Cryptanalysis of RadioGatun »
  6. « Keccak and the SHA-3 Standardization »

Liens externes[modifier | modifier le code]