Article technique
Comment calculer un checksum
Les checksums de différents types sont couramment utilisés dans les protocoles de communication de données pour permettre au destinataire d'un message de déterminer rapidement et facilement si les données ont pu être corrompues lors de leur transmission. Si vous additionnez tous les octets d'un message et constatez (en ignorant les dépassements) que la somme est égale à 96, puis que vous ajoutez ce nombre au message avant de l'envoyer, le destinataire peut refaire votre calcul sur les N – 1 premiers octets du message et comparer le résultat au dernier octet pour vérifier s'il est bien égal à 96. Si c'est le cas, le destinataire peut en déduire que le message n'a probablement pas été altéré en transit.
Il existe une grande variété de techniques de checksum couramment utilisées. Trois des plus répandues sont le checksum conventionnel, le LRC (contrôle de redondance longitudinal) et le CRC (contrôle de redondance cyclique). Ce dernier n'est pas vraiment un checksum au sens habituel du terme, mais constitue un exemple de fonction de hachage à sens unique appartenant à la famille des « générateurs congruentiels linéaires ».
Notez que j'ai indiqué plus haut que ces techniques d'intégrité des données permettent de déterminer si les données ont « pu être corrompues ». Aucune technique de checksum n'est fiable à 100 % dans le cas général, pour des données de longueur arbitraire. Certaines techniques restent néanmoins nettement plus efficaces que d'autres.
Voyons comment calculer un LRC, un checksum et un CRC en JavaScript.
Comment calculer un checksum de manière traditionnelle
Le checksum conventionnel sur 8 bits est exactement ce que son nom indique : la somme de toutes les valeurs d'octets de l'entrée, tout dépassement de capacité (résultant d'opérations de retenue) étant ignoré. En JavaScript :
L'entrée de cette fonction doit être une chaîne hexadécimale ressemblant par exemple à « 48656C6C6F20776F726C6421 » (qui correspond ici à la représentation hexadécimale de la chaîne ASCII « Hello world! »). Si l'on utilise « 48656C6C6F20776F726C6421 » comme entrée pour la fonction ci-dessus, la sortie sera « 5d », soit la valeur hexadécimale de la somme finale sur 8 bits.
Le code est très simple. Nous commençons (à la ligne 3) par décomposer l'entrée hexadécimale en segments de deux nibbles à l'aide de l'expression régulière /../g — ce qui signifie : rechercher les sous-chaînes correspondant au motif « n'importe quel caractère suivi de n'importe quel caractère » (c'est ce que représentent les deux points), et ce de manière globale (c'est le rôle du 'g'). Le résultat est un tableau, s, de valeurs hexadécimales à deux chiffres.
À la ligne 5, nous entrons dans une boucle (à l'aide de la construction d'itération forEach ) dans laquelle nous convertissons la représentation en chaîne d'une valeur hexadécimale à deux nibbles en un nombre réel sur lequel nous pouvons effectuer des opérations. À la ligne 7, nous réalisons la sommation proprement dite. Notez que le nombre sum est essentiellement un entier 32 bits en coulisse, ce qui signifie que la valeur finale pourrait être bien supérieure à 255. Une fois la boucle terminée, nous devons veiller à contraindre la somme à une valeur sur 8 bits. Nous le faisons à la ligne 9, par un ET logique avec 255. Dans le même temps, nous revenons à la représentation hexadécimale en utilisant la méthode toString() avec un argument de 16 (indiquant que nous souhaitons utiliser la base 16 pour la représentation finale du nombre).
Aux lignes 10 et 11, nous devons vérifier que la valeur hexadécimale finale comporte bien deux nibbles. L'opération toString(16) de JavaScript renvoie une valeur à un seul chiffre pour les valeurs inférieures à 10. Dans ce cas, nous devons préfixer la réponse par '0'.
Si vous souhaitez tester le code, copiez-collez le code ci-dessus dans votre console JS (dans Chrome, utilisez Maj-Cmd-J pour ouvrir la console), puis ajoutez une ligne tout en bas (en dehors de la fonction) : CHECKSUM("48656C6C6F20776F726C6421"). Lorsque vous appuyez sur Entrée, la console devrait afficher '5d' comme valeur de retour.
Comment calculer une somme de contrôle avec LRC
Le contrôle de redondance longitudinal (LRC) est une variante de la somme de contrôle sur 8 bits, dont la seule différence réside dans le fait que l'« addition » est effectuée par XOR plutôt que par addition numérique.
À la ligne 6, vous pouvez observer l'opérateur XOR en place (^=).
Étant donné que le XOR ne génère jamais de dépassement, il n'est pas nécessaire de contraindre le résultat final à 8 bits par un ET logique. Il suffit de vérifier que la longueur est de deux nibbles, puis de retourner la valeur finale.
Si vous testez le code dans la console avec la chaîne indiquée plus haut, vous devriez obtenir le résultat « 21 ».
Limites de la somme de contrôle et du LRC
Ni la somme de contrôle ni le LRC ne peuvent être considérés comme robustes face à la corruption de messages. Par exemple, prenons le message original (« 48656C6C6F20776F726C6421 ») : supposons que nous modifions les deux derniers octets du message, en remplaçant 6421 par 6520. Le LRC et la somme de contrôle restent inchangés ! (Nous avons simplement activé un bit dans un octet en amont et désactivé le bit de même position en aval, créant ainsi deux modifications qui s'annulent mutuellement au moment du calcul de la somme de contrôle.)
De même, considérons ce qui se passe si vous inversez le message (c'est-à-dire si vous renversez l'ordre des octets, de sorte qu'il commence par 21 et se termine par 48). Là encore, le LRC et la somme de contrôle restent identiques à ceux du message original. Cela s'explique par le fait que le XOR et l'addition sont commutatifs : A + B sera toujours égal à B + A.
Par ailleurs, il convient de noter que, dans la mesure où un LRC ou une somme de contrôle sur 8 bits ne peut prendre que 256 valeurs différentes, il existe une probabilité de 1 sur 256 qu'un message donné produise exactement le même LRC (ou la même somme de contrôle) qu'un autre message choisi au hasard.
En règle générale, il est très facile de « tromper » les algorithmes de somme de contrôle et de LRC, ce qui les rend peu fiables pour vérifier l'intégrité des messages.
Heureusement, il existe des algorithmes plus performants que le LRC ou la somme de contrôle pour la vérification de l'intégrité, mais ils impliquent un coût en termes de charge de calcul.
Comment calculer une somme de contrôle avec CRC
Lorsque la vérification d'intégrité est véritablement critique, il est généralement nécessaire de recourir à un hachage non commutatif. Cela implique souvent un hachage cryptographique, tel que SHA-1 ou MD5, mais ces algorithmes sont coûteux en calcul et peuvent être considérés comme « surdimensionnés » dans bien des situations.
Le contrôle de redondance cyclique offre un bon compromis entre charge de calcul et fiabilité. Il existe en plusieurs variantes, bien que le CRC 16 bits décrit ci-dessous soit suffisant (et très répandu) pour les messages courts (jusqu'à environ 4 kilo-octets).
Le CRC est un sujet fascinant, mais il serait impossible d'en faire un traitement exhaustif ici. (Consultez Google.) D'un point de vue pratique, il suffit de savoir qu'un CRC sur deux octets offre une très bonne sensibilité aux inversions de bits aléatoires dans les données et génère rarement de faux positifs en présence d'erreurs multiples. Pour cette raison, et parce qu'il est facile à implémenter en matériel ou en logiciel, s'exécute très rapidement et nécessite très peu de mémoire, vous le retrouverez dans de nombreux environnements de communication de données, notamment les contrôleurs de disques de stockage (où les erreurs disque sont souvent détectées par CRC), les modems, et les petits appareils électroniques (dont l'ensemble des lecteurs de cartes de crédit de la gamme ViVOpay d'ID TECH).
Le code JavaScript suivant illustre le calcul d'une valeur CRC 16 bits (retournée sous forme de quatre quartets en hexadécimal ASCII).
Le CRC met en œuvre un algorithme de hachage qui peut être décrit ainsi :
- Initialiser la valeur de départ du crc à 0xFFFF — Ligne 10
- Lire un octet de données en entrée (sous forme d'un nombre 8 bits) — Ligne 13
- Décaler la valeur courante du crc de 8 bits vers la droite — Ligne 14
- Effectuer un XOR entre le crc décalé vers la droite et l'octet d'entrée — Ligne 14
- Utilisez la valeur résultante j (les 8 bits inférieurs uniquement) comme décalage dans un tableau afin d'y rechercher un « octet de substitution » dans le tableau connu sous le nom de crcTable — Ligne 15
- Décalez la valeur crc de 8 bits vers la GAUCHE, puis appliquez un XOR avec l'« octet de substitution » — Ligne 15
- Répétez ces opérations à partir de la Ligne 13, en utilisant l'octet suivant des données d'entrée
- Une fois toutes les données d'entrée traitées de cette façon, appliquez un XOR du résultat avec zéro et conservez les 16 bits inférieurs du CRC — Ligne 17
Nous utilisons un petit utilitaire pour convertir le nombre final d'un entier en chaîne hexadécimale :
Si vous chargez ces deux fonctions (numToHex et CRC) dans la console JS de votre navigateur et exécutez CRC( "48656C6C6F20776F726C6421" ), vous devriez obtenir un CRC de 'BD22' pour nos données d'entrée « Hello world! ».
À titre d'exercice, vous pourriez essayer d'inverser un bit dans les données d'entrée pour observer l'effet sur le résultat. Par exemple, en utilisant notre chaîne « Hello world! » comme entrée et en modifiant le dernier octet de la donnée de 21 à 20, le CRC passe à 'AD03', ce qui n'a aucun rapport avec 'BD22'. Remplacer les deux derniers octets par '6520' donne un CRC de '9E32'. (Rappelons que cette même modification n'avait pas perturbé le LRC ni la somme de contrôle.)
Considérons une chaîne représentant dix octets nuls (zéro). La valeur LRC d'une telle chaîne serait zéro. Le checksum serait évidemment zéro. Mais le CRC serait E139.
Vous devriez pouvoir vous convaincre assez facilement qu'inverser l'ordre des données d'entrée produirait un CRC entièrement différent de celui obtenu avec les données dans leur ordre d'origine. (Ce qui n'était pas le cas pour le LRC ou le checksum.) Le CRC n'est pas commutatif, en raison de la façon dont les 8 bits de poids fort du CRC sont soumis à un XOR avec l'octet d'entrée avant de tout décaler vers la gauche (ce qui est similaire au fonctionnement du chiffrement par blocs enchaînés , sauf qu'ici la taille du « bloc de chiffrement » est de 8 bits).
Notez que si le CRC est bien une fonction de hachage à sens unique, il ne s'agit pas à proprement parler d'un hachage cryptographique, car il est en réalité assez facile de calculer une « valeur de correction » qui, ajoutée aux données, permettrait à une modification donnée de celles-ci de produire le CRC final souhaité. (Ce n'est pas le cas des fonctions de hachage dites cryptographiques, pour lesquelles il est difficile de calculer un « facteur de correction » permettant de ramener un bloc de données altéré au hachage désiré.) Le CRC est donc adapté à la détection des corruptions de données non intentionnelles.
Conclusion
Les algorithmes de « contrôle d'intégrité » permettant de surveiller la corruption des paquets de données ne manquent pas. Dans certains cas, un simple checksum ou LRC suffit. Mais lorsqu'il s'agit de volumes de données non négligeables et d'une exigence stricte en matière d'intégrité des données, il faut presque nécessairement se tourner vers un hachage de type « générateur congruentiel linéaire » . La famille d'algorithmes CRC a été soigneusement affinée et optimisée pour offrir une bonne discrimination d'intégrité, combinée à une facilité de mise en œuvre, une exécution rapide et de faibles besoins en mémoire — ce qui rend le CRC particulièrement attractif pour une grande variété de scénarios de vérification de données, allant des disques durs aux lecteurs de cartes bancaires.