3 ms·
Disochash is a simple prime-multiplication ARX (addition rotation XOR) hash that's high-quality and fast. It's only 120 lines of code. There's lots of great ha
by keepamovin 3y ago
Disochash is a simple prime-multiplication ARX (addition rotation XOR) hash that's high-quality and fast. It's only 120 lines of code.
There's lots of great hash functions out there: some are super fast, like xxhash and highly optimized, others are also super fast like umash and based on interesting math ideas from finite fields^1, while maintaining high quality (according to SMHasher). Others are also fast and interesting (tabulation hash, that may sometimes be seemingly universal): one of the main originators of tabulation hash ideas is Mikkel Thorup^2.
Anyway, a couple of years ago I also tried my hand at building hashes and created a few that passed SMHasher (tifuhash ~ a floating point hash, beamsplitter - a seemingly-universal tabulation style hash, and this one discohash - a "more traditional" ARX-based design (addition rotation xor)^3 ).
0: https://github.com/rurban/smhasher/blob/master/xxh3.h https://github.com/rurban/smhasher/blob/master/xxh3.h
1: https://pvk.ca/Blog/2022/12/29/fixing-hashing-modulo-alpha-equivalence/ https://pvk.ca/Blog/2022/12/29/fixing-hashing-modulo-alpha-e...
2: https://arxiv.org/abs/1505.01523 https://arxiv.org/abs/1505.01523
3: https://eprint.iacr.org/2018/898.pdf https://eprint.iacr.org/2018/898.pdf https://crypto.polito.it/content/download/480/2850/file/document.pdf https://crypto.polito.it/content/download/480/2850/file/docu...
4: https://en.wikipedia.org/wiki/BLAKE_(hash_function) https://en.wikipedia.org/wiki/BLAKE_(hash_function)
Discohash (posted here) is the fastest one I made, it's simple and doesn't rely on any arch-specific optimizations or vector instructions (AVX etc ~ tho I suppose...they could be added? I'm definitely no expert in them, I barely get away with doing the C/C++ implementations!)
The main mixing round function is:
mix(const int A) {
const int B = A + 1;
ds[A] *= P;
ds[A] = rot(ds[A], 23);
ds[A] *= Q;
ds[B] ^= ds[A];
ds[B] *= P;
ds[B] = rot(ds[B], 23);
ds[B] *= Q;
}
where P and Q are two randomly chosen 64-bit primes (P is actually the largest unsigned 64-bit prime!), and A is an index into the 256-bit internal state.
I love it because of its simplicity (and because I Created it :) ha), but I think it has some room to grow. An interesting design feature is the internal state is actually variable, it can be larger than 32-bytes.
Some future directions (for anyone who is interested and wants to extend it):
- add a sponge construction to create an infinite output stream / keystream generator
- add AVX instructions (or other optimizations to squeeze more out of a serial implementation)
- figure out how to use a Merkle construction on discohash (like the Blake hashes^4 use to improve their not-that-impressive serial speed using parallelization), hard for discohash I think because state operations are essentially "chained together"
- see if it can be parameterized with other pairs of primes (perhaps into a "universal" family of functions). P & Q in discohash have the interesting and quite rare property that P - Q = P ^ Q (their difference equals their XOR), I surmise that may required for other P and Q to work in discohash.
I just added a PR to Smhasher^5 to update the hash to a faster version and fix some implementation issues related to memory alignment that after much fuffing about with ChatGPT I was thankfully able to resolve! Relief!
I'm no math expert, nor an expert in optimization, nor cryptanalysis, I basically just developed these hashes intuitively, flying by the seat of my pants! But they worked, hoo rah! :)
5: https://github.com/rurban/smhasher/pull/268 https://github.com/rurban/smhasher/pull/268
- keepamovin 3y agoIn fact the implementation is so short I can just post the whole thing here: // also known as BEBB4185 // Copyright 2020 Cris Stringfellow // https://github.com/dosyago/discohash #include <cstdio> #include <inttypes.h> #include <cstring> #include "discohash.h" constexpr int STATE = 32; constexpr int STATE64 = STATE >> 3; constexpr int STATEM = STATE-1; constexpr int HSTATE64M = (STATE64 >> 1)-1; constexpr int STATE64M = STATE64-1; alignas(uint64_t) uint8_t disco_buf[STATE] = {0}; constexpr uint64_t P = 0xFFFFFFFFFFFFFFFF - 58; constexpr uint64_t Q = 13166748625691186689U; alignas(uint64_t) uint8_t *ds8 = (uint8_t *)disco_buf; uint64_t *ds = (uint64_t *)disco_buf; //-------- // State mix function static inline uint64_t rot( uint64_t v, int n) { n = n & 63U; if (n) v = (v >> n) | (v << (64-n)); return v; } static inline uint8_t rot8( uint8_t v, int n) { n = n & 7U; if (n) v = (v >> n) | (v << (8-n)); return v; } static inline void mix(const int A) { const int B = A+1; ds[A] *= P; ds[A] = rot(ds[A], 23); ds[A] *= Q; ds[B] ^= ds[A]; ds[B] *= P; ds[B] = rot(ds[B], 23); ds[B] *= Q; } //--------- // Hash round function static inline void round( const uint64_t * m64, const uint8_t * m8, int len ) { int index = 0; int sindex = 0; uint64_t counter = 0xfaccadaccad09997; uint8_t counter8 = 137; for( int Len = len >> 3; index < Len; index++) { ds[sindex] += rot(m64[index] + index + counter + 1, 23); counter += ~m64[index] + 1; if ( sindex == HSTATE64M ) { mix(0); sindex++; } else if ( sindex == STATE64M ) { mix(2); sindex = 0; } else { sindex++; } } mix(1); index <<= 3; sindex = index&(STATEM); for( ; index < len; index++) { ds8[sindex] += rot8(m8[index] + index + counter8 + 1, 23); counter8 += ~m8[sindex] + 1; mix(index%STATE64M); if ( sindex >= STATEM ) { sindex = 0; } else { sindex++; } } mix(0); mix(1); mix(2); } //--------- // main hash function void DISCoHAsH_256 ( const void * key, int len, unsigned seed, void * out ) { int tempLen = len; if ( tempLen == 0 ) { tempLen = 1; } alignas(uint64_t) uint8_t* tempBuf = new uint8_t[tempLen]; const uint8_t *key8Arr = (uint8_t *)key; alignas(uint64_t) const uint8_t seedbuf[16] = {0}; const uint8_t *seed8Arr = (uint8_t *)seedbuf; const uint64_t *seed64Arr = (uint64_t *)seedbuf; uint32_t *seed32Arr = (uint32_t *)seedbuf; // the cali number from the Matrix (1999) seed32Arr[0] = 0xc5550690; seed32Arr[0] -= seed; seed32Arr[1] = 1 + seed; seed32Arr[2] = ~(1 - seed); seed32Arr[3] = (1+seed) * 0xf00dacca; // nothing up my sleeve ds[0] = 0x123456789abcdef0; ds[1] = 0x0fedcba987654321; ds[2] = 0xaccadacca80081e5; ds[3] = 0xf00baaf00f00baaa; memcpy(tempBuf, key, len); uint64_t* temp64 = reinterpret_cast<uint64_t*>(tempBuf); round( temp64, key8Arr, len ); round( seed64Arr, seed8Arr, 16 ); round( ds, ds8, STATE ); uint64_t h[4] = {ds[2] + ds[3], ds[3] ^ ds[2], ds[0] + ds[1], ds[1] ^ ds[0]}; // full 256-bit output //uint64_t h[1] = {ds[2] + ds[3]}; // 64-bit output memcpy(out, h, sizeof(h)); delete[] tempBuf; }