Hash has arbitrary seed-independent multicollisions, is not DoS resistant

[orlp]

There are probably other issues as well, but this line is particularly problematic:

gxhash/src/gxhash/platform/x86.rs

Line 86 in 8bee61e

let mut tmp1 = aes_encrypt(v0, v2);

This is trivial to invert and allows you to create arbitrary seed-independent multicollisions. I would suggest not advertising DoS resistance on this hash at all.

// Not an endorsement of aes_crypto, just the first crate
// I could find that allows cross-platform single-round encryption.
use aes_crypto::AesBlock;

fn main() {
    let zero_key = AesBlock::zero();

    let mut s0 = [0u8; 192];
    let mut s1 = [0u8; 192];

    s0[64] = 100;
    s1[64] = 42;
    
    let v0 = AesBlock::new(s0[64..64 + 16].try_into().unwrap());
    v0.enc(zero_key).store_to(&mut s0[64 + 32..]);

    let v0 = AesBlock::new(s1[64..64 + 16].try_into().unwrap());
    v0.enc(zero_key).store_to(&mut s1[64 + 32..]);

    // Different strings.
    assert!(s0 != s1);
    
    // Collide regardless of seed.
    assert!(gxhash::gxhash128(&s0, 0) == gxhash::gxhash128(&s1, 0));
    assert!(gxhash::gxhash128(&s0, 0xdeadbeef) == gxhash::gxhash128(&s1, 0xdeadbeef));
}

[ogxd]

Thanks a lot for this analysis @orlp! Let's see if we can improve DoS resistance without compromising performance. I don't know if it can be made 100% proof but I'm sure it can be improved (maybe using the seed in the main construction).

Btw DoS resistance is not advertised (unless I missed something?). See in readme:

This does not mean however that it is completely DOS resistant. This has to be analyzed further.

[orlp]

Btw DoS resistance is not advertised

I disagree. The way it is worded it sounds like it has some DoS resistance when there is none at all. Similarly with multicollision resistance.

[ogxd]

Let's see first if we can address this 😄 Feel free to submit a PR if you want.
After that, depending on the results, we can reword the DoS resistance section more accurately.

[ogxd]

Did not has much time to work on this, so in the meantime I've clarified the DOS resistance part in the readme https://github.com/ogxd/gxhash?tab=readme-ov-file#security

[purplesyringa]

There's probably a lot more problems with DoS resistance here. The most obvious one, IMO, is

https://github.com/ogxd/gxhash/blob/main/src/hasher.rs#L113-L117

compress_all is completely independent from the seed, so a collision in compress_all affects all seeds.

[ogxd]

Mixing the seed at the start instead of the end should significantly improve DoS resistance. I'm currently (slowly) exploring this path.

[thomasahle]

Follow-up to @orlp's report in this issue (a 192-byte seed-independent pair, June 2024) and to @purplesyringa's comment pointing out that compress_all is independent of the seed. The mechanism is theirs; what is added here is two short explicit pairs, one of them cross-length, a constant-time re-derivation of both (no search), and a single-file C program that reproduces everything.

Scope: gxhash v3, crate version 3.5.0, current main = 55bde47. The verifier implements the algorithm as it appears in the SMHasher3 port hashes/gxhash.cpp (written from 55bde47 by Frank J. T. Wojcik, MIT). The Rust crate is neither bundled nor executed by the reproducer; the pairs are properties of the algorithm, so they hold for any faithful implementation of it.

The two pairs

Same-length pair, 24 bytes:

m    = 000000000000000000000000000000000000000000000000
m'   = 0100000000000000a803d3a0b6cb85eb1120e4f3a270c9a6
compress_all(m) = compress_all(m') = 953a6ffc8610b87f7f40c81e7dea7eaf
seed = 0xd73a9a3d941e7ec7  ->  gxhash_64 = 0x4c6ff29ce0549cdd for both
                               gxhash (128) = dd9c54e09cf26f4c390150562e7344f4 for both

Cross-length pair, 15 vs 16 bytes:

m    = 000000000000000000000000000000
m'   = ffffffffffffffffffffffffffffffff
compress_all(m) = compress_all(m') = 0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f0f
seed = 0xf556ecbfcbfee3ad  ->  gxhash_64 = 0x43ec3783791d0fb8 for both
                               gxhash (128) = b80f1d798337ec43c5cdc136b3c57d0d for both

The 128-bit values above are little-endian memory bytes, as the program prints them; the second one read as an integer is 0x0d7dc5b336c1cdc543ec3783791d0fb8.

Where they come from

gxhash(m, seed) = finalize(aes_encrypt(compress_all(m), seed)) (src/gxhash/mod.rs#L68-L70). Everything after compress_all is a bijection of the 128-bit state for each fixed seed, so two messages with equal compress_all collide for every seed, and the collision survives truncation to 64 or 32 bits.

• 17-32 bytes: the return is aes_encrypt_last(hv, P2(v0)) = SR(SB(hv)) ^ P2(v0) (mod.rs#L124-L125), where hv is the partial vector of the leading len % 16 bytes and P2 is two AES rounds under the public KEYS. P2 is invertible, so any change to hv is cancelled by v0' = P2^-1( P2(v0) ^ SR(SB(hv)) ^ SR(SB(hv')) ) - one inverse round pair, no search. That is pair 1.
• At most 16 bytes: compress_all returns get_partial (mod.rs#L83-L86), which zero-pads and adds the length to every byte (platform/arm.rs#L28-L37, same in x86.rs). So 00*15 and ff*16 both compress to 0f*16: every message shorter than 16 bytes has a 16-byte twin. That is pair 2.

Verification program

Attached is a single-file C11 program, gxhash64_verify.c, no dependencies, MIT (it also carries the upstream MIT lines for ogxd/gxhash and for the SMHasher3 port it was written from):

cc -O2 -o gxhash64_verify gxhash64_verify.c -lm   # ARMv8 AES is picked up automatically; add -maes on x86
./gxhash64_verify                                 # 2^24 random seeds, about 1 s
./gxhash64_verify 26                              # 2^26 seeds

It refuses to report anything unless it first reproduces the SMHasher3 verification values 0x48F84240 (gxhash_64) and 0x64A77B47 (gxhash), cross-checks the hardware AES round and its inverse against a portable table round, and reproduces the published test value 69ccb8a053812a7b for pair 1 at seed 0x0123456789abcdef. It then re-derives each m' from m in constant time, prints the two equal compress_all states, and samples random seeds. At 2^24 seeds all four counts (two pairs, 64- and 128-bit output) are 16777216/16777216; at 2^26 they are 67108864/67108864. The rate is exactly 1 by the argument above - the sampling only confirms that the implementation really is gxhash. Exit status is 0 only if every check passes.

What is and is not claimed

• Claimed: two fixed message pairs whose collision probability over a uniformly random hidden seed is exactly 1, on the 32-, 64- and 128-bit outputs. For a fixed pair that probability is either 0 or 1, because the seed enters only after compress_all; these two are on the 1 side. Seed randomisation and the 128-bit state therefore give no reduction at all against these families. This is an exact count, not a measured estimate.
• Not claimed: this is not an interactive attack and involves no seed recovery or secret extraction; no exhaustive search was done, so these two families are not claimed to be the only short seed-independent pairs; and nothing here is a statement about gxhash's speed. The Rust crate itself was not executed, nor its AVX2/VAES build - the program covers the portable table path, ARMv8 AES and x86 AES-NI, which agree with each other.
• Practical shape: the 24-byte pair collides whenever the full byte stream handed to the hasher agrees, so it applies to write-based hashing of equal-length keys. A Hash implementation that writes a length or a terminator before the bytes (as Rust's slice and str impls do) neutralises the cross-length pair but not the equal-length one. This was not tested through GxHasher.

The README's security section already states that gxhash is not fully DoS resistant, so this is not a contradiction of a claim; the point is only that for these two families the reduction from seeding is zero rather than partial. The same seed-after-compression shape is known for CityHash64 (Aumasson-Bernstein-Bosslet 2012; Peters 2024).

This will be part of a public write-up on collisions in fast hash functions that need no knowledge of the seed. Happy to adjust the wording or timing, and corrections are welcome if any of the above misreads the implementation or its intended guarantee.

Thomas Ahle

Standalone verification programs: https://github.com/thomasahle/hash-collision-witnesses