Une fonction de hachage est une application $h:\Sigma^* \longrightarrow \Sigma^n, n \in \mathbb{N}$
En clair, les fonctions de hachage associent, à des chaînes de caractères de longueur arbitraire, des chaînes de caractères de longueur fixée. Elles ne sont jamais injectives.
L'application qui associe $b_1 \oplus b_2 \oplus ... \oplus b_n$ au mot binaire $b_1 b_2 ... b_k$ dans $\{0;1\}^*$ est une fonction de hachage ($\oplus$ désigne le ou exclusif booléen).
Elle envoie, par exemple, le mot 01101 en 1. Et, d'une façon générale, elle envoie une chaîne de caractères $b$ en 1 si le nombre de 1 dans $b$ est impair et en 0 sinon.
Les fonctions de hachage peuvent être fabriquées au moyen de fonctions de compression : c'est-à-dire avec des applications de la forme...
$h:\Sigma^m \longrightarrow \Sigma^n, m,n \in \mathbb{N}, m>n$
C'est-à-dire que les fonctions de compression remplacent une chaîne de caractères de longueur fixée par une chaîne de caractères plus courte, de longueur fixée.
L'application qui envoie le mot $b_1 b_2 ... b_m \in \{0,1\}^m$ en $b_1 \oplus b_2 \oplus ... \oplus b_n$ est une application de compression quand $m>1$.
Les fonctions de hachage et de compression sont utilisées dans de nombreux contextes, par exemple pour construire des dictionnaires. En cryptographie, elles jouent un rôle important.
Les fonctions de hachage et de compression cryptographiques doivent avoir des propriétés qui garantissent leur sécurité. Nous décrivons ces propriétés de façon informelle.
Soit $h:\Sigma^* \longrightarrow \Sigma^n$ une fonction de hachage ou $h:\Sigma^m \longrightarrow \Sigma^n$ une fonction de compression.
Notons $D$ l'ensemble de départ de $h$.
Si $h$ est utilisée en cryptographie, l'élément $h(x)$ doit être facile à calculer pour tout $x \in D$. Nous allons supposer que c'est le cas.
On dit que $h$ est une fonction à sens unique s'il est impossible de l'inverser.
Autrement dit, si le calcul de $x$ tel que $h(x)=s$, à partir de $s$, est infaisable. Mais que veut dire infaisable ?
Mathématiquement, l'infaisabilité est une idée compliquée à mettre en forme. Il faudrait employer les concepts de la théorie de la complexité, ce qui va bien au-delà de la portée de ce texte. Par conséquent, nous n'en donnerons qu'une idée intuitive.
Une fonction $h$ est à sens unique quand les algorithmes qui essaient de calculer $x$ tel que $h(x)=s$, à partir d'une donnée $s$, échouent presque toujours (parce qu'il y a besoin de beaucoup trop d'espace ou de temps.)
On ne sait pas s'il existe une vraie fonction à sens unique. Toutefois, il existe des fonctions qui sont faciles à évaluer mais pour qui aucun algorithme efficace d'inversion n'est connu.
Alors, faute de mieux, on les utilise comme fonction à sens unique.
Soit $p$ un nombre premier de 1024 bits, choisi au hasard, et $g$ une racine primitive mod $p$.
On définit la fonction $\{0,2,...,p-1\} \longrightarrow \{1,2,... ,p-1\}$ par $x \longmapsto g^x \textrm{ mod } p $
C'est un fonction facile à calculer (avec l'exponentiation rapide), mais dont on ne connaît pas de fonction d'inversion efficace (pb du logarithme discret). Par conséquent, cette fonction peut servir de fonction à sens unique.
Une collision de $h$ est un couple $(x,x') \in D^2$ pour lequel $x \neq x'$ et $h(x)=h(x')$.
Les fonctions de hachage ou les fonctions de compression possèdent toujours une collision parce qu'elles ne sont pas injectives.
Une collision de la fonction de hachage de l'exemple précédent est le couple formé de deux chaînes de caractères disctinctes, ayant toutes les deux, ou n'ayant ni l'une ni l'autre, un nombre pair de 1, comme (111,100).
On dit que la fonction $h$ est faiblement résistante aux collisions s'il est infaisable de calculer une collision $(x,x')$ pour un $x \in D$ donné.
Voici l'exemple d'une situation où il est nécessaire qu'une fonction soit faiblement résistante aux collisions...
Ce test n'a de valeur que si la fonction de hachage $h$ est faiblement résistante aux collisions.
Sinon, un adversaire pourrait calculer une autre pré-image $x'$ de la valeur hachée $h(x)$. Il pourrait alors remplacer le programme $x$ par $x'$ sans qu'Alice ne s'en aperçoive, puisque $h(x)=h(x')$.
L'exemple précédent décrit une utilisation typique des fonctions de hachage résistantes aux collisions.
Elles permettent de réduire l'intégrité d'un document à l'intégrité d'une chaîne de caractères beaucoup plus petite.
On dit que la fonction de hachage $h$ est fortement résistante aux collisions s'il est infaisable de calculer une quelconque collision $(x,x')$ de $h$.
Dans certaines applications, il est nécessaire d'utiliser des fonctions de hachage fortement résistantes aux collisions, par exemple pour les signatures électroniques.
On peut montrer que les fonctions de hachage résistantes aux collisions sont des fonctions à sens unique.
Dans cette section, nous décrivons une attaque simple sur une fonction de hachage $h$ appelée l'attaque des anniversaires.
Elle s'attaque à la résistance de $h$ aux collisions, au sens fort et elle repose sur le paradoxe des anniversaires (voir TP de proba).
Dans l'attaque des anniversaires, nous calculons autant de valeurs hachées que le temps et l'espace le permettent.
Ces valeurs sont stockées avec leur images inverses et triées afin de chercher une collision.
Nous pouvons analyser cette procédure en utilisant le paradoxe des anniversaires. Les valeurs hachées sont les anniversaires.
Nous supposons que les chaînes de caractères peuvent être choisies dans $\Sigma^*$ de façon que la distribution correspondante, sur les valeurs hachées, soit la distribution uniforme.
Si $k$ chaînes de caractères sont choisies dans $x \in \Sigma^*$, avec $k \geqslant \frac{1+\sqrt{1+(8 \ln{2})|\Sigma|^n}}{2}$ alors la probabilité que deux valeurs hachées soient égales est supérieure à $\frac{1}{2}$.
Pour simplifier, nous supposons que $\Sigma=\{0,1\}$. Alors $k \geqslant f(n)=\frac{1+\sqrt{1+(8 \ln{2})2^n}}{2}$ suffit.
Le tableau suivant montre ce que vaut $\log_2{f(n)}$ pour des tailles typiques de $n$.
| n | 50 | 100 | 150 | 200 |
| $\log_2{f(n)}$ | 25,24 | 50,24 | 75,24 | 100,24 |
Donc, en calculant un peu plus que $2^{\frac{n}{2}}$ valeurs hachées, l'attaque des anniversaires trouve une collision avec une probabilité supérieure à 0,5.
Pour empêcher l'attaque des anniversaires, $n$ doit donc être choisi de façon que le calcul de $2^{\frac{n}{2}}$ valeurs hachées soit infaisable.
Actuellement, il est recommandé de prendre $n \geqslant 128$, voire $n \geqslant 160$.
On ne sait pas s'il existe une fonction de hachage résistante aux collisions, de même que l'on ne sait pas s'il existe un procédé de chiffrement sûr et efficace.
Cependant, il est possible de construire une fonction de hachage à partir d'un système de chiffrement, qui semble résister aux collisions tant que le système de chiffrement est sûr.
C'est ce que nous allons décrire maintenant...
Nous utilisons un cryptosystème où l'espace des messages en clair, l'espace des cryptogrammes et l'espace des clés sont tous égaux à $\{0;1\}^n$.
Les fonctions de chiffrement sont $e_k:\{0;1\}^n \longrightarrow \{0;1\}^n, k \in \{0;1\}^n$
Les valeurs hachées ont la longueur $n$.
Pour empêcher l'attaque des anniversaires, nous choisissons $n \geqslant 128$. Donc le DES, par exemple, ne peut pas être utilisé ici.
On peut définir des fonctions de hachage $h:\{0;1\}^n \times \{0;1\}^n \longrightarrow \{0;1\}^n$
en posant
Tant que le cryptosystème est sûr, ces fonctions de hachage semblent être résistantes aux collisions.
Malheureusement, aucune preuve de cette assertion n'est connue.
Des fonctions de compression résistantes aux collisions peuvent être utilisées pour construire des fonctions de hachage résistantes aux collisions.
Cela a été montré par R. Merkle, et voici son idée...
Soit $g:\{0;1\}^m \longrightarrow \{0;1\}^n$ une fonction de compression.
Posons $r=m-n$. Puisque $g$ est une fonction de compression, nous avons $r>0$ (un choix typique pour $n$ et $r$ est $n=128$ et $r=512$).
Nous voulons construire une fonction de hachage $h:\{0;1\}^* \longrightarrow \{0;1\}^n$ à partir de $g$.
Soit $x \in \{0;1\}^*$ ; nous expliquons le calcul de $h(x)$ dans le cas $r>1$...
La chaîne de caractères complète ainsi obtenue peut être vue comme une suite $x = x_1 x_2 ... x_t$, avec $x_i \in \{0;1\}^r$ de mots de longueur $r$.
Chacun des mots qui se trouvent à la fin (dans la partie qui représente la longueur de $x$) commence par le bit 1.
Avec $r=4$, prenons $x=111011$.
D'abord, nous transformons $x$ en 00111011 pour que sa longueur soit divisible par 4, puis nous incrivons 0000 la fin de ce mot, ce qui donne $\dot{x} = 001110110000$.
La longueur de $x$ est 6, le développement binaire de 6 est 110 ; il n'y a pas de 0 à ajouter parce que la longueur de ce mot est divisible par 3.
On place un 1 devant, ce qui donne 1110 et finalement, on obtient le mot binaire normalisé 0011101100001110.
La valeur hachée $h(x)$ est calculée par récurrence.
On pose $H_0 = 0^n$
Cette chaîne de caractères consiste en $n$ zéros. Puis on calcule ($\circ$ désigne ici l'opérateur de concaténation) $H_i = g(H_{i-1} \circ x_i), 1 \leqslant i \leqslant t$
et pour terminer on pose $h(x) = H_t$
$h$, ainsi construite, est résistante aux collisions, quand $g$ l'est.
La démonstration de ce résultat est relativement élémentaire, mais prendrait trop de place ici.
Pour obtenir un théorème digne de ce nom, il faudrait définir formellement la notion de résistance aux collisions.
Utilisez une fonction de chiffrement, ou de compression, pour faire une fonction de hachage.
Ces travaux pratiques viennent sûrement trop tôt dans le cours : vous pourrez y revenir après avoir programmé votre propre fonction de chiffrement.
Une fonction cryptographique de hachage fréquemment utilisée est SHA-1. Elle intervient dans le DSS (Digital Signature Standard).
Nous allons la décrire en détail, et vous allez la programmer.
Soit $x \in \{0;1\}^*$.
Nous supposons que la longueur (c'est-à-dire le nombre de chiffres) $||x||$ de $x$ est plus petite que $2^{64}$.
La valeur hachée de $x$ est calculée de la façon suivante...
Avant tout, on gonfle $x$ de façon que sa longueur devienne un multiple de 512. Pour cela, on procède de la façon suivante :
Soit $x$ le mot binaire
$01100001~~01100010~~01100011~~01100100~~01100101$
Après la première étape, $x$ est devenu $01100001~~01100010~~01100011~~01100100~~01100101~~1$
Sa longueur actuelle étant 41, nous devons ajouter 407 zéros à $x$ pour qu'elle devienne 448=512-64.
En représentation hexadécimale, $x$ est devenu
| 61626364 | 65800000 | 00000000 | 00000000 |
| 00000000 | 00000000 | 00000000 | 00000000 |
| 00000000 | 00000000 | 00000000 | 00000000 |
| 00000000 | 00000000 |
À l'origine, la longueur de $x$ était 40.
On écrit 40 en base 2 comme un nombre de 64 bits : en représentation hexadécimale, c'est $00000000 ~ 00000028$
et on colle ce nombre à la fin de $x$, ce qui donne, finalement, le mot binaire de 512 bits qui aurait pour représentation hexadécimale
| 61626364 | 65800000 | 00000000 | 00000000 |
| 00000000 | 00000000 | 00000000 | 00000000 |
| 00000000 | 00000000 | 00000000 | 00000000 |
| 00000000 | 00000000 | 00000000 | 00000028 |
Dans le calcul de la valeur hachée, on utilise 80 fonctions $f_t : \{0;1\}^{32} \times \{0;1\}^{32} \times \{0;1\}^{32} \longrightarrow \{0;1\}^{32}$
définies de la façon suivante ($\wedge$ représente le et logique exécuté bit à bit, $\vee$ est le ou logique, quand $\neg$ est la négation) : $f_t(B,C,D)$ est égal à...
On utilise aussi des constantes $K_t$, égales à
Soit $x$ un mot binaire qui a été gonflé en suivant la règle précédente. Sa longueur est divisible par 512 ; on l'écrit comme une suite de mots de 512 bits $x = M_1 M_2 ... M_n$
Pour l'initialisation, on utilise certains mots de 32 bits :
Dans ce qui suit :
La valeur hachée sera $SHA_1(x) = H_0 H_1 H_2 H_3 H_4$
On exécute la procédure suivante, pour $i=1,2, ... , n$ :
Programmez le SHA-1
La fonction de hachage SHA-256 agit sur une entrée dont le nombre de bits est $<2^{64}$ et sort un résumé de 256 bits.
La taille des blocs traités par SHA-256 est 512 bits.
On note ici
On définit alors 6 fonctions d'une ou plusieurs variables de 32 bits, ayant pour image un mot de 32 bits :
On utilise aussi 64 constantes de 32 bits notées $K_0^{256}, ..., K_{63}^{256}$
| 428a2f98 | 71374491 | b5c0fbcf | e9b5dba5 | 3956c25b | 59f111f1 |
| 923f82a4 | ab1c5ed5 | d807aa98 | 12835b01 | 243185be | 550c7dc3 |
| 72be5d74 | 80deb1fe | 9bdc06a7 | c19bf174 | e49b69c1 | efbe4786 |
| 0fc19dc6 | 240ca1cc | 2de92c6f | 4a7484aa | 5cb0a9dc | 76f988da |
| 983e5152 | a831c66d | b00327c8 | bf597fc7 | c6e00bf3 | d5a79147 |
| 06ca6351 | 14292967 | 27b70a85 | 2e1b2138 | 4d2c6dfc | 53380d13 |
| 650a7354 | 766a0abb | 81c2c92e | 92722c85 | a2bfe8a1 | a81a664b |
| c24b8b70 | c76c51a3 | d192e819 | d6990624 | f40e3585 | 106aa070 |
| 19a4c116 | 1e376c08 | 2748774c | 34b0bcb5 | 391c0cb3 | 4ed8aa4a |
| 5b9cca4f | 682e6ff3 | 748f82ee | 78a5636f | 84c87814 | 8cc70208 |
| 90befffa | a4506ceb | bef9a3f7 | c67178f2 |
Soit $M$ le message d'entrée.
Sa longueur en nombre de bits est $|M| = l < 2^{64}$.
Soit $k$ le plus petit entier tel que $l+k+1 \equiv 448 [512]$, c'est-à-dire $k = 448-l-1 [512]$
Le message préparé $M'$ est alors constitué des $l$ bits de $M$, suivi du bit 1, suivi de $k$ bits égaux à 0 et enfin de 64 bits représentant l'écriture du nombre $l$ en binaire.
Le message $M'$ a donc pour longueur : $|M'| = l+1+k+64 = 512 N$
Le message $M'$ est alors découpé en $N$ blocs de 512 bits : $M^(1),M^(2),...,M^(N)$.
Chaque bloc $M^(i)$ de 512 bits est lui-même découpé en 16 mots de 32 bits :
$M_0^(i),M_1^(i),...,M_{15}^(i)$
On va mettre le résultat du hachage (256 bits) dans 8 mots de 32 bits.
On part pour l'état initial du système de 8 mots de 32 bits nommés : $H_0^0, H_1^0, ..., h_7^0$
On va faire évoluer le sytème en calculant successivement $H_0^1, H_1^1, ...,H_7^1$, pour $1\leqslant i \leqslant N$, en utilisant successivement les blocs $M^(i)$.
Les valeurs initiales sont les suivantes :
Les mots ont, dans cet algorithme, pour taille 32 bits.
On dispose de 64 mots de tour $W_0, ..., W_{63}$ de 32 bits, de 8 variables de travail $a,b,c,d,e,f,g,h$ de 32 bits et de deux variables auxiliaires de 32 bits $T_1, T_2$.
Le message préparé et découpé comme précédemment est l'entrée du programme.
pour $(i=1 ; i \leqslant n ; i++)$ pour $(t=0 ; t \leqslant 15 ; t++)$ $W_t = M_t^(i)$ pour $(t=16 ; t \leqslant 63 ; t++)$ $W_t = \sigma_1^(256)(W_{t-2}) + W_{t-7} + \sigma_0^(256)(W_{t-15}) + W_{t-16}$ $a = H_0^(i-1) ; b = H_1^(i-1) ; c = H_2^(i-1) ; d = H_3^(i-1) ;$ $e = H_4^(i-1) ; f = H_5^(i-1) ; g = H_6^(i-1) ; h = H_7^(i-1) ;$ pour $(t=0 ; t \leqslant 63 ; t++)$ $T_1 = h + \Sigma_1^(256)(e) + Ch(e,f,g) + K_t^(256) + W_t;$ $T_2 = h + \Sigma_1^(256)(e) + Ch(e,f,g) + K_t^(256) + W_t;$ $h=g ; g=f ; f=e ; e=d+T_1 ;$ $d=c ; c=b ; b=a ; a=T_1+T_2;$ $H_0^(i) = a + H_0^(i-1) ; H_1^(i) = b + H_1^(i-1)$ ; $H_2^(i) = c + H_2^(i-1) ; H_3^(i) = d + H_3^(i-1)$ ; $H_4^(i) = e + H_4^(i-1) ; H_5^(i) = f + H_5^(i-1)$ ; $H_6^(i) = g + H_6^(i-1) ; H_7^(i) = h + H_7^(i-1)$ ;
La sortie est alors $H_0^(N)||H_1^(N)||H_2^(N)||H_3^(N)||H_4^(N)||H_5^(N)||H_6^(N)||H_7^(N)||$
Programmez le SHA-256.
Les autres fonctions de hachage utilisées en pratique sont construites comme ci-dessus.
Des modifications de cette construction accélèrent l'évaluation.
Le tableau suivant donne les caractéristiques de quelques fonctions de hachage utilisées en pratique.
| fonction de hachage | longueur des blocs | vitesse relative |
| MD4 | 128 | 1,00 |
| MD5 | 128 | 0,68 |
| RIPEMD-128 | 128 | 0,39 |
| SHA-1 | 160 | 0,28 |
| RIPEMD-160 | 160 | 0,24 |
Toutes ces fonctions de hachage sont très efficaces.
La fonction MD4 ne peut plus être considérée comme résistante : on a trouvé une collision en calculant $2^{20}$ valeurs hachées.
Cependant, le principe de construction de MD4 est utilisé dans toutes les autres fonctions de hachage de cette table.
De même, MD5 n'est plus totalement sûre.
Compte tenu de l'attaque des anniversaires, les 160 bits de SHA-1 impliquent une résistance à $2^{80}$ essais pour l'attaque brutale (ce n'est plus assez).
Des fonctions cryptographiques de hachage peuvent être utilisées pour tester si un fichier a été modifié :
Pour prouver l'intégrité d'un document et son authenticité, on peut utiliser des fonctions de hachage paramétrées.
Une fonction de hachage paramétrée est une famille $\{h_k, k \in K \}$ de fonctions de hachage, où $K$ est un ensemble appelé l'espace des clés de $h$.
Une fonction de hachage paramétrée s'appelle un code d'authentification de message. On dit aussi un MAC (Message Authentification Code).
La fonction de hachage $g:\{0;1\}^* \longrightarrow \{0;1\}^4$ peut être transformée pour donner le MAC $h_k: \{0;1\}^* \longrightarrow \{0;1\}^4, x \longmapsto g(x) \oplus k $ qui admet $\{0;1\}^4$ pour espace des clés.
L'exemple suivant illustre comment utiliser un MAC.
Le protocole de l'exemple précédent prouve l'authenticité à condition qu'il soit impossible de calculer le couple $(x,h_k(x))$ sans connaître $k$.
Essayez d'appliquer vos fonctions de hachage à un protocole d'authentification.