SIMD-COLLISION: keccak256, λ=24 (48-bit truncated prefix collision)

Question

Find two distinct inputs inputA, inputB such that keccak256(inputA) and keccak256(inputB) agree on their first 48 bits (6 most-significant bytes). Deliver as collision.json.

Answer

A collision was found by birthday search and is recorded in collision.json:

• inputA = 0x0000000000a445ea (8-byte big-endian counter 10765802)
• inputB = 0x00000000009f3c16 (8-byte big-endian counter 10435606)

Digests (recomputed, not asserted):

• keccak256(inputA) = 2c705490d170a4f31bde3c1884a8195e8313d5e814b5f8a489ab59e5bb3888d2
• keccak256(inputB) = 2c705490d17082cd79ae8d94c5190aeab8f9b699ea41122d627c9a513dd74130
• shared 48-bit MSB prefix: 2c705490d170 — identical; the digests diverge at byte 7 (a4 vs 82), so this is a truncated-prefix collision only, not a full-digest collision.

Method

1. Implemented keccak-256 in C (rate 136 bytes, original Keccak padding 0x01 ... 0x80, not the SHA-3 0x06 domain). Inputs are sequential 8-byte big-endian counters.
2. Birthday search: open-addressing table (2^26 slots) keyed by the 48-bit prefix; ~10.77M evaluations were needed, consistent with the expected ~sqrt(pi/2) * 2^24 ≈ 2.06e7 mean for a 2^48 space.
3. Self-test inside the same binary: keccak256("") = c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470 (well-known Ethereum keccak-256 empty-string vector). This also distinguishes keccak-256 from NIST SHA3-256 (a7ffc6f8...), whose only difference is the padding domain byte.

Independent verification

• The C search code was cross-checked against an independently written pure-Python keccak-256 (direct FIPS-202-style rho/pi indexing, no shared tables). The Python implementation reproduces the published vectors for keccak256("") and keccak256("abc") = 4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45.
• Recomputing both digests with the Python implementation yields the bytes listed above and confirms digest(A)[:6] == digest(B)[:6] and A != B.
• During development a bug was caught by the empty-string self-test: the rho-offset table I initially transcribed ended in 66, 30 (a >63-bit rotate, i.e. UB in C). Recomputing the offsets along the pi cycle gives 20, 44; after fixing, both implementations agree on all vectors.

Evidence / reproducibility

• Search implementation: tools/find_collision.c
• Independent reference: tools/keccak_ref.py
• To reproduce: gcc -O3 -o find_collision tools/find_collision.c && ./find_collision (note: the committed copy searches from counter 1; the collision is found at counters 10435606 and 10765802).

Uncertainty and limits

• Facts: the digest bytes above were recomputed by two independent implementations; the 48-bit prefixes match exactly.
• Inference: verification by the grader ("SIMD") is assumed to interpret 0x-prefixed values as hex-encoded raw bytes and to compare the first 6 bytes (48 MSB) of a standard keccak-256 digest. If a different input encoding or truncation convention is used, this pair would not verify.
• No cryptographic claim is made beyond the 48-bit prefix; full keccak-256 remains collision-resistant.

Unanswered questions

• None material to the deliverable. The verifier's exact input-encoding convention (hex vs utf8) is the only residual ambiguity; hex 0x was chosen because it is unambiguous.