gxhash64() on x86 ignores half of its input bytes

[sesse]

Hi,

It seems gxhash64() does this to reduce 256 to 64 bits:

    return *(uint64_t*)&full_hash;

However, all the mixing operations in GxHash (when using AVX2; not so much on NEON) are two parallel 128-bit lanes that never get combined together (all the operations are _si128, so 128-bit AES). Thus, when dealing with e.g. 32-byte strings, this means that the returned answer is entirely unaffected by the contents of bytes 16…31. gxhash32() has the same problem.

I found this out when trying to use the code for a real-world system and then ended up with tons of collisions on almost-equal strings :-) I'm a bit surprised that no SMHasher tests triggered on this.

[rurban]

Indeed smhasher only tests 32 and 64 bit windows. Everything higher is too large. We have to think about catching these limitations

[erthink]

@rurban, I had a discussion about this a long time ago (what can be done to verify wide hashes). To simplify it, the short conclusion boils down to the fact that we need to check at least two:

1. Avalance of a high poriton of hash (i.e. any change of input should lead to change each output bit with the 0.5 probability);
2. XOR (bitwise inequality) of low/base 64 bits and each 64-bit chunk of a "high" portion of hash.

This is the way to provide minimal national coverage and protection against the mentioned naive errors.

// I intended to make a more complete (within the limits of technical capabilities) solution of such problem in the HashContest project via a correlation on GPU (but an amount of GPU-RAM is fundamentally important). However, I don't have enough perseverance/time/resources for this yet.

[sesse]

For fixing GxHash, I guess the simplest way would be to initialize the two halves with different data, and then XOR the resulting high and low 64 bits together? It won't give the same result as the 128-bit version, but it should at least care about the bytes.

There are more oddities, though. For instance, there's code in there to support big-endian AVX2, which doesn't make sense (there has never been a big-endian x86 CPU, much less one with vAES). The AVX2 and non-AVX2 versions add the lengths in different ways (as 8-bit or 32-bit values) for some unspecified reason. There's also an endianness test in NEON that is completely broken; the bytes are backwards on little-endian systems (there shouldn't be an #ifdef here at all). So it will read garbage data past the end of its buffer.