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

[thomasahle]

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 (c0b5ea9, 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.

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:

   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 (c0b5ea9, 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):

/*
 * 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 <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#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.

[Cyan4973]

Thanks for the detailed report and repro.

If I do understand correctly, this offers higher-than-brute-force chances of generating a collision with carefully crafted pairs within the [32-240] length range, at a rate of 1 in 100 millions approximately.

Note that collision resistance is outside XXH3’s guarantees, since it's labelled non-cryptographic,
but this result is nonetheless worth documenting.
To this goal, the code comment for XXH3_mix16B() dedicated to this length region will be updated to reflect this finding.

I also think it's a good reminder that XXH3 is indeed non-cryptographic, and therefore shouldn't be used as such.

[thomasahle]

Thank you, and agreed on the framing: this is not a cryptographic claim. The setting I care about is the one the withSeed/withSecret documentation describes, a hidden random seed chosen once, where a hash table owner hopes that no fixed pair collides much more often than 2^-64. Documenting it in the XXH3_mix16B() comment sounds right to me.

Two updates since the report, in case they change what you want to write there:

1. A better pair in the same family reaches about 2^-21 rather than 2^-27. With xxHash 0.8.3, the default secret and XXH3_64bits_withSeed, the 128-byte pair below collides for 504 and 526 of 2^30 random seeds in two independent runs (pooled 2^-20.99):

M  = 8912a3da9fc464368202a1be238b7d11 a56186f8dc03bd1f78bfbd2ba3386ced 7093d3639fc8f076abe3f9a757e5c842 90720e6340b2e7820a16a5633b9b0344 773006232e3abc7d4727eafba248b46c f2a6516698382bd2fa890528924cd1b6 18df4aa87d1af4bcec13f92bf8a1163e 657fb0885deddf709a0252fbe3ae169d
M2 = 76ed5c25603b9bc97dfd5e41dc7482ee a56186f8dc03bd1f78bfbd2ba3386ced 7093d3639fc8f076abe3f9a757e5c842 90720e6340b2e7820a16a5633b9b0344 773006232e3abc7d4727eafba248b46c f2a6516698382bd2fa890528924cd1b6 18df4aa87d1af4bcec13f92bf8a1163e 657fb0885deddf709a0252fbe3ae169d
example seed 0xc8eae1baae13330b: H(M) = H(M2) = 0x448e3716c8effb94

The rate depends on the first two words (this pair was found by screening bases), not on the tail: changing bytes 16 onward changes the output but not the set of colliding seeds.

2. Because of that, the same colliding-seed set applies from 32 bytes up: the first 16 bytes of M and M2 with any fixed 16-byte tail collide at the same rate (fresh runs: 483 and 535 of 2^30 at both 32 and 128 bytes). The 16-byte prefix alone, on the 9–16-byte path, gave no collision in 2^32 seeds.

A standalone C program that reproduces the verification value, then the collision for the printed seed, then samples the rate, is ready; I can attach it here or link it from the write-up I am preparing, which will quote your reply as the maintainer's response. Corrections welcome.

[Cyan4973]

updated documentation, mentioning this study and its results.

[thomasahle]

Update: 2^-10.5 over the seed with the default secret; 2^-26.9 per key with a random secret

Thank you for the documentation update (#1146, #1150) and the changelog credit. Apologies for reporting this piecemeal: the search kept improving after each message, and I would rather the thread carry the current numbers than a tidy story. These two should be the last, because they change what the XXH3_mix16B comment now quotes, and they separate the two key models.

Default secret (XXH3_64bits_withSeed, 0.8.3, uniformly random hidden seed): a 32-byte pair in the same complement-one-block family collides for about 2^-10.47 of seeds, about 2^10.5 times the rate of the 128-byte pair above. The same seeds collide through XXH3_64bits_withSecretandSeed and the streaming reset_withSecretandSeed + digest, since inputs of at most 240 bytes use kSecret and the seed there.

M  = 00000000000000000000000000000000 51151210404400000000008204000105
M' = 00000000000000000000000000000000 aeeaedefbfbbffffffffff7dfbfffefa
seed 2468b3bc26a44073 -> both hash to dd686b61e2f6dc69

Bytes in memory order; M' is M with bytes 16..31 complemented. Mechanism: for 17..128 bytes each block contributes fold(w0 ^ (K[2i] + seed), w1 ^ (K[2i+1] - seed)) and the avalanche is a bijection, so the pair collides exactly when fold(A, B) = fold(~A, ~B) for that block. Choosing w0 and w1 from the non-adjacent form of K2 + K3 + 1 makes the two carry masks agree for most seeds, and fold(A, ~A) is symmetric. The witness seed makes the multiplicands 0 and ~0.

Measured against the unmodified upstream 0.8.3 source in its own translation unit (sanity vectors checked at startup): 2,264,081 hits in 3 x 2^30 seeds, 2^-10.4745 (exact 95% interval [-10.4763, -10.4726]). The pair is a local optimum under all single-bit and two-bit moves; it is a search result, not a bound. In the write-up's figure log2(L / rate) with L in 8-byte words this puts the seeded interface at 12.5 bits, where the 128-byte pair gave 23.0.

Random secret (XXH3_64bits_withSecret with 192 uniformly random bytes): the pair above does not transfer, because its bytes encode the default-secret words. What remains is the fold differential itself. Complementing one keyed word of a 16-byte block collides with probability about 2^-26.9 per key (527 hits in 2^36 keys for the 24-byte pair 0^24 vs ff^8 0^16, independent verifier written from scratch against the public API). That caps withSecret at 28.5 bits (L = 3) against 64 for an ideal keyed function, and it is the figure I now score XXH3-64 under, since it is the strongest key model the API supports. The 2^-10.47 figure is reported as a caveat for the seeded interfaces.

Setting, as before: two fixed inputs chosen without the key, key uniform and hidden, hit = full 64-bit equality; no oracle, no adaptive queries, no key recovery. These are caps on strength against a fixed pair, not flooding attacks.

Documentation. The sentence added by #1150 ("~2^-21 over random seeds ... not a known upper bound") was accurate when written; the observed figure is now about 2^-10.5 at 32 bytes with the default secret and about 2^-26.9 per key with a random secret. Happy to send a one-line PR with the two numbers and the key models named, or to leave the wording to you.

Reproduction. The xxh3-64 directory of https://github.com/thomasahle/hash-collision-witnesses carries both checks (./check 20 samples the default-secret pair; ./check random-secret 20 samples the 24-byte pair through XXH3_64bits_withSecret with a fresh secret per trial); the 0.8.3 header is embedded verbatim and checked against the SMHasher3 verification value and the xsum sanity vectors at startup.

Corrections welcome, as before.

Thomas Ahle

[Cyan4973]

We could certainly update the code comment, to keep it up to date,
but I think that the overall idea remains clear enough:
it's a non-cryptographic hash, there are known attack vectors to generate collisions with higher-than-brute-force odds,
therefore it should not be used for security-related applications.

[thomasahle]

Fully agree. Are there any kinds of seed-indpendent "patterns" you would be more worried about?