Les sommes de contrôle ne sont pas des hachages : CRC-32, Adler-32 et à quoi ils servent

Trois métiers qui produisent tous un petit nombre

La confusion commence avec la sortie. CRC-32, Adler-32, FNV-1a, MurmurHash3, MD5 et SHA-256 prennent tous des octets quelconques et renvoient un nombre de taille fixe : dans une API, ils semblent interchangeables. Ils ne le sont pas. Ils ont été conçus contre trois modèles de menace totalement différents, et choisir la mauvaise famille produit des défaillances silencieuses jusqu'à ce qu'elles deviennent catastrophiques.

Une somme de contrôle répond : ces données ont-elles changé par accident en chemin ? Son adversaire est un rayon cosmique, un câble limite, une écriture tronquée, un secteur de disque qui faiblit. Cet adversaire est aléatoire et ne s'adapte pas. CRC-32 et Adler-32 sont des sommes de contrôle. Un hachage cryptographique répond à une question plus dure : quelqu'un peut-il, avec tout le temps et le matériel qu'il peut acheter, trouver une seconde entrée de même sortie ? Son adversaire est une personne dotée d'un budget. MD5, SHA-1 et SHA-256 sont des tentatives dans ce sens — avec des succès variables, détaillés dans l'article compagnon sur le choix d'un hachage.

Le troisième métier est celui qu'on oublie. Un hachage de table répond : comment transformer cette clé en indice de seau, vite et uniformément ? Son adversaire est nominalement personne — jusqu'à ce que les clés proviennent de paramètres de requêtes HTTP, auquel cas l'adversaire est celui qui les envoie. FNV-1a et MurmurHash3 vivent ici. Ils excellent dans leur tâche et n'offrent strictement aucune protection sur les deux autres.

CRC-32 est linéaire, et voici la collision

CRC-32 est une division polynomiale sur GF(2), et la division est linéaire. Concrètement, pour trois messages quelconques de même longueur, crc(a XOR b XOR c) égale crc(a) XOR crc(b) XOR crc(c). Testé sur cinq triplets aléatoires de 32 octets, l'égalité a été exacte à chaque fois — un triplet a par exemple donné 8975e151 des deux côtés. Aucun hachage cryptographique ne possède une telle identité, et ce seul fait algébrique constitue toute la différence entre les deux familles.

La linéarité permet de résoudre pour obtenir une collision au lieu de la chercher. Prends un message qu'un attaquant veut modifier, donne-lui quelques octets de jeu n'importe où — remplissage, champ de commentaire, en-tête réservé, espaces en fin de ligne — et la valeur de jeu requise est la solution d'un système linéaire à 32 inconnues sur GF(2). L'élimination de Gauss règle cela en microsecondes.

Fait pour de vrai : le message d'origine était « config: mode=safe, retries=3, pad=...... », de CRC-32 78aa94ad. La contrefaçon devait se lire « config: mode=open, retries=9, pad= », suivi de six octets de remplissage à déterminer. La résolution de ces octets a donné « config: mode=open, retries=9, pad=!9[noI » — même longueur de 40 octets, 11 octets différents, et le CRC-32 identique 78aa94ad. Vingt-cinq remplissages candidats ont été essayés avant d'en obtenir un entièrement imprimable ; le programme entier a tourné en 0,11 seconde. Les empreintes SHA-256 des deux messages commencent par d9cddeec et 6b7bdc0c : voilà à quoi ressemble une fonction sans identité de linéarité.

Rien ici n'a exigé de cryptanalyse, de GPU ni de dictionnaire. Il a fallu savoir que CRC-32 est une application linéaire et disposer de six octets du message. Voilà pourquoi un CRC accompagnant un fichier sur un canal non fiable ne prouve rien contre la falsification : un attaquant qui peut modifier le fichier peut modifier le CRC en conséquence, et même si le CRC est livré séparément et intouchable, il peut toujours fabriquer un autre fichier qui le produit.

Ce que CRC-32 fait réellement très bien

Rien de ce qui précède ne fait de CRC-32 une mauvaise fonction. Cela en fait une fonction qui fait un autre métier, et à ce métier elle est quasi optimale. Ses garanties ne sont pas statistiques, elles sont démontrées : elle détecte toute erreur d'un bit, toute erreur de deux bits sur une longueur de message énorme, toute erreur affectant un nombre impair de bits, et toute erreur en rafale jusqu'à 32 bits — la longueur de la somme de contrôle elle-même.

Mesuré plutôt qu'affirmé : sur un message de 200 octets, les 1 600 basculements possibles d'un bit ont tous changé le CRC, et les 1 279 200 basculements possibles de deux bits l'ont changé aussi — aucun n'est passé. Sur une trame de 1500 octets de taille Ethernet, 200 000 erreurs en rafale aléatoires à chacune de six largeurs (8, 16, 32, 33, 40 et 64 bits) ont toutes été détectées. Les rafales de plus de 32 bits ne sont pas garanties, seulement extrêmement probables : la probabilité d'échappement vaut environ 2 puissance moins 32, soit une sur 4,29 milliards, d'où l'absence de raté sur 200 000 essais.

C'est pourquoi CRC-32 se trouve dans les trames Ethernet, les fins de fichier gzip, les blocs PNG, les entrées ZIP et le SATA. Ce sont tous des canaux dont le mode de défaillance est un défaut physique produisant une suite contiguë de bits corrompus — exactement la classe d'erreurs que les polynômes CRC sont construits pour attraper avec certitude. Un hachage cryptographique les attraperait aussi, mais à plusieurs fois le coût et sans garantie démontrée, seulement probabiliste.

Adler-32 : moins cher à calculer, plus faible à détecter

Adler-32, défini dans la RFC 1950 pour le format zlib, est constitué de deux sommes courantes modulo 65 521 : une somme simple des octets, et une somme de ces sommes partielles. Il a été conçu pour être bien moins cher qu'un CRC tout en détectant l'essentiel des mêmes erreurs — pas de table, juste des additions. En pratique, le modulo coûte assez cher pour que l'avantage promis s'évapore souvent : mesuré dans le même moteur JavaScript sur le même tampon de 64 Mo, Adler-32 a tourné à 174 Mo/s contre 262 Mo/s pour CRC-32. Adler-32 était plus lent.

Il a aussi un angle mort démontrable plutôt qu'estimé. Le module 65 521 est le plus grand nombre premier inférieur à 65 536. Si tu augmentes un octet de d et diminues un autre octet de d, la première somme est inchangée, et la seconde change de d fois la distance entre eux — ce qui s'annule modulo 65 521 exactement quand cette distance vaut 65 521. Ainsi, tout message de plus de 64 kilo-octets environ possède des paires de modifications compensatoires qu'Adler-32 ne peut absolument pas voir.

Démontré sur un tampon de 70 000 octets : augmenter l'octet 100 de 7 et diminuer l'octet 65 621 de 7 a laissé Adler-32 à 3fee717c, identique octet pour octet à la valeur propre, tandis que CRC-32 passait de abc586b8 à 43c209f4. Adler-32 est aussi médiocre sur les entrées courtes — 200 000 entrées aléatoires de quatre octets n'ont produit que 152 364 valeurs Adler-32 distinctes, là où une fonction 32 bits idéale en aurait produit environ 199 995. La RFC 1950 elle-même signale cette faiblesse pour les messages courts, d'où le fait que les flux zlib l'appliquent à des flux entiers plutôt qu'à de minuscules enregistrements.

FNV-1a et MurmurHash3 : la troisième catégorie

FNV-1a et MurmurHash3 ne sont ni des sommes de contrôle ni des hachages cryptographiques. Ce sont des hachages non cryptographiques conçus pour les tables de hachage, les filtres de Bloom et le partitionnement, où l'exigence est une distribution uniforme au coût par octet le plus bas possible. Ils tiennent parole. Dans le même moteur et sur le même tampon, MurmurHash3 a tourné à 730 Mo/s et FNV-1a à 520 Mo/s, contre 262 Mo/s pour CRC-32.

Les collisions y sont triviales à trouver, et l'exercice prend moins de deux secondes. En énumérant des chaînes de sept caractères, FNV-1a 32 est entré en collision sur « 7yzlaaa » et « e6apaaa », tous deux hachant en 15111984, après 700 997 candidats et 680 millisecondes. MurmurHash3 avec graine 0 est entré en collision sur « rynbaaa » et « ciaabaa », tous deux en e5407f96, après 1 679 907 candidats et 1,6 seconde. C'est attendu — 32 bits signifient une collision d'anniversaire vers 77 163 éléments — et ce n'est pas un défaut. Cela le devient quand quelqu'un choisit les clés.

L'inondation de hachage est l'attaque qui en découle, et elle est facile à reproduire. Collecter 20 000 clés dont la valeur FNV-1a tombe dans le seau 0 d'une table de 4 096 seaux a coûté une fraction de seconde de division d'essai. Les insérer a effondré la table en une seule chaîne de 20 000 entrées, là où des clés ordinaires donnaient une chaîne la plus longue de 12. Vingt mille recherches ont alors pris 1 397,9 millisecondes au lieu de 11,5 — un ralentissement d'un facteur 121, du temps constant au temps linéaire. Chaque requête qui touche une telle table devient un amplificateur : c'est exactement la classe de déni de service qui a poussé les moteurs de langage vers un SipHash à graine aléatoire pour leurs dictionnaires intégrés.

Choisir, en une question

Demande qui gagne si deux entrées différentes produisent la même valeur. Si la réponse est personne — tu attrapes des copies tronquées, des câbles capricieux, des archives corrompues, une pourriture de bits sur un disque de sauvegarde — une somme de contrôle convient et CRC-32 est le défaut sensé. Elle est petite, elle est partout, elle a des garanties démontrées contre exactement les formes d'erreur que produit le matériel, et les implémentations natives sont extrêmement rapides : le CRC-32 de zlib dans node a atteint 2 248 Mo/s sur le même tampon, trois fois les 763 Mo/s de SHA-256.

Si la réponse est quelqu'un — un téléchargement sur un réseau que tu ne contrôles pas, une signature, un fichier de licence, une charge de mise à jour, la déduplication d'objets fournis par les utilisateurs, un cache indexé par quoi que ce soit qu'un utilisateur influence — il te faut un hachage cryptographique, et cela signifie aujourd'hui SHA-256. Le coût est réel mais faible : 763 Mo/s reste plus rapide que la plupart des disques et des réseaux, et c'est la seule famille de cette comparaison où une seconde entrée de même sortie ne se calcule pas simplement.

Et si la valeur ne quitte jamais ton processus — indice de seau, filtre de Bloom, sélecteur de partition — utilise un hachage de table, mais pose une question de suivi : un attaquant peut-il choisir les clés ? Si oui, il te faut une fonction à clé et à graine aléatoire comme SipHash, pas un FNV-1a à graine fixe. La plupart des moteurs de langage modernes le font déjà pour leurs tables intégrées ; le danger est une table faite maison dans le code applicatif, qui ne le fait pas.

Questions fréquentes

CRC-32 est-il une fonction de hachage ?

Au sens le plus lâche oui — elle envoie une entrée quelconque sur une sortie fixe de 32 bits — mais l'appeler ainsi invite l'erreur que cet article existe pour éviter. CRC-32 est une fonction linéaire, calculée comme le reste d'une division polynomiale sur GF(2). Cette linéarité lui donne l'identité crc(a XOR b XOR c) = crc(a) XOR crc(b) XOR crc(c), vérifiée ici sur des triplets aléatoires, et de cette identité découle une collision obtenue en résolvant un système linéaire à 32 inconnues plutôt qu'en cherchant. Un hachage cryptographique est spécifiquement conçu pour qu'aucun raccourci algébrique de ce genre n'existe ; c'est le travail du mot cryptographique. CRC-32 est donc une somme de contrôle, et le bon modèle mental est un très bon code détecteur d'erreurs plutôt qu'un hachage faible. Si une bibliothèque, une API ou une revue de code l'appelle hachage, vérifie la propriété réellement invoquée : l'unicité face à un adversaire est celle qu'elle ne peut fournir, et c'est celle qu'on suppose.

Puis-je utiliser un CRC-32 pour vérifier un téléchargement ?

Cela dépend entièrement de ce contre quoi tu vérifies. Si tu contrôles que les octets arrivés correspondent aux octets partis — que la connexion n'a pas lâché en cours, que l'archive n'est pas tronquée, que le disque a écrit ce qu'on lui a donné — un CRC-32 est exactement l'outil adéquat et attrapera toute panne de transport réaliste. C'est pourquoi chaque entrée ZIP et chaque flux gzip en porte un. Si en revanche tu demandes si le fichier est bien celui voulu par l'éditeur, un CRC-32 ne répond rien. Un attaquant capable de substituer le fichier peut substituer le CRC aussi, et même là où le CRC est publié séparément et intouchable, il peut construire un autre fichier qui lui correspond — cet article l'a fait en 0,11 seconde. Pour vérifier l'éditeur, il faut une empreinte cryptographique publiée sur un canal que l'attaquant ne contrôle pas, et idéalement une signature sur cette empreinte plutôt que l'empreinte seule.

Pourquoi gzip utilise-t-il CRC-32 et zlib Adler-32 ?

Les deux formats enveloppent les mêmes données compressées DEFLATE et diffèrent surtout par leur conteneur. La RFC 1952 spécifie un CRC-32 dans la fin de fichier gzip ; la RFC 1950 spécifie un Adler-32 dans celle de zlib. Le raisonnement de l'époque était la vitesse : Adler-32 ne demande que des additions et un modulo, sans table de 256 entrées, donc sur les processeurs du début des années 1990 il était nettement moins cher par octet, et zlib visait des contextes où le coût de la somme comptait face à la compression. Cet avantage s'est largement évaporé. Les implémentations CRC-32 modernes utilisent des tables slicing-by-8 ou des instructions dédiées, et dans les mesures faites ici le CRC-32 natif de node a atteint 2 248 Mo/s tandis qu'un Adler-32 direct dans le même moteur JavaScript plafonnait à 174 Mo/s contre 262 Mo/s pour CRC-32. Les formats restent tels quels parce que changer d'algorithme casse tous les lecteurs existants, et les deux sont assez solides pour leur mission : attraper une corruption accidentelle dans un flux compressé.

Quelle est la probabilité d'une collision CRC-32 accidentelle ?

Pour un seul message corrompu, la réponse est excellente : les rafales jusqu'à 32 bits ne sont jamais manquées, et au-delà la probabilité d'échappement est d'environ une sur 4 294 967 296. Pour une collection de fichiers, c'est bien pire que l'intuition ne le suggère, à cause de l'effet anniversaire. Deux valeurs 32 bits aléatoires entrent en collision avec une probabilité d'une sur 4,29 milliards, mais un ensemble de n valeurs contient n(n−1)/2 paires : le seuil des 50 % arrive à 77 163 éléments. Dix mille fichiers portent déjà 1,16 % de chances qu'une paire partage un CRC-32, et cent mille en portent 68,8 %. Cela compte si tu utilises CRC-32 comme clé de déduplication ou identifiant adressé par contenu sur un large corpus, où une collision écarte silencieusement l'un de deux fichiers différents. Pour un contrôle d'intégrité fichier par fichier contre les dommages de transport, l'effet anniversaire est hors sujet : tu compares une valeur à une valeur attendue, tu ne cherches pas des correspondances dans une population.

FNV-1a et MurmurHash3 sont-ils sûrs sur des clés fournies par l'utilisateur ?

Pas sans graine aléatoire, non. Les deux sont sans clé par défaut : leur sortie est donc une fonction publique que quiconque peut calculer hors ligne. Cela permet à un attaquant de précalculer des clés atterrissant dans le même seau et de toutes les envoyer d'un coup — l'inondation de hachage. Reproduite ici sur une table de 4 096 seaux : 20 000 clés fabriquées ont toutes haché dans le seau 0, transformant une chaîne la plus longue de 12 en une chaîne unique de 20 000 et faisant passer 20 000 recherches de 11,5 à 1 397,9 millisecondes — 121 fois plus lent, la collecte de ces clés ayant demandé moins d'une seconde d'effort. Le correctif n'est pas un hachage sans clé plus fort ; c'est un hachage à clé avec une graine aléatoire par processus, qui rend le précalcul hors ligne impossible. SipHash est le choix standard et c'est ce qu'utilisent désormais la plupart des moteurs pour leurs dictionnaires. Si tes clés viennent de la configuration, de ta propre base ou d'un endroit qu'un attaquant ne peut influencer, FNV-1a et MurmurHash3 sans graine restent parfaits et très rapides.

Que faut-il utiliser pour les clés de cache et la déduplication ?

Décide selon qui fournit le contenu et selon le coût d'une mauvaise réponse. Pour un cache en mémoire dont tu génères les clés — une forme de requête, un nom de gabarit rendu, un identifiant interne — un hachage non cryptographique rapide convient, et MurmurHash3 à 730 Mo/s est un bon choix. Pour une déduplication sur un corpus que tu contrôles, où une collision revient à ne conserver silencieusement qu'un des deux objets différents, 32 bits est trop étroit : le point anniversaire à 50 % arrive à 77 163 éléments. Passe à un hachage non cryptographique 64 ou 128 bits, ou à un SHA-256 tronqué. Pour tout ce dont l'utilisateur fournit le contenu — fichiers téléversés, objets générés par les utilisateurs, magasin adressé par contenu, cache partagé entre plusieurs clients — utilise SHA-256 en entier. Là, une collision n'est pas un accident mais une capacité : elle permet de placer un objet choisi sous un identifiant déjà existant, et seul un hachage cryptographique rend cela infaisable. Le coût est modeste : les 763 Mo/s mesurés ici dépassent la couche de stockage vers laquelle tu écris.