absl::Hash: fixed string pairs that collide for every seed (0 vs 8 bytes, and every 9..16-byte string ending in kMul hashes to 0)

[thomasahle]

Scope up front: Abseil states that absl::Hash makes no security claim, and this report does not say otherwise. It documents that several fixed pairs of short strings collide under absl::Hash<std::string_view> for every seed, including every one of the 32 per-table SwissTable seeds and the process seed, and that one code comment next to the affected path describes the second family as needing an "incredibly unlucky" seed when it in fact needs none. It is not a hash-flooding exploit and I have not built one.

Version: master at 73d2688300440c8af028eec865ee0dcd85e93025 (2026-09-17); absl/hash/internal/hash.h (sha256 65f71f11a2726a570d94610b494cde0592ae0a40d67d25f05559da1443d8e288) and hash.cc (f2b6084bffd569da77eb2822176c5d71b31bddcdde961cd8fad9cfb12db8857e) are, as far as I can tell, the files LTS 20260817.0 ships. Default open-source build (ABSL_OPTION_INLINE_HW_ACCEL_STRATEGY 0); the pairs are at most 16 bytes, so the LowLevelHash backend does not enter and the result is the same on the x86-64 scalar build, the -msse4.2 -maes build and, by source structure, the arm64 ARM-crypto build (that last one I have only compiled, not run).

The pairs

For len <= 8 the whole hash is Mix(state ^ v, kMul) (hash.h L1168), where v is the public packing of the bytes (Read4To8 / Read1To3, 0x57 for the empty string), state is the seed XOR the length mix D(len) (the 8-byte window of kStaticRandomData at offset len), and Mix(a, b) = hi64(a*b) ^ lo64(a*b). Seed and length are XORed into the same multiplicand before one fixed map, so any two (len, bytes) with equal v ^ D(len) collide for every seed:

pair 1:  ""   (0 bytes)  vs  a6e02637c07bd386 (8 bytes)      m' = bytes8(D(0) ^ D(8) ^ 0x57)
pair 2:  "a"  (0x61)     vs  44b53d572db1948b (8 bytes)      m' = bytes8(D(1) ^ D(8) ^ 0x616161)

Every string of 0..8 bytes has such an 8-byte twin. For 9..16 bytes the hash is Mix(state ^ w0, kMul ^ w1) with w1 the last 8 bytes (L1207), so every string whose last 8 bytes are kMul = 0x79d5f9e0de1e8cf5 little-endian (f58c1edee0f9d579) hashes to 0 for every seed, a 2^64-way same-length multicollision:

pair 3:  6162636465666768f58c1edee0f9d579  vs  4142434445464748f58c1edee0f9d579   ("abcdefgh"/"ABCDEFGH" + kMul), both hash to 0

The comment above that code (L1201-L1205) says one half of the mix becoming zero happens for "exactly 1 in 2^64 values for each side ... unless the seed is also incredibly unlucky". That is right for the state ^ w0 side, but the kMul ^ w1 side does not involve the seed at all, so the zero is reached by one fixed choice of the last eight bytes under every seed.

Explicit values from the real library, hash_internal::HashWithSeed().hash(absl::Hash<std::string_view>{}, sv, seed):

seed 0:         H("") = H(a6e02637c07bd386) = 2bda3ac53577c4b7     H("a") = H(44b53d572db1948b) = a65e8ab2c950c927
seed 0x4055c8:  H("") = H(a6e02637c07bd386) = 06bb4292e0eae907     H("a") = H(44b53d572db1948b) = e3a0eef311f0006a
any seed:       H(pair 3, either string) = 0000000000000000

(0x4055c8 was Seed(), the address of MixingHashState::kSeed, in one non-PIE Linux binary; in a PIE binary it is ASLR-slid. Either way it is one value the pairs already cover.)

Measurements

• Real library at 73d2688, scalar and -maes builds, through HashWithSeed: all three pairs collide on the 32 SwissTable seeds {0, 64, ..., 1984} (exhaustive) and on 268,435,456 / 268,435,456 uniform 64-bit seeds, on both builds.
• Real flat_hash_set<std::string> and flat_hash_map<std::string, int> (CMake add_subdirectory build): 800 tables, whose seeds are exactly the 32 values above; hash_of(k) equals HashWithSeed().hash(Hash<string>{}, k, seed) on 1200/1200 keys; the pairs collide inside every table, 2400/2400.
• A single-file C re-implementation written from hash.h/hash.cc matches the real library on 325 recorded vectors (len 0..8192) on both builds and gives the same 32/32 and 2^28/2^28 counts.

The rate is exactly 1 by the algebra; the sampling only confirms that the code under test is the shipped absl::Hash.

Reproduction

The verify/abseil-hash/ directory of https://github.com/thomasahle/hash-collision-witnesses has the C program (MIT; no Abseil source text copied, the two constant tables are Abseil's under Apache-2.0), a README with the seed protocol and the expected output, and the two native checkers:

cd verify/abseil-hash
cc -O2 -std=c11 -o abseil_hash_verify abseil_hash_verify.c -lm
./abseil_hash_verify           # 2^20 uniform seeds + the 32 table seeds, 0.2 s; make check expects 32 1048576 32 1048576 32 1048576
./abseil_hash_verify 28        # 2^28 seeds, about 45 s
make native                    # git fetch abseil-cpp at 73d2688, sha256-check hash.h/hash.cc, run the same pairs and vectors through the real library
make swiss                     # the same pairs inside real flat_hash_set/flat_hash_map tables

The C program aborts unless all 325 real-library vectors reproduce, the pair recipes re-derive the published hex from kStaticRandomData and kMul, and the recorded values at seeds 0 and 0x4055c8 reproduce; exit status is 0 only if every check passes.

What is and is not claimed

• Claimed: three fixed pairs (two cross-length at one 8-byte word, one same-length at two words) whose collision probability over any distribution of the seed is exactly 1, for absl::Hash<std::string>/string_view/Cord bytes and for the default hasher of the Swiss tables. In the metric of the write-up this appears in, log2(L / epsilon) over the random seed, that is 0 bits at L = 1.
• Not claimed: no DoS or flooding demonstration; no statement about the hash's speed or its avalanche behaviour, which is what hash.h actually promises ("intended to strongly mix input bits with a target of passing an Avalanche Test"); and no claim that Abseil promised otherwise. The Seed() comment says plainly that the seed "is not meant as a security feature right now", and the per-table seed is 5 bits, which by itself bounds every pair at 2^-5 regardless of the hash. The hash.h sentence "One should assume that a hash algorithm is chosen randomly at the start of each process" is the one these pairs are indifferent to: for them, every choice is the same.
• Scope: only byte strings (std::string and friends). Integer keys use a different fast path and are not covered by these pairs. The len > 32 LowLevelHash path has its own seed-independent families on the scalar and ARM builds, which I have not included here; the -maes x86 build behaves differently above 32 bytes. The non-default CRC32C configuration was not measured with these pairs.

I found no prior report of these pairs for the current absl::Hash; the multiply-fold cancellation is the same primitive that wyhash/rapidhash-style pairs use, and the length-mix cancellation looks new to me. Pointers to earlier reports are welcome and will be credited.

Two concrete things that might be worth doing on your side, if any: correcting the L1201 comment so that it does not suggest the kMul side needs an unlucky seed, and, if a per-process random seed is ever adopted as the comment leaves the door open to, noting that the len <= 8 and 9..16 paths would need the seed to enter differently for it to help against these families.

This will be part of a public write-up on fixed-pair collisions in fast hashes, with the verification package alongside. Please tell me if I have misread the code or its intended guarantee and I will correct the text.

Thomas Ahle

[derekmauro]

@ezbr @goldvitaly

[goldvitaly]

I believe the observation is correct. It is indeed true that last 8 bytes being equal to kMul would make hash equal to 0.

I would wish all people use ABSL_OPTION_INLINE_HW_ACCEL_STRATEGY=1...

I think we may indeed update the comment, but do not change implementation.

[thomasahle]

Thanks. I checked the hardware-accelerated path too (ABSL_OPTION_INLINE_HW_ACCEL_STRATEGY=1,
built with -msse4.2 on Ice Lake and on an Apple M2), and it has the same problem for a
different reason, so switching to it does not remove the seed-independent collisions.

For 9 <= len <= 32 the CRC path folds each 8-byte read through crc32c into the state.
crc32c is affine over GF(2) and the seed only sets the initial value, so for two equal-length
strings the CRC difference is crc32c(0, w XOR w'), which does not depend on the seed. The
8-byte crc32c map has a 2^32-element kernel, so any byte difference that lies in that kernel
on every read leaves the hash unchanged for every seed. No search: it is linear algebra.

Explicit 9-byte pair (shortest possible; lengths <= 8 use the bijective 4-byte/1-byte crc32c
reads and have no such collision). Both hash to 3146e4736b5c9f18 for every seed, on x86 and
arm64:

m = 41 42 43 44 45 46 47 48 49 ("ABCDEFGHI")
m' = 41 b3 35 a8 40 47 47 48 49

These are not isolated pairs but whole subspaces: 2^24 nine-byte strings, 2^64 at 16 bytes,
2^128 at 32 bytes, all colliding to one value for every seed. Inserting a 2^16 subset of the
9-byte family into a real absl::flat_hash_setstd::string collapses all 65536 distinct keys
to a single H1 slot and a single H2 control byte, independent of the per-table seed.

The integer fast path collides too: absl::Hash<uint64_t>(0xd4c5434b454823a5) ==
absl::Hash<uint64_t>(0xc8823c07fd48c0dd) for every seed, and partners like this exist for
most values.

For len > 32 the CRC path hands off to LowLevelHash (AES / scalar), which is not CRC-based,
so this argument does not reach it.

So the hardware-accelerated build has the same every-seed collisions, with multicollisions at every length from 9 to 32 bytes. Reproduction and the derivation are available.