Les fonctions de hachage

Tout le monde en utilise, mais personne ne sait comment c'est fait

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Tout le monde se secoue ! :D

J’ai commencé (mercredi 24 mai 2017 à 09h38) la rédaction d’un tutoriel au doux nom de « Les fonctions de hachage » et j’ai pour objectif de proposer en validation un texte aux petits oignons. Je fais donc appel à votre bonté sans limites pour dénicher le moindre pépin, que ce soit à propos du fond ou de la forme. Vous pourrez consulter la bêta à votre guise à l’adresse suivante :

Bonjour à tous,

J’avais prévu il y a quelques temps d’écrire un court tuto sur les fonction de hachage, et vu que ça intéressait du monde, je l’ai en effet commencé. Il n’est pas encore fini, mais je préfère avoir des retours/critiques/potentielles améliorations/corrections à faire le plus tôt possible.

En espérant que ce tuto vous plaira ;)

Bien à vous.

Édité par Ryx

+4 -0

Salut,

D’un point de vue technique :

  • On ne parle pas vraiment de résistance à l’inversion (vu qu’une foncion de hash est non-inversible), mais de résistance à la (première) préimage.
  • Ta définition de la résistance à la collision est correcte (difficulté de trouver deux messages qui rentrent en collision). Cela dit l’exemple que tu donnes avec "Zeste de" ressemble plus à de la résistance sur la seconde préimage (soit un clair donné, peut-on trouver facilement un autre clair qui possède le même hash ?). Comme tu l’expliques, la résistance à la collision peut se buteforce en $\sqrt N$ opérations, où $N$ est la taille de l’espace du hash. Au contraire, il existe très peu de méthodes pour casser la seconde préimage, à part explorer $N$ en entier. Je crois que pour MD5, on est descendu à quelque chose comme devoir calculer $2^{120}$ hashs sur les $2^{128}$, mais rien de transcendant.

  • Enfin, tu ne parles pas non plus du fait qu’une fonction de hash cryptographique doive empêcher de modifier le message sans altérer le hash. Autrement dit, n’importe quelle légère modification du message entraîne une modification complète du hash. C’est de la résistance sur la seconde préimage, mais ça va mieux en le disant clairement.

Bon et sinon, je ne sais pas exactement si tu veux en parler, mais les fonctions de hash n’ont pas qu’un rôle cryptographique, loin de là. Pour ces applications non cryptographiques, il n’y a souvent pas besoin de ces résistances à la préimage, ou à la collision.

A part ça, tu peux aussi parler de rainbow tables, de (H)MAC, recherche de triplets ayant le même hash… Mais je ne sais pas si tu veux être aussi exhaustif dans ton tuto.


Sur la forme, tu n’introduis pas bien tes $2^{80}$ dans la partie "Avec des vraies fonctions de hachage", et dans la partie "signature électronique", tu ne dis pas ce qu’est une clef privée, ce qui peut poser problème parce que tout le monde n’est pas forcément familier avec le chiffrement asymétrique. Dans la partie "Quel peut-être le problème d’une collision ?", sous-partie "Exemple avec la fonction bidon", tu dis que Alice signe d1 avec sa clef privée et obtient S, et que M en profite pour signer d2 avec S. Ce n’est pas tout à fait ça, vu qu’en fait Bob n’a pas besoin de faire quoi que ce soit, il lui suffit de publier d2 et S, et tout correspondra.

Voilà voilà, bonne continuation. :)

Juste pour le fun, je rajoute un petit PDF qui explique comment DoS plein de serveurs Web en exploitant une faiblesse des fonctions de hash : https://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf La faille a été corrigée depuis, mais c’est quand même instructif.

+0 -0
Auteur du sujet

C’est prit en note, merci.

Dans les applications j’avais prévu de rajouter des choses, et concernant les histoires de préimages (alors déjà je vais changer les exemples pour que ça ressemble plus à une collision qu’à de la recherche de seconde préimage), je vais en effet ajouter un paragraphe dessus.

Il faut seulement que je réfléchisse un peu parce que je n’ai pas envie de mettre de trucs de manière compliquée.

Je n’avais pas du tout le but d’être exhaustif (de toute façon, ça doit être un peu compliqué), mais j’avais mis ce à quoi je pensais directement. Ceci dit, je pense quand même ajouter des choses. Merci pour les idées ;)

Édité par Ryx

+0 -0
Auteur du sujet

Bonjour les agrumes !

La bêta a été mise à jour et décante sa pulpe à l’adresse suivante :

Merci d’avance pour vos commentaires.

J’ai ajouté quelques explications en essayant tout de même de ne pas partir trop loin. J’ai du mal à avoir du recul sur ce que j’ai fait donc je veux bien vos avis avisés ;)

Il y a encore probablement des typos, et il y a des choses que je pense pouvoir détailler un peu plus (je vais faire une conclusion notamment, et peut-être expliquer un peu plus en détail les signatures).

Merci beacoup à tous les béta-lecteurs, ça m’aide vraiment.

Édité par Ryx

+0 -0
Auteur du sujet

Désolé pour le double (même triple) post.

Le bêta avance et j’aimerais bien savoir ce que vous en pensez, les choses à ajouter/supprimer/développer sachant que je fais quelque chose qui reste général.

Merci pour ceux qui prendront un peu de temps pour me relire ;)

Édité par Ryx

+0 -0

Ben pour moi ça va, simplement quand tu parles de complexité c’est toujours bien de préciser les unités, en l’occurrence tu mesures le nombre de hash calculés. D’ailleurs, on parle souvent de Google dans les résultats de SHAttered, mais on oublie bien souvent que ce sont des chercheurs hollandais qui ont trouvé la méthode avant de travailler avec Google. ^^

+0 -0

J’ai survolé mais ça me paraît un peu léger que la seule fonction de hachage présentée soit cette histoire de troncage… Ça serait intéressant de détailler un peu comment on fait des vraies fonctions de hachage (pour les exemples cryptographiques y a le choix, pour le reste au moins présenter le hachage polynomial sur les chaînes…). De plus le titre est un peu trompeur car on fait surtout de la crypto alors que c’est pas forcément l’application la plus évidente.

Auteur du sujet

Ah merci pour les retours. J’avais en effet pensé à faire des exemples avec des autres fonctions de hachage mais j’ai oublié entre temps. Merci du coup, je vais ajouter des exemples. Peut-être deux : un avec une vraie fonction de hachage et un avec une fonction bidon, mais un peu plus compliqué (genre un truc avec des xor etc…)

Petit changement de titre pour être plus clair.

Qu’entends-tu par "hachage polynomial sur les chaînes" ?

Édité par Ryx

+0 -0

Est-ce que du coup c’est légitime de parler des tables de hachage dans un tuto sur les fonctions de hachage cryptographiques ?

Je sais pas vraiment quels exemples tu pourrais prendre, j’ai pas mal d’exemples en tête mais ça risque d’être dur si tu veux vraiment mettre 0 maths dans ton article. Y a toute une littérature dessus, donc il doit y avoir moyen de trouver des trucs élégants et abordables intuitivement sans algèbre derrière.
Après si tu veux taper un peu dans le sensationnel tu peux décrire rapidement des trucs comme MD5 ou SHA (qui sont du hash cryptographique au moins a priori), mais c’est pas forcément ce qu’il y a de plus parlant. Dans tous les cas, ça serait bien d’avoir des exemples vraiment fonctionnels et pas juste bricolés maison. Encore une fois ça a été beaucoup étudié, je t’encourage à parcourir un peu des eprints là-dessus, y a de quoi faire !

Après quitte à faire des exemples ça serait sympa de faire un peu le tour de ce qui se fait « du point de vue du designer » ; je pense à des choses comme Merkle-Damgard. On pourrait aussi évoquer les MAC.

Mon histoire de hachage polynomial n’est pas un exemple cryptographique, il consiste simplement pour hacher une chaîne $(s_0,\ldots,s_{n-1})$ sur un certain alphabet, à considérer $P=\sum_i s_iX^i$ et à renvoyer $P(x)$$x$ est disons pris dans un certain $\mathbf{Z}_m$. En faisant des choix uniformes des paramètres on a une famille universelle de hash. C’est souvent ce qu’on utilise dans Rabin-Karp pour des raisons calculatoires (c’est facile de recalculer les hash sur une fenêtre glissante).

Auteur du sujet

Merci pour ces infos,

En fait j’aurais bien aimé montré une fonction de hachage un peu complexe, mais avec une attaque pas trop difficile à expliquer par exemple.

Si je parle de MD5 ou de SHA, je peux expliquer le principe, mais l’algo est trop complexe pour l’étudier. Ce n’est d’ailleurs pas vraiment le but de ce tuto. La raison pour laquelle je boulais faire un truc maison c’était pour faire quelque chose qui soit une fonction de hachage pas trop nulle, mais avec une attaque asses évidente, histoire que ce soit pédagogique.

Comme le tuto est à l’origine sensé être très accessible, je ne sais pas si je devrais mettre HMAC et Merkle-Damgard dedans, mais ça peut se discuter. Enfin si j’explique le principe du SHA, je suis bon pour faire un petit rappel sur les opérations booléennes donc pourquoi pas.

Édité par Ryx

+0 -0
Auteur du sujet

Pour un mot de longueur l, on pourrait utiliser un truc à valeurs dans [0, N-1] du genre $h(x) = \sum_{i=0}^{l-1}{x[i]B^{l-i-1} mod N}$ avec $B$ une puissance de $2$.

Je ne pense pas que ce soit une vraie fonction de hachage, mais ça reste à peu près simple et on peut faire des trucs un peu plus intéressants.

Après ça, je voulais faire un truc court et général sans entrer dans des trucs trop techniques.

Je vais donc adapter mes exemples avec cette autre fonction moins bricolée et peut-être faire quelques lignes sur HMAC et Merkle-Damgard à la fin histoire de les présenter, mais je ne vais clairement pas m’éterniser dessus. Sinon, je ne pense pas rajouter trop de choses.

Édité par Ryx

+0 -0

Bonjour,

La bêta du contenu « Les fonctions de hachage cryptographiques » a été désactivée.


Le tuto est publié (et la béta plus vieille que la version publiée).

Édité par Gabbro

Hier, dans le parc, j’ai vu une petite vieille entourée de dinosaures aviens. Je donne pas cher de sa peau.

+0 -0
Ce sujet est verrouillé.