# Non-cryptographic hash function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Non-cryptographic_hash_function
> Markdown URL: https://mediated.wiki/source/Non-cryptographic_hash_function.md
> Source: https://en.wikipedia.org/wiki/Non-cryptographic_hash_function
> Source revision: 1339544775
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Hash functions intended for applications that do not need rigorous security}}
The '''non-cryptographic hash functions''' ('''NCHFs'''{{sfn|Estébanez|Saez|Recio|Isasi|2013}}) are [hash function](/source/hash_function)s intended for applications that do not need the rigorous security requirements of the [cryptographic hash function](/source/cryptographic_hash_function)s (e.g., [preimage resistance](/source/preimage_resistance)) and therefore can be faster and less resource-intensive.{{sfn|Sateesan|Biesmans|Claesen|Vliegen|2023|p=1}} Typical examples of CPU-optimized non-cryptographic hashes include [FNV-1a](/source/FNV-1a) and [Murmur3](/source/Murmur3).{{sfn|Sateesan|Biesmans|Claesen|Vliegen|2023|p=2}} 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 function](/source/universal_hash_function)s.{{sfn | Mittelbach | Fischlin | 2021 | p=303}}

== Applications and requirements ==
Among the typical uses of non-cryptographic hash functions are [bloom filter](/source/bloom_filter)s, [hash table](/source/hash_table)s, and [count sketch](/source/count_sketch)es. These applications require, in addition to speed, [uniform distribution](/source/Discrete_uniform_distribution) and [avalanche](/source/Avalanche_effect) properties.{{sfn|Sateesan|Biesmans|Claesen|Vliegen|2023|p=2}} [Collision resistance](/source/Collision_resistance) is an additional feature that can be useful against [hash flooding](/source/hash_flooding) attacks; simple NCHFs, like the [cyclic redundancy check](/source/cyclic_redundancy_check) (CRC), have essentially no collision resistance{{sfn|Stamp|2011}} and thus cannot be used with an input open to manipulation by an attacker.

NCHFs are used in diverse systems: [lexical analyzer](/source/lexical_analyzer)s, [compiler](/source/compiler)s, [database](/source/database)s, [communication network](/source/communication_network)s, video games, [DNS server](/source/DNS_server)s, [filesystem](/source/filesystem)s—anywhere in computing where there is a need to find the information very quickly (preferably in the [O(1)](/source/O(1)) time, which will also achieve perfect [scalability](/source/scalability)).{{sfn|Estébanez|Saez|Recio|Isasi|2013|p=1}}

Estébanez et al. list the "most important" NCHFs:{{sfn|Estébanez|Saez|Recio|Isasi|2013|pp=3-4}}
* The [Fowler–Noll–Vo hash function](/source/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function) (FNV) was created by Glenn Fowler and Phong Vo in 1991 with contributions from [Landon Curt Noll](/source/Landon_Curt_Noll).  FNV with its two variants, FNV-1 and FNV-1a, is very widely used in [Linux](/source/Linux), [FreeBSD](/source/FreeBSD) OSes, DNS servers, [NFS](/source/Network_File_System), [Twitter](/source/Twitter), [PlayStation 2](/source/PlayStation_2), and [Xbox](/source/Xbox_(console)), among others.
* [lookup3](/source/lookup3) was created by [Robert Jenkins](/source/Robert_John_Jenkins_Jr.).  This hash is also widely used and can be found in [PostgreSQL](/source/PostgreSQL), Linux, [Perl](/source/Perl), [Ruby](/source/Ruby_(programming_language)), and [Infoseek](/source/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](/source/WebKit) (part of [Safari](/source/Safari_(browser)) and [Google Chrome](/source/Google_Chrome)).
* [MurmurHash](/source/MurmurHash)2 was created by Austin Appleby in 2008 and is used in [libmemcached](/source/Memcached), Maatkit, and [Apache Hadoop](/source/Apache_Hadoop).
* DJBX33A ("Daniel J. Bernstein, Times 33 with Addition"). This very simple multiplication-and-addition function was proposed by [Daniel J. Bernstein](/source/Daniel_J._Bernstein). It is fast and efficient during initialization. Many programming environments based on [PHP 5](/source/PHP_5), [Python](/source/Python_(language)), and [ASP.NET](/source/ASP.NET) use variants of this hash. The hash is easy to [flood](/source/hash_flooding), exposing the servers.
* BuzHash was created by [Robert Uzgalis](/source/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](/source/Donald_Knuth) and is one of the oldest hashes that is still in use.

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

Many NCHFs have a relatively small result size (e.g., 64 bits for [SipHash](/source/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.{{sfn|Patgiri|Nayak|Muppalaneni|2023|pp=37–38}}

==References==
{{Reflist}}

==Sources==
* {{cite journal | last1 = Sateesan | first1 = Arish | last2 = Biesmans | first2 = Jelle | last3 = Claesen | first3 = Thomas | last4 = Vliegen | first4 = Jo | last5 = Mentens | first5 = Nele | title = Optimized algorithms and architectures for fast non-cryptographic hash functions in hardware | journal = Microprocessors and Microsystems | date = April 2023 | volume = 98 | article-number = 104782 | issn = 0141-9331 | doi = 10.1016/j.micpro.2023.104782 | pmid = | url =https://lirias.kuleuven.be/bitstream/20.500.12942/714306/2/fast_noncrypto_hashes_micpro.pdf }}
* {{cite journal | last1 = Estébanez | first1 = César | last2 = Saez | first2 = Yago | last3 = Recio | first3 = Gustavo | last4 = Isasi | first4 = Pedro | title = Performance of the most common non-cryptographic hash functions | journal = Software: Practice and Experience | date = 28 January 2013 | volume = 44 | issue = 6 | pages = 681–698 | issn = 0038-0644 | doi = 10.1002/spe.2179 | pmid = | url = https://e-archivo.uc3m.es/bitstream/handle/10016/30764/performance_JSPE_2014_ps.pdf}}
* {{cite book | first1 = Mark | last1 = Stamp | date = 8 November 2011 | title = Information Security: Principles and Practice | edition = 2 | publisher = John Wiley & Sons | pages = | isbn = 978-1-118-02796-7 | oclc = 1039294381 | chapter = Non-Cryptographic Hashes  | chapter-url = https://books.google.com/books?id=UW3SS9P9hdEC&pg=PT118}}
* {{cite book | first1 = Ripon | last1 = Patgiri | first2 = Sabuzima | last2 = Nayak | first3 = Naresh Babu | last3 = Muppalaneni | date = 25 April 2023 | title = Bloom Filter: A Data Structure for Computer Networking, Big Data, Cloud Computing, Internet of Things, Bioinformatics and Beyond | publisher = Academic Press | pages = 37–38 | isbn = 978-0-12-823646-8 | oclc = 1377693258 | url = https://books.google.com/books?id=BIdGEAAAQBAJ&pg=PA38}}
* {{cite book | last=Mittelbach | first=Arno | last2=Fischlin | first2=Marc | title=The Theory of Hash Functions and Random Oracles | chapter=Non-cryptographic Hashing | publisher=Springer International Publishing | publication-place=Cham | date=2021 | isbn=978-3-030-63286-1 | doi=10.1007/978-3-030-63287-8_7 | pages=303–334}}

Category:Hash function (non-cryptographic)

---
Adapted from the Wikipedia article [Non-cryptographic hash function](https://en.wikipedia.org/wiki/Non-cryptographic_hash_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Non-cryptographic_hash_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.