CRC32 peut-il être utilisé comme fonction de hachage?
peut-on utiliser CRC32 comme fonction de hachage? Des inconvénients à cette approche? Tout tradedeoffs?
3 réponses
CRC32 œuvres très bien comme un algorithme de hachage. Le point entier D'un CRC est de Hasher un flux d'octets avec le moins de collisions possible. Cela dit, il y a quelques points à considérer:
-
Les CRC ne sont pas sécuritaires. Pour secure hashing vous avez besoin d'un algorithme beaucoup plus coûteux de calcul. Pour un simple hachoir à seau, la sécurité n'est généralement pas un problème.
-
différentes saveurs CRC existent avec des propriétés différentes. Assurez-vous d'utiliser le bon algorithme, par exemple avec le polynôme de hachage 0x11EDC6F41 (CRC32C) qui est le choix d'usage général optimal.
-
comme compromis entre la vitesse de hachage et la qualité, l'instruction x86 CRC32 est difficile à battre. Cependant, cette instruction n'existe pas dans les CPU plus anciens donc méfiez-vous des problèmes de portabilité.
---- Modifier - - - -
Mark Adler a fourni un lien vers un article utile pour l'évaluation du hachage par Bret Mulvey. En utilisant le code source fourni dans l'article, j'ai fait le "test du seau" pour CRC32C et Jenkins96. Ces tableaux montrent la probabilité qu'une distribution vraiment uniforme serait pire que le résultat mesuré par hasard seulement. Donc, les nombres plus élevés sont mieux . L'auteur a estimé que 0,05 ou moins était faible et 0,01 ou plus faible à très faible. Je fais entièrement confiance à l'auteur sur tout cela et je ne fais que rapporter les résultats.
j'ai placé un * par tous les cas où CRC32C a mieux fonctionné que Jenkins96. Par ce simple décompte, CRC32C était un hachage plus uniforme que Jenkins96 54 de 96 fois. surtout si vous pouvez utiliser l'instruction x86 CRC32, le compromis entre la vitesse et les performances est excellent.
CRC32C (0x1EDC6F41)
Uniform keys Text keys Sparse keys
Bits Lower Upper Lower Upper Lower Upper
1 0.671 *0.671 *1.000 0.120 *0.572 *0.572
2 *0.706 *0.165 *0.729 *0.919 0.277 0.440
3 *0.878 *0.879 *0.556 0.362 *0.535 *0.542
4 0.573 0.332 0.433 0.462 *0.855 0.393
5 0.023 *0.681 0.470 0.907 0.266 0.059
6 *0.145 *0.523 0.354 *0.172 *0.336 0.588
7 0.424 0.722 0.172 *0.736 0.184 *0.842
8 *0.767 0.507 *0.533 0.437 0.337 0.321
9 0.480 0.725 *0.753 *0.807 *0.618 0.025
10 *0.719 0.161 *0.970 *0.740 *0.789 0.344
11 *0.610 0.225 *0.849 *0.814 *0.854 *0.003
12 *0.979 *0.239 *0.709 0.786 0.171 *0.865
13 *0.515 0.395 0.192 0.600 0.869 *0.238
14 0.089 *0.609 0.055 *0.414 *0.286 *0.398
15 *0.372 *0.719 *0.944 0.100 *0.852 *0.300
16 0.015 *0.946 *0.467 0.459 0.372 *0.793
et pour Jenkins96, dont l'auteur de l'article considéré comme un excellent hachage:
Jenkins96
Uniform keys Text keys Sparse keys
Bits Lower Upper Lower Upper Lower Upper
1 0.888 0.572 0.090 0.322 0.090 0.203
2 0.198 0.027 0.505 0.447 0.729 0.825
3 0.444 0.510 0.360 0.444 0.467 0.540
4 0.974 0.783 0.724 0.971 0.439 0.902
5 0.308 0.383 0.686 0.940 0.424 0.119
6 0.138 0.505 0.907 0.103 0.300 0.891
7 0.710 0.956 0.202 0.407 0.792 0.506
8 0.031 0.552 0.229 0.573 0.407 0.688
9 0.682 0.990 0.276 0.075 0.269 0.543
10 0.382 0.933 0.038 0.559 0.746 0.511
11 0.043 0.918 0.101 0.290 0.584 0.822
12 0.895 0.036 0.207 0.966 0.486 0.533
13 0.290 0.872 0.902 0.934 0.877 0.155
14 0.859 0.568 0.428 0.027 0.136 0.265
15 0.290 0.420 0.915 0.465 0.532 0.059
16 0.155 0.922 0.036 0.577 0.545 0.336
évidemment, vous pourriez, mais vous ne devriez pas. Un crc32 distribue mal les bits d'entrée au hachage. En outre, il ne devrait certainement pas jamais être utilisé comme un hachage à sens unique, car il n'en est pas un. Il est très facile de modifier un message pour produire un crc donné.
utilisez un algorithme de hachage conçu pour le but que vous avez en tête, peu importe ce que c'est.
Je ne sais pas pourquoi Mark Adler a dit que"crc32 distribue mal les bits d'entrée au hachage". Il n'y a pas de bit unique dans le hachage crc32 qui soit exactement égal aux bits d'entrée. N'importe quel morceau du hachage est une combinaison linéaire des bits d'entrée. Deuxièmement, crc toujours uniformément carte le même nombre de différentes séquences d'entrée à une valeur de hachage. Par exemple, si vous avez un message de 1000 bits, après crc32, vous pouvez toujours trouver 2 ^ (1000-32) séquences qui produisent une valeur de hachage donnée, pas plus, pas moins.
si vous n'avez pas besoin de la fonction de sécurité, Le crc peut parfaitement servir de hachage.
en fait, je pense que d'autres fonctions de hachage non sécurisées peuvent être plus simples que le crc, si vous avez besoin d'un crc plus long, par exemple le crc-256.