Non-cryptographic hash function
The non-cryptographic hash functions (NCHFs ) 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…
≈ 5 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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
edit edit sourceAmong 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]
- The Fowler–Noll–Vo hash function (FNV) was created by Glenn Fowler and Phong Vo in 1991 with contributions from Landon Curt Noll. FNV with its two variants, FNV-1 and FNV-1a, is very widely used in Linux, FreeBSD OSes, DNS servers, NFS, Twitter, PlayStation 2, and Xbox, among others.
- lookup3 was created by Robert Jenkins. This hash is also widely used and can be found in PostgreSQL, Linux, Perl, Ruby, and Infoseek.
- SuperFastHash was created by Paul Hsieh using ideas from FNV and lookup3, with one of the goals being a high degree of avalanche effect. The hash is used in WebKit (part of Safari and Google Chrome).
- MurmurHash2 was created by Austin Appleby in 2008 and is used in libmemcached, Maatkit, and Apache Hadoop.
- DJBX33A ("Daniel J. Bernstein, Times 33 with Addition"). This very simple multiplication-and-addition function was proposed by Daniel J. Bernstein. It is fast and efficient during initialization. Many programming environments based on PHP 5, Python, and ASP.NET use variants of this hash. The hash is easy to flood, exposing the servers.
- BuzHash was created by Robert Uzgalis in 1992. It is designed around a substitution table and can tolerate extremely skewed distributions on the input.
- DEK is an early multiplicative hash based on a proposal by Donald Knuth and is one of the oldest hashes that is still in use.
Design
edit edit sourceNon-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]
References
edit edit source- ^ Estébanez et al. 2013. Wikipedia revision 1339544775, retrieved 2026-11-19
- ^ a b Sateesan et al. 2023, p. 1. Wikipedia revision 1339544775, retrieved 2026-11-19
- ^ a b c Sateesan et al. 2023, p. 2. Wikipedia revision 1339544775, retrieved 2026-11-19
- ^ Mittelbach & Fischlin 2021, p. 303. Wikipedia revision 1339544775, retrieved 2026-11-19
- ^ Stamp 2011. Wikipedia revision 1339544775, retrieved 2026-11-19
- ^ Estébanez et al. 2013, p. 1. Wikipedia revision 1339544775, retrieved 2026-11-19
- ^ Estébanez et al. 2013, pp. 3–4. Wikipedia revision 1339544775, retrieved 2026-11-19
- ^ Patgiri, Nayak & Muppalaneni 2023, pp. 37–38. Wikipedia revision 1339544775, retrieved 2026-11-19
Sources
edit edit source- Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (April 2023). "Optimized algorithms and architectures for fast non-cryptographic hash functions in hardware" (PDF). Microprocessors and Microsystems. 98 104782. doi:10.1016/j.micpro.2023.104782. ISSN 0141-9331.
- Estébanez, César; Saez, Yago; Recio, Gustavo; Isasi, Pedro (28 January 2013). "Performance of the most common non-cryptographic hash functions" (PDF). Software: Practice and Experience. 44 (6): 681–698. doi:10.1002/spe.2179. ISSN 0038-0644.
- Stamp, Mark (8 November 2011). "Non-Cryptographic Hashes". Information Security: Principles and Practice (2 ed.). John Wiley & Sons. ISBN 978-1-118-02796-7. OCLC 1039294381.
- Patgiri, Ripon; Nayak, Sabuzima; Muppalaneni, Naresh Babu (25 April 2023). Bloom Filter: A Data Structure for Computer Networking, Big Data, Cloud Computing, Internet of Things, Bioinformatics and Beyond. Academic Press. pp. 37–38. ISBN 978-0-12-823646-8. OCLC 1377693258.
- Mittelbach, Arno; Fischlin, Marc (2021). "Non-cryptographic Hashing". The Theory of Hash Functions and Random Oracles. Cham: Springer International Publishing. pp. 303–334. doi:10.1007/978-3-030-63287-8_7. ISBN 978-3-030-63286-1.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1339544775 under CC BY-SA 4.0; modifications have been made.