Fonctions de hachage et codes d'authentification

Toute la cryptographie de la confidentialité laisse une question en suspens : comment s’assurer qu’un message n’a pas été altéré, et qu’il provient bien de qui l’on croit ? C’est le domaine des fonctions de hachage et des codes d’authentification, qui ne chiffrent rien mais garantissent l’intégrité et l’authenticité. On les rencontre partout — vérification d’un fichier téléchargé, identification d’un malware par son empreinte, signature numérique, stockage des mots de passe, authentification des messages et des entités.

WARNING

Une fonction de hachage ne chiffre pas : elle ne permet aucune restitution du message d’origine. Confondre les deux est une faute d’analyse fréquente.

La fonction de hachage

Une fonction de hachage $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ associe à un message de longueur arbitraire une empreinte de taille fixe. La conséquence est immédiate et structurelle : $H$ ne peut être injective, et il existe donc nécessairement des collisions — deux messages distincts de même empreinte. Toute la difficulté sera de les rendre introuvables.

Les trois propriétés de sécurité

Une fonction de hachage est dite cryptographique si sa sortie est pseudo-aléatoire et qu’elle satisfait trois résistances, qu’il importe de ne pas confondre :

• résistance à la préimage : étant donné $y$, il est difficile de trouver $x$ tel que $H(x)=y$ ;
• résistance à la seconde préimage : étant donné $x_1$, il est difficile de trouver $x_2\ne x_1$ de même empreinte ;
• résistance aux collisions : il est difficile de trouver un quelconque couple $x_1\ne x_2$ tel que $H(x_1)=H(x_2)$.

Ces notions sont distinctes, et de force croissante : collision $\ne$ seconde préimage $\ne$ préimage.

L’oracle aléatoire

Pour raisonner formellement, on idéalise $H$ en un oracle aléatoire : à tout message nouveau il répond une valeur tirée uniformément dans $\{0,1{\}}^n$, et à un message déjà vu la même valeur qu’auparavant. Ce modèle permet de démontrer des propriétés de sécurité — étant entendu qu’aucune fonction réelle n’est un véritable oracle aléatoire, ce qui fait de ces preuves des garanties heuristiques plutôt qu’absolues.

Ce qu’en coûte une attaque par force brute

L’oracle aléatoire fixe les complexités de référence. Trouver une préimage ou une seconde préimage revient à essayer des entrées au hasard, en $O(2^n)$ opérations en moyenne. Une collision, en revanche, se trouve bien plus vite : le paradoxe des anniversaires garantit qu’en tirant de l’ordre de $2^{n/2}$ empreintes, deux d’entre elles coïncideront.

Propriété	Complexité générique
Préimage	$O(2^n)$
Seconde préimage	$O(2^n)$
Collision	$O(2^{n/2})$

La collision étant l’attaque la plus efficace, c’est elle qui dicte la taille des empreintes : une sortie de 256 bits ne vaut « que » 128 bits de sécurité face aux collisions.

Construire une fonction de hachage

En pratique, on hache itérativement. On se donne une fonction de compression $h:\{0,1{\}}^k\times \{0,1{\}}^n\to \{0,1{\}}^n$, on découpe le message padé en blocs $x_1\Vert \dots \Vert x_t$, et l’on chaîne à partir d’une valeur initiale :

$y_0=\text{IV},y_i=h(x_i,y_{i-1}),H(x)=y_t.$

flowchart LR
    IV --> h1[h]
    x1 --> h1
    h1 --> y1
    y1 --> h2[h]
    x2 --> h2
    h2 --> y2
    y2 --> h3[h]
    xt --> h3
    h3 --> Hx[H_x]

Le théorème qui fonde cette construction (Merkle-Damgård) est le suivant : toute collision sur $H$ induit une collision sur $h$. La sécurité de l’ensemble est donc bornée par celle de sa fonction de compression — il suffit de bien construire $h$.

Une variante, le hachage arborescent de Merkle, découpe le message en feuilles hachées puis recombinées deux à deux jusqu’à une racine unique ; le même théorème s’y applique.

flowchart TB
    m1 --> h1[h]
    m2 --> h2[h]
    m3 --> h3[h]
    m4 --> h4[h]
    h1 --> h12[h]
    h2 --> h12
    h3 --> h34[h]
    h4 --> h34
    h12 --> root[racine]
    h34 --> root

Côté standards, on retiendra que les familles historiques — MD4, MD5, SHA-0, SHA-1 — sont aujourd’hui cassées pour la résistance aux collisions, et qu’il faut leur préférer SHA-2 (SHA-256, SHA-512) ou SHA-3.

Le code d’authentification de message

Le hachage seul garantit l’intégrité, non l’authenticité : quiconque peut recalculer $H(m)$ après avoir modifié $m$. Pour lier l’empreinte à une identité, on introduit une clé secrète partagée.

Définition

Un code d’authentification de message (MAC) est une fonction ${\mathrm{MAC}}_k:\{0,1{\}}^{\ast }\to \{0,1{\}}^n$ dont la sortie dépend d’une clé secrète $k$. Sans la clé, on ne peut ni forger ni vérifier le code.

Combiner chiffrement et authentification

Lorsqu’on veut à la fois confidentialité et authenticité, l’ordre des opérations compte. La composition Encrypt-then-MAC — chiffrer, puis authentifier le chiffré — est la seule recommandée : on rejette un message inauthentique avant tout déchiffrement, se prémunissant contre les attaques à chiffré choisi. Le schéma inverse, MAC-then-Encrypt, est conceptuellement plus fragile.

CBC-MAC

On peut bâtir un MAC sur un chiffrement par bloc, à la manière du mode CBC :

$H_0=\text{IV},H_i=E_k(H_{i-1}\oplus m_i),$

le MAC étant le dernier bloc $H_t$.

flowchart LR
    IV --> X1[XOR]
    m1 --> X1
    X1 --> E1[E_k]
    E1 --> H1
    H1 --> X2[XOR]
    m2 --> X2
    X2 --> E2[E_k]
    E2 --> H2
    H2 --> Xt[XOR]
    mt --> Xt
    Xt --> Et[E_k]
    Et --> MAC

L’IV n’a pas besoin d’être secret (on le fixe souvent à zéro), mais le procédé n’est sûr que pour des messages de longueur fixe — sur des longueurs variables, il se laisse forger.

HMAC

Les constructions naïves à base de hachage — $H(k\Vert m)$, $H(m\Vert k)$ — sont vulnérables, notamment aux attaques par extension de longueur sur les fonctions de type Merkle-Damgård. La construction robuste et standardisée est HMAC :

${\mathrm{HMAC}}_k(m)=H((k_0\oplus \text{opad})\Vert H((k_0\oplus \text{ipad})\Vert m)),$

où $k_0$ est la clé ajustée à la taille de bloc, $\text{ipad}=\text{0x36}\dots$ et $\text{opad}=\text{0x5C}\dots$. HMAC demeure sûr tant que $H$ n’est pas complètement brisée, indépendamment de certaines faiblesses structurelles internes — ce qui explique son omniprésence, de TLS à IPsec en passant par l’authentification des API.

Authentifier une entité, déjouer le rejeu

Authentifier un message ne suffit pas à authentifier son émetteur dans le temps : un adversaire peut rejouer un message valide intercepté. La parade est le nonce — un défi aléatoire, intégré au message authentifié à chaque échange. Un ancien MAC, calculé sur un ancien nonce, devient dès lors invalide, et le rejeu échoue.