stringtranslate.com

Non-cryptographic hash function

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]

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

  1. ^ Estébanez et al. 2013.
  2. ^ a b Sateesan et al. 2023, p. 1.
  3. ^ a b c Sateesan et al. 2023, p. 2.
  4. ^ Mittelbach & Fischlin 2021, p. 303.
  5. ^ Stamp 2011.
  6. ^ Estébanez et al. 2013, p. 1.
  7. ^ Estébanez et al. 2013, pp. 3–4.
  8. ^ Patgiri, Nayak & Muppalaneni 2023, pp. 37–38.

Sources