Fowler – Noll – Vo hashovací funkce - Fowler–Noll–Vo hash function

Fowler – Noll – Vo je ne-kryptografické hashovací funkce vytvořil Glenn Fowler, Landon Curt Noll a Kiem-Phong Vo.

Základ hashového algoritmu FNV byl převzat z nápadu zaslaného jako komentáře recenzenta IEEE POSIX P1003.2 výbor Glenna Fowlera a Phong Vo v roce 1991. V následujícím kole hlasování vylepšil Landon Curt Noll svůj algoritmus. V e-mailové zprávě Landonovi to pojmenovali Fowler / Noll / Vo nebo FNV hash.^[1]

Přehled

Aktuální verze jsou FNV-1 a FNV-1a, které dodávají prostředky k vytváření nenulové hodnoty Základ offsetu FNV. FNV v současné době přichází v 32-, 64-, 128-, 256-, 512- a 1024-bitových variantách. U čistých implementací FNV je to určeno pouze dostupností FNV prvočísla pro požadovanou délku bitu; webová stránka FNV však popisuje způsoby přizpůsobení jedné z výše uvedených verzí na menší délku, která může nebo nemusí být mocninou dvou.^[2][3]

Algoritmy hash FNV a referenční FNV zdrojový kód^[4][5] byly propuštěny do veřejná doména.^[6]

Po mnoho let Programovací jazyk Python použil pro své výchozí nastavení mírně upravenou verzi hash FNV hash funkce.^[7] To bylo změněno v Pythonu 3.4 za účelem ochrany před DoS útoky na aplikace Pythonu.

FNV není kryptografický hash.^[8]

Hash

Jednou z klíčových výhod FNV je, že je jeho implementace velmi jednoduchá. Začněte s počáteční hashovací hodnotou Základ offsetu FNV. Pro každý bajt na vstupu násobit hash podle FNV prime, pak XOR to s bajtem ze vstupu. Alternativní algoritmus FNV-1a obrací kroky násobení a XOR.

FNV-1 hash

Algoritmus hash FNV-1 je následující:^[9][10]

algoritmus fnv-1 je    hash := FNV_offset_basis    pro každého byte_of_data být hašován dělat        hash := hash × FNV_prime        hash := hash XOR byte_of_data    vrátit se hash

Ve výše uvedeném pseudo kód, všechny proměnné jsou nepodepsaný celá čísla. Všechny proměnné, kromě byte_of_data, mají stejný počet bity jako hash FNV. Proměnná, byte_of_data, je 8 bit nepodepsaný celé číslo.

Jako příklad zvažte 64-bit FNV-1 hash:

• Všechny proměnné, kromě byte_of_data, jsou 64-bit nepodepsaný celá čísla.
• Proměnná, byte_of_data, je 8-bit nepodepsaný celé číslo.
• The FNV_offset_basis je 64-bit Základ offsetu FNV hodnota: 14695981039346656037 (v hexadecimálním formátu, 0xcbf29ce484222325).
• The FNV_prime je 64-bit FNV prime hodnota: 1099511628211 (v hexadecimálním formátu, 0x100000001b3).
• The násobit vrací spodní 64-bity z produkt.
• The XOR je 8-bit operace, která upravuje pouze spodní 8-bity hash hodnoty.
• The hash vrácená hodnota je 64-bit nepodepsaný celé číslo.

FNV-1a hash

Hash FNV-1a se liší od hash FNV-1 pouze v pořadí, ve kterém násobit a XOR se provádí:^[9][11]

algoritmus fnv-1a je    hash := FNV_offset_basis    pro každého byte_of_data být hašován dělat        hash := hash XOR byte_of_data        hash := hash × FNV_prime    vrátit se hash

Výše pseudo kód má stejné předpoklady, jaké byly zaznamenány u FNV-1 pseudo kód. Změna pořadí vede k mírně lepšímu lavinové vlastnosti.^[9][12]

FNV-0 hash (zastaralé)

Hash FNV-0 se liší od hash FNV-1 pouze inicializační hodnotou hash proměnná:^[9][13]

algoritmus fnv-0 je    hash := 0    pro každého byte_of_data být hašován dělat        hash := hash × FNV_prime        hash := hash XOR byte_of_data    vrátit se hash

Výše pseudo kód má stejné předpoklady, jaké byly zaznamenány u FNV-1 pseudo kód.

Použití hash FNV-0 je zastaralé s výjimkou výpočtu Základ offsetu FNV pro použití jako hash parametry FNV-1 a FNV-1a.^[9][13]

Základ offsetu FNV

Existuje několik různých Základ offsetu FNV pro různé délky bitů. Tyto Základ offsetu FNV jsou počítány výpočtem FNV-0 z následujících 32 oktety když je vyjádřeno v ASCII:

chongo  /  ../ 

který je jedním z Landon Curt Noll je podpisové řádky. Toto je jediné současné praktické použití pro zastaralé FNV-0.^[9][13]

FNV prime

An FNV prime je prvočíslo a je stanovena takto:^[14][15]

Za dané ${ displaystyle s}$:

• ${ displaystyle s in mathbb {I} ^ {*} ~}$ (tj. s je celé číslo )
• ${ displaystyle 4$

kde ${ displaystyle n}$ je:

• ${ displaystyle n = 2 ^ {s}}$

a kde ${ displaystyle t}$ je:

• ${ displaystyle t = left lfloor { frac {5 + 2 ^ {s}} {12}} right rfloor}$

POZNÁMKA: ${ displaystyle lfloor x rfloor ,}$ je funkce podlahy

pak n-bit FNV prime je nejmenší prvočíslo ${ displaystyle p}$ ve tvaru:

${ displaystyle 256 ^ {t} + 2 ^ {8} + mathrm {b} ,}$

takové, že:

• ${ displaystyle 0$
• Počet jednobitů v binární číslo zastoupení ${ displaystyle b}$ je 4 nebo 5
• ${ displaystyle p mod (2 ^ {40} -2 ^ {24} -1)> (2 ^ {24} + 2 ^ {8} + 2 ^ {7})}$

Experimentálně, FNV prime shoda s výše uvedenými omezeními má tendenci mít lepší disperzní vlastnosti. Zlepšují charakteristiku polynomiální zpětné vazby, když FNV prime vynásobí střední hodnotu hash. Vyrobené hodnoty hash jsou proto více rozptýleny po celém souboru n-bit hash prostor.^[14][15]

Parametry hash FNV

Výše FNV prime omezení a definice Základ offsetu FNV výtěžek následující tabulky hash parametrů FNV:

Nekryptografický hash

FNV hash byl navržen pro rychlé hash tabulka a kontrolní součet používat, ne kryptografie. Autoři identifikovali následující vlastnosti, díky nimž je algoritmus nevhodný jako a kryptografická hashovací funkce:^[8]

• Rychlost výpočtu - Jako hash určený primárně pro použití hashtable a kontrolního součtu byly FNV-1 a FNV-1a navrženy tak, aby byly rychle vypočítatelné. Stejná rychlost však umožňuje rychlejší nalezení konkrétních hodnot hash (kolizí) hrubou silou.
• Sticky State - Protože jde o iterativní hash založený primárně na násobení a XOR, je algoritmus citlivý na číslo nula. Konkrétně, pokud by se hodnota hash měla kdykoli během výpočtu stát nulou a další hašovaný bajt byly také všechny nuly, hash by se nezměnil. Díky tomu jsou kolizní zprávy triviální k vytvoření dané zprávy, která má v určitém bodě výpočtu za následek nulovou hodnotu nula. Další operace, jako je přidání třetí konstantní prime v každém kroku, to mohou zmírnit, ale mohou mít škodlivé účinky na lavinový efekt nebo náhodné rozdělení hodnot hash.
• Difúze - Ideální zabezpečená hashovací funkce je funkce, při které má každý bajt vstupu stejně složitý účinek na každý bit hash. V hash FNV je místo těch (bit zcela vpravo) vždy XOR bitu nejvíce vpravo každého vstupního bajtu. To lze zmírnit pomocí XOR-foldingu (výpočet hash s dvojnásobnou požadovanou délkou a poté XOR bitů v „horní polovině“ s bity ve „spodní polovině“).^[18]

Viz také

• Bloomův filtr (aplikace pro rychlé hashování)
• Nekryptografické hashovací funkce

Reference

externí odkazy

• Webová stránka Landona Curta Nolla na FNV (s tabulkou základních a hlavních parametrů)
• Internetový koncept Fowlera, Nolla, Voa a Eastlaka (Informační internetový koncept IETF)