La compétition SHA-3 du NIST : où en est-on ?

Le 31 octobre 2008, le National Institute of Standards and Technology a clôturé son appel à candidature pour la standardisation de SHA-3. Mais depuis, aucune information n'a été publiée. Où en est-on exactement ?

Les fonctions de hachage cryptographiques sont des briques fondamentales de la cryptographie. Elles permettent notamment de vérifier l’intégrité de données (dans les paquets réseaux, pour les « packages » distribués et installés sous certains OS), de stocker les mots de passe de manière sécurisée, etc.

Nécessité d’un processus de standardisation

Le NIST (National Institute of Standards and Technology) est une agence gouvernementale américaine ayant pour vocation la promotion et le développement, notamment, de standards technologiques. Dans le domaine de la cryptographie, le NIST est à l’origine de la standardisation de l’AES (Advanced Encryption Standard), un algorithme de chiffrement symétrique par blocs aujourd’hui largement adopté et utilisé [1]. L’avantage d’un processus de standardisation est de soumettre différents algorithmes aux spécialistes du domaine, ces derniers devant éprouver leur robustesse aux différentes attaques de l’état de l’art. La « cryptographic hash algorithm competition » a ainsi pour objectif la standardisation de SHA-3, successeur des fonctions MD5, SHA-1 et autres fonction de hachage actuellement utilisées sans toutefois avoir le statut de standards. Celles-ci ont en effet révélé des faiblesses ces dernières années, par exemple pour MD5 pour laquelle il est aujourd’hui trivial de trouver des collisions.

Détails sur le processus de soumission

La compétition a été ouverte le 2 novembre 2007, la date limite des soumissions étant fixée au 31 octobre 2008. Le NIST a fourni des spécifications très détaillées sur ce qui doit être soumis [2] : • Spécifications et sécurité : hormis les spécifications détaillées de l’algorithme, les candidats doivent détailler chaque point de sécurité qu’ils revendiquent. Le minimum requis est un algorithme résistant aux attaques classiques (collisions, première et seconde pré-image, multi-collisions …).• Codes source et performances : le NIST a fourni une plate-forme de référence précise sur laquelle est testé le code de référence fourni par les candidats. En plus du code de référence, les candidats sont invités à fournir des codes source optimisés pour les plate-formes 32 et 64 bits. Les codes optimisés sont testés grâce à l’outil eBash [3], qui est un outil de tests automatisés. Le NIST demande aussi de fournir une estimation des performances de l’algorithme en implémentation hardware (FPGA, carte à puce …).• Vecteurs de test : chaque candidat doit fournir un ensemble de vecteurs de test (i.e. les sorties de l’algorithme pour des entrées déterminées) qui servira de référence aux futures implémentations. Il faut noter que le strict respect des spécifications du NIST est de rigueur puisque le moindre oubli peut valoir un rejet de candidature. Les deux principaux critères de sélection des candidats seront la sécurité et la performance tant au niveau software que hardware. A noter qu’il n’est pas exclu qu’il y ait plus d’un candidat qui sorte vainqueur de la compétition.

Quoi de neuf depuis le 31 octobre ?

Depuis la fin de la soumission, le NIST n’a rien communiqué. La période de vérification des candidatures peut prendre un à deux mois, ce qui nous amène à courant décembre pour une publication de la liste des candidats jugés « valides ». Cela n’a pas empêché certaines équipes de cryptologues de rendre publique leur candidature. Le site [4] recense d’ailleurs les 28 candidats déclarés à ce jour alors que la rumeur fait état d’une soixantaine de candidatures déposées auprès du NIST. Parmi les candidats déclarés, le niveau des soumissions est très hétérogène. Certaines soumissions ont d’ailleurs déjà été cryptanalysées (au moins 6 candidats sont considérés comme faibles). D’autres sont au contraire déjà pré-senties comme finalistes, du fait notamment de la notoriété de leurs auteurs :

MD6 [5], fonction de hachage de Rivest et al. (Rivest était déjà à l’origine de MD5).
Skein [6], élaborée par Shneier et al.
Grœstl [7], soumis par Knudsen et al.

La suite ?

De manière officielle, la présentation des candidats au premier tour sera faite lors d’une conférence au second trimestre 2009, et la liste des candidats validés ne saurait tarder. Une année après (second trimestre 2010), les cryptanalyses sur les candidats seront résumées lors d’une autre conférence. Le troisième trimestre 2010 marquera alors la sélection des finalistes de la compétition. Après d’éventuelles modifications des algorithmes, les candidats seront figés dans leur version finale fin 2010. Ce n’est que début 2012 qu’aura lieu la dernière conférence de la compétition, suivie de l’annonce du ou des choix de SHA-3 au second trimestre. Ryad Benadjila, ingénieur en sécurité

Références :

[1] http://fr.wikipedia.org/wiki/Standard_de_chiffrement_avanc%C3%A9[2] http://csrc.nist.gov/groups/ST/hash/sha-3/Submission_Reqs/index.html[3] http://bench.cr.yp.to/ebash.html[4] http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo[5] http://groups.csail.mit.edu/cis/md6/[6] http://www.skein-hash.info[7] http://www.groestl.info