Comments on Les fonctions de hachage, c'est génial

Ruxor (2014-12-25T22:09:27Z)

@Martin: Si la fonction de hachage est bonne, elle résiste aux attaques par collision, c'est-à-dire qu'on ne sait pas fabriquer deux messages distincts quelconques ayant le même haché, quel que soit leur contenu (et a fortiori pas si l'un doit commencer par ALICE et l'autre par BOB). Dans le cas de MD5, on n'a plus cette résistance, mais les différentes fonctions SHA-2 résistent encore. (« Résister » veut dire qu'on ne sait pas attaquer la fonction autrement que par force brute, la force brute étant l'attaque idiote qui marche toujours mais qui coûte beaucoup.)

Martin (2014-12-25T11:45:37Z)

Et le cas d'Alice qui aurait trouvé deux messages : "ALICE blablabla ldkgjd lgjldgjlf3453524" et "BOB lj lsjflfjlsf skld2342342242" de même haché. Est-ce si improbable ? (si Bob décide que le nom contenu dans le message est le vainqueur, Alice envoie à Bob le premier message, sinon elle envoie le deuxième message)

simple-touriste (2013-02-01T00:25:51Z)

> de celui qui a calculé le haché

Mais pas forcément de celui qui a fait la publication du hash que la plupart des gens auront vu.

> au moins d'une personne, c'est surtout ça qui est important

Souvent il est surtout important de savoir qui l'a énoncé en premier, je pense que ça peut en piéger quelque uns.

Si on veut être reconnu il faut inclure son nom dans le message :

"moi, Grotexdick, j'ai découvert un moyen de construire la quadrature du cercle que voici : …"

Bien sûr "découvrir" peut consister à faire un copier-coller de ce qu'a écrit une personne quelconque (qui peut être la même personne), mais on peut ainsi dater ce copier-coller. Le hash ne prouve pas que l'affirmation est vraie, juste qu'elle a été exprimée. (Donc si l'affirmation est de la forme "Je suis capable d'exprimer l'affirmation suivante : …" cela prouve que l'affirmation est vraie.)

<hr>

> on ne sait pas faire des bonnes fonctions de hachage, alors qu'on sait faire des bons block ciphers

Pour une bonne explication de la différence entre chiffrement et hachage, voir la réponse de Thomas Pornin à la question "Why AES is not used for secure hashing, instead of SHA-x?"

http://security.stackexchange.com/a/8064/5133

> Bon, la plupart des usages de la fonction de hachage n'ont rien à faire du fait qu'elle soit extensible, mais dans certains cas ça peut être un problème.

Pour être tranquille il faut utiliser HMAC(h) au lieu de seulement h, ce qui annule ces équations.

Ruxor (2013-01-31T18:15:59Z)

@simple-touriste: de celui qui a calculé le haché (et donc au moins d'une personne, c'est surtout ça qui est important).

simple-touriste (2013-01-31T16:36:55Z)

" que le document était bien connu au moment où le haché a été révélé. "

Connu de qui?

A.Smith (2005-09-09T09:42:13Z)

Cher Monsieur,
bravo pour votre article pédagogique et enthousiaste qui a eu le succès qu'il mérite auprès de vos correspondants.
Newton a usé d'une méthode proche (dans la mémétosphère) en adressant à Leibniz la terrifiante anagramme 6accdae13eff7i3l9n4o4qrr4s8t12ux
pour s'assurer la priorité de la découverte du théorème fondamental du calcul différentiel et intégral. Dans le cas bien improbable où vous ou un lecteur ne connaîtrait pas cette anecdote, voici un lien
http://www.mathpages.com/home/kmath414.htm

En vous souhaitant des jours heureux et studieux,je reste

votre dévoué A.Smith.

bidibulle (2005-09-02T21:42:47Z)

Et pourquoi ne vas tu pas la?

<URL: http://www.commentcamarche.net/ >

Ruxor (2005-08-31T23:34:29Z)

Stranger → Je n'ai pas de réponse vraiment satisfaisante, mais il y a des *Que sais-je* qui sont très bien (notamment celui sur Internet), et il y a aussi d'excellents articles sur la Wikipédia.

Stranger (2005-08-31T19:00:16Z)

Puisqu'on en est là, je me permets de demander à Ruxor et aux lecteurs de ce blog s'ils peuvent m'indiquer un ouvrage qui explique de façon pas trop compliquée (je suis un béotien) mais tecnique et non totalement vulgarisée quand même comment s'architecture un ordinateur depuis les O et les 1 du circuit jusqu'aux langages élaborés, en passant par le langage machine, etc. Et le cas échéant, un autre ouvrage qui expliquerait, pareil, de façon accessible, quelles sont les strates entre la toile, le réseau, etc… J'en ai assez d'avoir l'impression de faire des incantations magiques que je ne comprends pas. Merci beaucoup.

Ruxor (2005-08-30T15:38:47Z)

Tiens, tu n'as pas tort, Nick. On va admettre cette réponse… voilà.

Nick (2005-08-30T13:02:47Z)

Je proteste contre ton site d'enigmes. A la question:
"The more it dries the wetter it gets."

Je reponds "cloud", qui est une reponse correcte et il
refuse obstinement d'augmenter mon score. J'ai reeassaye plusieurs fois.

Je suis sur qu'il y a un bug dans la fonction de hachage que tu utilises!

Tofas (2005-08-30T12:51:16Z)

Post très instructif, merci beaucoup !

Ruxor (2005-08-29T16:06:52Z)

Gilles & Nicky → J'aurais dû préciser plus clairement que je parlais là des fonctions de hachage de type « cryptographique[ment fortes] », qui se rapprochent certes des fonctions de hachage de type « rapides et petites (mais faibles) » qu'on utilise dans les tables de hachage (au moins, la plupart). Les fonctions de hachage cryptographiques ne produisent *en pratique* jamais de collision, donc on n'a pas à se soucier des doublons, par exemple ; d'un autre côté, elles sont beaucoup plus lentes à calculer (en SHA224 mon ordinateur hache environ 50Mo/s alors que pour une fonction rapide et faible ce serait plutôt plusieurs Go/s) et la sortie est bien trop grande pour servir directement d'indice dans une table (on peut bien sûr n'utiliser que le début, mais on perd la force cryptographique). Une fonction de hachage rapide mais faible produit un haché tout petit (par exemple CRC32 en produit 32 bits), donc les collisions sont très faciles à générer, mais c'est utile pour répartir les données de façon équitable. L'idée d'une table de hachage, c'est que pour comparer un texte donné à toute une liste de textes possibles le mieux est de commencer par le hacher, rechercher le haché dans la table, puis, s'il y a risque de collision, rechercher le texte lui-même dans le sous-ensemble des candidats ayant le même haché. (Il faut cependant remarquer que, dans la plupart des cas où on utilise une table de hachage, c'est parce que c'est plus facile qu'un arbre binaire quelconque, et les arbres binaires sont en fait presque toujours plus efficaces que les tables de hachage.)

Fred C. → Dans les grandes lignes, la fonction de hachage a un état interne (de 256 bits, par exemple, dans le cas de SHA224), elle lit les données à hacher par blocs (de 512 bits dans le cas de SHA224), et, pour chaque bloc, elle modifie son état interne en fonction du bloc d'après le cœur de la fonction de hachage, qu'on appelle sa « fonction de compression interne », et à la fin elle renvoie essentiellement l'état interne (ou une partie de celui-ci, dans le cas de SHA224 et SHA384). Le point important, c'est donc la fonction de compression interne, et celle-ci consiste à effectuer toutes sortes de calculs bien spécifiés (des additions et des opérations logiques diverses) sur les entrées, en général un unique calcul qu'on répète un grand nombre de fois avec des petites variations (en faisant tourner les entrées et les constantes qui interviennent). Tous ces calculs sont conçus par les cryptographes de façon que le moindre changement d'un bit dans l'entrée ait les effets les plus énormes sur la sortie. C'est assez bien expliqué sur <URL: http://en.wikipedia.org/wiki/SHA-1 >, où il y a, en plus, un joli dessin qui illustre avec des flèches comment c'est fait.

Matoo (2005-08-29T12:02:28Z)

Ouai arrêtez les matheux, ça m'excite vos pugilats abscons ! :-)))

Nicky (2005-08-29T11:32:39Z)

Excellent exposé! Tu pourrais expliquer aussi ce que sont les tables de hachage, et à quoi elles servent? Les articles de wikipedia sur le sujet sont assez peu clairs pour un non-informaticien. D'ailleurs, tu pourrait aussi compléter l'article wikipedia "fonctions de hachage" à partir de cette note, ça ne peut pas faire de mal…

phi (2005-08-29T09:25:19Z)

Et puis ta méthode a été brevetée depuis longtemps par Microsoft pour générer des programmes.

Fred C. (2005-08-29T09:10:07Z)

Message très pédagogique pour un vrai naïf comme moi, bravo. Mais, à part brièvement dans une note, il me semble que tu ne traites que des propriétés des fonctions de hachage, et pas des méthodes utilisées pour les faire tourner. Je suppose qu'expliquer ça, même dans les très grandes lignes, c'est une autre paire de manches ?

Gilles (2005-08-29T08:20:20Z)

Bonjour,
Je me permets de faire une petite intrusion dans ton blog (je faisais des recherches sur le hachage et je suis tombé sur ton site..voilà pour l'explication)
Si je peux me permettre , la fonction de hachage présente un petit défaut , cela se passe durant les tris.Le hachage génére des doublonsalors on utilise le double hachage mais c'est reculer pour mieux sauter.Dans l'industrie cela arrive parfois , surtout losrqu'on doit traiter des milliards de données.
Sinon j'ai bien aimé ta façon d'expliquer le hachage , trés ludique.

Ruxor (2005-08-28T23:40:13Z)

Ce que j'essaie de t'expliquer, c'est qu'on peut prendre n'importe quelle borne sur le temps d'exécution, j'appelle quand même ça une exécution « diagonale ». Rien ne m'empêche d'exécuter 10 instructions sur le premier programme quand j'en exécute 1 sur le second, puis 100 sur le premier avant d'en exécuter 1 sur le troisième, et ainsi de suite, auquel cas on aura un compromis différent sur le couple (longueur de la compression, temps de décompression), et on choisit exactement l'exécution « diagonale » selon le compromis qu'on veut faire (que la longueur compte exponentiellement plus que le temps, ou n'importe quoi). La seule chose qui compte c'est de mettre *certaines* bornes (finies à tout moment). C'est clair, maintenant ? On peut laisser tomber ce sujet que j'ai introduit juste en voulant faire une remarque amusante au passage, et qui est en train de tourner au coupage de cheveux en quatre vraiment crétin ?

phi (2005-08-28T22:55:37Z)

-> Nicolas
La complexité de Bennett est le temps d'exécution du programme *le plus court en espace* et elle est donc subordonnée à la complexité de Kolmogorov, et est donc tout autant indécidable. La méthode de Ruxor sélectionne d'abord sur le temps; son "exécution diagonale" empêche tout au plus les programmes d'exagérer trop sur le temps trop rapidement. D'ailleurs, il évoque bien dans son texte optimiser "la longueur de la compression + temps de décompression", et par construction, je veux bien croire que c'est le meilleur: le programme le plus rapide, c'est celui qui termine en premier… et j'imagine que son exécution diagonale garantit le troc 1 instruction excutée contre 1 case mémoire. Quoique, cette correspondance n'a pas grand sens et est tout à fait arbitraire, relativement à une machine donnée.
Mais ça risque d'être sans aucun intérêt puisque le décompactage est souvent bien plus coûteux en temps que la taille du fichier de départ. Ma question était: est-ce que la méthode ne risque pas de sélectionner la plupart du temps le chargement immédiat de la donnée non compressée?
Une autre question était: que donne *en espace* cette méthode de compression on ne peut plus généraliste (par construction), par rapport aux méthodes ad hoc sur les fichiers habituels, une classe beaucoup plus restreinte que celle des fichiers peu complexes. D'ailleurs, la même question peut se poser pour les compressions généralistes (zip…) par rapport aux compressions spécifiques (mpeg…). Si la réponse est claire pour le mpeg, il y a des cas où la compression "intelligente" ne fait pas mieux que les génériques.
Ruxor avait bien sûr compris la question dès le début mais c'est tellement agréable de se faire prier pour distiller ses précieux talents pédagogiques!

Nicolas (尼古拉) (2005-08-28T18:22:25Z)

Oui par cet exemple de compression des décimales de pi on illustre bien la différence fondamentale entre les complexités de Kolmogorov et de Benett. Pour la définition mathématique rigoureuse, le livre de Jean-Paul Delahaye "Complexité et hasard" est assez accessible (pas besoin de le relire 10 fois pour saisir) tout en étant pointu.

Ruxor (2005-08-28T16:56:58Z)

Je crois que le concept d'exécution diagonale t'échappe, mais j'ai la flemme d'expliquer et ce n'est pas le sujet.

phi (2005-08-28T16:50:28Z)

Justement, pour les décimales de pi, si on a une machine avec division et nombres décimaux, le codage le plus court est sans doute la somme alternée. Seulement, le temps que la machine parvienne au résultat, un autre programme plus long aura terminé et aura été retenu. Sans parler de faisabilité pratique, je ne vois pas comment ta méthode est simplement théoriquement possible. Sans chipoter sur le temps de compression, il faudrait quand même qu'il soit borné, au moins pour un programme donné.

Ruxor (2005-08-28T15:51:31Z)

Euh, phi, si on ignore le temps de compression, ma méthode est démontrablement meilleure, pour toute fonction de complexité qu'on voudra bien fixer (dans les détails de l'énumération diagonale), que n'importe quelle autre méthode (pour peu qu'on compte la taille du décompresseur dans la taille des données comprimées). Évidemment, c'est une compression sans pertes. Mais s'il s'agit de comprimer, par exemple, les décimales de pi, elle devrait découvrir qu'il s'agit des décimales de pi et coder juste un petit programme qui calcule les décimales de pi ; et de même, si on essaie de comprimer des données chiffrées (ce qu'aucun gzip ou équivalent ne sait faire), elle commence par trouver l'algorithme et casser la clé, et elle stocke les données comprimées + la clé pour rechiffrer. Pratique.

Dommage que ce soit peu utilisable en pratique. :-)

phi (2005-08-28T15:27:09Z)

Je ne suis pas sûr de ta "méthode de compression qui battra n'importe quelle autre". Même en excluant une foule de contre-exemples plus ou (plutôt) moins honnêtes, ça risque d'être terriblement inefficace, par exemple, sur un flux vidéo.
Le côté tautologique inhérent à tout algorthme de compression, "je suis bon pour ce que à quoi je suiis adapté" est encore lié ici à la machine considérée mais la ~complexité de Kolmogoroff est certes la plus généraliste. Par contre, elle est sans doute inutilement générale: elle comprime mieux ce qui a peu de chances de se rencontrer, comprime aussi peu que les autres méthodes les fichiers peu compressibles et beaucoup moins bien que les méthodes ad hoc les fichiers les plus courants…
Enfin, la (première) "machine qui s'arrête en produisant le texte voulu" n'est pas forcément celle au programme le plus court, et cela risque d'empirer gravement lorsque le texte d'entrée s'allonge. À l'extrême, le programme trouvé serait celui qui cherge l'intégralité du texte comme valeur immédiate! Quant à attendre les autres, on risque la non-termination.

Ruxor (2005-08-28T13:25:55Z)

fahree → Ça dépend ce que tu veux en faire, bien sûr. Si ton modèle de sécurité fait que ce n'est pas grave si un attaquant peut produire une collision (que c'est seulement grave s'il peut inverser la fonction, et là on en est très loin) alors SHA-1 n'est pas problématique (d'ailleurs, même MD5 est utilisable). Et puis, après tout, trouver une collision dans SHA-1 est « encore » aussi coûteux que ça l'était dans MD5 juste par force brute. Pour RIPEMD-160, il me semble qu'il était menacé par des attaques récentes, mais je n'ai pas de détails. Tiger et Whirlpool, je ne sais pas. AEShash c'est peut-être une bonne idée parce que j'ai entendu des experts dire « manifestement, on ne sait pas faire des bonnes fonctions de hachage, alors qu'on sait faire des bons block ciphers, donc c'est une bonne piste d'utiliser les block ciphers comme fonctions de hachage ». Mais la recommandation « officielle » est quand même SHA224 et SHA256 ; pour ce qui est de leur vitesse (environ deux à trois fois plus lente que SHA-1 selon les implémentations), sur mon PC (P4@3.4GHz) il vont à une vitesse comparable aux disques (de l'ordre de grandeur de 50Mo/s), donc c'est « acceptable ». Parfois certains recommandent MD5||SHA-1, parce qu'il est généralement plus rapide que SHA256 et donne plus de bits, mais en fait il y a une attaque connue en 2^80 sur MD5||SHA-1.

koxinga → Les longueurs 224 et 384 ont surtout pour avantage de matcher des longueurs de clés souvent utilisées : de toute façon, SHA224 calcule en fait un SHA256 sur des valeurs initiales différentes et jette à la fin le 8e mot de son état interne, et de même SHA384 calcule un SHA512 sur des valeurs initiales différentes et jette les 7e et 8e mots (de 64 bits). L'extensibilité est facile à expliquer : les fonctions de hachage sont incrémentales, elles ont un état interne (qui, pour MD5, SHA-1, SHA256 et SHA512, a exactement la longueur du haché final) qu'elles mettent à jour avec des blocs de texte qui entre, à la fin il y a juste une petite opération de padding et conclusion mais sinon on fournit directement l'état des registres ; donc si je connais h(X) (et aussi la longueur de X, ce que j'ai oublié de préciser) alors je connais l'état des registres de la fonction de hach quand elle a digéré X (+ le padding final, c'est là que la longueur de X intervient), et du coup, pour n'importe quel texte Y (commençant par le padding final appliqué à X, quand même) je peux continuer d'appliquer l'opération de mise à jour des registres, et calculer h(X||Y). Alors que pour SHA224 et SHA384, comme je n'ai pas tous les registres, je ne peux rien faire. Bon, la plupart des usages de la fonction de hachage n'ont rien à faire du fait qu'elle soit extensible, mais dans certains cas ça peut être un problème.

Kurtosis → Ce n'est pas seulement Alice qui peut essayer de deviner le choix que Bob va faire, Bob aussi peut essayer de deviner le choix qu'Alice a fait. S'ils veulent jouer comme ça, si chacun s'imagine meilleur « psychologue » que l'autre, c'est leur problème : il suffit qu'un seul des deux (ou, a fortiori, les deux) décide de faire appel à une vraie source de hasard pour son choix (et ne le fasse pas de tête !) et le jeu devient exactement pile-ou-face. Donc à partir du moment où l'un des deux joueurs veut jouer à pile-ou-face, ils joueront effectivement à pile-ou-face (peu importe ce que fait l'autre) ; si aucun des deux ne le veut, ben, c'est leur problème, n'est-ce pas ? Et effectivement, la situation est précisément la même pour pierre-papier-ciseaux (où la stratégie optimale au sens de von Neumann est de jouer chacun avec probabilité 1/3 uniformément et indépendamment), c'est juste que quand on joue à pierre-papier-ciseaux on a rarement une vraie source de hasard sous la main, et le cerveau en est une très mauvaise (et certains s'imaginent qu'ils sont bons psychologues, plus fins que l'adversaire, bref…).

Ni → Excellent, ça ! Mais sinon je peux proposer une méthode de compression qui battra n'importe quelle autre sur la longueur de la compression + temps de décompression, et qui n'est (en complexité du temps à faire la compression) « que » exponentielle dans la longueur du texte à comprimer. Il s'agit de fixer une fois pour toutes une machine abstraite (genre, machine de Turing) et d'exécuter de façon diagonale tous les programmes possibles pour cette machine (dans l'ordre, et sur autant de machines différentes) jusqu'à ce qu'une machine s'arrête en produisant le texte voulu. (Ça calcule « presque » la complexité de Kolmogoroff : modulo un terme de complexité puisqu'on exécute diagonalement et pas jusqu'à l'arrêt ce qui ne serait pas possible.)

Mouton (2005-08-28T13:03:41Z)

Kurtosis > Cela n'est donc pas totalement équivalent à pile ou face. puisque cela joue sur les répétitions que
> formulera le deuxième joueur en fonction des succès et des échecs passés (un peu comme à Papier/Ciseau/Caillou).

La seule chose dont on peut être sûr, effectivement, c'est que si l'un des deux veut rendre la chose aléatoire, elle le sera. Mais effectivement, les fonction de hash permettent également de jouer à Pierre papier ciseaux de manière fiable.

> Le plus aléatoire ne serait-il pas de concaténer deux messages, émis par
> chacun des joueurs, et de regarder le dernier bit ?

Il faudrait que tu proposes un protocole, mais le naïf pose un problème. Si je suis Bob, et qu'Alice vient de m'envoyer un message, je peux me débrouiller pour envoyer un message dont le dernier bit aille dans le bon sens, pour moi (quitte à devoir essayer plusieurs combinaisons de mots plausibles, pour ça). Ainsi, je suis sûr de gagner…

Ni (2005-08-28T12:16:18Z)

> il n'y a évidemment aucune façon de retrouver le document. (En un sens c'est dommage, parce que ce serait une méthode de compression merveilleuse, si on pouvait !)

Il y a pourtant des gens qui essayent: <URL: http://freedaemonconsulting.com/tech/hzip.php >

Ganymède (2005-08-28T10:31:43Z)

pov'mouton… finir ainsi en hachis!
enfin, je vois que Ruxounet a passé des vacances… heu, studieuses!

Kurtosis (2005-08-28T08:15:35Z)

Une chose que je n'ai pas vraiment compris à propos du jeu de pile ou face entre Alice et Bob. Mais ma remarque porte davantage sur le jeu en lui-même que sur les principes du hashages, brillament exposés.

Dans le jeu tel que tu le présentes, le but pour Alice est en effet d'anticiper le choix de Bob (gagnant ou perdant).

Cela n'est donc pas totalement équivalent à pile ou face. puisque cela joue sur les répétitions que formulera le deuxième joueur en fonction des succès et des échecs passés (un peu comme à Papier/Ciseau/Caillou).

Le plus aléatoire ne serait-il pas de concaténer deux messages, émis par chacun des joueurs, et de regarder le dernier bit ?

koxinga (2005-08-28T07:07:17Z)

Très intéressant et bravo pour tes programmes.

Pourquoi utiliser des hash de longueurs 224 et 384?

Sinon, comment fait-on pour "compute hash(x||y) knowing hash(x) and y" avec les autres types de hachages, comme tu le dis sur ton mail ? (si ce n'est pas trop compliqué à expliquer , mais puisque tu es d'humeur pédagogique, j'en profite)

Nicolas (尼古拉) (2005-08-28T04:27:09Z)

Vraiment sympa le mini-cite!

fahree (2005-08-28T04:24:20Z)

SHA-1 est déjà cassé *en pratique*? Y a pas un autre algorithme moins lourd que SHA-224 qui soit (reconnu comme) fiable? Genre RIPEMD-160 ou Tiger-192, Whirlpool ou AEShash? Que recommendent les experts?