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

Question

Je suis en train de construire un système qui doit être capable de trouver si les blobs d'octets ont été mis à jour . Plutôt que de stocker l'ensemble du blob (qui peut atteindre 5 Mo), je pense que je devrais calculer une somme de contrôle de celui-ci, le stocker et calculer la même somme de contrôle un peu plus tard, pour voir si le blob a été mis à jour.

L'objectif est de minimiser les éléments suivants (dans cet ordre) :

• taille de la somme de contrôle
• temps de calcul
• probabilité de collisions (2 sommes de contrôle identiques se produisent même si le contenu a été modifié).

Il est acceptable pour notre système que la collision ne soit pas supérieure à 1/1 000 000. La préoccupation n'est pas la sécurité, mais simplement la détection des mises à jour/erreurs, donc les rares collisions sont acceptables. (C'est pourquoi je l'ai placé en dernier dans les choses à minimiser).

De plus, nous ne pouvons pas modifier nous-mêmes les blocs de texte.

Bien sûr, md5 , crc o sha1 me viennent à l'esprit, et si je voulais une solution rapide, je la choisirais. Cependant, plus qu'une solution rapide, je cherche à savoir ce qui pourrait être une comparaison des différentes méthodes ainsi que leurs avantages et inconvénients .

Answer 1

Je vous suggère de jeter un coup d'œil à cette page SO CRC contre MD5/SHA1.
La vitesse et les collisions sont abordées dans cet autre fil .
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 qu'elle soit proche de celle que la Lune entre en collision avec la Terre dans les 5 prochaines minutes ?

Si oui, choisissez la famille SHA.
Dans votre cas, je modifierais la façon dont le contrôle de la mise à jour est en train de se faire.
Par exemple, un numéro incrémentiel pourrait être associé au blob, et être envoyé à la place de l'icône dièse le demande d'actualisation serait nécessaire si le numéro est différent de l'autre côté. La probabilité de collision dans ce cas passe de ~10^-18 à ~0 (en gros 0 + probabilité de bug )...

Editar commentaires suivants

J'ai trouvé cet algorithme, Adler-32, qui est bon pour les longs messages (MB) avec un CRC de 32 bits, c'est-à-dire environ ~1/10^9 (MD5 a une longueur de 128 bits).
Le calcul est rapide.
Adler-32 . Il y a un échantillon (lien) au bas de la page.

Answer 2

Blake2 est la fonction de hachage la plus rapide que vous puissiez utiliser et c'est la raison pour laquelle elle est principalement adoptée :

BLAKE2 n'est pas seulement plus rapide que les autres bonnes fonctions de hachage, il est même plus rapide que MD5 ou SHA-1 Fuente

Le gagnant du concours SHA-3 était l'algorithme Keccak mais il n'a pas encore d'implémentation populaire et n'est pas adopté par défaut dans les distributions GNU/Linux. Au lieu de cela, Blake2, qui était un candidat au concours SHA-3, est plus rapide que Keccak et fait partie de l'ensemble des algorithmes SHA-3. GNU coreutils . Ainsi, sur votre distribution GNU/Linux, vous pouvez utiliser b2sum pour utiliser l'algorithme de hachage Blake2.