https://github.com/orlp/polymur-hash Skip to content Toggle navigation Sign up * Product + Actions Automate any workflow + Packages Host and manage packages + Security Find and fix vulnerabilities + Codespaces Instant dev environments + Copilot Write better code with AI + Code review Manage code changes + Issues Plan and track work + Discussions Collaborate outside of code Explore + All features + Documentation + GitHub Skills + Blog * Solutions For + Enterprise + Teams + Startups + Education By Solution + CI/CD & Automation + DevOps + DevSecOps Resources + Customer Stories + White papers, Ebooks, Webinars + Partners * Open Source + GitHub Sponsors Fund open source developers + The ReadME Project GitHub community articles Repositories + Topics + Trending + Collections * Pricing Search or jump to... Search code, repositories, users, issues, pull requests... Search [ ] Clear Search syntax tips Provide feedback We read every piece of feedback, and take your input very seriously. [ ] [ ] Include my email address so I can be contacted Cancel Submit feedback Saved searches Use saved searches to filter your results more quickly Name [ ] Query [ ] To see all available qualifiers, see our documentation. Cancel Create saved search Sign in Sign up You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session. {{ message }} orlp / polymur-hash Public * Notifications * Fork 4 * Star 199 The PolymurHash universal hash function. License Zlib license 199 stars 4 forks Activity Star Notifications * Code * Issues 2 * Pull requests 0 * Actions * Projects 0 * Security * Insights More * Code * Issues * Pull requests * Actions * Projects * Security * Insights orlp/polymur-hash This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository. master Switch branches/tags [ ] Branches Tags Could not load branches Nothing to show {{ refName }} default View all branches Could not load tags Nothing to show {{ refName }} default View all tags Name already in use A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch? Cancel Create 1 branch 2 tags Code * Local * Codespaces * Clone HTTPS GitHub CLI [https://github.com/o] Use Git or checkout with SVN using the web URL. [gh repo clone orlp/p] Work fast with our official CLI. Learn more about the CLI. * Open with GitHub Desktop * Download ZIP Sign In Required Please sign in to use Codespaces. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching GitHub Desktop If nothing happens, download GitHub Desktop and try again. Launching Xcode If nothing happens, download Xcode and try again. Launching Visual Studio Code Your codespace will open once ready. There was a problem preparing your codespace, please try again. Latest commit Git stats * 9 commits Files Permalink Failed to load latest commit information. Type Name Latest commit message Commit time extras .gitignore LICENSE README.md polymur-hash.h test.c View code PolymurHash How to use it License How it works and why it's fast Resistance against cryptanalysis No weak keys Acknowledgements README.md PolymurHash PolymurHash is a 64-bit universal hash function designed for use in hash tables. It has a couple desirable properties: * It is mathematically proven to have a statistically low collision rate. When initialized with an independently chosen random seed, for any distinct pair of inputs m and m' of up to n bytes the probability that h(m) = h(m') is at most n * 2^-60.2. This is known as an almost-universal hash function. In fact PolymurHash has a stronger property: it is almost pairwise independent. For any two distinct inputs m and m' the probability they hash to the pair of specific 64-bit hash values (x, y) is at most n * 2^ -124.2. * It is very fast for short inputs, while being no slouch for longer inputs. On an Apple M1 machine it can hash any input <= 49 bytes in 21 cycles, and processes 33.3 GiB/sec (11.6 bytes / cycle) for long inputs. * It is cross-platform, using no extended instruction sets such as CLMUL or AES-NI. For good speed it only requires native 64 x 64 -> 128 bit multiplication, which almost all 64-bit processors have. * It is small in code size and space. Ignoring cross-platform compatibility definitions, the hash function and initialization procedure is just over 100 lines of C code combined. The initialized hash function uses 32 bytes of memory to store its parameters, and it uses only a small constant amount of stack memory when computing a hash. To my knowledge PolymurHash is the first hash function to have all those properties. There are already very fast universal hash functions, such as CLHASH, umash, HalftimeHash, etc., but they all require a large amount of space (1KiB+) to store the hash function parameters, are not optimized for hashing small strings, and/or require specific instruction sets such as CLMUL. There are also very fast cross-platform hashes such as xxHash3, komihash or wyhash, but they do not come with proofs of universality. SipHash claims to be cryptographically secure, but is relatively slow, leading people to use reduced-round variants with unknown cryptanalysis, or to use a fast but insecure hash altogether. Needless to say, PolymurHash passes the full SMHasher suite without any failures*. For the proof of the collision rate, see extras/ universality-proof.md. How to use it PolymurHash is provided as a header-only C library polymur-hash.h. Simply include it and you are good to go. First the hash function must have its PolymurHashParams initialized from a seed, for which there are two functions. PolymurHash uses two 64-bit secrets, but provides a convenient function to expand a single 64-bit seed to that: void polymur_init_params(PolymurHashParams* p, uint64_t k, uint64_t s); void polymur_init_params_from_seed(PolymurHashParams* p, uint64_t seed); The proof of almost universality applies to both, but for the proof of almost pairwise independence to hold you must provide 128 bits of entropy. Once initialization is complete, you can compute as many hashes as you want with it: // Computes the full hash of buf. The tweak is added to the hash before final // mixing, allowing different outputs much faster than re-seeding. No claims are // made about the collision probability between hashes with different tweaks. uint64_t polymur_hash(const uint8_t* buf, size_t len, const PolymurHashParams* p, uint64_t tweak); The tweak allows you to have a different hash function for each hash table without having to calculate new parameters from another seed. This can prevent certain worst-case problems when inserting into a second hash table while iterating over another. License PolymurHash is available under the zlib license, included in polymur-hash.h. How it works and why it's fast At its core, PolymurHash is a Carter-Wegman style polynomial hash that treats the input as a series of coefficients for a polynomial, and then evaluates that polynomial at a secret key k modulo some prime p. The result of this universal hash is then fed into a Murmur-style permutation followed by the addition of a second secret key s. The polynomial part of the hash provides the universality guarantee, and the Murmur-style bit mixing part provides good bit avalanching and uniformity over the full 64 bit output. The final addition of s provides pairwise independence and resistance against cryptanalysis by making the otherwise trivially invertible permutation a lot harder to invert. Now to make the above fast, a couple tricks are employed. The prime used is p = 2^61 - 1, a Mersenne prime. By expressing any number x as 2^61 a + b where b < 2^61, we notice that mod p this is equal to just a + b. With this we can do efficient reduction: reduce(x) = (x >> 61) + (x & P611) This allows us to keep the numbers small very efficiently. Furthermore we also limit k during initialization in such a way that we overflow 64/128 bit numbers less often and thus need to perform the above reduction less often. We also use a trick similar to the one found in "Polynomial evaluation and message authentication" by Daniel J. Bernstein, where we forego computing an exact polynomial m[0]k + m[1]k^2 + m[2]k^3 + ... and instead compute any polynomial that is injective. That is, we're good as long as each input maps to a distinct polynomial. Then we can use the 'pseudo-dot-product' to compute (k + m[0])*(k^2 + m[1]) + (k^3 + m[2])*(k^4 + m[3]) + ... which allows us to process twice as much data per multiplication. It also allows us to pre-compute a couple powers of k to then use instruction-level parallelism to further increase throughput. The loop used for large inputs m[i] = loadword(buf + 7*i) & ((1 << 56) - 1) f = (f + m[6]) * k^7 f += (k + m[0]) * (k^6 + m[1]) f += (k^2 + m[2]) * (k^5 + m[3]) f += (k^3 + m[4]) * (k^4 + m[5]) f = reduce(f) processes 49 bytes of input using seven parallel 64-bit additions and binary ANDs, four parallel 64 x 64 -> 128 bit multiplications, three 128-bit additions and one 128-bit to 64-bit modular reduction. For small inputs we use custom injective polynomials that are fast to evaluate, filled with input from potentially overlapping reads to avoid branches on the input length. Resistance against cryptanalysis PolymurHash has strong collision guarantees for input chosen independently from its random seed. An interactive attacker however can craft its input based on earlier seen hashes. PolymurHash is not a cryptographically secure collision-resistant hash if the attacker can see (or worse, request) hash values at will. This is not a failure of the underlying hash, for example the well-known Poly1305 hash used to secure TLS suffers from the same problem. It solves this by hiding its hash values from attackers by adding an encrypted nonce acting as a one-time-pad. PolymurHash is not intended to be used in a context where an attacker can see the hash values. Its main intended use case is as a hash function for DoS-resistant hash tables. However, a clever attacker might still acquire some information about the hash values by using side-channels such as hash table iteration order, or timing attacks on collisions. To protect against this PolymurHash is structured in a way so that it is not trivial to invert the hash, nor to set up controlled informative experiments through side-channels. Roughly speaking, every bit of input is first mixed with the secret key k by modular multiplication and addition modulo a prime. This is a linear process, so to hide the linear structure of the underlying hash we pass the resulting value through a Murmur-style bit-mixing permutation which is highly non-linear. Finally, to ensure the permutation is not trivially invertible, we add the second secret key s. The above process is by no means a strong multi-round cipher and would likely not hold up to proper cryptanalysis in a standard context. But the underlying structure is sound (e.g. the ChaCha cipher has the form mix(secret + input) + secret where mix is an unkeyed permutation), and I believe that extrapolating what little information you can get from side-channels to recover k, s to execute a HashDoS attack is difficult. No weak keys Polynomial hashing has one potential issue: weak keys. The multiplicative group of numbers mod p = 2^61-1 has subgroups of (much) smaller size. This means that for some keys k^(i + d) mod p == k^i mod p for small constant d. In other words, you can swap the 7-byte block at index i with the one at i + d without changing the hash value for such a weak key. What is the probability you choose such a weak key if you pick a key at random from the 2^61 - 2 possible keys? If d is a divisor of p - 1, then there are totient(d) such keys with the above property. And of course, for the attack to work we need d <= n / 7. Here is a small table showing the probabilities: Max length of input Divisors Weak key probability 64 bytes 8 2^-56.5 1 kilobyte 49 2^-50.5 1 megabyte 811 2^-37.3 1 gigabyte 3420 2^-26.1 These probabilities are very small. Nevertheless, it didn't sit well with me that the possibility existed of picking a key that has such a flaw. So, the seeding algorithm for PolymurHash makes sure to select a key that is a generator of the multiplicative group, that is, the only solution to k^(i + d) mod p == k^i mod p is d = 2^61 - 1. In other words, PolymurHash does not suffer from weak keys. As a trade-off our key space is slightly more limited: in combination with the fact we want k^7 < 2^60 - 2^56 for efficiency reasons we get a total key space of totient(2^61 - 2) * (2^60 - 2^56) / (2^61 - 1) ~= 2^57.4. Additionally, initialization is also slower than simply selecting a random key, on an Apple M1 it takes ~300 cycles on average. If you feel the need to seed many different hashes, consider looking at the tweak parameter instead to see if it fits your criteria. Acknowledgements I am standing on the shoulders of giants, and in the well-researched field of (universal) hash functions there are a lot of them. J. Lawrence Carter, Mark N. Wegman, Ted Krovetz, Phillip Rogaway, Mikkel Thorup, Daniel J. Bernstein, Daniel Lemire, Martin Dietzfelbinger, Austin Appleby, many names come to mind. I have read many publications by them, and borrowed ideas from all of them. About The PolymurHash universal hash function. Resources Readme License Zlib license Activity Stars 199 stars Watchers 9 watching Forks 4 forks Report repository Releases 2 tags Packages 0 No packages published Languages * C 87.7% * Python 12.3% Footer (c) 2023 GitHub, Inc. Footer navigation * Terms * Privacy * Security * Status * Docs * Contact GitHub * Pricing * API * Training * Blog * About You can't perform that action at this time.