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 #1127
Labels
No labels
announcement
bug
build
CI
dependencies
documentation
duplicate
enhancement
experience feedback
feature request
github_actions
help wanted
install
invalid
Long-term
optimization
portability
question
target-specific
test issue
wontfix
No milestone
No assignees
1 participant
Notifications
Due date
No due date set.
Dependencies
No dependencies set
Reference
gh-Cyan4973/xxHash#1127
Loading…
Reference in a new issue
No description provided.
Delete branch "%!s()"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
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 about2^-27, and
XXH3_128bits_withSeed(m1) == XXH3_128bits_withSeed(m2)(both halves) also withprobability about 2^-27. The same holds for
XXH3_64bits_withSecret/XXH3_128bits_withSecretwith 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:
first (
w1 == ~w0), remaining bytes arbitrary;~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
devbranch head (c0b5ea995d, 2026-07-27), whose XXH3 arithmetic is unchanged relative to v0.8.3.Threat model
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_withSecretdocumentation). 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
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,
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 <= 240the 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 == ~w0norcomplementing 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: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 inone fold. Both output halves are functions of
(acc.low64, acc.high64), so they collidetogether — in the measurements below the low-only and high-only counts always equal the
full-collision count.
The comment block above
XXH3_mix16Balready documents seed-dependent multicollisions caused bya 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-bytesecret (
withSecret). A collision is counted only if the full output is equal (both halves forthe 128-bit variants). Pair A is the pair described above; B and C are controls:
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=1for v0.8.3,rng_seed=2for 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_seedgives identical counts, as expected for identical bytes; that table is omitted.)The last three lines of each table exercise
XXH3_mul128_fold64alone 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
xxhash0.8.3 header) —./xxh3_collide 30 all 0 1dev branch (
c0b5ea995d, 2026-07-27, still reports XXH_VERSION 0.8.3) —./xxh3_collide 30 all 0 2Two remarks on the numbers:
withSecretvariants 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.
withSeedvariants 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 near2^-27 in all 24 seeded cells across the two streams. Pairs of type C (unrelated
w1) underXXH3_64bits_withSeedranged from 0 to 91 collisions per 2^30 across the twelve cells; the128-byte pair that gave 91 (
rng_seed=1), re-measured against two fresh seed streams(
./xxh3_collide 30 seed64 128 2 1and... 3 1), gave 97 and 109, i.e. about 2^-23.3 forthat 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_seed2..5) gave 1–4 collisions apiecefor both seeded variants, consistent with the rates above.
Reproduction
Self-contained C program (build with
cc -O2 xxh3_collide.c -o xxh3_collidewithxxhash.hnextto it;
./xxh3_collide 30prints the whole table for one header,./xxh3_collide 26 seed64 32runs one 32-byte cell at 2^26 trials in a few seconds):
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
mix16Bwould alter hash values).Two questions for the maintainers:
scope for XXH3, given the existing disclaimer about seed-dependent multicollisions?
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.
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.
Thank you, and agreed on the framing: this is not a cryptographic claim. The setting I care about is the one the
withSeed/withSecretdocumentation 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 theXXH3_mix16B()comment sounds right to me.Two updates since the report, in case they change what you want to write there:
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):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.
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.
updated documentation, mentioning this study and its results.
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_mix16Bcomment 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 throughXXH3_64bits_withSecretandSeedand the streamingreset_withSecretandSeed+digest, since inputs of at most 240 bytes usekSecretand the seed there.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 whenfold(A, B) = fold(~A, ~B)for that block. Choosingw0andw1from the non-adjacent form ofK2 + K3 + 1makes the two carry masks agree for most seeds, andfold(A, ~A)is symmetric. The witness seed makes the multiplicands0and~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)withLin 8-byte words this puts the seeded interface at 12.5 bits, where the 128-byte pair gave 23.0.Random secret (
XXH3_64bits_withSecretwith 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 pair0^24vsff^8 0^16, independent verifier written from scratch against the public API). That capswithSecretat 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-64directory of https://github.com/thomasahle/hash-collision-witnesses carries both checks (./check 20samples the default-secret pair;./check random-secret 20samples the 24-byte pair throughXXH3_64bits_withSecretwith 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
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.
Fully agree. Are there any kinds of seed-indpendent "patterns" you would be more worried about?