Hachage dans les systèmes: intégrité, arbres et preuves

Hachage dans les systèmes: intégrité, arbres et preuves

Une fonction de hachage cryptographique, présentée en détail dans Condensés cryptographiques : propriétés, constructions et familles, transforme un contenu de taille quelconque en une empreinte de taille fixe, 256 bits pour SHA-256, de telle sorte qu’il soit irréaliste de trouver deux contenus de même empreinte. Ce chapitre quitte la fonction pour regarder les systèmes qui l’emploient : vérification de téléchargements, arbres de Merkle, journaux de transparence, preuves de stockage, déduplication et circuits de preuves à divulgation nulle. Le fil conducteur est simple et souvent oublié : une empreinte dit si quelque chose a changé, jamais qui l’a écrit, et elle ne protège un secret que si ce secret est difficile à deviner.

Explication de la marmotte

Une empreinte de fichier ressemble à une empreinte digitale : une petite trace, propre à chaque document, qui permet de vérifier qu’on a bien le bon sans relire tout son contenu. Cette page montre comment ces traces protègent des téléchargements, des registres entiers ou des preuves, et pourquoi elles disent seulement si quelque chose a changé, jamais qui l’a écrit.

→ Lire l’explication complète de la marmotte

Comment vérifier l’intégrité d’un fichier ?

Le cas d’école est le téléchargement d’une image d’installation. L’éditeur publie à côté du fichier un digest (empreinte) SHA-256 ; l’utilisateur recalcule l’empreinte du fichier reçu et compare.

# Calculer l'empreinte d'un fichier
sha256sum debian-12.iso
# 3f2a...e91c  debian-12.iso

# Vérifier un lot de fichiers contre une liste publiée
sha256sum -c SHA256SUMS --ignore-missing
# debian-12.iso: OK

Cette vérification détecte une corruption accidentelle (téléchargement interrompu, disque défaillant) et une modification du fichier seul. Elle ne détecte pas un attaquant qui contrôle à la fois le fichier et la liste d’empreintes, ce qui est exactement la situation d’un miroir compromis ou d’un site piraté : il remplace l’image et met à jour la ligne correspondante, la comparaison réussit, et l’utilisateur installe un système piégé avec la satisfaction du devoir accompli. Publier uniquement un hash ne prouve donc pas l’authenticité.

La réponse est une signature au-dessus du hash : l’éditeur signe le fichier d’empreintes avec sa clé privée, et l’utilisateur vérifie cette signature avec une clé publique obtenue par un autre canal, idéalement en amont et une fois pour toutes.

# Vérifier la signature du fichier d'empreintes, puis les empreintes elles-mêmes
gpg --verify SHA256SUMS.sign SHA256SUMS
sha256sum -c SHA256SUMS --ignore-missing

Le schéma est efficace parce qu’une seule signature couvre des centaines de fichiers : la signature garantit l’origine de la liste, et la résistance aux collisions de la fonction de hachage étend cette garantie à chaque fichier listé. La page Signer numériquement détaille la vérification d’une signature.

Encore faut-il que la fonction résiste aux collisions dans le contexte. MD5 et SHA-1 sont cassés pour cet usage : la collision SHA-1 publiée en 2017 sous le nom SHAttered a produit deux fichiers PDF (Portable Document Format) distincts de même empreinte, et le logiciel malveillant Flame, découvert en 2012, a exploité une collision MD5 pour forger un certificat de signature de code accepté par Windows Update. Une collision n’est dangereuse que si l’attaquant peut préparer les deux documents ; vérifier qu’un fichier tiers n’a pas été corrompu en transit ne relève que de la seconde préimage, contre laquelle MD5 tient encore. Ce n’est pas une raison pour le garder : la frontière entre les deux situations est difficile à garantir.

Arbres de Merkle et preuves d’inclusion

Hacher un million d’enregistrements en une seule empreinte permet de vérifier l’ensemble, mais pas un élément isolé sans tout relire. L’arbre de Merkle résout ce problème : les feuilles sont les empreintes des éléments, chaque nœud interne est l’empreinte de la concaténation de ses deux enfants, et la racine résume l’ensemble.

Prenons quatre éléments A, B, C, D, et notons H la fonction de hachage :

Pour prouver que C appartient à l’ensemble dont la racine publiée est R, il suffit de fournir hD et N1. Le vérificateur calcule hC = H(C), puis N2 = H(hC || hD), puis H(N1 || N2), et compare le résultat à R. La preuve d’inclusion contient une empreinte par niveau de l’arbre, soit log₂(n) empreintes : 2 pour 4 éléments, 20 pour un million, 30 pour un milliard. À 32 octets par empreinte SHA-256, prouver l’appartenance d’un élément parmi un milliard tient en moins d’un kilo-octet.

Un détail sépare la version d’école de la version sûre : il faut distinguer le hachage d’une feuille de celui d’un nœud interne. Sans cette distinction, un nœud interne (64 octets de deux empreintes concaténées) peut être présenté comme une feuille, ce qui permet de « prouver » l’appartenance d’un élément qui n’en est pas un. La RFC 6962, qui définit la Certificate Transparency, préfixe donc les feuilles par l’octet 0x00 et les nœuds par 0x01 : H(0x00 || feuille) et H(0x01 || gauche || droite). C’est un premier exemple de domain separation (séparation de domaine), sur laquelle la fin de ce chapitre revient.

Un arbre de Merkle n’est pas une blockchain. La blockchain chaîne des blocs dont chacun contient l’empreinte du précédent, et elle emploie des arbres de Merkle à l’intérieur de chaque bloc pour résumer les transactions ; mais un arbre de Merkle seul n’implique ni consensus distribué, ni jeton, ni minage. C’est une structure de données, pas un modèle de gouvernance. La page Chaînes de blocs, wallets et cryptographie économique traite l’autre sujet.

Journaux transparents et chaîne d’approvisionnement

Les journaux de transparence combinent arbre de Merkle et contrainte d’ajout seul (append-only). La Certificate Transparency oblige les autorités de certification à inscrire les certificats qu’elles émettent dans des journaux publics. Chaque journal publie régulièrement une racine signée ; il fournit sur demande une preuve d’inclusion (ce certificat figure bien dans l’arbre de racine R) et une preuve de cohérence (l’arbre de racine R₂ prolonge l’arbre de racine R₁ sans rien modifier ni retirer). Des auditeurs indépendants vérifient ces preuves : un journal qui réécrirait son passé, ou qui montrerait deux versions différentes à deux observateurs, se trahirait par une racine incohérente.

Le même mécanisme protège désormais la chaîne d’approvisionnement logicielle. La base de sommes de contrôle du langage Go (sum.golang.org) inscrit l’empreinte de chaque version de module dans un journal transparent : un développeur qui télécharge une version reçoit la même empreinte que tous les autres, et un dépôt qui servirait une version modifiée à une seule victime serait détecté. Le projet Sigstore applique la même idée aux signatures d’artefacts avec son journal Rekor. L’intérêt n’est pas d’empêcher l’attaque mais de la rendre visible.

Atelier : vérifier un artefact logiciel de bout en bout

Une vérification complète d’un artefact téléchargé enchaîne quatre contrôles, chacun répondant à une question différente :

1. La clé publique de l’éditeur est-elle la bonne ? Elle a été obtenue par un canal indépendant du téléchargement (paquet de la distribution, empreinte publiée dans la documentation officielle, trousseau déjà installé).
2. La liste d’empreintes est-elle signée par cette clé ? gpg --verify répond, et sa sortie doit mentionner une signature valide par la clé attendue, pas seulement « signature correcte » par une clé inconnue.
3. L’artefact correspond-il à la liste ? sha256sum -c répond.
4. Le contexte signé est-il le bon ? Une signature valide sur l’empreinte de la version 1.2.3 ne dit rien de la version 1.2.4. Si le nom de fichier ou le numéro de version ne fait pas partie de ce qui est signé, un attaquant peut servir une ancienne version authentique et vulnérable, parfaitement signée. Les formats modernes signent donc un manifeste qui inclut nom, version et empreinte.

Oublier ce quatrième point est le piège le plus courant : la signature est mathématiquement valide, et pourtant elle atteste autre chose que ce que le vérificateur croit.

Stockage, déduplication et fuites

Un client qui confie des données à un prestataire veut parfois s’assurer qu’elles sont toujours là sans tout retélécharger. Les proofs of storage (preuves de stockage), étudiées notamment depuis 2007 sous les noms PDP (Provable Data Possession) et PoR (Proofs of Retrievability), répondent à ce besoin par un défi : le client demande l’empreinte d’un ensemble de blocs tirés au hasard, combinés à une valeur fraîche. La valeur fraîche est essentielle : si les défis sont prévisibles, un serveur malhonnête précalcule les réponses, jette les données et répond quand même. Une preuve de stockage n’est pas pour autant une sauvegarde vérifiée : elle atteste que le prestataire détient les données au moment du défi, pas qu’une restauration complète fonctionnerait, ni que les données sont copiées ailleurs.

La déduplication évite de stocker deux fois le même fichier en l’identifiant par son empreinte. Pratiquée côté client, elle économise aussi la bande passante : le client envoie l’empreinte, et si le serveur la connaît déjà, l’envoi est sauté. C’est une fuite de présence : n’importe quel client apprend, en mesurant si l’envoi a eu lieu, qu’un fichier donné existe déjà chez le prestataire. Avec des documents à faible variabilité, la fuite devient une attaque : un modèle de lettre de l’entreprise où seul un code d’accès à 4 chiffres change n’offre que 10 000 versions possibles, et un attaquant qui les teste une à une apprend laquelle est stockée. Des chercheurs ont décrit ce type d’attaque dès 2010 contre des services de stockage grand public. Le chiffrement convergent, qui dérive la clé de chiffrement de l’empreinte du fichier pour permettre la déduplication de données chiffrées, hérite exactement de la même faiblesse.

Le problème général est celui des données à faible entropie. Hacher un numéro de téléphone pour le « pseudonymiser » ne protège rien : il existe de l’ordre de 10¹⁰ numéros à dix chiffres, et un processeur graphique calcule plusieurs milliards d’empreintes SHA-256 par seconde. L’empreinte d’un numéro, d’une date de naissance ou d’une adresse électronique se retrouve en quelques secondes par énumération. La parade dépend du besoin. Pour rendre les empreintes non comparables entre elles, on ajoute un sel unique et aléatoire. Pour empêcher un tiers de recalculer les empreintes, on utilise un HMAC (Hash-based Message Authentication Code) avec une clé secrète, ce qui transforme l’empreinte en pseudonyme réellement dépendant d’un secret. Pour des mots de passe, on utilise une fonction volontairement lente comme Argon2id, objet de la page Transformer mots de passe et secrets applicatifs en clés. Le sel n’est pas une solution universelle : il empêche les tables précalculées, pas l’énumération d’un espace minuscule.

Hachage dans les circuits à divulgation nulle

Les preuves à divulgation nulle de connaissance, ou ZK (Zero-Knowledge), présentées dans Prouver sans révéler, permettent de prouver qu’un calcul a été correctement effectué sans en révéler les entrées. Ce calcul doit être exprimé sous forme d’un circuit arithmétique sur un corps fini, et son coût de preuve croît avec le nombre de contraintes du circuit.

Les fonctions généralistes comme SHA-256 sont conçues pour les processeurs : elles manipulent des bits, des rotations et des opérations logiques, toutes coûteuses à exprimer comme équations sur un grand corps fini. Une seule compression SHA-256 représente plusieurs dizaines de milliers de contraintes. D’où les hachages algébriques, conçus pour être peu coûteux dans ces circuits : MiMC, Poseidon ou Rescue n’utilisent que des additions et des multiplications dans le corps, et ramènent le coût à quelques centaines de contraintes. La contrepartie est une maturité moindre : ces familles sont récentes, leur cryptanalyse progresse encore, et elles ne remplacent pas SHA-256 hors de ce contexte. Choisir un hachage algébrique pour hacher des fichiers sur un serveur, ou SHA-256 dans un circuit sans raison d’interopérabilité, revient à payer un coût sans contrepartie. Le choix précis d’une fonction et de ses paramètres dépend du système de preuve et doit suivre les recommandations de ses concepteurs.

La domain separation prend ici toute son importance. Lorsqu’une même fonction sert à plusieurs usages dans un protocole (feuilles, nœuds, engagements, dérivation de défis), chaque usage reçoit une étiquette distincte, préfixe ou paramètre d’initialisation, pour qu’une sortie produite dans un rôle ne puisse jamais être réinterprétée dans un autre. C’est la même leçon que celle des octets 0x00 et 0x01 de la Certificate Transparency, à une autre échelle.

Ce qu’il ne faut pas confondre

Une empreinte n’est pas une signature : la première dit « ce contenu n’a pas changé par rapport à cette référence », la seconde dit « cette référence vient du détenteur de cette clé ». Un arbre de Merkle n’est pas une blockchain, une preuve de stockage n’est pas une sauvegarde vérifiée, et un hachage algébrique n’est pas un hachage généraliste au rabais mais un outil spécialisé, pertinent dans un seul type de système.

🐝 Ce qui arrive si on s’en passe

Sans empreintes vérifiées ni journal limité à l’ajout, un artefact modifié entre sa publication et son installation passe inaperçu : le système l’exécute avec la même confiance que l’original. La perte se paie aussi après coup. Faute d’empreinte conservée au moment de l’installation, impossible d’établir quelle version tournait réellement le jour de l’incident, ni depuis quand ; l’enquête compare alors des souvenirs plutôt que des octets. Un journal dépourvu de preuve d’inclusion permet en outre de retirer discrètement une entrée gênante, sans que personne puisse démontrer qu’elle a un jour existé.

🦫 Explication de la marmotte 🍫

Une fonction de hachage transforme n’importe quel contenu en une empreinte courte, toujours de la même taille. Le moindre changement dans le contenu donne une empreinte totalement différente. Pour vérifier un fichier téléchargé, on recalcule son empreinte et on la compare à celle publiée par l’auteur. Cela prouve seulement que le fichier correspond à cette empreinte : si un pirate remplace à la fois le fichier et l’empreinte sur un site miroir, la comparaison réussit quand même. Il faut donc une signature, calculée avec la clé secrète de l’auteur et posée sur l’empreinte. Pour de grandes quantités de données, on range les empreintes dans un arbre de Merkle : on hache les éléments deux par deux, puis les résultats deux par deux, jusqu’à obtenir une seule empreinte au sommet. Prouver qu’un élément appartient à l’ensemble ne demande alors que quelques empreintes voisines. Les journaux publics de certificats reposent sur ce principe et n’acceptent que des ajouts. Il existe des limites. Si les données possibles sont peu nombreuses, un attaquant calcule toutes les empreintes et retrouve la donnée d’origine ; on ajoute alors un sel, une valeur aléatoire mêlée au contenu, ou mieux une clé secrète. La déduplication, qui évite de stocker deux fois le même fichier, peut aussi révéler qu’un fichier existe déjà ailleurs.

À lire aussi

• Prouver qu’un message vient du bon secretExpliquer les MAC, les PRF et les tags symétriques, en insistant sur la vérification stricte et le temps constant.
• Calculer, engager et anonymiser avec des primitives spécialiséesRegrouper les primitives avancées qui protègent des calculs, des engagements ou des identités, tout en exposant leurs coûts et leurs fuites résiduelles.
• Comprendre la cryptanalyse sans perdre le fil pratiqueExpliquer comment lire une attaque cryptographique: modèle, coût, données nécessaires, marge et impact opérationnel.
• Équité, vote, contrats et divulgation contrôléeConserver les protocoles avancés classiques en les réorganisant autour des problèmes d’équité, de décision collective et de divulgation contrôlée.

Pages voisines

La citent

• AI Act : journalisation automatique d'une IA à haut risque (articles 12, 19 et 26)
• Ce qu'on garde
• La chaîne d'approvisionnement logicielle
• La règle 3-2-1 à l'épreuve du rançongiciel

Hachage dans les systèmes: intégrité, arbres et preuves

Elle cite

• ⇄Lien dans les deux sens :Condensés cryptographiques : propriétés, constructions et familles
• Transformer mots de passe et secrets applicatifs en clés
• Chaînes de blocs, wallets et cryptographie économique
• Prouver sans révéler : ZK et identification
• Signer numériquement : preuve publique, politiques de vérification
• Surveiller Certificate Transparency pour son domaine
• Anonymisation ou pseudonymisation des données
• Architecture de journalisation d’audit immuable centralisée

⇄ : les deux pages se citent l’une l’autre.