Nouvelles fonctions de hachage

Posté par  (site web personnel) . Modéré par rootix.
Étiquettes :
0
26
jan.
2007
Sécurité
Après la découverte par l'équipe de Wang de collisions dans SHA-1, une des fonctions de hachage standard, c'est un peu le nouveau buzz du moment dans le petit monde de la cryptographie. On suspecte SHA-2 de plus n'être plus aussi sécurisé qu'on a pu le croire et on se demande si on a vraiment une idée pour construire un algorithme de hachage suffisamment solide.

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

  • # PAM ?

    Posté par  (site web personnel) . Évalué à 4.

    La question que l'on se pose tous, les hash Whirlpool sont-ils pris en charge par LDAP et les modules d'authentification pam ?

    • [^] # Re: PAM ?

      Posté par  (site web personnel) . Évalué à 3.

      j'sais pas mais ce que je sais c'est que l'algo a intégré le noyau Linux y'a un paquet de temps (dans le 2.6.9 cf http://lwn.net/Articles/107010/ )

      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  . Évalué à 7.

        l'algo [de hachage Whirlpool ] a intégré le noyau Linux

        Et il paraît que le code est particulièrement propre...

    • [^] # Re: PAM ?

      Posté par  . Évalué à 3.

      sans humour : c'est exactement la question que je me suis posé.

      • [^] # Re: PAM ?

        Posté par  (site web personnel) . Évalué à 10.

        Moi je me demandais plus si elle integrait un programme laine et un programme chemise en plus des programmes classiques blanc et syntehtique ?

        --------> []

  • # collisions...

    Posté par  . Évalué à 8.

    après la découverte par l'équipe de Wang de collisions dans SHA-1,
    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  . Évalué à 3.

      Il me semble que le problème concerne surtout la possibilité de fabriquer un message arbitraire dont le hash serait identique à un message de référence à un coût relativement faible (très inférieur au coût d'une recherche exhaustive).

      • [^] # Re: collisions...

        Posté par  . Évalué à 8.

        Ça c'est un autre problème que les collisions, on appelle ça la seconde préimage. C'est effectivement quelque chose qui serait beaucoup plus grave en pratique, parce que les collisions, finalement, on ne sait pas en faire grand chose... (c'est bien pour ça qu'on continue d'utiliser MD5). Mais c'est aussi une attaque beaucoup plus dure à construire, et il a très peu de fonctions de hachage qui sont cassées à ce point (à ma connaissance, seulement MD2, et avec une complexité en 2^{102} — en tout cas, ni MD4, ni MD5, ni les SHA).

    • [^] # Re: collisions...

      Posté par  . Évalué à 8.

      Oui, tout à fait. Mais à prirori, il faut essayer 2^{n/2} messages différents avant de trouver une collision (grace au paradoxe des anniversaires), et ça n'est pas faisable en pratique (on choisit n suffisament grand). Dans certaines preuves de sécurités, on suppose qu'il est impossible de trouver une collision dans la fonction de hachage utilisé, même si on sait qu'il en existe.

      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  . Évalué à 2.

        donc ça reste hors de portée > pour la plupart d'entre nous oui, mais pas forcément pour certains centre de calcul gouvernementaux ;)
        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  . Évalué à 3.

        « n » est le nombre de bits du hash, je suppose. Cela ne se devine pas tout seul si on n'a pas le nez quotidiennement dans les preuves de complexité cryptographique !

        (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  . Évalué à 5.

    "On suspecte SHA-2 de plus n'être plus aussi ..."
    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  . Évalué à 9.

    Notons quand même que Whirlpool est sortie "gagnante" du processus NESSIE essentiellement parce que c'était la seule fonction de hachage soumise. À vaincre sans péril, on triomphe sans gloire...

    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  (site web personnel) . Évalué à 3.

      Est-ce que le fait que Whirlpool soit basé sur AES ne renforce pas la confiance que l'on peut avoir en elle ?

      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  . Évalué à 10.

        Pour les performances, j'ai fait quelques essais sur un Athlon Sempron 3000+, en mode AMD64, sous Linux (Ubuntu 3.10). Le compilateur C est annoncé comme :

        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  (site web personnel) . Évalué à 2.

          C'est certain que ça va prendre des années pour que les CPU suivent mais on en trouve déjà !

          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  . Évalué à 3.

            Les instructions SSE* peuvent aider pour certains algorithmes de crypto ; surtout ceux qui manipulent des mots de 64 bits et font des opérations arithmétiques et logiques avec ces mots. L'effet est surtout sensible en mode 32 bits.

            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  (site web personnel) . Évalué à 3.

              > 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.

              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.