Non-cryptographic hash function

Last updated

The non-cryptographic hash functions (NCHFs [1] ) are hash functions intended for applications that do not need the rigorous security requirements of the cryptographic hash functions (e.g., preimage resistance) and therefore can be faster and less resource-intensive. [2] Typical examples of CPU-optimized non-cryptographic hashes include FNV-1a and Murmur3. [3] Some non-cryptographic hash functions are used in cryptographic applications (usually in combination with other cryptographic primitives); in this case they are described as universal hash functions. [4]

Contents

Applications and requirements

Among the typical uses of non-cryptographic hash functions are bloom filters, hash tables, and count sketches. These applications require, in addition to speed, uniform distribution and avalanche properties. [3] Collision resistance is an additional feature that can be useful against hash flooding attacks; simple NCHFs, like the cyclic redundancy check (CRC), have essentially no collision resistance [5] and thus cannot be used with an input open to manipulation by an attacker.

NCHFs are used in diverse systems: lexical analyzers, compilers, databases, communication networks, video games, DNS servers, filesystems—anywhere in computing where there is a need to find the information very quickly (preferably in the O(1) time, which will also achieve perfect scalability). [6]

Estébanez et al. list the "most important" NCHFs: [7]

Design

Non-cryptographic hash functions optimized for software frequently involve the multiplication operation. Since in-hardware multiplication is resource-intensive and frequency-limiting, ASIC-friendlier designs had been proposed, including SipHash (which has an additional benefit of being able to use a secret key for message authentication), NSGAhash, and XORhash. Although technically lightweight cryptography can be used for the same applications, the latency of its algorithms is usually too high due to a large number of rounds. [3] Sateesan et al. propose using the reduced-round versions of lightweight hashes and ciphers as non-cryptographic hash functions. [2]

Many NCHFs have a relatively small result size (e.g., 64 bits for SipHash or even less): large result size does not increase the performance of the target applications, but slows down the calculation, as more bits need to be generated. [8]

See also

References

Sources