Après quelques workshops préliminaires, le NIST (l'organisme de normalisation des standards et de la technologie aux USA) a donc décidé d'empoigner le taureau par les cornes et a annoncé le 23 janvier 2007 l'ouverture d'un processus de développement de nouveaux algorithmes de hashage standard.
Comme pour AES, la communauté cryptographique est donc invitée à proposer des algorithmes et parmi eux un ou plusieurs seront sélectionnés à l'issue du processus. Les digests de ces fonctions doivent supporter les tailles de 256, 384 et 512 bits (comme SHA-2 donc).
Si tout se passe bien le gagnant devrait être connu à la fin 2011.
PS : A noter qu'une autre primitive de hachage solide existe déjà : la fonction de hachage Whirlpool est sortie gagnante du processus de sélection européen NESSIE et est maintenant un standard ISO.
Aller plus loin
- L'annonce du NIST (6 clics)
- Collisions sur SHA-1 (6 clics)
- Annonce DLFP : SHA-1 aurait été cassé (7 clics)
- SHA-2 (2 clics)
- Whirlpool (35 clics)
# PAM ?
Posté par Sytoka Modon (site web personnel) . Évalué à 4.
[^] # Re: PAM ?
Posté par patrick_g (site web personnel) . Évalué à 3.
Konqueror, dans KDE, permet de vérifier les hashs par l'intermédiaire de Jackum et ce dernier est compatible avec Whirlpool (cf http://lwn.net/Articles/204457/ )
[^] # Re: PAM ?
Posté par Olivier Jeannet . Évalué à 7.
Et il paraît que le code est particulièrement propre...
[^] # Re: PAM ?
Posté par - - . Évalué à 3.
[^] # Re: PAM ?
Posté par Philippe F (site web personnel) . Évalué à 10.
--------> []
# collisions...
Posté par M . Évalué à 8.
Toutes fonctions de hachage possèdent des collisions : si la fonctions de hachage est sur n bits, sur 2^n + 1 contenu différent, et au moins 2 auront le même hash...
D'ailleurs meme le lien wikipedia donné le dit.
[^] # Re: collisions...
Posté par VoixOff . Évalué à 3.
[^] # Re: collisions...
Posté par newbix . Évalué à 8.
[^] # Re: collisions...
Posté par newbix . Évalué à 8.
En fait ce qui passe avec SHA-1, c'est qu'on a une méthode pour trouver des collisions plus efficacement que ça, donc on considère que SHA-1 est cassée. Mais en fait, l'algo est en 2^{63} (pour l'instant ...) donc ça reste hors de portée, et on a pas de collisions connues dans SHA-1. Par contre, on en a pour MD4 et MD5.
[^] # Re: collisions...
Posté par briaeros007 . Évalué à 2.
c'est pour ca que la limite de sécu est à 2^80 (enfin d'apres ce que me disais mon prof).
[^] # Re: collisions...
Posté par Aldoo . Évalué à 3.
(on m'a toujours dit dans les petites classes qu'une complexité algorithmique ne voulait rien dire si on ne précise pas en fonction de quelle dimension du problème elle s'exprime !)
# Mot compte double
Posté par feth . Évalué à 5.
Sinon, de façon générale, je trouve la nouvelle très intéressante, et me sens flatté d'y avoir compris quelque chose : il faudrait faire un petit effort sur le jargon peut-être... (essayez de faire lire ça à une de vos connaissances non geek ni cryptographe pour voir).
# NESSIE
Posté par Thomas Pornin . Évalué à 9.
Il y a beaucoup d'effervescence sur les fonctions de hachage actuellement, et pas mal de chercheurs qui bossent sur le sujet. On ne sait pas actuellement caractériser une fonction de hachage "solide" autrement que comme "on a tapé dessus mais on n'a pas réussi à la casser". Outre Whirlpool, il reste des choses comme SHA-256 et SHA-512 (aucune attaque, même théorique et embryonnaire), Tiger ou Panama. Whirlpool a l'insigne désavantage d'être plutôt lente, de l'ordre de la centaine de cycles d'horloge par octet traité, alors qu'un banal MD5 peut tourner à moins de 10 cycles par octet (et MD4 descend en dessous de 4, ce qui est outrageusement rapide).
[^] # Re: NESSIE
Posté par patrick_g (site web personnel) . Évalué à 3.
Quand au problème de rapidité l'article de wikipedia indique que Whirlpool est plus adapté aux processeurs 64 bits et qu'elle est très lente sur des machine 32 bits. En plus les nouveaux CPU ne savent pas quoi faire de tous leurs transistors et je pense qu'il va y avoir de plus en plus de modules hardware pour les primitives crypto. Si Whirlpool gagne la compétition NIST je te parie qu'elle sera gérée "en dur" dans les futurs processeurs.
[^] # Re: NESSIE
Posté par Thomas Pornin . Évalué à 10.
gcc version 4.1.2 20060928 (prerelease) (Ubuntu 4.1.1-13ubuntu5)
Ça donne ça :
- En mode AMD64, ça tourne à 61 cycles par octet traité.
- En mode i386, sur la même machine, ça fait du 116 cycles par octet.
Donc oui, c'est optimisé 64 bits : le passage de 32 à 64 bits double quasiment les performances. Par comparaison, pour MD4, le passage de 32 à 64 bits ne gagne même pas 1% en vitesse, parce que le 32 bits lui suffit, et il n'a que faire de registres plus grands ou plus nombreux. Mais Whirlpool reste lent : mon Sempron utilisé à plein régime fait du 26 Mo/s, ce qui n'est même pas suffisant pour suivre le disque dur (et c'est en supposant que 100% du cpu est dédié à la tâche). MD4 tape au-delà des 450 Mo/s, ce qui est tout de même mieux. Il y a probablement un "juste milieu" entre un MD4 hyper-rapide et cassé, et un Whirlpool pas cassé mais lent.
Ces mesures marchent aussi bien avec mon code à moi qu'avec le code de référence de Whirlpool, code de référence qui est celui repris tel quel dans le noyau Linux. Il n'y a pas 36 manières d'optimiser un Whirlpool sur PC... Et vues les primitives utilisées, il n'y a pas de raison particulière pour qu'un passage en assembleur optimisé à la main permette de gagner plus que les 5 à 30% qu'on constate usuellement.
Pour ce qui est des implémentations matérielles de Whirlpool, je suis un peu sceptique. L'AES lui-même a été publié en 2001 et il n'y a pas beaucoup de plateformes qui offrent une implémentation matérielle de l'AES. Il y a visiblement des délais assez longs dans l'industrie des microprocesseurs.
Quant à l'aspect dérivé de l'AES, disons qu'il fait débat. Whirlpool est fondé sur un algorithme de chiffrement par blocs, nommé "W" (rien à voir avec un président américain), dont la structure est une version étendue de Rijndael, c'est-à-dire l'AES. Mais W est utilisé dans le mode usuel pour faire une fonction de hachage, c'est-à-dire en faisant rentrer le message en tant que clé. L'AES n'a pas été évalué pour ce mode d'utilisation ; dans le jargon des cryptographes, une collision sur Whirlpool serait une paire de "clés liées" pour W, et on ne sait pas grand chose sur les clés liées de l'AES. Ce n'est pas une propriété intéressante à étudier pour un algorithme de chiffrement utilisé simplement en mode chiffrement.
En bref, Whirlpool est un concept intéressant, et une fonction à surveiller, mais ce n'est pas la panacée et il y a encore beaucoup à inventer dans le domaine des fonctions de hachage.
[^] # Re: NESSIE
Posté par patrick_g (site web personnel) . Évalué à 2.
Les processeurs VIA => http://www.via.com.tw/en/initiatives/padlock/hardware.jsp
Y'a un module crypto hardware qui fait du AES + SHA-1/SHA-256 + RSA + PRNG
Sinon pour les processeurs plus classiques est-ce que les nouvelles instructions vectorielles SSE4 des futurs Intel pourront servir pour accelerer les primitives de crypto ?
Je suis allé voir là http://en.wikipedia.org/wiki/SSE4 mais je ne m'y connais pas assez pour pouvoir en déduire quoi que ce soit.
Sinon merci pour l'explication sur la fonction W et le lien avec AES. C'est très intéressant et je comprends mieux pourquoi on ne peut pas déduire grand chose au point de vue sécurité du fait que Whirlpool se base sur AES.
[^] # Re: NESSIE
Posté par Thomas Pornin . Évalué à 3.
L'exemple typique est SHA-512. L'implémentation de SHA-512 dans OpenSSL est en C, mais, quand elle tourne sur un processeur disposant du jeu d'instruction SSE2, alors elle commute automatiquement vers une implémentation en assembleur utilisant à fond le SSE2. SHA-512 fait des additions, des rotations, et des opérations booléennes bit à bit sur des mots de 64 bits, ce qui est pile-poil dans ce que SSE2 permet de faire. Le gain est impressionnant : ça fait passer SHA-512 de 20 à plus de 80 Mo/s sur la même machine. On ne retrouve pas ce gain en AMD64, car alors les registres "standard" sont en 64 bits et sont en nombre suffisant pour faire le boulot.
Pour Whirlpool, c'est moins clair. Une phase de Whirlpool est exprimée, mathématiquement, comme un ensemble de transformations (dont certaines linéaires) dans un espace vectoriel de dimension 8 sur un corps GF(256). C'est très en dehors de ce que les processeurs savent faire "nativement". Ça s'implémente efficacement en faisant des accès à des tables précalculées : grosso-modo, il faut, pour chaque mot de 64 bits, le découper en huit octets, faire un accès indexé par chacun de ces octets dans huit tables, et faire un XOR des résultats (chaque table -- il y en a 8 -- contient 256 entrées de 64 bits). Il y a 16 mots d'état de 64 bits dans un Whirlpool, et il faut faire ça 10 fois, donc 1280 accès à une table pour un bloc de données (un bloc = 64 octets). À peu près tout le coût d'un Whirlpool est concentré dans ces accès, soit 20 accès par octet en entrée.
Tout ça pour dire que les capacités de calcul de SSE ne seront pas exploitées par Whirlpool ; et il n'y a pas, à ma connaissance, d'opcode SSE (même dans SSE4) pour accéder à une table en mémoire selon un index stocké dans un registre SSE. Il faudra faire une partie du traitement dans les registres entiers usuels. On peut imaginer que les registres SSE serviraient pour le XOR des sorties des tables ; il faudrait que je me penche sur la question sérieusement. À froid, je peux imaginer un gain, mais relativement faible, pour l'usage de SSE2 par rapport à une implémentation 32 bits "simple". Mais SSE4 n'apportera rien en lui-même (par rapport à SSE2), et tous ces gains disparaissent si on passe en mode AMD64 (et les processeurs sachant faire du SSE4 sauront probablement faire aussi de l'AMD64, donc on aurait tort de se priver).
Je ne sais pas si l'usage du SSE est posible dans le noyau Linux. Dans le temps, on ne pouvait pas utiliser la FPU dans le noyau. Ça pourrait simplifier la question.
Usuellement, les cryptographes travaillent dans l'autre sens : ils observent l'existence de nouveaux opcodes, et ils se demandent comment s'en servir pour inventer de nouvelles fonctions qui en profiteront.
[^] # Re: NESSIE
Posté par ouah (site web personnel) . Évalué à 3.
> Linux. Dans le temps, on ne pouvait pas utiliser la FPU dans le
> noyau. Ça pourrait simplifier la question.
L'usage du SSE comme du FPU sont disablés à la compilation du kernel pour éviter l'overhead dû au sauvage des registres. Maintenant on peut utiliser du code assembleur SSE dans le code du noyau en prenant les mesures de précaution adéquates comme par exemple en n'oubliant pas de désactiver
la préemption lorsque le code SSE est exécuté.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.