Fowler–Noll–Vo (orFNV) is anon-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 theIEEE 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 Noll, they named it theFowler/Noll/Vo or FNV hash.[1]
The current versions are FNV-1 and FNV-1a, which supply a means of creating non-zeroFNV offset basis. FNV currently[as of?] comes in 32-, 64-, 128-, 256-, 512-, and 1024-bit variants. For pure FNV implementations, this is determined solely by the availability ofFNV primes for the desired bit length; however, the FNV webpage discusses methods of adapting one of the above versions to a smaller length that may or may not be a power of two.[2][3]
The FNV hash algorithms and reference FNVsource code[4][5] have been released into thepublic domain.[6]
ThePython programming language previously used a modified version of the FNV scheme for its defaulthash
function. From Python 3.4, FNV has been replaced withSipHash to resist "hash flooding"denial-of-service attacks.[7]
FNV is not acryptographic hash.[4]
One of FNV's key advantages is that it is very simple to implement.[8] Start with an initial hash value ofFNV offset basis. For each byte in the input,multiplyhash by theFNV prime, thenXOR it with the byte from the input. The alternate algorithm, FNV-1a, reverses the multiply and XOR steps.
The FNV-1 hash algorithm is as follows:[9][10]
algorithm fnv-1ishash :=FNV_offset_basisfor eachbyte_of_data to be hasheddohash :=hash ×FNV_primehash :=hashXORbyte_of_datareturnhash
In the abovepseudocode, all variables areunsignedintegers. All variables, except forbyte_of_data, have the same number ofbits as the FNV hash. The variable,byte_of_data, is an 8-bit unsignedinteger.
As an example, consider the 64-bit FNV-1 hash:
The FNV-1a hash differs from the FNV-1 hash only by the order in which themultiply andXOR is performed:[9][11]
algorithm fnv-1aishash :=FNV_offset_basisfor eachbyte_of_data to be hasheddohash :=hashXORbyte_of_datahash :=hash ×FNV_primereturnhash
The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode. The change in order leads to slightly betteravalanche characteristics.[9][12]
The FNV-0 hash differs from the FNV-1 hash only by the initialisation value of thehash variable:[9][13]
algorithm fnv-0ishash := 0for eachbyte_of_data to be hasheddohash :=hash ×FNV_primehash :=hashXORbyte_of_datareturnhash
The above pseudocode has the same assumptions that were noted for the FNV-1 pseudocode.
A consequence of the initialisation of the hash to 0 is that empty messages and all messages consisting of only the byte 0, regardless of their length, hash to 0.[13]
Use of the FNV-0 hash isdeprecated except for the computing of the FNV offset basis for use as the FNV-1 and FNV-1a hash parameters.[9][13]
There are several different FNV offset bases for various bit lengths. These offset bases are computed by computing the FNV-0 from the following 32octets when expressed inASCII:
chongo <Landon Curt Noll> /\../\
This is one ofLandon Curt Noll'ssignature lines. This is the only current practical use for thedeprecated FNV-0.[9][13]
AnFNV prime is aprime number and is determined as follows:[4][14]
For a given integers such that4 <s < 11, letn = 2s andt =⌊(5 +n) / 12⌋; then then-bit FNV prime is the smallestprime numberp that is of the form
such that:
Experimentally, FNV primes matching the above constraints tend to have better dispersion properties. They improve the polynomial feedback characteristic when an FNV prime multiplies an intermediate hash value. As such, the hash values produced are more scattered throughout then-bit hash space.[4][14]
The above FNV prime constraints and the definition of the FNV offset basis yield the following table of FNV hash parameters:
Size in bits | Representation | FNV prime | FNV offset basis |
---|---|---|---|
32 | Expression | 224 + 28 + 0x93 | |
Decimal | 16777619 | 2166136261 | |
Hexadecimal | 0x01000193 | 0x811c9dc5 | |
64 | Expression | 240 + 28 + 0xb3 | |
Decimal | 1099511628211 | 14695981039346656037 | |
Hexadecimal | 0x00000100000001b3 | 0xcbf29ce484222325 | |
128 | Representation | 288 + 28 + 0x3b | |
Decimal | 309485009821345068724781371 | 144066263297769815596495629667062367629 | |
Hexadecimal | 0x0000000001000000000000000000013b | 0x6c62272e07bb014262b821756295c58d | |
256 | Representation | 2168 + 28 + 0x63 | |
Decimal | 374144419156711147060143317 | 100029257958052580907070968620625704837 | |
Hexadecimal | 0x00000000000000000000010000000000 | 0xdd268dbcaac550362d98c384c4e576ccc8b153 | |
512 | Representation | 2344 + 28 + 0x57 | |
Decimal | 358359158748448673689190764 | 965930312949666949800943540071631046609 | |
Hexadecimal | 0x0000000000000000 0000000000000000 | 0xb86db0b1171f4416 dca1e50f309990ac | |
1024 | Representation | 2680 + 28 + 0x8d | |
Decimal | 501645651011311865543459881103 | 14197795064947621068722070641403218320 | |
Hexadecimal | 0x0000000000000000 0000000000000000 | 0x0000000000000000 005f7a76758ecc4d |
The FNV hash was designed for fasthash table andchecksum use, notcryptography. The authors have identified the following properties as making the algorithm unsuitable as acryptographic hash function:[16]
A structural weakness of FNV-1a arises from its use of XOR before multiplication, which can cause predictable relationships between hashes of related inputs. For example, the following identity holds in both the 32-bit and 64-bit variants:
fnv1a("some-string-a")XOR fnv1a("some-id-1231") = fnv1a("some-string-b")XOR fnv1a("some-id-1232")
because the differing characters ('a' vs 'b', and '1' vs '2') differ by the same bit pattern. This illustrates how certain bitwise symmetries in input can lead to unintended hash correlations. XOR-folding does not remove this weakness.
{{cite journal}}
:|last5=
has generic name (help)