Quel algorithme de sum de contrôle dois-je utiliser?

Je construis un système qui doit être capable de trouver si les blobs d’octets ont été mis à jour . Plutôt que de stocker le blob entier (ils peuvent atteindre 5 Mo), je pense que je devrais en calculer une sum de contrôle, la stocker et calculer la même sum de contrôle un peu plus tard, pour voir si le blog a été mis à jour.

Le but est de minimiser les éléments suivants (dans cet ordre):

  • taille de la sum de contrôle
  • le temps de calculer
  • probabilité de collision (2 sums de contrôle identiques se produisant même si le contenu a été modifié).

Il est acceptable que notre système ne soit pas soumis à une collision supérieure à 1/1 000 000. Le souci n’est pas la sécurité, mais simplement la mise à jour / la détection des erreurs, les collisions sont donc rares. (Ce qui est la raison pour laquelle je mets la dernière dans les choses à minimiser).

En outre, nous ne pouvons pas modifier les taches de texte nous-mêmes.

Bien sûr, md5 , crc ou sha1 crc vient à l’esprit, et si je voulais une solution rapide, je le ferais. Cependant, plus qu’une solution rapide, je cherche ce qui pourrait être une comparaison de différentes méthodes, ainsi que des avantages et des inconvénients .

Je vous suggère de jeter un oeil à cette page SO , CRC vs MD5 / SHA1.
La vitesse et les collisions sont discutées dans cet autre sujet .
Et comme toujours, Wikipedia est votre ami.

Si je devais choisir, il y a une question importante à laquelle il faut répondre: voulez-vous que, dans tous les cas, il n’y ait pas de collision – ou du moins que la probabilité soit si faible que la Lune entre en collision avec la Terre? dans les 5 prochaines minutes?

Si oui, choisissez la famille SHA.
Dans votre cas, je changerais la façon dont la vérification de la mise à jour est effectuée.
Par exemple, un numéro incrémentiel pourrait être associé au blob et être envoyé à la place du hachage , la demande de mise à jour serait requirejse si le numéro est différent de l’autre côté. La probabilité de collision dans ce cas va de ~ 10 ^ -18 à ~ 0 (essentiellement une probabilité de bug de 0 +) …

Modifier les commentaires suivants

Trouvé cet algorithme, Alder-32, qui est bon pour les messages longs (MB) avec un CRC de 32 bits, soit environ ~ 1/10 ^ 9 (MD5 a une longueur de 128 bits).
Il est rapide à calculer.
Adler-32 . Il y a des extraits (lien) en bas.

Blake2 est la fonction de hachage la plus rapide que vous pouvez utiliser et qui est principalement adoptée:

BLAKE2 n’est pas seulement plus rapide que les autres bonnes fonctions de hachage, il est encore plus rapide que les sources MD5 ou SHA-1

Le gagnant du concours SHA-3 était l’algorithme de Keccak, mais son implémentation populaire n’est pas encore adoptée par défaut dans les dissortingbutions GNU / Linux. Au lieu de cela, Blake2 qui était un candidat au concours SHA-3 est plus rapide que Keccak et fait partie de GNU coreutils . Donc, sur votre dissortingbution GNU / Linux, vous pouvez utiliser b2sum pour utiliser l’algorithme de hachage Blake2.