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

```c
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.

1. **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` / `-s` pair across the two halves. This is a property of
`XXH3_mul128_fold64` alone 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).

2. **64-bit variant.** In `XXH3_len_17to128_64b` and `XXH3_len_129to240_64b` the accumulator is
`len*PRIME64_1 + sum of XXH3_mix16B(...)` followed by `XXH3_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. Neither `w1 == ~w0` nor
complementing both words is required: complementing the first word alone suffices (controls
B and C).

3. **128-bit variant.** `XXH128_mix32B` feeds the first chunk into `acc.low64` via the same
`mix16B`, and into `acc.high64` only through the raw word sum:

```c
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.high64` never 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.64
```

### dev 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 only: 9)
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.64
```

Two remarks on the numbers:

* For the `withSecret` variants the effective multiplicands (a, b) are uniform for any message,
so every pair of type A, B or C is expected to collide at the fold rate (about 2^-26.6 for
(~a,~b) and (a,~b), about 2^-27.4 for (~a,b) in the fold-only lines), and the cells are
consistent with that.
* For the `withSeed` variants the seed is added to one secret word and subtracted from the next,
so (a, b) ranges over a one-parameter family that depends on the message words, and the
per-pair rate varies with the pair. Pairs of type A (`w1 == ~w0`) were consistently near
2^-27 in all 24 seeded cells across the two streams. Pairs of type C (unrelated `w1`) under
`XXH3_64bits_withSeed` ranged from 0 to 91 collisions per 2^30 across the twelve cells; the
128-byte pair that gave 91 (`rng_seed=1`), re-measured against two fresh seed streams
(`./xxh3_collide 30 seed64 128 2 1` and `... 3 1`), gave 97 and 109, i.e. about 2^-23.3 for
that particular pair. I have not characterised which pairs are affected; for the seeded
variants the 2^-27 figure should be read as typical, not as an upper bound.

Four other random 32-byte pairs (2^28 trials each, `rng_seed` 2..5) gave 1–4 collisions apiece
for both seeded variants, consistent with the rates above.

## Reproduction

Self-contained C program (build with `cc -O2 xxh3_collide.c -o xxh3_collide` with `xxhash.h` next
to it; `./xxh3_collide 30` prints the whole table for one header, `./xxh3_collide 26 seed64 32`
runs one 32-byte cell at 2^26 trials in a few seconds):

```c
/*
* xxh3_collide.c -- measure a structured collision differential in XXH3
* (64-bit and 128-bit, seeded and custom-secret) for 32..160-byte inputs.
*
* Build: cc -O2 xxh3_collide.c -o xxh3_collide (xxhash.h next to it)
* Run: ./xxh3_collide [log2_trials=30] [variant] [length] [rng_seed=1] [msg_seed=0]
* variant in {seed64, seed128, secret64, secret128, fold, all}
* length in {32, 48, 64, 100, 128, 160, 0=all}
* msg_seed != 0 draws the message pair from its own stream (see run_cell), so one
* fixed pair can be re-measured against independent seeds/secrets.
*
* Message pair (per cell, fixed for all trials; words are 8-byte little-endian):
* A: m1 random with word1 = ~word0; m2 = m1 with word0 and word1 complemented.
* B: same m1 as A (word1 = ~word0); m2 = m1 with word0 complemented only. [control]
* C: m1 random, word1 unrelated; m2 = m1 with word0 and word1 complemented. [control]
* Per trial: fresh uniformly random 64-bit seed (seed64/seed128) or fresh uniformly
* random 192-byte secret (secret64/secret128). A collision is counted only when the
* full output is equal (both 64-bit halves for the 128-bit variants).
* The "mul128_fold64 only" lines do not call XXH3 at all: they count, for uniformly
* random 64-bit a and b, how often XXH3_mul128_fold64(a,b) equals the fold of
* (~a,~b), (~a,b) and (a,~b) respectively.
*/
#define XXH_INLINE_ALL
#include "xxhash.h"
#include
#include
#include
#include
#include

#ifndef LABEL
#define LABEL "xxhash.h"
#endif

/* ---- xoshiro256** seeded by splitmix64 ---- */
static uint64_t st[4];
static inline uint64_t rotl64(uint64_t x, int k) { return (x << k) | (x >> (64 - k)); }
static inline uint64_t rng(void) {
uint64_t r = rotl64(st[1] * 5, 7) * 9, t = st[1] << 17;
st[2] ^= st[0]; st[3] ^= st[1]; st[1] ^= st[2]; st[0] ^= st[3]; st[2] ^= t; st[3] = rotl64(st[3], 45);
return r;
}
static void rng_seed(uint64_t x) {
for (int i = 0; i < 4; i++) {
x += 0x9E3779B97F4A7C15ULL; uint64_t z = x;
z = (z ^ (z >> 30)) * 0xBF58476D1CE4E5B9ULL; z = (z ^ (z >> 27)) * 0x94D049BB133111EBULL;
st[i] = z ^ (z >> 31);
}
}

enum { V_SEED64, V_SEED128, V_SECRET64, V_SECRET128, V_FOLD, V_COUNT };
static const char* vname[V_COUNT] = { "XXH3_64bits_withSeed", "XXH3_128bits_withSeed",
"XXH3_64bits_withSecret", "XXH3_128bits_withSecret",
"mul128_fold64 only" };

static void build_pair(uint8_t* m1, uint8_t* m2, size_t len, char cons) {
uint64_t w0, w1;
for (size_t i = 0; i < len; i++) m1[i] = (uint8_t)rng();
memcpy(&w0, m1, 8);
if (cons == 'C') memcpy(&w1, m1 + 8, 8);
else { w1 = ~w0; memcpy(m1 + 8, &w1, 8); }
memcpy(m2, m1, len);
w0 = ~w0; memcpy(m2, &w0, 8);
if (cons != 'B') { w1 = ~w1; memcpy(m2 + 8, &w1, 8); }
}

static double lg(unsigned long long c, unsigned long long n) { return c ? log2((double)c / (double)n) : -INFINITY; }

static uint64_t cell_seed(uint64_t base, int variant, size_t len, char cons) {
return base * 0x9E3779B97F4A7C15ULL + (uint64_t)variant * 1000003ULL + (uint64_t)len * 1009ULL + (uint64_t)cons;
}

/* msg_seed == 0: message pair and trials come from one stream seeded by base_seed (default).
* msg_seed != 0: message pair from a stream seeded by msg_seed, trials from base_seed, so the
* same pair can be re-measured against an independent set of seeds/secrets. */
static void run_cell(int variant, size_t len, char cons, unsigned long long trials, uint64_t base_seed, uint64_t msg_seed) {
uint8_t m1[256], m2[256], secret[192];
unsigned long long coll = 0, lo = 0, hi = 0;
rng_seed(cell_seed(msg_seed ? msg_seed : base_seed, variant, len, cons));
build_pair(m1, m2, len, cons);
if (msg_seed) rng_seed(cell_seed(base_seed, variant, len, cons) ^ 0x5555555555555555ULL);
for (unsigned long long t = 0; t < trials; t++) {
uint64_t seed = rng();
if (variant == V_SEED64) {
coll += XXH3_64bits_withSeed(m1, len, seed) == XXH3_64bits_withSeed(m2, len, seed);
} else if (variant == V_SEED128) {
XXH128_hash_t a = XXH3_128bits_withSeed(m1, len, seed), b = XXH3_128bits_withSeed(m2, len, seed);
int l = a.low64 == b.low64, h = a.high64 == b.high64; lo += l; hi += h; coll += (l & h);
} else {
for (int i = 0; i < 24; i++) { uint64_t r = rng(); memcpy(secret + 8 * i, &r, 8); }
if (variant == V_SECRET64) {
coll += XXH3_64bits_withSecret(m1, len, secret, 192) == XXH3_64bits_withSecret(m2, len, secret, 192);
} else {
XXH128_hash_t a = XXH3_128bits_withSecret(m1, len, secret, 192), b = XXH3_128bits_withSecret(m2, len, secret, 192);
int l = a.low64 == b.low64, h = a.high64 == b.high64; lo += l; hi += h; coll += (l & h);
}
}
}
printf("%-16s | %-24s | %4zu | %c | %8llu / 2^%.0f | 2^%.2f", LABEL, vname[variant], len, cons, coll, log2((double)trials), lg(coll, trials));
if (variant == V_SEED128 || variant == V_SECRET128) printf(" (low64 only: %llu, high64 only: %llu)", lo, hi);
printf("\n"); fflush(stdout);
}

/* fold-only: for uniform random a, b, how often does XXH3_mul128_fold64 agree on
* (a,b) vs (~a,~b), (~a,b), (a,~b)? No XXH3 call involved. */
static void run_fold(unsigned long long trials, uint64_t base_seed) {
static const char* pat[3] = { "~a~b", "~a b", "a ~b" };
for (int k = 0; k < 3; k++) {
unsigned long long coll = 0;
rng_seed(base_seed * 0x9E3779B97F4A7C15ULL + 4242 + (uint64_t)k);
for (unsigned long long t = 0; t < trials; t++) {
uint64_t a = rng(), b = rng(), f = XXH3_mul128_fold64(a, b);
uint64_t g = k == 0 ? XXH3_mul128_fold64(~a, ~b) : k == 1 ? XXH3_mul128_fold64(~a, b) : XXH3_mul128_fold64(a, ~b);
coll += f == g;
}
printf("%-16s | %-24s | %4s | %-4s | %8llu / 2^%.0f | 2^%.2f\n", LABEL, vname[V_FOLD], "-", pat[k], coll, log2((double)trials), lg(coll, trials));
fflush(stdout);
}
}

int main(int argc, char** argv) {
int log2t = argc > 1 ? atoi(argv[1]) : 30;
const char* vsel = argc > 2 ? argv[2] : "all";
size_t lsel = argc > 3 ? (size_t)atoi(argv[3]) : 0;
uint64_t base_seed = argc > 4 ? strtoull(argv[4], 0, 0) : 1;
uint64_t msg_seed = argc > 5 ? strtoull(argv[5], 0, 0) : 0;
unsigned long long trials = 1ULL << log2t;
static const size_t lens[] = { 32, 48, 64, 100, 128, 160 };
printf("# %s = xxhash.h %d.%d.%d, XXH_INLINE_ALL, rng_seed=%llu, msg_seed=%llu\n", LABEL, XXH_VERSION_MAJOR, XXH_VERSION_MINOR, XXH_VERSION_RELEASE, (unsigned long long)base_seed, (unsigned long long)msg_seed);
printf("# header | variant | len | pair | collisions / trials | log2 rate (ideal: 2^-64 for 64-bit, 2^-128 for 128-bit)\n");
for (int v = 0; v < V_FOLD; v++) {
if (strcmp(vsel, "all") && strcmp(vsel, vname[v] + 5) && strcmp(vsel, v == V_SEED64 ? "seed64" : v == V_SEED128 ? "seed128" : v == V_SECRET64 ? "secret64" : "secret128")) continue;
for (size_t i = 0; i < sizeof lens / sizeof *lens; i++) {
if (lsel && lens[i] != lsel) continue;
for (const char* c = "ABC"; *c; c++) run_cell(v, lens[i], *c, trials, base_seed, msg_seed);
}
}
if (!strcmp(vsel, "all") || !strcmp(vsel, "fold")) run_fold(trials, base_seed);
return 0;
}
```

## Scope

XXH3 is documented as a non-cryptographic hash and, as far as I can tell, makes no
universal-hashing or per-pair collision-probability guarantee; the seed/secret is described as
making intentional collisions "more difficult", not as a security boundary. So this may well be
outside XXH3's design goals, and I am not suggesting that the function should change (any change
to `mix16B` would alter hash values).

Two questions for the maintainers:

1. Do you consider a 2^-27 per-pair collision probability under a random hidden seed to be in
scope for XXH3, given the existing disclaimer about seed-dependent multicollisions?
2. If not, would it be worth extending that disclaimer (and the 128-bit "NOT affected" remark) to
mention that fixed input pairs of this form collide with probability about 2^-27 under a random
seed or secret, for both the 64- and 128-bit variants, so that users who rely on the seed for a
low per-pair collision bound are aware of it?

Happy to provide more data or test any proposed wording.

Start with XXH3_mix16B, XXH3_len_17to128_64b, XXH3_len_129to240_64b, and XXH128_mix32B, then reproduce the fixed-pair collision measurements described for seeded and secret-based variants. The issue establishes an unusual collision rate but does not specify a code change; done requires determining and documenting the appropriate resolution.

Written by the indexing model from the issue text.