keccak256 48-bit truncated collision (λ = 24)

Answer

A collision exists in keccak256 truncated to its first 48 bits (most significant bits of the 32-byte digest), and was found:

• inputA = 0x00000000009f3c16 (counter n = 10435606, encoded as 8-byte big-endian)
• inputB = 0x0000000000a445ea (counter n = 10765802, encoded as 8-byte big-endian)
• keccak256(inputA) = 2c705490d17082cd79ae8d94c5190aeab8f9b699ea41122d627c9a513dd74130
• keccak256(inputB) = 2c705490d170a4f31bde3c1884a8195e8313d5e814b5f8a489ab59e5bb3888d2
• Both truncate to 2c705490d170 (48 bits). The inputs are distinct.

The deliverable is collision.json at the repository root: {"algo": "keccak256", "lambda": 24, "inputA": "0x00000000009f3c16", "inputB": "0x0000000000a445ea"}

Method

1. tools/keccak256.h: a dependency-free C Keccak-256 with original Keccak padding (0x01), not the SHA3-256 padding (0x06). Its output on the empty string and on "abc" matches the standard Keccak-256 vectors:
   • "" → c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
   • "abc" → 4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45
2. tools/find_collision.c: a birthday search. It hashes the counters n = 0, 1, 2, … as 8-byte big-endian inputs and stores each counter in an open-addressing table keyed by its 48-bit prefix. The first prefix match yields the pair. The table has 2^26 slots of 4 bytes each (256 MiB).
3. test/scratch/verify.py: an independent pure-Python Keccak-f[1600] implementation. It reproduces the empty-string vector, recomputes both digests, and checks the truncated equality and distinctness before writing collision.json.

Evidence (facts, from runs in this session)

• The C search ran in about 19 s wall-clock (14 s user) on one core and returned the pair above at counter 10765802 (the larger counter).
• The Python implementation independently gives the same full digests and the same 48-bit prefix 2c705490d170.
• The first Python run failed its own known-answer test because of a transcription error in my round constants. I fixed it and reran. The C result did not depend on that file.

Inferences

• The search is a valid collision search: the table stores only counters, and a match is confirmed by recomputing the prefix of the stored counter, so the reported pair is not a hash-table artifact. The independent Python check is what establishes this.
• The number of evaluations, about 1.08·10^7, is consistent with the stated birthday cost of about 2^24. For a 48-bit output, the expected number of samples for a 50% collision chance is about sqrt(2·ln2·2^48) ≈ 1.97·10^7 ≈ 2^24.2. A single run that stops at 1.08·10^7 is within normal variance. This is one sample, so it says nothing about the distribution of run lengths.

Uncertainty and limits

• The verifier recomputes with SIMD, and I did not check its Keccak implementation. My two independent implementations agree with each other and with the empty-string and "abc" vectors. Those vectors are the only external checks. I did not re-fetch the Keccak specification or FIPS 202 during this task, so the padding claim rests on my knowledge of the spec, not a fresh source.
• The truncation convention is taken from the task: the first 48 bits, most significant first, of the 32-byte digest. Other conventions (for example, the last 48 bits, or the 48 bits of the hex string) would not match this pair.
• The input encoding (8-byte big-endian counter) is my choice. The task accepts either hex or UTF-8 input.

Unanswered questions

• Whether the SIMD verifier uses the same Keccak-256 variant (original padding, not SHA3-256). If it used SHA3-256 the pair would not verify. The pair is only for the variant described here.