XXH3 (64- and 128-bit): a fixed pair of 32–240-byte messages collides with probability about 2^-27 over a uniformly random seed or secret
Summary
For the 17–240-byte code path, there is a simple, seed-independent way to choose two distinct
messages m1, m2 such that, when the seed (or the 192-byte secret) is drawn uniformly at random
and kept hidden, XXH3_64bits_withSeed(m1) == XXH3_64bits_withSeed(m2) with probability about
2^-27, and XXH3_128bits_withSeed(m1) == XXH3_128bits_withSeed(m2) (both halves) also with
probability about 2^-27. The same holds for XXH3_64bits_withSecret / XXH3_128bits_withSecret
with a fresh uniformly random 192-byte secret. For comparison, an ideal 64-bit (resp. 128-bit)
hash would give 2^-64 (resp. 2^-128) for any fixed pair, so the measured rate is about 2^37
(resp. 2^101) times the ideal. (2^-27 is the typical figure; for the seeded variants the rate
depends on the particular pair, and one measured pair reached about 2^-23, see below.)
The pair is:
- m1: any message of length 32..240 whose second 8-byte word is the bitwise complement of the
first (
w1 == ~w0), remaining bytes arbitrary; - m2: m1 with the first two 8-byte words complemented (
~w0,~w1).
For the 64-bit variant neither condition is needed: complementing the first 8-byte word alone, or both of the first two words, of an arbitrary message already collides at a comparable rate (controls B and C below; for the seeded variant the per-pair rate then varies from pair to pair, see the remarks under Measurements). For the 128-bit variant both conditions are needed (controls B and C give zero collisions for it).
Lengths measured: 32, 48, 64, 100, 128, 160 bytes (2^30 trials per cell, tables below), plus 200 and 240 bytes for the 128-bit seeded variant (4 and 2 collisions in 2^28 trials, i.e. about 2^-26 and 2^-27); at 241 bytes, where the long-input path takes over, the same pair gives no collisions in 2^28 trials, as expected.
I measured this on v0.8.3 (the newest release tag; byte-identical to the Homebrew package) and on
the dev branch head (c0b5ea995d66691734b1a79ad89e73a0d2fd5a53, 2026-07-27), whose XXH3 arithmetic is unchanged relative to v0.8.3.
Threat model
- The seed (or secret) is a uniformly random hidden value, chosen once, unknown to the attacker.
- The attacker chooses the inputs, with no knowledge of the seed and no oracle access.
- The probability quoted is over the choice of seed/secret, for a fixed pair of inputs.
This is the setting in which one would hope that seeding makes it "more difficult for an
external actor to prepare an intentional collision" (wording from the XXH3_64bits_withSecret
documentation). It is not a claim about unseeded XXH3, about SMHasher-style statistical quality,
or about recovering the seed. It is also not, by itself, a practical way to flood a hash table:
one collision per ~2^27 prepared pairs is far above 2^-64 but still small in absolute terms.
Why it happens
For 32 <= len <= 240 the first 16 input bytes enter the hash only through
XXH3_mix16B(input, secret, seed)
= XXH3_mul128_fold64(w0 ^ (secret[0..8) + seed), w1 ^ (secret[8..16) - seed))where XXH3_mul128_fold64(a, b) = lo64(a*b) ^ hi64(a*b). (For 17..31 bytes the "last 16 bytes"
window overlaps the first 16, so 32 is the smallest clean length; above 240 the long-input path is
used.) Write a = w0 ^ K0 and b = w1 ^ K1 for the two effective multiplicands; with a random seed
or secret, (a, b) is (close to) uniformly random. Complementing w0 and w1 complements a and b.
The fold does not separate complemented multiplicands. Over the integers mod 2^128,
(~a)*(~b) = a*b + (a + b + 1) - 2^64 * (a + b + 2) (mod 2^128)so, writing s = a + b + 1 (mod 2^64), the low 64 bits of the product gain s and the high 64 bits lose approximately s. The XOR of the two halves is unchanged whenever the bit pattern flipped by adding s to the low half equals the pattern flipped by subtracting from the high half. Since carry chains are short, this coincidence has probability about 2^-26.7 for uniformly random (a, b) — not 2^-64. Complementing only one multiplicand behaves the same way:
(~a)*b = 2^64*b - (a*b + b) (mod 2^128), and negating a 128-bit value (plus the shift by b) again moves a+s/-spair across the two halves. This is a property ofXXH3_mul128_fold64alone and can be measured without calling XXH3 at all (the "mul128_fold64 only" lines in the table: (~a,~b), (~a,b) and (a,~b) all agree with (a,b) with probability about 2^-27).64-bit variant. In
XXH3_len_17to128_64bandXXH3_len_129to240_64bthe accumulator islen*PRIME64_1 + sum of XXH3_mix16B(...)followed byXXH3_avalanche. For 32 <= len <= 240 the first 16-byte chunk is mixed exactly once, and every other term is identical for m1 and m2, so whenever that one fold coincides the whole hash collides. Neitherw1 == ~w0nor complementing both words is required: complementing the first word alone suffices (controls B and C).128-bit variant.
XXH128_mix32Bfeeds the first chunk intoacc.low64via the samemix16B, and intoacc.high64only through the raw word sum:acc.low64 += XXH3_mix16B(input_1, secret+0, seed); acc.low64 ^= XXH_readLE64(input_2) + XXH_readLE64(input_2 + 8); acc.high64 += XXH3_mix16B(input_2, secret+16, seed); acc.high64 ^= XXH_readLE64(input_1) + XXH_readLE64(input_1 + 8);Under (w0, w1) -> (~w0, ~w1) the sum becomes -2 - (w0 + w1) mod 2^64, which equals w0 + w1 exactly when w0 + w1 is 2^64 - 1 or 2^63 - 1 (mod 2^64). Choosing w1 = ~w0 gives the first case, so
acc.high64never sees the difference, and the two evaluations again differ only in one fold. Both output halves are functions of(acc.low64, acc.high64), so they collide together — in the measurements below the low-only and high-only counts always equal the full-collision count.
The comment block above XXH3_mix16B already documents seed-dependent multicollisions caused by
a multiplicand becoming zero (about 2^-63 per word), and notes that the 128-bit variant is not
affected thanks to the raw-sum step in XXH128_mix32B. The event described here is different:
no multiplicand is zero, a fixed pair collides with probability 2^-27 rather than 2^-63, and the
raw-sum step is bypassed by the choice w1 = ~w0.
Measurements
Each cell: one random message pair of the given length (fixed for the cell), 2^30 trials, each
trial with a fresh uniformly random 64-bit seed (withSeed) or a fresh uniformly random 192-byte
secret (withSecret). A collision is counted only if the full output is equal (both halves for
the 128-bit variants). Pair A is the pair described above; B and C are controls:
- A: w1 = ~w0 in m1; m2 = m1 with w0 and w1 complemented.
- B: w1 = ~w0 in m1; m2 = m1 with w0 complemented only (control).
- C: w1 unrelated to w0 in m1; m2 = m1 with w0 and w1 complemented (control).
Ideal rates: 2^-64 (64-bit) and 2^-128 (128-bit), i.e. an expected 2^-34 and 2^-98 collisions per
cell. Apple M2 Pro, Apple clang 17, -O2, XXH_INLINE_ALL.
The two tables below use different pseudo-random streams (rng_seed=1 for v0.8.3, rng_seed=2
for dev), so they are independent samples, with different message pairs and different
seeds/secrets. (Running the v0.8.3 build and a build against Homebrew's header with the same
rng_seed gives identical counts, as expected for identical bytes; that table is omitted.)
The last three lines of each table exercise XXH3_mul128_fold64 alone on uniformly random
(a, b), 2^34 trials for (~a,~b) and 2^32 for each pattern.
v0.8.3 (newest release tag; byte-identical to Homebrew's xxhash 0.8.3 header) — ./xxh3_collide 30 all 0 1
variant | len | pair | collisions / trials | log2 rate
XXH3_64bits_withSeed | 32 | A | 10 / 2^30 | 2^-26.68
XXH3_64bits_withSeed | 32 | B | 5 / 2^30 | 2^-27.68
XXH3_64bits_withSeed | 32 | C | 3 / 2^30 | 2^-28.42
XXH3_64bits_withSeed | 48 | A | 13 / 2^30 | 2^-26.30
XXH3_64bits_withSeed | 48 | B | 11 / 2^30 | 2^-26.54
XXH3_64bits_withSeed | 48 | C | 21 / 2^30 | 2^-25.61
XXH3_64bits_withSeed | 64 | A | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSeed | 64 | B | 7 / 2^30 | 2^-27.19
XXH3_64bits_withSeed | 64 | C | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSeed | 100 | A | 13 / 2^30 | 2^-26.30
XXH3_64bits_withSeed | 100 | B | 7 / 2^30 | 2^-27.19
XXH3_64bits_withSeed | 100 | C | 12 / 2^30 | 2^-26.42
XXH3_64bits_withSeed | 128 | A | 11 / 2^30 | 2^-26.54
XXH3_64bits_withSeed | 128 | B | 11 / 2^30 | 2^-26.54
XXH3_64bits_withSeed | 128 | C | 91 / 2^30 | 2^-23.49
XXH3_64bits_withSeed | 160 | A | 6 / 2^30 | 2^-27.42
XXH3_64bits_withSeed | 160 | B | 6 / 2^30 | 2^-27.42
XXH3_64bits_withSeed | 160 | C | 12 / 2^30 | 2^-26.42
XXH3_128bits_withSeed | 32 | A | 5 / 2^30 | 2^-27.68 (low64 only: 5, high64 only: 5)
XXH3_128bits_withSeed | 32 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 32 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 48 | A | 8 / 2^30 | 2^-27.00 (low64 only: 8, high64 only: 8)
XXH3_128bits_withSeed | 48 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 48 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 64 | A | 10 / 2^30 | 2^-26.68 (low64 only: 10, high64 only: 10)
XXH3_128bits_withSeed | 64 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 64 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 100 | A | 12 / 2^30 | 2^-26.42 (low64 only: 12, high64 only: 12)
XXH3_128bits_withSeed | 100 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 100 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 128 | A | 5 / 2^30 | 2^-27.68 (low64 only: 5, high64 only: 5)
XXH3_128bits_withSeed | 128 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 128 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 160 | A | 5 / 2^30 | 2^-27.68 (low64 only: 5, high64 only: 5)
XXH3_128bits_withSeed | 160 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 160 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_64bits_withSecret | 32 | A | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSecret | 32 | B | 3 / 2^30 | 2^-28.42
XXH3_64bits_withSecret | 32 | C | 17 / 2^30 | 2^-25.91
XXH3_64bits_withSecret | 48 | A | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSecret | 48 | B | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSecret | 48 | C | 14 / 2^30 | 2^-26.19
XXH3_64bits_withSecret | 64 | A | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSecret | 64 | B | 11 / 2^30 | 2^-26.54
XXH3_64bits_withSecret | 64 | C | 13 / 2^30 | 2^-26.30
XXH3_64bits_withSecret | 100 | A | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSecret | 100 | B | 7 / 2^30 | 2^-27.19
XXH3_64bits_withSecret | 100 | C | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSecret | 128 | A | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSecret | 128 | B | 5 / 2^30 | 2^-27.68
XXH3_64bits_withSecret | 128 | C | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSecret | 160 | A | 5 / 2^30 | 2^-27.68
XXH3_64bits_withSecret | 160 | B | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSecret | 160 | C | 13 / 2^30 | 2^-26.30
XXH3_128bits_withSecret | 32 | A | 7 / 2^30 | 2^-27.19 (low64 only: 7, high64 only: 7)
XXH3_128bits_withSecret | 32 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 32 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 48 | A | 12 / 2^30 | 2^-26.42 (low64 only: 12, high64 only: 12)
XXH3_128bits_withSecret | 48 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 48 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 64 | A | 11 / 2^30 | 2^-26.54 (low64 only: 11, high64 only: 11)
XXH3_128bits_withSecret | 64 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 64 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 100 | A | 6 / 2^30 | 2^-27.42 (low64 only: 6, high64 only: 6)
XXH3_128bits_withSecret | 100 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 100 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 128 | A | 15 / 2^30 | 2^-26.09 (low64 only: 15, high64 only: 15)
XXH3_128bits_withSecret | 128 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 128 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 160 | A | 18 / 2^30 | 2^-25.83 (low64 only: 18, high64 only: 18)
XXH3_128bits_withSecret | 160 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 160 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
mul128_fold64 only | - | ~a~b | 169 / 2^34 | 2^-26.60
mul128_fold64 only | - | ~a~b | 36 / 2^32 | 2^-26.83
mul128_fold64 only | - | ~a b | 24 / 2^32 | 2^-27.42
mul128_fold64 only | - | a ~b | 41 / 2^32 | 2^-26.64dev branch (c0b5ea995d66691734b1a79ad89e73a0d2fd5a53, 2026-07-27, still reports XXH_VERSION 0.8.3) — ./xxh3_collide 30 all 0 2
variant | len | pair | collisions / trials | log2 rate
XXH3_64bits_withSeed | 32 | A | 11 / 2^30 | 2^-26.54
XXH3_64bits_withSeed | 32 | B | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSeed | 32 | C | 0 / 2^30 | 2^-inf
XXH3_64bits_withSeed | 48 | A | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSeed | 48 | B | 7 / 2^30 | 2^-27.19
XXH3_64bits_withSeed | 48 | C | 3 / 2^30 | 2^-28.42
XXH3_64bits_withSeed | 64 | A | 14 / 2^30 | 2^-26.19
XXH3_64bits_withSeed | 64 | B | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSeed | 64 | C | 17 / 2^30 | 2^-25.91
XXH3_64bits_withSeed | 100 | A | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSeed | 100 | B | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSeed | 100 | C | 6 / 2^30 | 2^-27.42
XXH3_64bits_withSeed | 128 | A | 11 / 2^30 | 2^-26.54
XXH3_64bits_withSeed | 128 | B | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSeed | 128 | C | 4 / 2^30 | 2^-28.00
XXH3_64bits_withSeed | 160 | A | 11 / 2^30 | 2^-26.54
XXH3_64bits_withSeed | 160 | B | 14 / 2^30 | 2^-26.19
XXH3_64bits_withSeed | 160 | C | 4 / 2^30 | 2^-28.00
XXH3_128bits_withSeed | 32 | A | 12 / 2^30 | 2^-26.42 (low64 only: 12, high64 only: 12)
XXH3_128bits_withSeed | 32 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 32 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 48 | A | 16 / 2^30 | 2^-26.00 (low64 only: 16, high64 only: 16)
XXH3_128bits_withSeed | 48 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 48 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 64 | A | 9 / 2^30 | 2^-26.83 (low64 only: 9, high64 only: 9)
XXH3_128bits_withSeed | 64 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 64 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 100 | A | 4 / 2^30 | 2^-28.00 (low64 only: 4, high64 only: 4)
XXH3_128bits_withSeed | 100 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 100 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 128 | A | 11 / 2^30 | 2^-26.54 (low64 only: 11, high64 only: 11)
XXH3_128bits_withSeed | 128 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 128 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 160 | A | 10 / 2^30 | 2^-26.68 (low64 only: 10, high64 only: 10)
XXH3_128bits_withSeed | 160 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSeed | 160 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_64bits_withSecret | 32 | A | 14 / 2^30 | 2^-26.19
XXH3_64bits_withSecret | 32 | B | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSecret | 32 | C | 11 / 2^30 | 2^-26.54
XXH3_64bits_withSecret | 48 | A | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSecret | 48 | B | 8 / 2^30 | 2^-27.00
XXH3_64bits_withSecret | 48 | C | 13 / 2^30 | 2^-26.30
XXH3_64bits_withSecret | 64 | A | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSecret | 64 | B | 5 / 2^30 | 2^-27.68
XXH3_64bits_withSecret | 64 | C | 11 / 2^30 | 2^-26.54
XXH3_64bits_withSecret | 100 | A | 14 / 2^30 | 2^-26.19
XXH3_64bits_withSecret | 100 | B | 9 / 2^30 | 2^-26.83
XXH3_64bits_withSecret | 100 | C | 10 / 2^30 | 2^-26.68
XXH3_64bits_withSecret | 128 | A | 6 / 2^30 | 2^-27.42
XXH3_64bits_withSecret | 128 | B | 10 / 2^30 | 2^-26.68
XXH3_64bits_withSecret | 128 | C | 17 / 2^30 | 2^-25.91
XXH3_64bits_withSecret | 160 | A | 10 / 2^30 | 2^-26.68
XXH3_64bits_withSecret | 160 | B | 7 / 2^30 | 2^-27.19
XXH3_64bits_withSecret | 160 | C | 10 / 2^30 | 2^-26.68
XXH3_128bits_withSecret | 32 | A | 17 / 2^30 | 2^-25.91 (low64 only: 17, high64 only: 17)
XXH3_128bits_withSecret | 32 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 32 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 48 | A | 10 / 2^30 | 2^-26.68 (low64 only: 10, high64 only: 10)
XXH3_128bits_withSecret | 48 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 48 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 64 | A | 9 / 2^30 | 2^-26.83 (low64 only: 9, high64 only: 9)
XXH3_128bits_withSecret | 64 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 64 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 100 | A | 13 / 2^30 | 2^-26.30 (low64 only: 13, high64 only: 13)
XXH3_128bits_withSecret | 100 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 100 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 128 | A | 3 / 2^30 | 2^-28.42 (low64 only: 3, high64 only: 3)
XXH3_128bits_withSecret | 128 | B | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 128 | C | 0 / 2^30 | 2^-inf (low64 only: 0, high64 only: 0)
XXH3_128bits_withSecret | 160 | A | 9 / 2^30 | 2^-26.83 (low64 only: 9, high64 onSource: Cyan4973/xxHash