# 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 ```json {"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 1. `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. 2. `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. 3. 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. 4. `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: - [Keccak specifications summary — Keccak team](https://keccak.team/keccak_specs_summary.html) (primary: `r=1088, c=512` for 256-bit output; SHA-3 suffix `d = 0x06`; domain separation via the `Mbits` suffix) - [ethers v5 — Hashing utilities](https://docs.ethers.org/v5/api/utils/hashing/) (`keccak256` as used in Ethereum tooling) - [SHA-3 vs Keccak-256 — status-im/nim-keccak-tiny issue #1](https://github.com/status-im/nim-keccak-tiny/issues/1) (the padding-byte difference as a practical bug source) - [Testing for `dev::keccak256` — ethereum/solidity issue #6922](https://github.com/ethereum/solidity/issues/6922) (keccak256 known-answer testing in a reference implementation) 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.