A hash function using only add, sub, ror, and xor | Hacker News Reader

A hash function using only add, sub, ror, and xor

github.com

70 pointsanfilt27 comments

Here's another hash function / mixer that uses only add, rotate and xor. Actually this is based on common ARX ciphers, but a lot smaller because it doesn't need to be a secure cipher.

It is 48 x86_64 instructions, compared to the 36 instructions of khash in the link. I am sure you could put more data into b, c, and d as parameters, but I've only used it as a U64 to U64 function.

  static uint64_t rotl64(uint64_t n, uint8_t k) {
    uint64_t a = n << k;
    uint64_t b = n >> (64 - k);
    return a | b;
  }
  
  uint64_t hash(uint64_t a) {
    uint64_t b = 0;
    uint64_t c = 0;
    uint64_t d = 0;
    for (uint8_t i = 0; i < 4; i++) {
      b ^= rotl64(a + d, 7);
      c ^= rotl64(b + a, 9);
      d ^= rotl64(c + b, 13);
      a ^= rotl64(d + c, 18);
    }
  
    return a ^ b ^ c ^ d;
  }

Those numbers would be if you compile without the RORX instruction.

K-HASH: 26 instructions https://godbolt.org/z/s3f13nGdG

Your-ARX: 48 instructions (even with rorx) https://godbolt.org/z/cv6PeohP6

Worth pointing out for bystanders that in superscalar, pipelined processors the number of instructions has very little bearing over whether something is faster or slower (unless we are talking about differences of many orders of magnitude in the number of instructions). This applies even if we are not talking about instructions that deal with memory or I/O.

For the simple ops used in these particular algorithms, it should be possible to use SIMD to saturate the pipeline, getting high throughput for the same latency, assuming SIMD is part of the ISA. Cache misses wouldn't be a factor in comparing hash algorithms, as the memory layout is a feature of the hash input, and hash state would typically either be in register or in cache

Sure. But even if the CPU doesn't interleave them in reorder buffer, you can do it. At least as long as the dependency chain isn't too long.

Even if the dependency chain is too long for the CPU (or you) to split it, the CPU can always run hyperthread while waiting.

This is not a full-blown hash function, just a mixer, like in murmur. It hashes only a single word, not a buffer. Haven't yet checked how good it is, but it's definitely a bit slower than fnv1, and faster than murmur. Will add it to smhasher soon, as soon as I get the unaligned part written. So far it doesn't look too good.

I will add that 32 bit version compiles quite nicely on arm. It's also what made me try something with this structure. https://godbolt.org/z/abd79sEh1

As for x86/x86_64 processors compiling with a flag like -march=broadwell will remove quite few movs from the compiled code since the RORX instruction will be available which can take two register parameters, and a constant. Unlike the normal ROR instruction which is just a register and constant or the CL register for the rotation amount.

Now compared to functions that use multiplication. Multiplication can mix bits quite quickly. If the hardware multiplier is fast I don't think it would be faster with than fnv1 considering how simple that function is.

Thanks for maintaining your SMHasher fork by the way, I've got too darn many other projects. :)

> This is not a full-blown hash function

Meaning it's super easy to create collisions? How easy exactly?

No, it means it does only half of the job.

It can only take an input of fixed size and return an output of the same size.

"True" hash functions take an input buffer of an arbitrary size, and return an output of a fixed size. The mixer can be a part of the complete hash function, often the key part, but it is not the entire thing.

Not the GP, but in the sense that it can't be used to hash arbitrary (word-padded) data. This "hash" can only turn words into other words. A true hash function needs to produce a hash from a multi-word buffer, and do so in a way that all the data in the buffer is equally significant to the final hash value.

Typically it is important for a hash function to be fast, because it is on the critical path.

This hash function builds up a very long dependency chain, so takes about as many clock cycles as lines. It is generally better to keep dependency chains short and independent.

In this case, it would be better to start three or more separate expressions, and xor them together at the end, so they could execute in parallel, maybe 3x as fast.

But if you have an AES instruction, a couple of rounds of that are probably better and faster than what you would invent.

FWIW, binary pbm is a good format for these sort of images.

Heres a script to make one from /dev/urandom. Use something.pbm as the file name. size is in octets.

  case $# in
  1) file="$1"; size="100";;
  2) file="$1"; size="$2";;
  *) echo >&2 'Usage  ... file [size]'; exit 2;;
  esac

  (echo 'P4
  # random.pbm

  '
  echo $size $size
  dd if=/dev/urandom bs=8 count=$((size * size))
  ) > "$file"

SMHasher results are here: https://github.com/rurban/smhasher/ below the FNV's.

In short: it shows why a simple word mixer alone is not enough for a proper hash. It is insecure, fails all tests, and is not as fast as expected. I would not even use it for PRNG's, but I haven't tested that usage yet.

https://rigtorp.se/notes/hashing/ and links therein (https://github.com/martinus/better-faster-stronger-mixer ) are almost certainly preferable to this mixer.

Perhaps I'm missing something, but what are applications of a hash function that returns the same word size as its input? Just obfuscation of the input?

It is often useful to have integer-keyed associative arrays; or, if you prefer, sparse positional arrays.

In either case, a hash table is often the most optimal implementation strategy. And unless the keys are guaranteed to be evenly distributed, the identity is an asymptotically bad hash function.

But the hash still produces sparse outputs, it has some degree of avalanche effect does it not? In which case, wouldn't the hash function produce worse results w.r.t. cache misses?

I am not sure what you're getting at. Are you unfamiliar with hash tables as a data structure?

If your keys are maximally clustered then you can use an alternate dense representation. Otherwise, using a hash table with the identity hash function will likely result in many collisions.

https://en.wikipedia.org/wiki/Xorshift and https://en.wikipedia.org/wiki/Xoroshiro128%2B are reputable and popular.

Those are PRNGs, not hash functions.

Ok but why not use a PRNG for a hash function using the value as the seed? It will scramble the bits nicely.

PRNGs are not good mixers because they're not designed to be.

- A PRNG takes a pseudo-random state and produces another pseudo-random state

- A mixer takes possibly correlated inputs and must produce outputs as uncorrelated as possible.

I've actually experimented with using xorshift variants as mixers and they fail the basic statistical tests.

I'm not a cryptographer or even that into crypto, but maybe PRNGs would produce collisions much more often than hashes?

Nor am I, but I don't think that's the problem.

It seems to me is that if you want to do that, you would use the value as a seed to set the internal state of the PRNG and then call the PRNG just once to get the hash value.

But in order to do that, you would have to derive the seed from the data in an appropriate way, which is basically the same exercise as defining a general hash function (i.e. projecting a data of arbitrary length into a set of values of fixed length).

So it looks like you are back to square one, more or less.

Is it any better than reduced-round versions of some ARX ciphers like ChaCha20?

Probably not, and probably slower besides.

Reply on news.ycombinator.com