Fowler–Noll–Vo hash function
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.
The current versions are FNV-1 and FNV-1a, which supply a means of creating non-zero FNV offset basis. FNV currently comes in 32-, 64-, 128-, 256-, 512-, and 1024-bit flavors. For pure FNV implementations, this is determined solely by the availability of FNV 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.
For many years, the Python programming language used a slightly modified version of the FNV hash for its default
hash function. This was changed in Python 3.4 in order to protect from DoS attacks to Python applications.
One of FNV's key advantages is that it is very simple to implement. Start with an initial hash value of FNV offset basis. For each byte in the input, multiply hash by the FNV prime, then XOR it with the byte from the input. The alternate algorithm, FNV-1a, reverses the multiply and XOR steps.
algorithm fnv-1 is hash := FNV_offset_basis do for each byte_of_data to be hashed hash := hash × FNV_prime hash := hash XOR byte_of_data return hash
In the above pseudocode, all variables are unsigned integers. All variables, except for byte_of_data, have the same number of bits as the FNV hash. The variable, byte_of_data, is an 8 bit unsigned integer.
As an example, consider the 64-bit FNV-1 hash:
- All variables, except for byte_of_data, are 64-bit unsigned integers.
- The variable, byte_of_data, is an 8-bit unsigned integer.
- The FNV_offset_basis is the 64-bit FNV offset basis value: 14695981039346656037 (in hex, 0xcbf29ce484222325).
- The FNV_prime is the 64-bit FNV prime value: 1099511628211 (in hex, 0x100000001b3).
- The multiply returns the lower 64-bits of the product.
- The XOR is an 8-bit operation that modifies only the lower 8-bits of the hash value.
- The hash value returned is a 64-bit unsigned integer.
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-0 hash (deprecated)
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 offset basis
chongo <Landon Curt Noll> /\../\
For a given :
- (i.e., s is an integer)
and where is:
- NOTE: is the floor function
- The number of one-bits in the binary number representation of is either 4 or 5
Experimentally, FNV prime 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 the n-bit hash space.
FNV hash parameters
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|
|64||Expression||240 + 28 + 0xb3|
|128||Representation||288 + 28 + 0x3b|
|256||Representation||2168 + 28 + 0x63|
|512||Representation||2344 + 28 + 0x57|
|1024||Representation||2680 + 28 + 0x8d|
The FNV hash was designed for fast hash table and checksum use, not cryptography. The authors have identified the following properties as making the algorithm unsuitable as a cryptographic hash function:
- Speed of Computation – As a hash designed primarily for hashtable and checksum use, FNV-1 and FNV-1a were designed to be fast to compute. However, this same speed makes finding specific hash values (collisions) by brute force faster.
- Sticky State – Being an iterative hash based primarily on multiplication and XOR, the algorithm is sensitive to the number zero. Specifically, if the hash value were to become zero at any point during calculation, and the next byte hashed were also all zeroes, the hash would not change. This makes colliding messages trivial to create given a message that results in a hash value of zero at some point in its calculation. Additional operations, such as the addition of a third constant prime on each step, can mitigate this but may have detrimental effects on avalanche effect or random distribution of hash values.
- Diffusion – The ideal secure hash function is one in which each byte of input has an equally-complex effect on every bit of the hash. In the FNV hash, the ones place (the rightmost bit) is always the XOR of the rightmost bit of every input byte. This can be mitigated by XOR-folding (computing a hash twice the desired length, and then XORing the bits in the "upper half" with the bits in the "lower half").
- FNV hash history
- Changing the FNV hash size – xor-folding
- Changing the FNV hash size – non-powers of 2
- The Source Code
- FNV source
- FNV put into the public domain on isthe.com
- Why is FNV Non-Cryptographic?
- Eastlake, Donald; Hansen, Tony; Fowler, Glenn; Vo, Kiem-Phong; <unknown-email-Landon-Noll>, Landon Noll (June 4, 2020). "The FNV Non-Cryptographic Hash Algorithm". tools.ietf.org. Retrieved 2020-06-04.
- "FNV Hash". www.isthe.com. Retrieved 2020-06-04.
- FNV-1a alternate algorithm
- FNV-0 historic note
- FNV Primes
- A few remarks on FNV primes
- FNV Constants
- Parameters of the FNV hash
- Other Hash Sizes and XOR Folding