Truncated keccak256 collision (λ=24, 48-bit prefix)
Task. [SIMD-COLLISION:keccak256:24] — find two distinct messages whose keccak256
digests are identical in the first 48 bits (MSB-first), and deliver them as
collision.json.
Status: answered. A collision was found, written to collision.json, and
independently re-verified by three implementations other than the one that found it.
Date of work: 2026-10-05. Host: Apple M4, arm64, Darwin 24.3.0, Apple clang 17.0.0.
1. The answer
{"algo":"keccak256","lambda":24,"inputA":"0x8375360100000000","inputB":"0x7131040200000000"}
| value |
|---|
inputA (8 bytes) | 0x8375360100000000 |
inputB (8 bytes) | 0x7131040200000000 |
keccak256(inputA) | 8851a59bbb9d·6231d46ab9566296d3aed4afb5cd4212a1f68a094142b0366868 |
keccak256(inputB) | 8851a59bbb9d·27a12c8340ba34a0ac8820e6315e00542945f74d66f4ef53a9b1 |
| shared first 48 bits | 8851a59bbb9d = 100010000101000110100101100110111011101110011101 |
| first differing byte | byte 6 (0x62 vs 0x27) |
collision.json is 93 bytes, sha256 03ffa2ad732db7f0d3f754b3086be4cd534ecaa4907dca6c4d4ba5091b771cd6,
and contains exactly the four required keys and nothing else.
The two messages are the 8-byte little-endian encodings of the counters
20,346,243 and 33,829,233. They are distinct as byte strings, which is the property the
rules require.
2. Facts (directly observed, reproducible)
F1 — The collision holds. Four independent keccak256 implementations produce the two
digests above, agreeing on all 256 bits of each digest:
| implementation | provenance | result |
|---|
src/keccak.h (C, this repo) | written for this task; permutation constants per FIPS 202 / Keccak reference | 8851a59bbb9d6231… / 8851a59bbb9d27a1… |
tools/verify_collision.py (pure Python, this repo) | written separately from the C code, no shared code path | identical |
pycryptodome 3.23.0 Crypto.Hash.keccak | third-party C library, installed | identical |
pysha3 (sha3.keccak_256) | third-party binding over the Keccak Code Package reference code | identical |
Verifier output (make verify):
inputA bytes = 8375360100000000 digest = 8851a59bbb9d6231d46ab9566296d3aed4afb5cd4212a1f68a094142b0366868
inputB bytes = 7131040200000000 digest = 8851a59bbb9d27a12c8340ba34a0ac8820e6315e00542945f74d66f4ef53a9b1
first 48 bits (lambda=24): A=100010000101000110100101100110111011101110011101 (8851a59bbb9d)
first 48 bits (lambda=24): B=100010000101000110100101100110111011101110011101 (8851a59bbb9d)
[ok] pycryptodome cross-check (8851a59bbb9d... / 8851a59bbb9d...)
VERIFIED: distinct inputs, identical first 48 bits of keccak256
F2 — Both local implementations pass published known-answer tests. Each reproduces the
widely published keccak256 vectors, including the empty string
c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470 (the Ethereum EOA
codehash constant) and keccak256("abc") = 4e03657aea45a94f…. These vectors were
hard-coded before the digests were computed, not copied from the implementations' own
output, and they also match pycryptodome and pysha3. Run via make selftest and the
verifier's _self_kat().
The multi-block path (messages longer than the 136-byte rate) was checked separately:
keccak256('a'*200) = 96ea54061def936c4be90b518992fdc6f12f535068a256229aca54267b4d084d
under all four implementations. The delivered messages are 8 bytes and use the
single-block path, so this is defence in depth rather than a load-bearing check.
F3 — The search cost matches the birthday prediction. The search evaluated
33,829,233 messages (≈2^25.0) in 15.1 s single-threaded before the first 48-bit repeat.
The expected count for a 48-bit target is √(π/2·2^48) ≈ 2.1·10^7 (≈2^24.3), with the
median near 1.9·10^7; 3.4·10^7 is ≈1.6× the mean, which is an unremarkable draw from the
birthday distribution (P(no collision after 3.4·10^7) ≈ exp(−(3.4·10^7)²/2^49) ≈ 0.13).
This is evidence the hash output behaves as expected and that no shortcut or error
inflated the result.
F4 — The result is deterministic. No randomness, no threading, counters walked from 1.
A second full run produced a byte-identical collision.json (diff clean). Anyone with
the repo can re-derive the same pair with make search.
F5 — keccak256 ≠ SHA3-256 for this pair. Under NIST SHA3-256 the same two inputs hash
to be9557c38cf08b7b… and 45a1116d3edd3852… — no shared prefix. The two functions
differ only in the padding/domain-separation suffix (0x01 for original Keccak vs 0x06
for SHA-3); the Keccak team's own specification summary lists SHA3-256 as r=1088, c=512
with d = 0x06, while the original Keccak submission uses plain multi-rate padding.
F6 — The verifier rejects bad claims. Negative tests (in test/scratch/, not
delivered): identical inputs → FAIL: inputs are identical; a non-colliding pair →
FAIL: truncated digests differ; "algo":"sha256" → FAIL: algo is not keccak256; an
extra JSON key → FAIL: unexpected key set. Only the real claim exits 0. So the
"VERIFIED" line in F1 is not a function that always says yes.
3. Inferences (supported, not directly observed)
I1 — keccak256 in this task means the Ethereum/original-Keccak variant, not FIPS 202
SHA3-256. The name keccak256 is used in the blockchain ecosystem specifically for the
0x01-padded original Keccak; the Ethereum Yellow Paper specifies KECCAK-256 "as per the
winning entry to the SHA-3 contest" rather than FIPS 202, and libraries expose the two
under distinct names (keccak_256 vs sha3_256). The delivered pair is built on that
reading. Confidence: high, but see U1.
I2 — λ=24 denotes the birthday exponent, and the truncation width is 48 bits. The task
states "truncated to the first 48 bits (λ=24)" and "birthday cost is about 2^24", so 48 =
2λ. The verifier computes bits = 2 · lambda. This reading is self-consistent with the
stated cost. Note the claim is robust either way: a 48-bit prefix match necessarily
implies a 24-bit prefix match, so a checker that truncated to 24 bits would also pass.
I3 — Hex input form is unambiguous. inputA/inputB are given as 0x-prefixed hex
of 8 bytes each, which the task explicitly permits. Both strings are even-length hex, so
a verifier decoding 0x… as bytes gets exactly the messages used here. Had the bytes been
delivered as UTF-8 they would not be printable, so hex was the only safe choice.
4. Uncertainty and residual risk
U1 — Which keccak variant the grading verifier uses. If SIMD recomputes with FIPS 202
SHA3-256 while calling it keccak256, this claim fails (F5). We cannot inspect the
verifier, so this is unresolved by observation and rests on I1. Mitigating a mismatch is
not practical: a pair colliding under both functions at 48 bits costs ≈2^48 work, roughly
16 million times this search, rather than 2^24.
- Not mitigated. If this is the failure mode, rerunning
make search with the padding
byte changed from 0x01 to 0x06 in src/keccak.h produces a SHA3-256 pair in ~15 s.
U2 — Truncation convention. "First 48 bits MSB" is read as the first 6 digest bytes in
standard big-endian digest order (the order every library prints). If a verifier instead
truncated a little-endian or word-reversed rendering of the digest, the comparison would
differ. Treated as settled by the phrase "truncated to 48 bits MSB", but not independently
confirmed against the verifier.
U3 — Correctness of the implementations is argued, not proved. F1/F2 show four
implementations agreeing and matching published vectors; that is strong evidence, not a
proof. The strongest single piece of evidence is that two of the four
(pycryptodome, pysha3) are widely deployed third-party libraries with no connection to
code written here.
U4 — Published test vectors were not fetched from a primary KAT file. The vectors in F2
were written from prior knowledge and then corroborated by third-party libraries and by a
web search confirming the empty-string constant. The corroboration is real, but no
byte-level diff against the Keccak team's ShortMsgKAT files was performed.
5. Unanswered questions
- Q1: Does SIMD's verifier use original-Keccak padding or FIPS 202? (drives U1)
- Q2: Does it accept
0x-prefixed hex of arbitrary length, and does it treat an input
without a 0x prefix as UTF-8? Only the hex path is exercised here.
- Q3: Is any constraint imposed on message length or on the inputs being the same length?
Both messages here are 8 bytes, which satisfies the strictest plausible reading.
- Q4: Is λ=24 ever intended as 24 bits rather than 48? Unresolved, but harmless (I2).
6. Method
src/keccak.h implements Keccak-f[1600] (24 rounds; θ, ρ, π, χ, ι with the FIPS 202
round constants, rotation offsets and lane permutation) plus a keccak256 sponge at
rate 136 bytes with 0x01 … 0x80 multi-rate padding.src/collide.c enumerates messages LE64(ctr) for ctr = 1, 2, 3, …. Because a message
is fully determined by its counter, the birthday table stores only counters: a 2^26-slot
open-addressed uint32 table (256 MiB), indexed by a mix of the 48-bit prefix. A
non-empty slot triggers a recomputation of the stored counter's digest and an exact
48-bit comparison, so hash-index aliasing can never produce a false collision —
wrong guesses just linear-probe onward. A fast path XORs the 8-byte message, the 0x01
pad and the 0x80 terminator straight into the state and runs one permutation.- Before writing output the finder re-hashes both messages through the generic
(multi-block, arbitrary-length) code path and re-checks that the first 6 bytes match and
that the messages differ; it exits non-zero otherwise.
tools/verify_collision.py re-verifies the file from scratch with its own pure-Python
Keccak, and additionally cross-checks against pycryptodome when installed.
Reproduce: make selftest && make search && make verify.
7. Sources
Technical facts about the keccak256/SHA3-256 distinction:
Everything in §1–§4 other than the keccak-variant background is first-hand output of the
commands in §6, run on the host named above. Web pages were read as data.