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 !
Aller plus loin
- L’annonce du NIST (168 clics)
- Le site de Keccak (675 clics)
- Justification succinte du choix par le NIST (fichier PDF) (524 clics)
- [LinuxFr.org] Nouvelles attaques sur SHA-1 (135 clics)
- [LinuxFr.org] Rugby et cryptographie : Shabal est en demi‐finale ! (182 clics)
# Le nom ?
Posté par Benoît Sibaud (site web personnel) . Évalué à 9. Dernière modification le 03 octobre 2012 à 14:13.
Keccak se prononcerait [kɛtʃak] comme "ketchak" (selon Wikipedia) ou "catch-ack" selon d'autres sources. Mais d'où vient ce nom ? Je pensais à du cyrillique au départ, mais apparement pas. Une symétrie jouant sur les formes du e et a ?
Il existe aussi Keccup (ketchup) reduced-round versions of Keccak par Guido Bertoni, Michaël Peeters et Gilles Van Assche. Cf http://www.hyperelliptic.org/DIAC/slides/PermutationDIAC2012.pdf
[^] # Re: Le nom ?
Posté par boubou (site web personnel) . Évalué à 6.
Le kecak est une danse de Bali et en Indonésien le c se prononce effectivement tch. Comme c'est une ancienne colonie des Pays-Bas, il y a peut être un lien. Mais deux c au milieu ça fait douter…
# Ordre de magnitude ?
Posté par Xavier Combelle (site web personnel) . Évalué à 7.
Ce ne devrait pas être ordre de grandeur plutôt ?
[^] # Re: Ordre de magnitude ?
Posté par patrick_g (site web personnel) . Évalué à 4.
Oui tu as raison. J'ai modifié la traduction.
[^] # Re: Ordre de magnitude ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à -2.
Magnitude (latin MAGNUS = grand) est grandeur, non ? J'ai du mal à saisir la nuance exprimée en substituant l'un à l'autre ?
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Ordre de magnitude ?
Posté par nerbrume . Évalué à 8.
"ordre de magnitude" est un anglicisme (an order of magnitude). Ordre de grandeur, c'est du francais.
[^] # Re: Ordre de magnitude ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à -2.
Magnitude, de l'anglais ? J'y voyais la composition du latin magn- (grand) et du suffixe français -itude (d'après atilf : suffixe formateur de substantifs abstraits de genre féminin désignant la qualité ou l'état exprimé par la base). D'où un substantif synonyme de grandeur.
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Ordre de magnitude ?
Posté par Larry Cow . Évalué à 1.
Magnitude est un mot français, mais qui ne veut pas dire la même chose. Chez nous, c'est plutôt lié à la luminosité (perçue) d'une étoile.
[^] # Re: Ordre de magnitude ?
Posté par barmic . Évalué à 2.
On l'utilise aussi pour parler de séisme.
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
[^] # Re: Ordre de magnitude ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à -3.
Et dans beaucoup de domaines où il est nécessaire de définir des grandeurs relatives. Bizarre…
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Ordre de magnitude ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à -1.
Non, ça c'est l'un de ses emplois les plus courants (donc assez rare également, il faut bien l'admettre). Ce n'est pas exclusif de son acception première qui reste extrêmement proche de son étymologie. Étymologie au demeurant fort simple — ceci expliquant sans doute cela — permettant à tout un chacun d'inférer son sens dans l'expression où il était employé.
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
[^] # Re: Ordre de magnitude ?
Posté par barmic . Évalué à 3.
Faut faire gaffe avec l’étymologie, une langue sa vie et le sens des mots peu évoluer, il suffit de voir le mot « pédérastre » (qui a donné l'insulte bien connue) pour s'en rendre compte.
Tous les contenus que j'écris ici sont sous licence CC0 (j'abandonne autant que possible mes droits d'auteur sur mes écrits)
[^] # Re: Ordre de magnitude ?
Posté par ǝpɐןƃu∀ nǝıɥʇʇɐW-ǝɹɹǝıԀ (site web personnel) . Évalué à -1. Dernière modification le 04 octobre 2012 à 12:21.
Absolument. En étant conscient, je me suis donc fendu d'un laïus justifiant en quoi, dans ce cas précis, l'emploi de l'étymologie pouvait paraître parfaitement adaptée. Et pas qu'à moi (heureusement) puisque, par exemple atilf retient comme sens premier du mot « importance ».
« IRAFURORBREVISESTANIMUMREGEQUINISIPARETIMPERAT » — Odes — Horace
# Traduction
Posté par NilugeKiWi . Évalué à 4.
[^] # Re: Traduction
Posté par Benoît Sibaud (site web personnel) . Évalué à 2.
Corrigé, merci.
# Éponge contre Merkle-Damgård
Posté par windu.2b . Évalué à 10.
Mis à part le fait que ça nous donne là un titre de série Z, quelqu'un pourrait nous en dire plus sur les différences entre ces 2 méthodes, et plus particulièrement celle de l'éponge, à la base de SHA-3 ?
Parce que j'ai beau essayer de lire l'article à ce sujet, je bite pas grand chose, en fait…
[^] # Re: Éponge contre Merkle-Damgård
Posté par Spack . Évalué à 2.
--> []
[^] # Re: Éponge contre Merkle-Damgård
Posté par DerekSagan . Évalué à -3.
C'est un truc de crypto-umpistes qui veulent relancer le combat Flamby contre Merkel-Sarkozy mais de façon plus discrète.
[^] # Re: Éponge contre Merkle-Damgård
Posté par calandoa . Évalué à 8.
J'y connais pas grand chose à la cryptographie mais les liens donnés sont assez clairs je trouve. Ça c'est du Merkle-Machin :
On prend le message de taille X, on le découpe en petits morceaux, et chaque petit morceau est trituré d'abord avec un vecteur d'init, puis avec la sortie de bouillie précédante autant de fois que le message est grand… et à la fin on prend juste la sortie.
Avec Bob l'éponge, on fait un peu la même chose au début (enfin le coup du xor sur une partie de la bouille précédente est précisé ici, alors que pour Merkle ça pourrait être un xor mais aussi autre chose, et dans un autre sens), mais à la fin on ne s'arrête pas et on continue à faire des itération pour produire des petits bouts de hash qu'on concatène.
Voilà, la crypto, c'est compliquée, mais avec un peu de hash on comprend beaucoup mieux.
[^] # Re: Éponge contre Merkle-Damgård
Posté par Al . Évalué à 2.
Pour l'amateur que je suis, il n'est pas évident que ça change énormément de choses au premier coup d’œil. Par exemple, on a le même problème si f a le malheur d'avoir des propriétés de linéarité. C'est la difficulté avec la cryptographie, du point de vue de l'utilisateur : souvent on comprend facilement comment ça s'implémente, au moins naïvement, mais on comprend rarement pourquoi ça marche plus ou moins dans tel ou tel cas.
# Bon travail
Posté par dsant69 . Évalué à 2.
Ce qui est remarquable, c'est (à priori) le sérieux avec lequel c'est réalisé : 5 ans. Et combien de contributeurs ?
Un développement fermé aurait pu faire faire le travail en 15 jours ! Et les données auraient été aussi bien protégées que les fichiers de Microsoft Office cryptés à une époque, ou avec certains sharewares gratuits.
# Ne concerne que les Etats-Unis ?
Posté par dsant69 . Évalué à 2. Dernière modification le 04 octobre 2012 à 17:01.
Ce choix ne concerne que les Etats-Unis ? Quel sont les conséquences administratives au US, et en Europe ?
[^] # Re: Ne concerne que les Etats-Unis ?
Posté par patrick_g (site web personnel) . Évalué à 9.
Le NIST est un organisme américain mais ses préconisations sont généralement suivies par tout le monde. Dans un sens ce n'est pas déconnant puisque l'évaluation a été effectuée par la communauté mondiale des cryptographes. D'ailleurs, comme pour AES, l'algo vainqueur a été conçu par des non américains ce qui tend à prouver qu'il n'y a pas de favoritisme.
On peut noter qu'entre 2000 et 2003 l'Europe avait elle aussi lancé un grand concours pour faire émerger des primitives cryptographiques. C'est le projet NESSIE. Le retentissement médiatique et l'adoption par les utilisateurs ont été bien moins forte que pour les compétitions NIST.
[^] # Re: Ne concerne que les Etats-Unis ?
Posté par calandoa . Évalué à 4.
Généralement, mais pas toujours … Par exemple, concernant la standardisation de Dual_EC_DRBG, un générateur de nombres (pas forcement) aléatoires: http://www.schneier.com/blog/archives/2007/11/the_strange_sto.html
En gros, le NIST a poussé pour standardiser un algorithme lent et sans intérêt proposé par la NSA, en expliquant certaines parties et en gardant le silence sur d'autres, alors que cet algo possédait une grosse faille de sécurité permettant, à partir des données passées sous silence, de facilement casser tout chiffrement basé sur ce générateur. En gros, le NIST a été plus ou moins accusé d'avoir promu une backdoor de la NSA.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.