Можно ли построить "хорошую" хэш-функцию, используя CRC32C в качестве базы?

Ответ 1

Revisited, август 2014
Подтвержденный Арно Бушезом в недавнем комментарии, и с учетом других ответов и комментариев, я подтверждаю, что исходный ответ должен быть изменен или наименее квалифицирован. Я оставил оригинал как есть, в конце, для справки.

Во-первых, и, возможно, самое важное, справедливый ответ на вопрос зависит от предполагаемого использования хеш-кода: что означает "хороший" [хэш-функция...]? Где/как будет использоваться хеш? (например, это для хэширования относительно короткого входного ключа? Является ли он для целей индексирования/поиска, для создания дайджестов сообщений или для других целей? Сколько времени занимает желаемый хеш-код, все 32 бита [из CRC32 или их производных], больше бит, меньше... и т.д.

Вопросы OP требуют " быстрее хэш-функции общего назначения", поэтому основное внимание уделяется SPEED (что-то меньшее, чем интенсивность ЦП и/или что-то, что может использоваться параллельно обработка различной природы). Здесь мы можем отметить, что время вычисления самого хеш-кода часто является лишь частью проблемы в приложении хеша (например, если размер хеш-кода или его внутренних характеристик приводит к множеству столкновений, для которых требуются дополнительные циклы с). Также требование "общего назначения" оставляет много вопросов относительно возможных применений.

С учетом этого, короткий и лучший ответ, возможно:

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

В исходном ответе была приведена статья об оценке функций хеширования Брет Малви и как указано в ответе Mdlg: вывод этой статьи ошибочен в отношении CRC32, поскольку реализация CRC32 была основана на был ошибочным/ошибочным. Несмотря на эту основную ошибку в отношении CRC32, статья дает полезные указания относительно свойств хэш-алгоритмов в целом. URL-адрес этой статьи теперь не функционирует; Я нашел его на archive.today, но я не знаю, есть ли у автора его в другом месте, а также обновил ли он его.

Другие ответы здесь цитируют CityHash 1.0 как пример хэш-библиотеки, использующей CRC32C. По-видимому, это используется в контексте некоторых более длинных (более 32 бит) хэш-кодов, но не для самой функции CityHash32(). Кроме того, использование CRC32 по функциям City Hash относительно невелико, по сравнению со всеми смещениями и перетасовкой и другими операциями, которые выполняются для создания хеш-кода. (Это не критика CityHash, для которой у меня нет практического опыта. Я пойду на конечность, из поверхностного обзора исходного кода, который функции CityHash дают хорошие, например, распределенные коды, но не значительно быстрее чем другие другие хэш-функции.)

Наконец, вы также можете найти представление по этому вопросу в квазидвуклевом вопросе о SO.

Оригинальный ответ и редактирование (апрель 2010 г.)

Априори, это звучит как плохая идея!.

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

[BRB: Я ищу онлайн-ссылки на этот эффект...]

Google первый [ключевые слова = распределение CRC32], похоже, подтверждает это:
  Оценка CRC32 для хэш-таблиц

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

Например, нижняя (или более высокая, в зависимости от реализации) 16 бит кода CRC32 имеют относительно равномерное распределение и при условии, что их не интересуют криптографические свойства хэш-кода (то есть, например, факт что аналогичные ключи генерируют очень похожие коды), может быть возможно построить хеш-код, который использует, например, конкатенацию младших [или более высоких] 16 бит для двух кодов CRC32, созданных с двумя половинами (или любым делением) оригинальный ключ.
Нужно было бы запустить тесты, чтобы убедиться, что эффективность встроенной команды CRC32 относительно альтернативных хеш-функций будет такова, что накладные расходы на вызов команды дважды и объединение кода вместе и т.д. Не приведет к общая медленная функция.

Ответ 2

В статье, приведенной в других ответах, приводятся неправильные выводы, основанные на баггическом коде crc32. Алгоритм ранжирования Google не ранжируется на основе научной точности.

В отличие от упомянутой статьи "Оценка CRC32 для хеш-таблиц" выводы, CRC32 и CRC32C приемлемы для использования хэш-таблицы. В образце кода автора есть ошибка в генерации таблицы crc32. Фиксирование таблицы crc32 дает удовлетворительные результаты с использованием той же методологии. Также скорость инструкции CRC32 делает ее лучшим выбором во многих контекстах. Код, использующий инструкцию CRC32, на 16 раз быстрее, чем оптимальная реализация программного обеспечения. (Обратите внимание, что CRC32 не совсем то же самое, что CRC32C, который реализует команда intel.)

CRC32, очевидно, не подходит для использования в криптографии. (32 бит - это шутка для грубой силы).

Ответ 3

Да. CityHash 1.0.1 содержит некоторые новые "хорошие хэш-функции", которые используют инструкции CRC32.

Ответ 4

До тех пор, пока вы не используете крипто хэш, это может сработать.

Ответ 5

В криптографических целях CRC32 является плохим капиталом, поскольку он является линейным (над векторным пространством GF (2) ^ 32) и его трудно исправить. Он может работать в не криптографических целях.

Однако в последних ядрах Intel есть инструкции AES-NI, которые в основном выполняют 1/10-е шифрование блока AES за два тактовых цикла, Они доступны на самых последних процессорах i5 и i7 (см. страница Википедии для некоторых деталей). Это похоже на хороший старт для построения криптографической хэш-функции (и хеш-функция, которая хороша для криптографии, также будет хороша для чего-либо еще).

Действительно, по крайней мере один из SHA-3 "round 2" кандидатов (ECHO хеш-функция) построена вокруг элементов AES, так что коды операций AES-NI обеспечивают очень существенное повышение производительности. (К сожалению, в отсутствие инструкции AES-NI производительность ECHO несколько отстой.)