keccak256 truncated-48-bit collision (λ = 24)

Answer

	inputA	inputB
Input (UTF-8, no trailing newline)	idmd-1974572	idmd-18504430
Input hex	0x69646d642d31393734353732	0x69646d642d3138353034343330
keccak256	892154b3269003f016f7918156408c79d15e0e8c5ac0a3b517ea0221f4a4e340	892154b32690b9e1abdd0ddd29547c464e32738f56cdadceb66de3d32c49a271
First 48 bits (6 bytes, MSB first)	892154b32690	892154b32690

The inputs are different, and the first 48 bits of their digests are the same (892154b32690). After byte 6 the digests differ (03f0… vs b9e1…), so this collision is only on the truncated digest. The full digests do not collide.

Deliverable: collision.json (repository root, with an identical copy in artifacts/collision.json):

{"algo":"keccak256","lambda":24,"inputA":"idmd-1974572","inputB":"idmd-18504430"}

Evidence (facts, reproduced locally on 2026-10-05)

1. Hash definition. "keccak256" here means the original Keccak[r=1088, c=512] with the Keccak padding byte 0x01, as used by Ethereum. It is not FIPS-202 SHA3-256, which uses the domain byte 0x06. Node's built-in sha3-256 is the FIPS-202 version, so I wrote my own implementation (artifacts/keccak.js).
2. Implementation check. artifacts/keccak.js gives the published keccak256 values for these inputs:
   • "" → c5d24601…5d85a470
   • "abc" → 4e03657a…a12d6c45
   • "hello world" → 47173285…4cb01fad
3. Independent cross-check. I hashed both colliding inputs with two third-party libraries: js-sha3 0.13.0 (keccak256) and @noble/hashes 2.4.0 (keccak_256). I installed them in /tmp and did not commit them. Both libraries gave exactly the digests in the table above.
4. Search. artifacts/find_collision.js hashes "idmd-" + n for n = 0, 1, 2, … and stores each 48-bit prefix in an open-addressing hash table with 2^26 slots, built from typed arrays. It stops at the first repeated prefix. Run: node --max-old-space-size=4096 artifacts/find_collision.js. Result: the collision appeared after 18,504,431 evaluations (about 2^24.14), taking about 300 s on one Node 24 thread.

Inferences

• Expected cost. By the birthday bound, the expected number of evaluations before the first collision in a 48-bit space is about √(π/2 · 2^48) ≈ 1.25 · 2^24 ≈ 21.0 M. The observed 18.5 M is consistent with that and with the "about 2^24" figure in the task.
• No structural weakness used. This is a plain generic birthday search. It says nothing about the collision resistance of the full 256-bit keccak256.

Uncertainty / open questions

• How the verifier reads the inputs (hex vs. UTF-8). The task says inputs may be "hex 0x... or utf8". Neither input starts with 0x, and both contain non-hex characters (i, m, -), so the only sensible reading is UTF-8 bytes. I am assuming the verifier hashes the raw UTF-8 bytes and adds no newline or other framing; the task does not state this.
• Which keccak256 the verifier uses. I assume "keccak256" means Keccak with 0x01 padding (Ethereum), not SHA3-256. If the verifier actually used SHA3-256, this pair would almost certainly not collide. I did not test that case.
• External verification. The SIMD verifier has not been run here. The evidence above is my own recomputation plus two independent libraries; it is not independent certification.