Fonctions de hachage

Comment vérifier 700 Mo sans les relire ?

Awa télécharge un logiciel de 700 Mo. Le site indique : « SHA-256 : ba78… ». Comment savoir que le fichier reçu est exactement celui publié, sans le comparer octet par octet avec un original qu'elle n'a pas ? Elle calcule une empreinte (en anglais digest ou hash) du fichier reçu et la compare à l'empreinte publiée : 64 caractères à comparer au lieu de 700 millions d'octets.

Qu'est-ce qu'une fonction de hachage ?

Une fonction de hachage prend des données de n'importe quelle taille (une suite d'octets) et renvoie une valeur de taille fixe. SHA-256, de la famille SHA-2 définie par la norme FIPS 180-4, renvoie toujours 256 bits, soit 32 octets. On les écrit en hexadécimal (base 16 : chiffres 0 à 9 puis lettres a à f), où chaque caractère représente 4 bits : 256 ÷ 4 = 64 caractères.

Tapez abc dans le widget ci-dessous : vous devez retrouver la deuxième ligne. Un fichier de 700 Mo, lui aussi, donne 64 caractères.

Deux familles de fonctions « de hachage »

À l'atelier 102, la fonction de hachage d'une table sert à répartir des clés dans des cases : il suffit qu'elle soit rapide et bien répartie. Une fonction de hachage cryptographique doit en plus résister à quelqu'un qui cherche activement à la mettre en défaut. On utilise la première pour des structures de données, la seconde pour la sécurité. Quand on dit « hachage » sans précision dans la suite du cursus, on parle de la seconde.

Un piège de débutant : ce qu'on hache vraiment

On hache des octets. Pour un texte, ce sont les octets de son codage (ici UTF-8). Un espace en trop ou un retour à la ligne caché change l'empreinte :

printf 'hello' | sha256sum
# 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

echo hello | sha256sum
# 5891b5b522d5df086d0ff0b110fbd9d21bb4fc7163af34d08286a2e846f6be03

La seconde commande hache hello suivi d'un retour à la ligne (la commande echo en ajoute un). Ce n'est pas la même donnée, donc pas la même empreinte. Quand deux personnes ne trouvent pas la même empreinte pour « le même texte », c'est presque toujours une différence invisible de ce genre.

À quoi sert une empreinte ?

• Vérifier l'intégrité d'un fichier téléchargé ou copié (leçon 4).
• Identifier un contenu par son empreinte : le système de versions Git nomme ainsi chaque objet.
• S'engager sur une donnée sans la révéler tout de suite : on publie l'empreinte, on dévoile la donnée plus tard.
• Lier des blocs : chaque bloc contient l'empreinte du précédent (leçon 4, puis les ateliers de blockchain).

Ce que cela ne garantit pas

• Une empreinte seule ne dit pas qui a produit le fichier : n'importe qui peut calculer le SHA-256 de n'importe quoi. Prouver l'auteur demande une signature (atelier 105).
• Elle ne cache pas forcément la donnée (leçon 3).
• Deux fichiers dont les empreintes sont égales sont, en pratique, identiques ; l'inverse « empreintes différentes ⇒ fichiers différents » est, lui, absolument certain.

À retenir

Fonction de hachage : octets de taille quelconque → empreinte de taille fixe (SHA-256 : 256 bits, 64 caractères hexadécimaux). Elle porte sur les octets, au caractère près. L'empreinte identifie un contenu, mais n'en identifie pas l'auteur.

Que doit-on exiger d'une bonne empreinte ?

Imaginons qu'Awa utilise comme empreinte « la somme des codes des lettres, modulo 1 000 ». C'est rapide, de taille fixe… et inutilisable : « AWA » et « AAW » ont la même empreinte (anagrammes), et changer une lettre ne change l'empreinte que de quelques unités. Les trois propriétés ci-dessous sont celles que ce jouet n'a pas.

1. Déterminisme

La même entrée donne toujours la même empreinte, sur toute machine, à tout moment, sans clé secrète. C'est ce qui permet à deux personnes qui ne se connaissent pas de comparer leurs résultats. Le déterminisme s'accompagne d'une sortie de taille fixe (SHA-256 : 256 bits) et d'un calcul rapide : hacher un fichier est presque instantané.

2. Effet d'avalanche

Un changement minuscule de l'entrée — un seul caractère, un seul bit — change l'empreinte de façon imprévisible, comme si elle était entièrement nouvelle. Comparez :

Seule la première lettre change (h → H, un seul bit d'écart dans le codage). Pourtant l'empreinte ne ressemble plus à l'autre : en les comparant position par position, 61 des 64 caractères hexadécimaux diffèrent. Ce n'est pas un hasard : si deux chaînes hexadécimales étaient indépendantes, chaque position coïnciderait avec la probabilité 1/16, soit en moyenne 64 ÷ 16 = 4 positions identiques et environ 60 différentes. Voir environ 60 différences, quelle que soit la proximité des entrées, est exactement ce qu'on attend. Cela correspond à environ la moitié des bits : un caractère hexadécimal diffère dès qu'un seul de ses 4 bits diffère, ce qui arrive 15 fois sur 16, alors que chaque bit pris isolément diffère une fois sur deux. Utilisez le widget pour comparer deux textes d'un caractère d'écart et compter les différences.

L'avalanche est un critère de conception, observable à l'œil, qui découle des exigences de sécurité ; il n'est pas à lui seul une preuve de sécurité. Il explique pourtant pourquoi on ne peut pas « s'approcher » d'une empreinte cible par petites retouches successives.

3. Résistance aux collisions (et à ses deux cousines)

Une collision est un couple de deux entrées différentes qui donnent la même empreinte. Les collisions existent forcément : il y a une infinité d'entrées possibles et seulement 2^256 empreintes (principe des tiroirs). La propriété demandée est qu'il soit infaisable de les trouver. Les manuels distinguent trois niveaux, du plus faible au plus exigeant :

Combien d'essais ? Des ordres de grandeur

Pour SHA-256, retrouver une préimage par essais aveugles demande de l'ordre de 2^256 ≈ 1,2 × 10^77 essais. Pour une collision, le paradoxe des anniversaires montre qu'on en trouve une après environ la racine carrée de ce nombre, soit de l'ordre de 2^128 ≈ 3,4 × 10^38 essais : c'est la meilleure attaque générique connue, et c'est pourquoi on dit que SHA-256 offre environ 128 bits de sécurité contre les collisions. Ces nombres sont hors d'atteinte de tout matériel imaginable.

Pour sentir le principe, tronquons l'empreinte à 16 bits (65 536 valeurs possibles) : par le même raisonnement, une collision apparaît après environ √65 536 = 256 entrées, c'est-à-dire en quelques instants. La longueur de l'empreinte fixe le coût de l'attaque : une empreinte courte est une empreinte cassée.

Ce que cela ne garantit pas

• « Infaisable » ne veut pas dire « impossible » : c'est un jugement sur l'état actuel du calcul et de la cryptanalyse. Une fonction peut être affaiblie : MD5 et SHA-1 en sont les exemples (leçon 4).
• À ma connaissance, aucune collision pratique sur SHA-256 n'a été publiée ; cela peut changer, et c'est pourquoi les normes sont revues. Les chiffres ci-dessus valent pour les attaques génériques sur un ordinateur ordinaire ; des ordinateurs quantiques, s'ils existent un jour à grande échelle, réduiraient ces coûts génériques (sans les rendre nuls), et c'est un sujet suivi par les organismes de normalisation.
• Ces trois propriétés ne couvrent ni le secret ni l'authenticité (leçon 3).

À retenir

Déterminisme : même entrée, même sortie, taille fixe. Avalanche : un petit changement fait diffèrer environ 60 caractères sur 64. Résistance aux collisions : trouver deux entrées de même empreinte est infaisable (environ 2^128 essais pour SHA-256), bien que de telles paires existent.

« On a chiffré les codes PIN avec SHA-256 »

Un petit service garde, pour chaque client, l'empreinte SHA-256 de son code PIN à 4 chiffres, et dit : « les codes sont chiffrés, personne ne peut les lire ». Est-ce vrai ? La réponse demande de séparer deux opérations qu'on confond souvent.

Chiffrer et hacher : deux outils différents

Hacher est à sens unique pour deux raisons qui s'ajoutent. D'abord, la fonction perd de l'information : un fichier de 1 Go donne 32 octets, et d'innombrables entrées donnent la même empreinte, donc « déchiffrer » n'aurait même pas de sens. Cela ne suffit pourtant pas (couper un fichier après ses 32 premiers octets perd aussi de l'information, et se « retrouve » trivialement quand l'entrée est courte). Ensuite, la résistance à la préimage : trouver une entrée qui donne une empreinte donnée est supposé infaisable… à condition de ne pas pouvoir deviner l'entrée.

Le piège des entrées devinables

Un code PIN à 4 chiffres n'a que 10 000 valeurs possibles (0000 à 9999). Un attaquant qui dérobe la base de données calcule le SHA-256 de ces 10 000 candidats et cherche chaque empreinte volée dans sa liste. Ce calcul prend une fraction de seconde sur un ordinateur ordinaire (quelques millisecondes en Python). Le SHA-256 de 1234, par exemple, est 03ac674216f3e15c761ee1a5e255f067953623c8b388b4459e13f978d7c846f4 : n'importe qui peut le calculer et le reconnaître. L'empreinte ne « cache » donc rien : la sécurité d'un secret haché est la sécurité de la difficulté à le deviner. Le PIN n'était pas protégé, il était seulement déguisé.

Mots de passe : il faut un hachage fait pour cela

Un bon hachage de mots de passe doit être lent exprès et salé :

• le sel (salt) est une valeur aléatoire propre à chaque utilisateur, stockée à côté de l'empreinte et mélangée au mot de passe avant le hachage. Deux utilisateurs avec le même mot de passe ont alors des empreintes différentes, et les tables d'empreintes précalculées deviennent inutiles ;
• une fonction volontairement lente (Argon2, scrypt, bcrypt, PBKDF2 ; Argon2 et scrypt exigent en plus beaucoup de mémoire) rend chaque essai de l'attaquant coûteux. SHA-256 simple, conçu pour être rapide, est un mauvais choix ici.

Aucune de ces précautions n'est « du chiffrement » : le mot de passe n'est jamais récupéré, seulement comparé.

Prouver qui a produit un message : HMAC

Une empreinte seule ne prouve pas l'auteur : l'attaquant peut modifier le message et recalculer l'empreinte. Un HMAC mélange une clé secrète partagée au message avant le hachage : seule une personne qui connaît la clé peut produire l'HMAC correct. Le widget ci-dessous calcule un HMAC-SHA256 : essayez-le avec une clé fictive (par exemple cle-fictive-de-demonstration), puis changez un caractère du message ou de la clé et observez que l'HMAC change entièrement. Avec un HMAC, celui qui vérifie doit connaître la même clé que celui qui produit : la preuve est donc partagée entre deux personnes, pas publique. Les signatures de l'atelier 105 apporteront une preuve vérifiable par tous.

Ce que cela ne garantit pas

• Hacher ne cache pas une donnée devinable (PIN, prénom, numéro de téléphone) : l'attaquant essaie toutes les possibilités.
• Une empreinte égale révèle que deux données sont égales : c'est utile (détecter un doublon) mais c'est aussi une fuite.
• Une empreinte ne prouve pas l'origine : n'importe qui peut hacher n'importe quoi.

À retenir

Chiffrer = réversible avec une clé ; hacher = sans clé, à sens unique, taille fixe. Un secret haché n'est protégé que par la difficulté de le deviner : les PIN et mots de passe demandent un hachage lent et salé. HMAC ajoute une clé pour authentifier un message entre deux personnes qui la partagent.

Vérifier une empreinte de fichier

Sur Linux et macOS : sha256sum fichier (ou shasum -a 256 fichier). Sous Windows, dans PowerShell : Get-FileHash fichier -Algorithm SHA256. En Python :

import hashlib

def sha256_file(path):
    h = hashlib.sha256()
    with open(path, "rb") as f:
        for chunk in iter(lambda: f.read(65536), b""):
            h.update(chunk)
    return h.hexdigest()

On lit par morceaux pour ne pas charger 700 Mo en mémoire ; l'empreinte finale est la même que si l'on avait lu tout d'un coup. Les projets publient souvent un fichier d'empreintes dont chaque ligne est « empreinte, deux espaces, nom du fichier », que sha256sum -c vérifie automatiquement.

Lire le résultat. Les deux empreintes sont identiques au caractère près, ou elles ne le sont pas : il n'y a pas de « presque identique ». Une seule différence — même au dernier caractère — signifie que le fichier n'est pas celui qui a été publié. Cela peut être une corruption (téléchargement interrompu) ou une altération volontaire ; dans les deux cas, ne l'exécutez pas.

D'où vient l'empreinte de référence ?

Vérifier suppose que l'on fait confiance à l'empreinte publiée. Si le fichier et l'empreinte viennent du même serveur compromis, l'attaquant remplace les deux et la vérification réussit. L'empreinte protège donc contre la corruption accidentelle et contre un fichier altéré lorsque l'empreinte a été obtenue par un canal distinct et fiable (autre site officiel, annonce signée). Pour une preuve qui tienne même si le serveur est compromis, il faut une signature numérique (atelier 105).

Enchaîner des blocs par leurs empreintes

L'atelier 103 s'est terminé sur un problème : modifier une ligne du journal ne laissait aucune trace. Voici l'idée qui le résout. Chaque bloc contient ses données et l'empreinte du bloc précédent ; son empreinte à lui est calculée sur le tout. Notre chaîne JOUET, avec la convention « numéro | données | empreinte précédente » :

bloc 1 : 1|Awa credit 100|GENESIS
         empreinte h1 = fa68461319a4bcab4ea332b39bc1d03311f222f813c36432235756047f20c312

bloc 2 : 2|Awa pays Kofi 30|fa68461319a4bcab4ea332b39bc1d03311f222f813c36432235756047f20c312
         empreinte h2 = fdec2cc6e9c9c0997020c1acc3b3f044ab80cb6fd5a963da3881ac1c035523bd

bloc 3 : 3|Kofi pays Mba 10|fdec2cc6e9c9c0997020c1acc3b3f044ab80cb6fd5a963da3881ac1c035523bd
         empreinte h3 = eff5f1c07e8133f22ba376f95f24d1692dbcb842b23746824cc84afd1cb10575

Vous pouvez recalculer h1 en tapant exactement 1|Awa credit 100|GENESIS dans le widget sha256.

L'attaque. Un fraudeur change, dans le bloc 2, « 30 » en « 300 ». L'empreinte du bloc 2 devient 2f359f87ad0dcc90… au lieu de fdec2cc6e9c9c099…. Or le bloc 3 contient toujours l'ancienne empreinte (fdec2cc6…) : en recalculant, la vérification constate que l'empreinte du bloc 2 ne correspond plus à ce que le bloc 3 annonce. L'altération est détectée.

Pour la cacher, le fraudeur doit corriger le bloc 3 (il y met 2f359f87…), ce qui change l'empreinte du bloc 3, donc il doit corriger le bloc 4, et ainsi de suite jusqu'à la fin de la chaîne. Dans une chaîne de n blocs où l'on modifie le bloc k, il faut recalculer tous les blocs de k + 1 à n. Et si quelqu'un d'autre a gardé une copie de la dernière empreinte, la chaîne réécrite ne correspondra plus à cette copie. Le widget « chain-explorer » vous laisse modifier un bloc et voir se briser les empreintes suivantes.

L'avertissement honnête

• Le chaînage détecte une modification ; il ne l'empêche pas. Si personne ne conserve ailleurs la dernière empreinte, un fraudeur qui contrôle toute la chaîne peut la réécrire entièrement, proprement. Que plusieurs acteurs indépendants gardent la même chaîne est l'objet de l'atelier sur le consensus.
• Il ne dit pas qui a écrit un bloc, ni que son contenu est vrai : il garantit seulement que le contenu n'a pas changé depuis que l'empreinte a été calculée.
• Notre convention de chaîne est un jouet. Les vraies chaînes ont un format précis (en-têtes d'octets, double hachage dans Bitcoin), que vous verrez plus tard.

MD5 et SHA-1 : pourquoi on les proscrit

Des collisions pratiques ont été publiées pour MD5 (dans les années 2000) et pour SHA-1 (première collision publique en 2017). Ces fonctions ne remplissent donc plus la résistance aux collisions, et on ne les utilise plus pour des signatures ou des certificats. MD5 reste correct pour détecter une corruption accidentelle, mais pas face à un adversaire. Voir l'exercice de sécurité.

À retenir

Vérifier un fichier = calculer son empreinte et la comparer, caractère par caractère, à une référence obtenue par un canal fiable. Chaîner des blocs par leurs empreintes rend toute modification détectable et oblige à recalculer tous les blocs suivants, sans la rendre impossible.