Можно ли использовать CRC32 в качестве хеш-функции?

CRC32 очень хорошо работает как алгоритм хеширования. Весь смысл CRC состоит в том, чтобы хэшировать поток байтов с минимальным количеством конфликтов, насколько это возможно. Тем не менее, есть несколько моментов, которые следует учитывать:

• CRC небезопасны. Для безопасного хеширования вам понадобится гораздо более затратный в вычислительном отношении алгоритм. Для простого хэшера ведра безопасность обычно не является проблемой.

• Существуют разные ароматы CRC с разными свойствами. Убедитесь, что вы используете правильный алгоритм, например с хеш-полиномом 0x11EDC6F41 (CRC32C), который является оптимальным выбором общего назначения.

• Как компромисс между скоростью хеширования и качеством, инструкцию x86 CRC32 сложно превзойти. Однако этой инструкции нет в старых процессорах, поэтому остерегайтесь проблем с переносимостью.

---- РЕДАКТИРОВАТЬ ----

Марк Адлер предоставил ссылку на полезную статью Брета Малви по оценке хэша. Используя исходный код, представленный в статье, я провел «тест корзины» как для CRC32C, так и для Jenkins96. Эти таблицы показывают вероятность того, что действительно равномерное распределение будет хуже, чем результат измерения случайно. Итак, большее число лучше. Автор считал 0,05 или меньше слабым, а 0,01 или меньше очень слабым. Во всем этом я полностью доверяю автору и просто сообщаю результаты.

Я поставил * все экземпляры, в которых CRC32C работает лучше, чем Jenkins96. Судя по этому простому подсчету, CRC32C был более однородным хешем, чем Jenkins96 54 из 96 раз. Особенно, если вы можете использовать инструкцию x86 CRC32, соотношение скорости и производительности будет отличным.

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

А для Jenkins96, который автор статьи посчитал отличным хешем:

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

Я не знаю, почему Марк Адлер сказал, что «crc32 плохо распределяет входные биты по хешу». В хэше crc32 нет ни одного бита, который в точности равнялся бы входным битам. Любой бит хеша представляет собой линейную комбинацию входных битов. Во-вторых, crc всегда равномерно отображает одно и то же количество различных входных последовательностей на заданное значение хеш-функции. Например, если у вас есть сообщение длиной 1000 бит, после crc32 вы всегда можете найти 2 ^ (1000-32) последовательности, которые производят заданное хеш-значение, не больше и не меньше.

Если вам не нужна функция безопасности, crc может отлично служить хешем.

На самом деле, я думаю, что другие незащищенные хэш-функции могут быть проще, чем crc, если вам нужно иметь более длинный crc, например crc-256.

CRC32 преобразует байты в 32-битные целые числа перед их накоплением с помощью xor. Это означает, что каждый байт влияет только на 8 из 32 бит вашего хеша. Конечно, CRC32 тоже переключается, но это только скрывает проблему под ковриком. Т.е. он будет распределять ключи неравномерно, в каком-то регионе будет сильная кластеризация. Может показаться, что такой хеш работает нормально, пока вы не попадете в этот регион, и вдруг ваша хеш-таблица O (1) превратится в таблицу O (n).

CRC32 был разработан для обнаружения поврежденных файлов, а не для хеширования. И, как упомянул Марк, это не защитит ваши файлы от изменений, поскольку хакеры могут изменять их по своему желанию, просто вставив правильно созданное 32-битное значение после изменения.