# 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.