Les fonctions de hachage cryptographique 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
Attention

Cette propriété est efficace seulement si la donnée en entrée est suffisamment conséquente et non prédictible. Un attaquant pourrait en effet pré-calculer les variantes d’un texte en entrée puis trouver la correspondance avec le condensat qu’il aurait déjà.

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

Une fonction de hachage cryptographique 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 cryptographique ne doit pas être négligée.

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

Une fonction de hachage cryptographique 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 cryptographique 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.

Note

Savez-vous pourquoi le condensat d’une fonction de hachage cryptographique devrait toujours être au moins égal à 256 bits ? À cause du paradoxe des anniversaires ! Il s’agit d’une particularité statistique contre-intuitive. Seulement 23 personnes aléatoirement sélectionnées sont nécessaires pour qu’il y ait 50% de chances que deux personnes partagent la même date d’anniversaire. On passe à 99% de chances avec 57 personnes. En généralisant, la probabilité que deux entrées différentes donnent le même condensat est donc de \(\small 2^{n/2}\). Et comme un algorithme cryptographique moderne est considéré sécurisé avec un paramètre de sécurité de 128 bits ou plus, si \(\small n = 256\) alors il faudra au moins \(\small 2^{256/2}\) opérations à l’attaquant pour trouver probablement au moins une collision.

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.

Vocabulaire

Avant de clôturer cet article, je tenais à faire un point sur le vocabulaire à employer lorsque l’on parle des fonctions de hachage cryptographique. La sortie d’une telle fonction doit être appelée condensat, digest ou hash. Les termes signature, empreinte, fingerprint, checksum ou somme de contrôle sont à proscrire car trop ambiguës.

Signer un fichier, c’est chiffrer son condensat avec la clé privée de son propriétaire puis lier le certificat du propriétaire et cette signature au fichier. On utilise bien une fonction de hachage cryptographique mais aussi de la cryptographie asymétrique.

Une empreinte, fingerprint, checksum ou somme de contrôle peut provenir d’une fonction de hachage cryptographique mais aussi d’une fonction de hachage non cryptographique, c’est-à-dire qui ne respecte pas nécessairement les propriétés de résistance. Attention donc.