En 2007, le NIST (National Institute of Standards and Technology) a lancé une compétition internationale pour choisir une fonction de hachage de nouvelle génération.
Les attaques sur SHA-1 avaient généré une certaine inquiétude et les experts pensaient que la famille SHA-2 (SHA-256, SHA-384, SHA-512) serait menacée à plus ou moins longue échéance. Cela a donc conduit à l’organisation d’une compétition SHA-3 sur le modèle de celle ayant conduit à la sélection de l’algorithme de chiffrement AES.
Plus de 64 propositions ont été reçues et soumises, au fil des années, aux tentatives de cassages de la communauté cryptographique mondiale. Cette longue compétition vient enfin de s’achever puisque le NIST a désigné Keccak comme l’algorithme gagnant. Ce dernier devient donc officiellement SHA-3.
Plus de détails dans la suite de la dépêche.
La compétition organisée par le NIST a duré plusieurs années et a pris la forme d’une course d’obstacles, avec élimination des algorithmes les plus faibles à chaque étape. De 64 candidats à l’origine (voir le SHA-3 Zoo) le nombre a très vite été réduit à 25 après élimination des algorithmes fantaisistes ou facilement cassables. En 2009, le round 2 a ensuite éliminé 11 autres candidats et les 14 survivants ont eu la possibilité d’apporter des modifications mineures à leur mode de fonctionnement (voir le fichier SHA-3 round 2 tweaks).
En décembre 2010, le round 3 a réduit la liste à 5 finalistes : BLAKE, Grøstl, JH, Keccak et Skein. Dans cette dernière ligne droite, les équipes de cryptanalyse du monde entier ont cherché à « casser » les candidats, ainsi qu’à évaluer leur rapidité (en mode logiciel ou bien dans une implémentation matérielle).
Bruce Schneier, un des auteurs de l’algorithme candidat Skein, a écrit une publication sur son blog il y a quelques jours, afin de faire connaître son avis juste avant la décision du NIST. Selon lui, cette compétition, bien qu’intéressante, s’est révélée un peu prématurée. Après les doutes et les percées cryptographiques sur SHA-1, il s’avère que SHA-2 a bien résisté à l’épreuve du temps.
Nous sommes en 2012 et SHA-512 continue à sembler solide.
Encore pire, aucun des candidats SHA-3 n’est significativement meilleur. Certains sont plus rapides, mais on ne gagne pas des ordres de grandeur en rapidité. Certains sont plus petits, pour les implémentations matérielles, mais là encore on ne gagne pas des ordres de grandeur. Quand SHA-3 sera annoncé, et à moins que les avantages soient vraiment critiques pour leurs applications, je recommanderai aux gens de continuer à utiliser le bon vieux SHA-512. Au moins pour un moment.
Même si, selon Bruce Schneier, aucun candidat ne sortait vraiment du lot, Keccak a finalement été choisi par le NIST comme l’algorithme de hachage de nouvelle génération SHA-3. Selon le document justificatif préliminaire (un rapport complet sera publié ultérieurement), il semble que le choix se soit effectué surtout sur la conception de Keccak. Même si d’autres concurrents étaient plus rapides, Keccak se base sur une toute nouvelle méthode (les fonctions éponges) pour construire l’algorithme. Alors que MD5, SHA-1 et SHA-2 se basent sur la très classique construction de Merkle‐Damgard, le fait de se baser sur une autre idée apporte certains bénéfices :
Keccak complémente bien la famille des algorithmes de hachage SHA-2. Le NIST reste confiant dans la sécurité de SHA-2, qui est maintenant largement répandu. Ces algorithmes SHA-2 continueront à être utilisés dans un futur prévisible, comme indiqué dans la déclaration de principe du NIST.
Un des avantages de Keccak, en tant que vainqueur de la compétition SHA-3, est le fait que son design et les propriétés de son implémentation sont très différents par rapport à SHA-2. Il semble très peu probable qu’une nouvelle approche ou une attaque cryptanalytique innovante puissent menacer simultanément les deux algorithmes. De la même manière, les propriétés très différentes des deux algorithmes vont permettre aux concepteurs de protocoles et d’applications de profiter d’une plus grande flexibilité, puisqu’ils pourront choisir celui des deux algorithmes qui répond le mieux à leurs besoins.
Le fait qu’à l’heure actuelle SHA-3 soit considéré comme seulement « complémentaire » de SHA-2 va probablement ralentir sa montée en puissance. Il faudra sans doute attendre que les concepteurs de puces proposent des instructions spécialement adaptées pour que son utilisation se répande réellement.
En dépit de ces réserves, et même si on peut imaginer sa déception à la suite de la non sélection de Skein, Bruce Schneier a été beau joueur :
C’est un bon choix. Je suis content que SHA-3 ne ressemble en rien à la famille SHA-2. Il est bon d’avoir quelque chose de complètement différent.
Félicitations à l’équipe Keccak. Félicitations — et merci — au NIST pour avoir organisé cette intéressante et agréable compétition de façon très professionnelle. Tout ce processus a augmenté de manière significative notre compréhension de la cryptanalyse des fonctions de hachage.
Enfin, on notera un point amusant. L’un des concepteurs de Keccak n’est autre que Joan Daemen, l’un des pères de l’algorithme de chiffrement AES. Ce cryptographe belge travaillant pour STMicroelectronics peut donc se targuer d’être à l’origine de deux des plus importantes primitives cryptographiques modernes !
