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

Можно ли использовать CRC32 в качестве хеш-функции? Есть ли недостатки этого подхода? Есть какие-нибудь компромиссы?

 Gumbo08 июн. 2012 г., 20:15
Это зависит от того, для чего вы хотите использовать хеш.
 starbolin08 июн. 2012 г., 20:23
Для некоторого подмножества установленного хэша, да. Однако это не блочный код, это код потока. Для очень маленьких блоков быстрее использовать стол.
 Pradyot08 июн. 2012 г., 20:15
Кажется, уже спросили.stackoverflow.com/questions/2694740/…

Ответы на вопрос(3)

Решение Вопроса

very well в качестве алгоритма хеширования.whole point CRC - это хэширование потока байтов с как можно меньшим количеством коллизий. Тем не менее, есть несколько моментов для рассмотрения:

CRC's are not secure. For secure hashing you need a much more computationally expensive algorithm. For a simple bucket hasher, security is usually a non-issue.

Different CRC flavors exist with different properties. Make sure you use the right algorithm, e.g. with hash polynomial 0x11EDC6F41 (CRC32C) which is the optimal general purpose choice.

As a hashing speed/quality trade-off, the x86 CRC32 instruction is tough to beat. However, this instruction doesn't exist in older CPU's so beware of portability problems.

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

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

Я поместил * во всех случаях, когда CRC32C работал лучше, чем Jenkins96. По этому простому подсчету CRC32C был более однородным хэшем, чем Jenkins96 54 из 96 раз.Especially если вы можете использовать инструкцию 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
 27 авг. 2014 г., 12:28
Брет Малви переместил этот сайт несколько месяцев назад так же, как и его заметку:bretmulvey.com/hash
 11 июн. 2012 г., 00:36
@Mark, автор не использовал полином CRC32C. CRC32C прекрасно работает как хеш для объединения строк байтов в своей тестовой программе.
 10 июн. 2012 г., 17:17
Нет, CRC не избегает коллизий, как и другие алгоритмы. Увидетьhome.comcast.net/~bretm/hash .
 11 июн. 2012 г., 01:19
Хорошее исследование! +1. Однако я все еще не думаю, что даже с инструкцией crc32 она будет превосходить алгоритмы хеширования, предназначенные для (не криптографического) хеширования. Вы можете найти более продвинутый алгоритм разработки и тестирования хеша здесь:code.google.com/p/smhasher .
 11 июн. 2012 г., 07:09
Это чертовски быстро, и может работать просто отлично, в зависимости от приложения для хэша. Все CRC, независимо от полинома, резко не проходят лавинообразный хэш-тест. Смотрите эту страницу по первой предоставленной мной ссылке:home.comcast.net/~bretm/hash/8.html .

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

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

 09 июн. 2012 г., 17:28
Приятно видеть папу Адлера-32. ;)
 08 нояб. 2018 г., 20:02
@AnatoliiStepaniuk Эта статья делает только некоторые махания рукой; он вообще не дает надежных цифр или математических рассуждений, показывающих, почему CRC32 является плохой хеш-функцией для хеш-таблиц. Конечно, никто не хочет заменять SHA256 CRC32, но статья не дает убедительного аргумента, почему он не подходит для хеш-таблицы.
 28 июл. 2018 г., 12:36
Цитата из хорошей статьи оdifference between CRC and hash functions - Нецелесообразно использовать CRC вместо хеш-функции общего назначения, потому что CRC обычно имеют смещенный вывод. В равной степени неуместно использовать хэш-функцию общего назначения вместо CRC, поскольку хеш-функции общего назначения обычно не дают никаких гарантий относительно условий, при которых могут возникнуть коллизии хеш-функций.

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

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

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

 05 дек. 2017 г., 13:56
Я полагаю, что он сказал это, потому что CRC не проходит статистические тесты на случайность - равномерно распределены по диапазону кода, без смещения к определенным битам.
 18 нояб. 2018 г., 17:07

Ваш ответ на вопрос