Aujourd’hui, nous allons parler de cryptographie à l’occasion de ma lecture du livre de David Wong, Real-World Cryptography, paru en septembre 2021 aux éditions Manning, dont le chapitre 2 est consacré aux fonctions de hachage.
De telles fonctions déterministes étaient bâties à l’origine pour répondre à trois propriétés fondamentales de sécurité que nous allons étudier :
- Résistance à la préimage,
- Résistance à la seconde préimage,
- Résistance aux collisions.
Notions d’image et de préimage d’une fonction
Considérons une fonction de X dans Y qui à x associe f(x). Pour un élément x dans X, l’unique élément f(x) qui lui est relié dans Y est appelé image de x par f, et dans ce cas on dit que x est un antécédent de f(x) par f . Ainsi, la totalité des images des éléments de l’ensemble X est appelée « image d’une fonction » ou « ensemble image ».
La préimage de f(x) inclus dans l’ensemble Y est le sous-ensemble de X constitué des éléments dont l’image par f appartient à f(x). Autrement dit, l’ensemble des antécédents de f(x) par f constitue la préimage de la fonction. Notez qu’en français, les termes « préimage », « image réciproque » et « image inverse » sont synonymes.
Résistance à la préimage
Une fonction de hachage est dite résistante à la préimage lorsqu’il est mathématiquement impossible dans un temps raisonnable de trouver une entrée qui produit une valeur en sortie prédéterminée, c’est-à-dire, que pour un y donné (valeur en sortie), il est quasiment impossible de trouver un x (valeur en entrée) tel que f(x) = y. Concrètement, on ne peut pas reconstituer la donnée en entrée de la fonction de hachage à partir de son condensat.
Il faut tout de même noter que si les données en entrées sont trop petites ou prédictibles (on parle alors de « small input space »), on peut facilement trouver l’entrée recherchée. Par exemple si l’attaquant connaît la longueur de x, il hachera tous les mots du dictionnaire ayant la même longueur. Il comparera les condensats en sortie avec le y déjà en sa possession jusqu’à identifier x. C’est pourquoi la qualité des données en entrée de la fonction de hachage ne doit pas être négligée.
Résistance à la seconde préimage
Une fonction de hachage est résistante à la seconde préimage lorsque dans un temps raisonnable, il est impossible pour un attaquant de trouver un x’ ayant le même condensat qu’un x donné et invariable.
La quantité de condensats possibles est finie bien que très grande. Par exemple avec SHA-256, elle est de 2256. La quantité d’entrée quant à elle est infinie, donc théoriquement la quantité d’entrée produisant le même condensat est également infinie ce que contredit les propriétés de résistance. Mais il faudrait une si grande puissance de calcul que pour le moment, SHA-256 est considéré comme un algorithme sécurisé.
Résistance à la collision
Une fonction de hachage est résistante à la collision lorsque dans un temps raisonnable, il est impossible pour un attaquant de trouver un x’ ayant le même condensat qu’un x. Autrement dit, deux entrées différentes ne peuvent pas donner un même condensat. Cette propriété implique logiquement la résistance à la seconde préimage.
En premier lieu, j’ai eu du mal à comprendre la différence entre la résistance à la seconde préimage et à la collision. J’ai donc cherché sur le Web des explications et je suis tombé sur un exemple parlant que je vais vous présenter.
MD5 est un algorithme de hachage non-sécurisé créé par Ronald Rivest, co-créateur du crypto-système RSA. MD5 est connu pour facilement générer des collisions même avec des machines peu puissantes. Je vous invite à explorer le GitHub de corkami pour comprendre comment forger des fichiers qui aboutissent à des collisions.
Différence entre résistance à la seconde préimage et à la collision
Un algorithme de signature cryptographique ne signe pas directement le fichier mais son condensat. On commence à voir les problèmes potentiels en cas d’attaques sur la seconde préimage.
L’attaquant récupère le condensat y, qui est public et qu’il ne maîtrise pas, généré par l’algorithme de signature d’un message x. La fonction de hachage utilisée dans l’algorithme de signature étant vulnérable, l’attaquant parvient à forger un message x’ illégitime dont le condensat vaut aussi y. La signature associée à x devient désormais aussi valable pour x’. Et là c’est le drame puisqu’il pourra faire passer des messages pour légitimes alors qu’ils ne le sont pas.
La collision intervient dans un autre cas d’attaque puisque contrairement à la seconde préimage, l’attaquant maîtrise les deux entrées. On peut l’imaginer envoyer un message anodin x dont le condensat est y puis créer un second message x’ disant le contraire de x mais dont le condensat vaut aussi y. Ceci voudrait dire que la victime aurait signé à son insu x’ en parallèle de x.
Alors, prêts à hacher de la donnée ? 😉
