Somme de Controle

Une somme de contrôle (ou checksum) est une valeur calculée à partir d'un bloc de données (nombre, message, fichier) au moyen d'une fonction déterministe. Cette valeur accompagne les données lors de leur stockage ou de leur transmission afin de détecter certaines altérations, notamment accidentelles : un bit qui bascule, un chiffre mal lu, etc.

Le principe repose sur la redondance : ajouter aux données une information calculée à partir de ces mêmes données.

Recalculer la somme de contrôle à l'arrivée, puis la comparer à la valeur reçue, permet de détecter certaines erreurs.

Un algorithme de checksum transforme les données en une valeur appelée somme de controle selon une règle déterministe.

Les méthodes utilisées varient selon l'algorithme. Elles peuvent notamment reposer sur l'arithmétique modulaire, le XOR (ou exclusif), ou même l'algèbre polynomiale.

Le bit de parité est l'une des formes les plus simples de contrôle d'erreur : appliquer un XOR à tous les bits d'un message permet de déterminer un bit supplémentaire à transmettre.

Pour une parité paire, le bit ajouté est choisi de sorte que le nombre total de bits à 1 soit pair. Pour une parité impaire, il est choisi de sorte que ce nombre soit impair.

Toute modification portant sur un nombre impair de bits inverse la parité et est donc détectée. En revanche, une modification portant sur un nombre pair de bits peut rester invisible, par exemple lorsque deux bits sont inversés.

Ce mécanisme illustre le compromis fondamental des codes de détection d'erreurs : ajouter très peu de redondance permet de détecter certaines erreurs, mais pas toutes.

— Le bit de parité (1 bit) est utilisé pour détecter certaines erreurs sur des données binaires.

— La formule de Luhn (1 chiffre de contrôle) est utilisée notamment pour certains numéros de cartes bancaires, les SIREN/SIRET et les IMEI. Elle permet surtout de détecter des erreurs courantes de saisie ou de transmission.

— L'Internet checksum (16 bits) est utilisé notamment par IPv4, TCP et UDP. Il repose sur une addition en complément à un.

— Les sommes de Fletcher utilisent des additions modulaires cumulées qui tiennent compte de la position des données.

— Le CRC-32 basé sur le polynôme utilisé par IEEE 802.3 est notamment employé pour la détection d'erreurs dans Ethernet et dans plusieurs formats de fichiers, dont PNG et ZIP.

— Le CRC-32C, également appelé Castagnoli, utilise un autre polynôme et est notamment employé par iSCSI ainsi que dans plusieurs systèmes et protocoles modernes.

— L'Adler-32, utilisé notamment par zlib, est rapide à calculer mais possède des propriétés de détection moins favorables que certains CRC, particulièrement pour certaines petites données.

— Les CRC-8, CRC-16 et CRC-64 existent en de nombreuses variantes adaptées à différents protocoles et formats.

Une collision survient lorsque deux contenus différents produisent la même valeur de contrôle.

Pour une fonction de N bits, la probabilité qu'une modification aléatoire produise une valeur donnée est approximativement 1/(2^N).

Pour une recherche de collision volontaire dans une fonction de hachage idéale de N bits, le paradoxe des anniversaires ramène la complexité générique à environ 2^(N/2).

Une somme de contrôle classique n'est donc pas conçue pour résister à un adversaire qui cherche activement une collision. Les fonctions de hachage cryptographiques sont conçues pour rendre ces recherches computationnellement difficiles.

Une somme de contrôle appartient principalement aux mécanismes de détection d'erreurs : lorsqu'une corruption est détectée, le système peut demander une retransmission ou relire les données depuis un autre support.

Les codes correcteurs ajoutent davantage de redondance afin de permettre la reconstruction de données endommagées sans retransmission. Les codes de Hamming peuvent corriger certaines erreurs binaires, les codes Reed-Solomon sont notamment utilisés dans les QR codes et certains supports optiques, tandis que les codes LDPC sont employés dans de nombreux systèmes modernes de communication.

Les deux approches peuvent être combinées : un système peut utiliser un code correcteur pour réparer certaines erreurs et une somme de contrôle pour détecter des corruptions résiduelles.

Une fonction de hachage transforme une donnée de longueur variable en une valeur de taille fixe conçu pour résister à une collision volontaire (contrairement aux sommes de controle). Pour y arriver, le hachage utilise l'effet avalanche, selon lequel une petite modification de l'entrée provoque une modification importante de la sortie.

Une somme de contrôle publiée avec les données ne protège pas contre un attaquant capable de modifier à la fois les données et la somme de contrôle. Pour obtenir une authentification, une information secrète ou une clé privée doit intervenir.

Une première solution est le HMAC (Hash-based Message Authentication Code), qui combine une fonction de hachage cryptographique et une clé secrète partagée. Seul un possesseur de la clé peut normalement produire un HMAC valide. Le HMAC fournit ainsi l'intégrité et l'authentification du message, mais pas la confidentialité.

Une seconde solution est la signature numérique, par exemple avec RSA, ECDSA ou EdDSA. L'émetteur signe avec une clé privée et le destinataire vérifie avec la clé publique correspondante. Cette approche est notamment utilisée pour authentifier des logiciels, des mises à jour ou des documents numériques.

Pour obtenir également la confidentialité, un chiffrement est nécessaire. Les modes de chiffrement authentifié (AEAD) combinent chiffrement et authentification afin de fournir confidentialité et intégrité des données.