Les fonctions de hachage sont des primitives cryptographiques omniprésentes lorsqu’il s’agit de vérifier l’intégrité de messages et de fichiers, de générer et de vérifier des signatures numériques ou de vérifier la correspondance de mots de passe, entre autres. Ces fonctions sont déterministes car bâties à l’origine pour répondre à trois propriétés fondamentales que nous allons étudier :

  • Résistance à la préimage,
  • Résistance à la seconde préimage,
  • Résistance aux collisions.

Image et préimage d’une fonction

Débutons par expliciter la notion d’image. Soit \(\small X \longrightarrow Y\) une fonction de l’ensemble de définition (domain) \(\small X\) à l’ensemble d’arrivée (codomain) \(\small Y\). Pour un élément \(\small x\) dans \(\small X\), l’unique élément \(\small f(x)\) qui lui est relié dans \(\small Y\) est appelé image de \(\small x\) par \(\small f\). On dit alors que \(\small x\) est un antécédent de \(\small f(x)\) par \(\small f\). Ainsi, la totalité des images des éléments de l’ensemble de définition \(\small X\) est appelée “ensemble image” de la fonction, notée \(\small f(X)\). Notons, qu’un élement de l’ensemble d’arrivée peut avoir plusieurs antécédents. Expliqué autrement, l’ensemble de définition \(\small X\), est l’ensemble des valeurs possibles telles que \(\small f(x)\) existe. Tandis que l’ensemble image \(\small f(X)\) est l’ensemble des valeurs obtenables en appliquant \(\small f\) aux éléments de \(\small X\). Avec un schéma, tout s’éclaircit !

L'image est constituée de deux gros ovales, celui de gauche est rouge et contient trois points noirs. Il représente l'ensemble de définition X. Celui de droite est bleu et contient également trois points noirs. Il représente l'ensemble d'arrivée Y. À l'intérieur de l'ensemble Y, se trouve un plus petit oval jaune contenant les trois points. Il s'agit des images x par f, soit f(x). Chaque point de l'ensemble X est relié bijectivement par une flèche aux points dans l'ensemble Y.
\(\small f\) est une fonction de l'ensemble \(\small X\), coloré en rouge, vers l'ensemble d'arrivée \(\small Y\), coloré en bleu. Le plus petit ovale jaune à l'intérieur d'\(\small Y\) est l'image de \(\small x\) par \(\small f\). - Crédit : wikipedia.org
L'image est constituée de deux gros ovales, celui de gauche est bleu et contient trois valeurs : -2, 1 et 2. Il représente l'ensemble de définition X. Celui de droite est vert et contient quatre valeurs : -1, 0, 2 et 5. Il représente l'ensemble d'arrivée Y. À l'intérieur de l'ensemble Y, se trouve un plus petit oval jaune contenant les valeurs 2 et 5 précedemment citées. Il s'agit des images x par f, soit f(x). La valeur -2 de l'ensemble X pointe avec une flèche vers la valeur 5 de l'ensemble Y. Idem pour 1 qui pointe vers 2 et 2 qui pointe vers 5. Ainsi f(-2)=5, f(1)=2 et f(2)=5.
L'ensemble image de la fonction, représenté par l'oval jaune, est \(\small f(X) = \{2;5\}\). Seuls \(\small 2\) et \(\small 5\) peuvent être obtenus en appliquant \(\small f\) aux éléments de \(\small X\). Ici, l'ensemble image est un sous-ensemble strict de l'ensemble d'arrivée car il contient moins d'éléments. Les valeurs \(\small -1\) et \(\small 0\) n'ont pas d'antécédent. - Crédit : nagwa.com

Abordons maintenant la notion de préimage, que l’on appelle également “image réciproque” ou “image inverse”. Soit \(\small X \longrightarrow Y\) une fonction de l’ensemble de définition \(\small X\) à l’ensemble d’arrivée \(\small Y\). La préimage d’un sous-ensemble \(\small B\) de \(\small Y\) par \(\small f\) est le sous-ensemble noté \(\small f^{-1}(B)\) de \(\small X\) constitué des éléments dont l’image par \(\small f\) appartient à \(\small B\).

L'image est constituée de deux gros ovales, celui de gauche est rouge et représente l'ensemble de définition X. Cet ensemble contient deux autres ovales imbriqués : le plus grand de couleur cyan représente le sous-ensemble C et le plus petit contenu lui-même dans C, de couleur verte, représente le sous-ensemble A. C contient trois points noirs dont deux intégrés à A. L'ovale de droite est bleu et contient deux points noirs au sein d'un sous-ensemble B vert. Il représente l'ensemble d'arrivée Y. Deux points du sous-ensemble A relient par une flèche un point du sous-ensemble B tandis que l'unique point du sous-ensemble C, excluant A, est relié à l'autre point du sous-ensemble B.
L'image de tous les éléments du sous-ensemble \(\small A\) est le sous-ensemble \(\small B\). La préimage du sous-ensemble \(\small B\) est le sous-ensemble \(\small C\). - Crédit : wikipedia.org

Propriété de résistance à la préimage

Une fonction de hachage sûre est dite résistante à la préimage lorsqu’il est mathématiquement impossible en un temps raisonnable de trouver une entrée \(\small x\) qui produit un condensat \(\small y\) prédéterminé, tel que \(\small f(x) = y\). Concrètement, avec une telle fonction, on ne peut pas reconstituer la donnée en entrée à partir de son condensat. Il est important de garder à l’esprit que si les données en entrée sont peu volumineuses (on parle alors de “small input space”) ou prédictibles, les chances de trouver l’entrée originale sont augmentées. Par exemple si l’attaquant connaît la longueur d’un mot de passe \(\small x\), il hachera toutes les combinaisons ayant la même longueur. Il comparera les condensats en sortie avec le \(\small y\) qu’il connait déjà jusqu’à identifier le \(\small x\) correct. C’est pourquoi la qualité des données en entrée de la fonction de hachage ne doit pas être négligée.

Propriété de résistance à la seconde préimage

Une fonction de hachage sûre est dite résistante à la seconde préimage lorsqu’il est mathématiquement impossible en un temps raisonnable de trouver une autre entrée \(\small x'\) qui produit le même condensat \(\small y\) qu’une entrée \(\small x\) donnée et invariable.

La quantité de condensats uniques est finie bien que très grande. Par exemple avec SHA-256, elle est de \(\small 2^{256}\). La quantité d’entrées quant à elle est virtuellement infinie, donc théoriquement, la quantité d’entrées produisant le même condensat est également infinie, ce qui contredit les propriétés de résistance. Seulement, il faudrait une si grande puissance de calcul afin de trouver un \(\small x'\), que pour le moment, SHA-256 est considéré comme un algorithme sécurisé.

Propriété de résistance à la collision

Une fonction de hachage sûre est dite résistante à la collision lorsqu’il est mathématiquement impossible en un temps raisonnable de trouver une entrée \(\small x'\) qui produit le même condensat \(\small y\) qu’une entrée \(\small 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.

MD5 est un algorithme de hachage non-sécurisé créé par Ronald Rivest, co-créateur du système cryptographique RSA. MD5 est connu pour facilement générer des collisions. Je vous invite à explorer le GitHub de corkami pour comprendre comment forger des fichiers qui aboutissent à des collisions.

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.

Différence entre résistance à la seconde préimage et à la collision

Un algorithme de signature cryptographique ne signe pas directement un fichier mais son condensat. On commence à voir les problèmes potentiels en cas d’attaque sur la seconde préimage. Imaginons le scénario suivant : l’attaquant récupère le condensat \(\small y \) d’un fichier \(\small x \) public qu’il ne maitrise pas. La fonction de hachage intégrée à cet algorithme de signature étant vulnérable, l’attaquant parvient à forger “facilement” un fichier \(\small x’ \) douteux dont le condensat vaut aussi \(\small y \). La signature associée à \(\small x’ \) devient donc tout aussi valide que celle de \(\small x \). Et là c’est le drame puisque l’attaquant pourra faire passer son propre fichier pour légitime alors qu’il ne l’est pas. C’est dans ce type de scénario que la résistance à la seconde préimage est fondamentale.

On peut également l’imaginer envoyer à sa victime un premier fichier anodin forgé \(\small x \) qu’elle renvoie signé et dont le condensat est \(\small y \). En parallèle, il forge un second fichier \(\small x’ \) disant l’exact contraire de \(\small x \) mais dont le condensat vaut aussi \(\small y \). Ceci signifie qu’indirectement, la victime a signé à son insu \(\small x’ \) en parallèle de \(\small x \). Ici, la résistance à la collision est primordiale.

Ainsi, la différence entre ces deux propriétés est la maitrise ou non par l’attaquant de \(\small x \). Dans le premier cas, il ne peut le choisir car fixé par un tiers. Dans le second cas, il le fabrique.