Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
Fast 64 bit evolved hash.
Fetching latest commit…
Cannot retrieve the latest commit at this time.
|Type||Name||Latest commit message||Commit time|
|Failed to load latest commit information.|
# INTRODUCTION This is BeagleHash and friends- a family of hash functions developed using genetic-algorithm techniques. Each hash function has a different set of trade offs, primarily relating to the size of the seed, the size the run time state of the hash, the method of seeding the hashes state, the block size for reads and the size of the final hash. Hash WordBits SeedBits StateBits HashBits BeagleHash 64 Variable 128 64 Zaphod64 64 191 192 64 StadtX 64 128 256 64 Zaphod32 32 95 96 32 Phat4 32 96 128 32 SBOX 64 128 524480 64 BeagleHash is named in honor of the the H.M.S. Beagle, the ship which carried Charles Darwin to the Galapogos Islands. Zaphod is named after the character from the Hitchhikers Guide to the Galaxy, and is also a play on the fact that Microsoft has a hash called "Marvin". StadtX is a hash function inspired by the metrohash family of hashes, and was named accordingly, "stadt" being the German word for city. Phat4 needs a new name. SBOX is named after how it works, which is substitution box hashing. SBOX is a toy, designed to demonstrate how "perfect unbreakable hashing" might behave. It hashes by looking up a random 64 bit value for each input byte. (And then switches to Zaphod64 like hashing after 32 bytes.) The purpose is purely for testing. I do not recommend you use it. # WHAT IS IT FOR The primary intention of the hash functions contained in this repository is for use in scripting languages such as Perl and other contexts where there is a single seed used to hash many keys, including ones from untrusted sources, and where there may be "leakage" of details about how the hash behaves. In particular one of the assumptions of the hash functions contained here is that they will be *rarely* seeded, but that we will hash many times with the same seed. ## BeagleHash BeagleHash is one core function exposed as a set of different functions each intended for a different seed or hash size. The core routine is the function beagle_hash_64_128_a() which expects a 128 bit random seed which has been "prepared" for use. Specifically the seed is expected to have certain properties: - Neither the first 64 bits nor the last may be either all zeros, nor all ones. - There must be a reasonable mix of ones and zeros. This function is wrapped by various other functions: beagle_hash_64_127_a() beagle_hash_32_127_a() beagle_hash_64_112_a() beagle_hash_32_112_a() beagle_hash_64_96_a() beagle_hash_32_96_a() beagle_hash_64_64_a() beagle_hash_32_64_a() The _96, _112 and _127 variants are exposed primarily for testing and are NOT recommended for general use as they include key preparation as part of their implementation. Instead one should use the functions beagle_hash_seed_prep_127_128_a() beagle_hash_seed_prep_112_128_a() beagle_hash_seed_prep_96_128_a() beagle_hash_seed_prep_64_128_a() to prepare the seed for use with beagle_hash_64_128_a() beagle_hash_32_128_a() both of which do no seed preparation at all. Only the _64 variant is recommended for use with variable seeds, as it uses a fast method for ensuring that seed is of sufficient quality. # HASH FUNCTION SECURITY Security for a hash function is a complex matter. Many contexts do not rely on security. If you are hashing the words in an "actual" dictionary, or hashing pointer addresses, then you probably don't need to worry about the security of that hash function, and can focus on speed and suitability to the data being hashed. On the other hand, if you are using hashing for signing messages then you really need to worry about using an academically peer reviewed and cryptographic grade hash function. Both of these markets are relatively well served by the existing corpus of hash functions and it is relatively straight-forward to choose one appropriate to the task at hand. However there is a middle ground between these two use cases where things are less clear. Perl is a good example of this middle ground. Perl, like many scripting languages, makes heavy use of hasing and hash-tables. The hash function it uses for strings is seeded once, at process start up, and is then used for all subsequent hashing requirements, from internal purposes like namespace management to application level logic like hashing arbitrary user input such as building a hash of the arguments to a web-request. While the hash values generated are considered "private" to the process, and transient to that process, information about the hash-function being used can and does leak in the form of printing out the keys of a hash in native key-order. Another key point here is that the hash table size is variable. In many of the tables only a few bits, usually the low bits, of the hash are actually used. Since we have to supporting hashing arbitrary user data we have to assume that sometimes that data may be hostile, and that someone may be setting up a collision attack on the hash function, and we must ensure that our hash function is sufficiently robust to make collision attacks impractical, which in turn means we have to make seed-discovery attacks impractical. ## Collision attacks ### Multi-Collision Attacks The most serious type of collision attack is the "multi-collision" attack, where it is possible to construct colliding keys without knowing the seed of the hash. Hashes which are based around the 64 bit Intel CRC32 intrinsic often suffer from this problem. It takes a few seconds to find a CRC32 collision, and once you have that, you can manufacture arbitrary numbers of keys which collide. Even if the seed changes, and thus the hash value produced changes, all the keys will still collide. There are other variants to this, for instance some hashes have the property that there is a key K such that H(P)=H(PK), or have the associative property such that H(AB)=H(BA). Any such weaknesses are a fatal blow to a hash function that needs to be robust to untrusted input data. At this time I do now know of any multi-collision attacks on the hash functions in this package. I believe that they are by design robust to such attacks, always mixing the length of the key into the state during hashing, and of sufficient complexity and construction that such attacks are unlikely. ### Brute-Forced Collisions An unfortunate fact of life is that if an attacker knows the seed for your hash function, and you are only using a few bits of the hash then an attacker can readily brute force collisions. For instance if you are using 32 bits of the hash then you can brute force a collision of keys longer than 32 bits in about 160k random tries. (Collisions in a hash are normal, excess collisions are not.) What this means is that our hash function must be robust to key-discovery attacks, or in other words the problem moves from avoiding collisions, to keeping our seed secret. ## Seed Discovery Attacks ### Brute-Force If the seed is small enough then we can brute force the hash function, and simply try every seed and see what hash, or key order we get. Note the hash-size doesnt matter much here, if the seed is 32 bits then the hash function can be brute forced in short order. This means that any decent hash function needs to have a seed at least 64 bits, if not longer. All of the hash functions in this package suport a seed larger than 64 bits. ### Solver Attacks If an attacker knows the hash function being attacked (and even if they dont to a certain extent) they can use a solver to compute the seed from a set of input/output. This means that the complexity of the hash function must be sufficient to make solving the hash impractical. Modern solver technology is very advanced, and can make short order of an insufficiently complex hash function. I do not know the solver status of these hash functions. If I had to guess I would say that the solver-resistance of the hash function is inversely proportional to the hash functions speed, but obviously the relative sizes of the seed, state and hash will play a big role. This needs further study. ## Relatively Speaking All of these hash functions use less state, or use less complex mix functions than SipHash, even in its 1-3 implementation. On the other hand they are faster than SipHash or SipHash13, and probably have a higher level of security than most "non-cryptographic" hash functions. # STATUS This project is a work in progress. It may change at any time until this notice is removed. Please do not use this code in any production systems without contacting me first. # LICENSE You may use this software either under the LGPL 3.0 or later, or under express license after contacting the author. # AUTHOR and COPYRIGHT Yves Orton wrote and ran the software (currently not included in this package) that evolved the internals used by BeagleHash, and wrote the "skeleton" that the genetic-algorithm "filled in". This software is copyright Yves Orton, 2017. # ACKNOWLEDGEMENTS The author would like to thank the following people who have one way or another influenced the development of this software: Damian Gryski - A smart cookie who has interest in this area and who has helped with some of the analysis. Brett Mulvey - Author of http://papa.bretmulvey.com/post/124027987928/hash-functions JP Aumasson "veorq" - One of the authors of SipHash which has been very influential in how this function was structured. Ryan Bastic - Porting, Doc fixes, actually building stuff, etc. Larry Wall - Author of Perl, where I got my chops, and why I started on this in the first place.