Article technique
Comment calculer une somme de contrôle
Les sommes de contrôle (checksums) de différentes natures sont couramment utilisées 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 altérées 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 ajoutez ce nombre au message avant de l'envoyer, le destinataire peut reproduire votre calcul sur les N – 1 premiers octets du message et comparer le résultat au dernier octet pour vérifier s'il vaut bien 96. Si c'est le cas, le destinataire peut en déduire que le message n'a vraisemblablement pas été modifié en transit.
Vous trouverez un large éventail de techniques de sommes de contrôle couramment utilisées. Parmi les plus répandues figurent la somme de contrôle classique, le LRC (contrôle de redondance longitudinale) et le CRC (contrôle de redondance cyclique). Ce dernier n'est pas, à proprement parler, une somme de contrôle au sens habituel du terme ; il s'agit plutôt d'un exemple de fonction de hachage à sens unique appartenant à la famille des « générateurs congruentiels linéaires ».
Notez que j'ai indiqué précédemment que ces techniques d'intégrité des données permettent de déterminer si les données « ont pu être altérées ». Aucune technique de somme de contrôle n'est infaillible à 100 % dans le cas général, pour des données de longueur arbitraire. Cependant, certaines techniques sont clairement plus fiables que d'autres.
Voyons comment calculer le LRC, la somme de contrôle et le CRC en JavaScript.
Comment calculer une somme de contrôle de manière traditionnelle
La somme de contrôle classique sur 8 bits correspond exactement à ce que son nom suggère : une somme de toutes les valeurs d'octets de l'entrée, avec suppression de tout dépassement (résultant des opérations de retenue). En JavaScript :
L'entrée de cette fonction est attendue sous la forme d'une chaîne hexadécimale ressemblant à « 48656C6C6F20776F726C6421 » (qui représente ici la version 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. On commence (à la ligne 3) par découper l'entrée hexadécimale en segments de deux chiffres hexadécimaux (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 d'un autre" (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 (en utilisant la construction d'itération forEach ) dans laquelle nous convertissons la version chaîne d'une valeur hexadécimale à deux quartets en un nombre réel sur lequel nous pouvons opérer. À la ligne 7, nous effectuons la sommation proprement dite. Notez que le nombre sum est essentiellement un entier 32 bits en coulisses, ce qui signifie que notre valeur finale pourrait être bien supérieure à 255. Une fois la boucle terminée, nous devons nous assurer de contraindre la somme à une valeur 8 bits. Nous faisons cela à la ligne 9, avec le ET logique appliqué à 255. Dans le même temps, nous revenons à la représentation hexadécimale en utilisant la méthode toString() avec un argument de 16 (ce qui signifie 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 quartets. L'opération toString(16) de JavaScript retourne une valeur à un seul chiffre pour les valeurs inférieures à 10. Dans ce cas, nous devons ajouter '0' en préfixe à la réponse.
Si vous souhaitez tester le code, copiez-collez le code ci-dessus dans votre console JS (dans Chrome, utilisez Shift-Cmd-J pour accéder à la console), puis ajoutez une ligne 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 le Checksum avec le LRC
Le contrôle de redondance longitudinal (LRC) est une variante du checksum 8 bits, qui s'en distingue uniquement par le fait que la « sommation » est effectuée à l'aide d'un XOR, plutôt que par une addition numérique.
À la ligne 6, vous pouvez observer l'opérateur XOR sur place (^=).
Étant donné que le XOR ne provoque jamais de dépassement de capacité, il n'est pas nécessaire de contraindre le résultat final à 8 bits à l'aide d'un ET logique. Il suffit de vérifier que la longueur correspond à deux nibbles, puis de retourner la valeur finale.
Si vous testez le code dans la console en utilisant la chaîne indiquée plus haut, vous devriez obtenir la réponse « 21 ».
Analyse critique du Checksum et du LRC
Ni le checksum ni le LRC ne peuvent être considérés comme robustes face à la corruption des messages. Par exemple, prenons le message d'origine (« 48656C6C6F20776F726C6421 ») : supposons que nous modifiions les deux derniers octets du message, en remplaçant 6421 par 6520. Le LRC et le checksum restent tous deux inchangés ! (Nous avons simplement activé un bit dans un octet en amont, et désactivé le bit à la même position en aval, créant ainsi deux modifications qui s'annulent mutuellement au moment du calcul du checksum.)
De même, réfléchissez à ce qui se passe si vous inversez le message (c'est-à-dire si vous renversez le message octet par octet, de sorte qu'il commence par 21 et se termine par 48). Là encore, le LRC et le checksum restent identiques à ceux du message d'origine. 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, puisqu'un LRC ou un checksum 8 bits ne peut prendre que 256 valeurs différentes, il existe une probabilité de 1 sur 256 qu'un message produise exactement le même LRC (ou checksum) qu'un autre message choisi aléatoirement.
En règle générale, il est très facile de « tromper » les algorithmes de checksum et de LRC, ce qui les rend peu fiables pour la vérification de l'intégrité des messages.
Heureusement, il existe des algorithmes plus performants que le LRC ou le checksum pour la vérification de l'intégrité, mais ils impliquent un coût en termes de charge de calcul.
Comment calculer un Checksum avec le CRC
Lorsque la vérification de l'intégrité revêt une importance réelle, il est généralement nécessaire de recourir à un hachage non commutatif d'une quelconque nature. Il s'agit souvent d'un hachage cryptographique, tel que SHA-1 ou MD5, mais ces méthodes sont très gourmandes en ressources de calcul et peuvent être considérées comme disproportionnées dans de nombreuses situations.
Un bon compromis entre charge de calcul et fiabilité peut être trouvé dans le contrôle de redondance cyclique (CRC), qui existe en plusieurs versions, 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 trop long d'en faire un traitement exhaustif ici. (Consultez Google.) Il suffit de savoir que, d'un point de vue pratique, 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 de données comportant plusieurs inversions de bits. C'est pourquoi, et parce qu'il est facile à implémenter en matériel ou en logiciel, et s'exécute très rapidement avec très peu de mémoire, vous le trouverez utilisé dans de nombreux environnements de communication de données, notamment les pilotes de disques de stockage (où les erreurs disque sont souvent détectées par CRC), les modems et les petits dispositifs électroniques (dont tous les lecteurs de cartes de crédit de la gamme ViVOpay de ID TECH).
Le code JavaScript suivant illustre le calcul d'une valeur CRC 16 bits (retournée sous la forme de quatre quartets en hex-ASCII).
Le CRC met en œuvre un algorithme de hachage qui peut être décrit en langage naturel comme suit :
- Définir la valeur initiale de crc à 0xFFFF — Ligne 10
- Lire un octet de données d'entrée (sous forme de nombre 8 bits) — Ligne 13
- Décaler à droite de 8 bits la valeur crc existante — Ligne 14
- Effectuer un XOR entre le crc décalé à droite et l'octet d'entrée — Ligne 14
- Utiliser la valeur résultante j (8 bits de poids faible uniquement) comme index de table pour rechercher un « octet de substitution » dans la table connue sous le nom de crcTable — Ligne 15
- Décaler la valeur crc de 8 bits vers la GAUCHE, puis effectuer un XOR avec l'« octet de substitution » — Ligne 15
- Répéter ces opérations à partir de la Ligne 13, en utilisant l'octet suivant des données d'entrée
- Une fois l'ensemble des données d'entrée traitées de cette manière, effectuer un XOR du résultat avec zéro et conserver les 16 bits de poids faible du CRC — Ligne 17
Nous utilisons une petite routine 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 pouvez essayer d'inverser un bit dans les données d'entrée pour observer l'effet sur la sortie. Par exemple, si vous utilisez notre chaîne « Hello world! » comme entrée et modifiez le dernier octet de 21 à 20, le CRC devient « AD03 », sans aucun lien avec « BD22 ». Remplacer les deux derniers octets par « 6520 » donne un CRC de « 9E32 ». (Rappelons que cette même modification n'avait aucune incidence sur le LRC ou le checksum.)
Considérons une chaîne représentant dix octets nuls (null). La valeur LRC d'une telle chaîne serait zéro. Le checksum serait évidemment zéro. Mais le CRC serait E139.
Vous pouvez assez facilement vous convaincre que l'inversion des données d'entrée produirait un CRC entièrement différent de celui obtenu avec les données dans leur sens 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 chaînage de blocs de chiffrement , à ceci près que dans ce cas la taille du « bloc de chiffrement » est de 8 bits).
Notez que si le CRC est bien un hachage unidirectionnel, ce n'est pas à proprement parler 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 des données de produire le CRC final souhaité. (Ce n'est pas le cas des hachages dits cryptographiques, pour lesquels il est difficile de calculer un « facteur correctif » permettant de recalibrer un bloc de données altéré vers le hachage désiré.) Le CRC est donc adapté à la détection de corruptions de données non intentionnelles.
Conclusion
Les algorithmes de « contrôle d'intégrité » ne manquent pas pour surveiller la corruption des paquets de données. Dans certains cas, un simple checksum ou LRC suffit. Mais pour les situations impliquant des volumes de données non négligeables et 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 ajustée et optimisée pour offrir une bonne discrimination en matière d'intégrité, tout en étant facile à implémenter, rapide à exécuter et peu gourmande en mémoire, ce qui rend le CRC attractif pour une grande variété de scénarios de vérification de données, couvrant aussi bien les disques durs que les lecteurs de cartes de paiement.