Можно создать “хорошую” хеш-функцию с помощью CRC32C в качестве основы?
Учитывая, что SSE 4.2 (Intel Core i7 и i5 части) включает инструкцию CRC32, кажется разумным заняться расследованиями, можно ли было создать более быструю хеш-функцию общего назначения. Согласно этому равномерно распределяются только 16 битов CRC32. Таким образом, что другое преобразование можно было бы применить для преодоления этого?
Обновление Как насчет этого? Только 16 битов подходят для значения хэш-функции.Отлично. Если Ваша таблица 65535 или меньше затем большая. В противном случае выполните значение CRC через Nehalem POPCNT (количество населения) инструкция получить количество набора битов. Затем используйте это в качестве индекса в массив таблиц. Это работает, если Ваша таблица к югу от 1-миллиметровых записей. Я держал пари, что это более дешево/быстрее что лучше всего работающие хеш-функции. Теперь, когда GCC 4.5 имеет внутреннее CRC32, должно быть легко протестировать..., если бы только у меня было обильное свободное время для работы над ним.
David
4 ответа
Revisited , август 2014 г.
По просьбе Арно Буше в недавнем комментарии, и с учетом других ответов и комментариев я подтверждаю, что исходный ответ должен быть быть измененным или для наименее квалифицированных. Я оставил оригинал как есть, в конце, для справки.
Первый и, возможно, самый важный, справедливый ответ на вопрос зависит от предполагаемого использования хэш-кода : Что означает «хорошая» [хеш-функция ...]? Где / как будет использоваться хеш? (например, для хеширования относительно короткого входного ключа? Для целей индексирования / поиска, для создания дайджестов сообщений или для других целей? Какова длина самого желаемого хеш-кода, все 32 бита [CRC32 или его производных] и т. бит, меньше ... и т. д.?
Вопросы OP требуют " более быстрой хэш-функции общего назначения ", поэтому основное внимание уделяется на СКОРОСТИ (что-то менее интенсивное для ЦП и / или что-то, что может использовать параллельную обработку различного характера). Здесь мы можем отметить, что время вычисления самого хеш-кода часто является лишь частью проблемы в применении хеш-кода (для Например, если размер хэш-кода или его внутренние характеристики приводят к множеству коллизий, которые требуют дополнительных циклов для обработки) .Также требование «общего назначения» оставляет много вопросов относительно возможных применений.
Имея это в виду, возможно, краткий и лучший ответ:
Да , аппаратные реализации CRC32C на новых процессорах Intel можно использовать для создания более быстрых хэш-кодов; Однако имейте в виду, что в зависимости от конкретной реализации хэша и его применения общие результаты могут быть неоптимальными из-за частоты конфликтов или необходимости использования более длинных кодов. Кроме того, безусловно, следует тщательно проверять криптографическое использование хэша, потому что сам алгоритм CRC32 очень слаб в этом отношении.
В исходном ответе цитировалась статья Брета Малви об оценке хеш-функций, и, как указано в ответе Mdlg, выводы этой статьи ошибочны в отношении CRC32 , поскольку реализация CRC32, на которой она была основана, была глючный / некорректный. Несмотря на эту серьезную ошибку в отношении CRC32, статья предоставляет полезные рекомендации относительно свойств хэш-алгоритмов в целом. URL-адрес этой статьи больше не существует; Я нашел его на archive.today , но я не знаю, есть ли он у автора в другом месте и обновлял ли он его.
В других ответах здесь цитируется CityHash 1.0 как пример хеш-библиотеки, использующей CRC32C. По-видимому, это используется в контексте некоторых более длинных (более 32 бит) хэш-кодов, но не для самой функции CityHash32 (). Кроме того, использование CRC32 функциями City Hash относительно невелико по сравнению со всеми операциями сдвига, перетасовки и другими операциями, которые выполняются для создания хэш-кода. (Это не критика CityHash, для которой у меня нет практического опыта.Я пойду на шаг, от беглого обзора исходного кода, который функции CityHash производят хорошо, например ell распределенные коды, но они не намного быстрее, чем различные другие хэш-функции.)
Наконец, вы также можете найти представление об этой проблеме в почти дублированном вопросе по SO .
Исходный ответ и правка (апрель 2010 г.)
Априори , это звучит как плохая идея! .
CRC32 был не предназначен для целей хеширования, и его распределение, вероятно, не будет равномерным, что делает его относительно плохим хеш-кодом. Кроме того, его «скремблирующая» мощность относительно мала, что делает односторонний хэш очень плохим, который может использоваться в криптографических приложениях.
[BRB: Я ищу в Интернете ссылки на этот счет ...]
Первое обращение Google [ключевые слова = распределение CRC32] похоже на подтвердите это:
Оценка CRC32 для хеш-таблиц
Редактировать : Цитированная выше страница и полная статья предоставляют хорошую основу для того, что искать в хеш-функциях .
Прочитав [быстро] эту статью, мы подтвердили общее заявление о том, что вообще CRC32 не следует использовать в качестве хэша, однако, в зависимости от конкретной цели хеширования, он может быть возможно использовать, по крайней мере частично, CRC32 в качестве хэш-кода.
Например, младшие (или более высокие, в зависимости от реализации) 16 бит кода CRC32 имеют относительно равномерное распределение и при условии, что никто не беспокоится о криптографических свойствах хэш-кода (т. Е.например тот факт, что одинаковые ключи создают очень похожие коды), можно создать хэш-код, который использует, скажем, конкатенацию младших [или более высоких] 16 бит для двух кодов CRC32, созданных с двумя половинами (или чем-то еще деление) исходного ключа.
Потребуется запустить тесты, чтобы убедиться, что эффективность встроенной инструкции CRC32 по сравнению с альтернативными хэш-функциямибыл бы таким, что накладные расходы на вызов инструкции дважды и объединение кода вместе и т. д. не привели бы к общей более медленной функции.
Для криптографических целей CRC32 - плохое финансирование, потому что он линейен (в векторном пространстве GF (2) ^ 32 ) и это трудно исправить. Он может работать в не криптографических целях.
Однако последние ядра Intel имеют инструкции AES-NI , которые в основном выполняют 1/10-ю блочного шифрования AES за два тактовых цикла. Они доступны на самых последних процессорах i5 и i7 (подробности см. На странице Википедии ). Этот выглядит как хорошее начало для построения криптографической хеш-функции (а хеш-функция, которая хороша для криптографии, будет полезна и для всего остального).
Действительно, по крайней мере один из кандидатов SHA-3 "раунд 2" (хэш-функция ECHO ) построен вокруг элементов AES, так что коды операций AES-NI обеспечивают очень существенный прирост производительности. (К сожалению, в отсутствие инструкции AES-NI производительность ECHO несколько отстой.)
В статье, указанной в другие ответы делают неправильные выводы на основе ошибочного кода crc32. Алгоритм ранжирования Google пока не оценивает на основе научной точности.
В отличие от упомянутой статьи «Оценка CRC32 для хеш-таблиц» выводы, CRC32 и CRC32C приемлемы для использования хеш-таблиц . В авторском примере кода есть ошибка при генерации таблицы crc32. Исправление таблицы crc32 дает удовлетворительные результаты с использованием той же методологии. Кроме того, скорость инструкции CRC32 делает ее лучшим выбором во многих контекстах. Код, использующий инструкцию CRC32, на пике в 16 раз быстрее, чем оптимальная программная реализация. (Обратите внимание, что CRC32 не совсем то же самое, что CRC32C, которое реализует инструкция Intel.)
CRC32, очевидно, не подходит для использования в криптографии. (32 бита - это шутка с грубой силой).