Введение
Некриптографическая хеш-функция Fowler–Noll–Vo (или FNV) — некриптографическая хеш-функция, разработанная Гленном Фаулером, Лэндоном Куртом Ноллом и Кием Фонг Во. Основа алгоритма хеширования FNV была взята из идеи, представленной в качестве замечаний рецензентов комитету IEEE POSIX P1003.2 Гленном Фаулером и Фонг Во в 1991 году. В последующем туре голосования Лэндон Курт Нолл усовершенствовал этот алгоритм. В электронном письме Лэндону они назвали его хешем Fowler/Noll/Vo или FNV.
Fowler–Noll–Vo (or FNV) is a non cryptographic hash function created by Glenn Fowler, Landon Curt Noll, and Kiem Phong Vo. The basis of the FNV hash algorithm was taken from an idea sent as reviewer comments to the IEEE POSIX P1003.2 committee by Glenn Fowler and Phong Vo in 1991. In a subsequent ballot round, Landon Curt Noll improved on their algorithm. In an email message to Landon, they named it the Fowler/Noll/Vo or FNV hash.
Некриптографический хэш
Хэш FNV был разработан для быстрого использования в хэш-таблицах и для вычисления контрольных сумм, а не для криптографии. Авторы выявили следующие свойства, делающие алгоритм непригодным для использования в качестве криптографической хеш-функции:
Скорость вычислений – Поскольку FNV 1 и FNV 1a разрабатывались прежде всего для использования в хэш-таблицах и контрольных суммах, они были оптимизированы для быстрого вычисления. Однако эта же скорость упрощает поиск конкретных хеш-значений (коллизий) методом перебора. "Липкое" состояние – Будучи итеративным хешем, основанным главным образом на умножении и XOR, алгоритм чувствителен к нулю. В частности, если значение хеша станет равным нулю на каком-либо этапе вычисления, а следующий обрабатываемый байт также будет состоять из нулей, хеш не изменится. Это упрощает создание коллизий, если известно сообщение, которое на каком-то этапе вычисления приводит к хеш-значению, равному нулю. Дополнительные операции, такие как добавление третьего постоянного простого числа на каждом шаге, могут уменьшить эту проблему, но могут негативно повлиять на эффект лавины или случайное распределение хеш-значений. Диффузия – Идеальная криптографическая хеш-функция должна обеспечивать, чтобы каждый байт входных данных оказывал равнозначно сложное влияние на каждый бит хеша. В хеше FNV младший бит (самый правый бит) всегда является XOR младшего бита каждого входного байта. Это можно смягчить с помощью XOR-сворачивания (вычисление хеша вдвое большей желаемой длины, а затем применение XOR к битам в "верхней половине" с битами в "нижней половине").