Хэш-функция Фаулера – Нолла – Во

Фаулер-Нолл-Во (или FNV ) — это некриптографическая хеш-функция, созданная Гленном Фаулером, Лэндоном Куртом Ноллом и Кием-Фонг Во.

В основу алгоритма хеширования FNV была положена идея, отправленная в качестве рецензентских комментариев комитету IEEE POSIX P1003.2 Гленном Фаулером и Фонг Во в 1991 году. В последующем раунде голосования Лэндон Курт Нолл улучшил свой алгоритм. В электронном письме Лэндону они назвали его хешем Fowler/Noll/Vo или FNV. ^{[ 1 ]}

Обзор

Текущие версии — FNV-1 и FNV-1a, которые предоставляют средства создания ненулевой базы смещения FNV . ФНВ в настоящее время ^{[ на момент? ]} поставляется в 32-, 64-, 128-, 256-, 512- и 1024-битных вариантах. Для чистых реализаций FNV это определяется исключительно наличием простых чисел FNV для желаемой длины в битах; однако на веб-странице FNV обсуждаются методы адаптации одной из вышеупомянутых версий к меньшей длине, которая может быть степенью двойки, а может и не быть. ^{[ 2 ]}^{[ 3 ]}

Алгоритмы хэширования FNV и исходный код FNV. ^{[ 4 ]}^{[ 5 ]} были переданы в общественное достояние . ^{[ 6 ]}

Язык программирования Python ранее использовал модифицированную версию схемы FNV по умолчанию. hash функция. Начиная с Python 3.4, FNV был заменен на SipHash для защиты от » с « хэш-наводнением » атак типа «отказ в обслуживании . ^{[ 7 ]}

FNV не является криптографическим хешем . ^{[ 4 ]}

Хэш

Одним из ключевых преимуществ FNV является простота реализации. Начните с начального значения хеш- функции смещения FNV . Для каждого входного байта умножьте хэш на простое число FNV , а затем выполните XOR с входным байтом. Альтернативный алгоритм FNV-1a меняет местами этапы умножения и XOR.

Хэш FNV-1

Алгоритм хеширования FNV-1 выглядит следующим образом: ^{[ 8 ]}^{[ 9 ]}

algorithm fnv-1 is
    hash := FNV_offset_basis

    for each byte_of_data to be hashed do
        hash := hash × FNV_prime
        hash := hash XOR byte_of_data

    return hash

В приведенном выше псевдокоде все переменные являются без знака целыми числами . Все переменные, за исключением byte_of_data , имеют то же количество бит, что и хэш FNV. Переменная byte_of_data представляет собой 8- битное без знака целое число .

В качестве примера рассмотрим 64- битный хэш FNV-1:

Все переменные, за исключением byte_of_data , представляют собой 64- битные без знака целые числа .
Переменная byte_of_data представляет собой 8- битное без знака целое число .
FNV_offset_basis — это 64- битное значение: 14695981039346656037 (в шестнадцатеричном формате 0xcbf29ce484222325).
FNV_prime — это 64- битное значение 1099511628211 (в шестнадцатеричном формате 0x100000001b3).
Умножение бита младшие 64 произведения возвращает .
XOR — это 8- битная операция, которая изменяет только младшие 8 бит хеш-значения.
битное целое Возвращаемое значение хеш-функции представляет собой 64- число знака без .

Хэш FNV-1a

Хэш FNV-1a отличается от хеша FNV-1 только порядком умножения и XOR : выполнения ^{[ 8 ]}^{[ 10 ]}

algorithm fnv-1a is
    hash := FNV_offset_basis

    for each byte_of_data to be hashed do
        hash := hash XOR byte_of_data
        hash := hash × FNV_prime

    return hash

Вышеупомянутый псевдокод имеет те же предположения, которые были отмечены для псевдокода FNV-1. Изменение порядка приводит к несколько лучшим характеристикам лавины . ^{[ 8 ]}^{[ 11 ]}

Хэш FNV-0 (устарел)

Хэш FNV-0 отличается от хеша FNV-1 только значением инициализации хэш- переменной: ^{[ 8 ]}^{[ 12 ]}

algorithm fnv-0 is
    hash := 0

    for each byte_of_data to be hashed do
        hash := hash × FNV_prime
        hash := hash XOR byte_of_data

    return hash

Вышеупомянутый псевдокод имеет те же предположения, которые были отмечены для псевдокода FNV-1.

Следствием инициализации хеша значением 0 является то, что пустые сообщения и все сообщения, состоящие только из байта 0, независимо от их длины, хэшируются до 0. ^{[ 12 ]}

Использование хеша FNV-0 устарело, за исключением расчета основы смещения FNV для использования в качестве параметров хеш-функции FNV-1 и FNV-1a. ^{[ 8 ]}^{[ 12 ]}

База компенсации FNV

Существует несколько различных баз смещения FNV для различной длины бит. Эти базы смещения вычисляются путем вычисления FNV-0 из следующих 32 октетов , выраженных в ASCII :

chongo <Landon Curt Noll> /\../\

Это одна из Лэндона Курта Нолла фирменных фраз . Это единственное практическое применение устаревшего FNV-0. ^{[ 8 ]}^{[ 12 ]}

ФНВ премьер

Простое число FNV является простым числом и определяется следующим образом: ^{[ 4 ]}^{[ 13 ]}

Для данного целого числа $s$ такого, что $4 < s < 11$ , пусть $n = 2 с$ и $т знак равно ⌊ (5 + п) / 12 ⌋$ ; тогда $n$ - битное простое число FNV — это наименьшее простое число $p,$ имеющее вид

256^{t}+2^{8}+\mathrm {b} \,

такой, что:

$0 < б < 2 8$ ,
количество однобитов в двоичном представлении $b$ равно 4 или 5, и
$р против (2 40 - 2 24 - 1) > 2 24 + 2 8 + 7$ .

Экспериментально, простые числа FNV, соответствующие вышеуказанным ограничениям, имеют тенденцию иметь лучшие дисперсионные свойства. Они улучшают характеристику полиномиальной обратной связи, когда простое число FNV умножает промежуточное значение хеш-функции. Таким образом, полученные хеш-значения более разбросаны по $n$ - битному хэш-пространству. ^{[ 4 ]}^{[ 13 ]}

Хэш-параметры FNV

Вышеупомянутые основные ограничения FNV и определение базиса смещения FNV дают следующую таблицу параметров хеш-функции FNV:

Параметры ФНВ ^{[ 4 ]}^{[ 14 ]}
Размер в битах $n=2^{s}$	Представительство	ФНВ премьер	База компенсации FNV
32	Выражение	2 ²⁴ + 2 ⁸ + 0x93
	Десятичный	16777619	2166136261
	Шестнадцатеричный	0x01000193	0x811c9dc5
64	Выражение	2 ⁴⁰ + 2 ⁸ + 0xb3
	Десятичный	1099511628211	14695981039346656037
	Шестнадцатеричный	0x00000100000001B3	0xcbf29ce484222325
128	Представительство	2 ⁸⁸ + 2 ⁸ + 0x3b
	Десятичный	309485009821345068724781371	144066263297769815596495629667062367629
	Шестнадцатеричный	0x0000000001000000000000000000013B	0x6c62272e07bb014262b821756295c58d
256	Представительство	2 ¹⁶⁸ + 2 ⁸ + 0x63
	Десятичный	374144419156711147060143317 175368453031918731002211	100029257958052580907070968620625704837 092796014241193945225284501741471925557
	Шестнадцатеричный	0x00000000000000000000010000000000 00000000000000000000000000000163	0xdd268dbcaac550362d98c384c4e576ccc8b153 6847b6bbb31023b4c8caee0535
512	Представительство	2 ³⁴⁴ + 2 ⁸ + 0x57
	Десятичный	358359158748448673689190764 890951084499463279557543925 583998256154206699388825751 26094039892345713852759	965930312949666949800943540071631046609 041874567263789610837432943446265799458 293219771643844981305189220653980578449 5328239340083876191928701583869517785
	Шестнадцатеричный	0x0000000000000000 0000000000000000 0000000001000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000157	0xb86db0b1171f4416 dca1e50f309990ac ac87d059c9000000 0000000000000d21 e948f68a34c192f6 2ea79bc942dbe7ce 182036415f56e34b ac982aac4afe9fd9
1024	Представительство	2 ⁶⁸⁰ + 2 ⁸ + 0x8d
	Десятичный	501645651011311865543459881103 527895503076534540479074430301 752383111205510814745150915769 222029538271616265187852689524 938529229181652437508374669137 180409427187316048473796672026 0389217684476157468082573	14197795064947621068722070641403218320 88062279544193396087847491461758272325 22967323037177221508640965212023555493 65628174669108571814760471015076148029 75596980407732015769245856300321530495 71501574036444603635505054127112859663 61610267868082893823963790439336411086 884584107735010676915
	Шестнадцатеричный	0x0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000010000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 000000000000018D	0x0000000000000000 005f7a76758ecc4d 32e56d5a591028b7 4b29fc4223fdada1 6c3bf34eda3674da 9a21d90000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 0000000000000000 000000000004c6d7 eb6e73802734510a 555f256cc005ae55 6bde8cc9c6a93b21 aff4b16c71ee90b3

Некриптографический хэш

Хэш FNV был разработан для быстрого использования хеш-таблиц и контрольных сумм , а не криптографии . Авторы определили следующие свойства, делающие алгоритм непригодным в качестве криптографической хэш-функции : ^{[ 15 ]}

Скорость вычислений . FNV-1 и FNV-1a, предназначенные в первую очередь для использования хеш-таблиц и контрольных сумм, были разработаны для быстрого вычисления. Однако эта же скорость позволяет быстрее находить конкретные значения хеш-функции (коллизии) методом грубой силы.
Липкое состояние . Будучи итеративным хешем, основанным в основном на умножении и XOR, алгоритм чувствителен к нулевому числу. В частности, если бы значение хеш-функции стало нулевым в любой момент во время расчета, а следующий хешированный байт также был бы нулевым, то хеш-код не изменился бы. Это делает создание конфликтующих сообщений тривиальным, учитывая сообщение, которое в какой-то момент вычисления приводит к нулевому хеш-значению. Дополнительные операции, такие как добавление третьего постоянного простого числа на каждом этапе, могут смягчить это, но могут оказать пагубное влияние на лавинный эффект или случайное распределение хеш-значений.
Распространение . Идеальная безопасная хеш-функция — это такая, в которой каждый входной байт оказывает одинаково сложное воздействие на каждый бит хеша. В хеше FNV единица (самый правый бит) всегда представляет собой XOR самого правого бита каждого входного байта. Это можно смягчить с помощью операции XOR (вычисление хэша в два раза больше желаемой длины, а затем выполнение XOR битов в «верхней половине» с битами в «нижней половине»). ^{[ 4 ]}

См. также

Фильтр Блума (приложение для быстрых хэшей)
Некриптографические хэш-функции

Ссылки

^ «FNV Hash — история хеша FNV» . www.isthe.com .
^ «FNV Hash — Изменение размера FNV хэша — xor-свертывание» . www.isthe.com .
^ «Хеш FNV — Изменение размера хеша FNV — не степени 2» . www.isthe.com .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Истлейк, Дональд; Хансен, Тони; Фаулер, Гленн; Во, Ким-Фонг; Нолл, Лэндон. «Алгоритм некриптографического хеширования FNV» . www.tools.ietf.org .
^ «Хеш FNV — источник FNV» . www.isthe.com .
^ FNV вынесен в общественное достояние на isthe.com.
^ «PEP 456 — Безопасный и взаимозаменяемый алгоритм хеширования» . Python.org .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Истлейк, Дональд; Хансен, Тони; Фаулер, Гленн; Во, Кием-Фонг; <unknown-email-Landon-Noll>, Лэндон Нолл (4 июня 2020 г.). «Алгоритм некриптографического хеширования FNV» . www.tools.ietf.org . Проверено 4 июня 2020 г. {{cite web}}: |last5= имеет общее имя ( справка )
^ «FNV Hash — ядро хеша FNV» . www.isthe.com . Проверено 4 июня 2020 г.
^ «FNV Hash — альтернативный алгоритм FNV-1a» . www.isthe.com .
^ "лавина - мурмурхаш" . сайты.google.com .
^ Перейти обратно: ^а ^б ^с ^д «FNV Hash — FNV-0 Исторический нет» . www.isthe.com .
^ Перейти обратно: ^а ^б «FNV Hash — несколько замечаний о простых числах FNV» . www.isthe.com .
^ «Хеш FNV — Параметры хеша FNV-1/FNV-1a» . www.isthe.com .
^ Истлейк, Дональд; Хансен, Тони; Фаулер, Гленн; Во, Ким-Фонг; Нолл, Лэндон. «Алгоритм некриптографического хеширования FNV» . www.tools.ietf.org . Проверено 12 января 2021 г.

Внешние ссылки

Веб-страница Лэндона Курта Нолла на FNV (с таблицей базовых и простых параметров)
Интернет-проект Фаулера, Нолла, Во и Истлейка (информационный интернет-проект IETF)

[1] «FNV Hash — история хеша FNV» . www.isthe.com .

[2] «FNV Hash — Изменение размера FNV хэша — xor-свертывание» . www.isthe.com .

[3] «Хеш FNV — Изменение размера хеша FNV — не степени 2» . www.isthe.com .

[FNV_prime-4] Перейти обратно: ^а ^б ^с ^д ^и ^ж Истлейк, Дональд; Хансен, Тони; Фаулер, Гленн; Во, Ким-Фонг; Нолл, Лэндон. «Алгоритм некриптографического хеширования FNV» . www.tools.ietf.org .

[5] «Хеш FNV — источник FNV» . www.isthe.com .

[6] FNV вынесен в общественное достояние на isthe.com.

[7] «PEP 456 — Безопасный и взаимозаменяемый алгоритм хеширования» . Python.org .

[FNV_basics-8] Перейти обратно: ^а ^б ^с ^д ^и ^ж Истлейк, Дональд; Хансен, Тони; Фаулер, Гленн; Во, Кием-Фонг; <unknown-email-Landon-Noll>, Лэндон Нолл (4 июня 2020 г.). «Алгоритм некриптографического хеширования FNV» . www.tools.ietf.org . Проверено 4 июня 2020 г. {{cite web}}: |last5= имеет общее имя ( справка )

[9] «FNV Hash — ядро хеша FNV» . www.isthe.com . Проверено 4 июня 2020 г.

[10] «FNV Hash — альтернативный алгоритм FNV-1a» . www.isthe.com .

[11] "лавина - мурмурхаш" . сайты.google.com .

[FNV0-12] Перейти обратно: ^а ^б ^с ^д «FNV Hash — FNV-0 Исторический нет» . www.isthe.com .

[FNV_prime_remarks-13] Перейти обратно: ^а ^б «FNV Hash — несколько замечаний о простых числах FNV» . www.isthe.com .

[14] «Хеш FNV — Параметры хеша FNV-1/FNV-1a» . www.isthe.com .

[15] Истлейк, Дональд; Хансен, Тони; Фаулер, Гленн; Во, Ким-Фонг; Нолл, Лэндон. «Алгоритм некриптографического хеширования FNV» . www.tools.ietf.org . Проверено 12 января 2021 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]