# Report: keccak256 collision truncated to 48 bits (λ=24)

## Answer
- inputA (UTF-8): `imd-9804673`
- inputB (UTF-8): `imd-17368822`

| input | keccak256 (full digest) |
|---|---|
| `imd-9804673`  | `2f72fe059bc2`493e489ac23cd5bb0119eee739455c6ba49cfd31f75a2b7be703 |
| `imd-17368822` | `2f72fe059bc2`f734345293e1223f429e97aea53934f75f186ac1c57ca5f1d550 |

Shared first 48 bits: `0x2f72fe059bc2`. The inputs are distinct byte strings, and the digests differ
from bit 49 onward. Neither input starts with `0x`, so both are read as UTF-8.

## Facts (checked locally)
1. Algorithm: original Keccak-256 with domain padding byte `0x01`, as Ethereum uses. This is not
   FIPS-202 SHA3-256, which pads with `0x06`. My implementation reproduced the known vectors
   keccak256("") = `c5d24601…5d85a470` and keccak256("abc") = `4e03657a…a12d6c45`, and gave a
   different result from Node's built-in `sha3-256` on the empty string.
2. Search: birthday search over the messages `imd-1`, `imd-2`, … I stored indices in an
   open-addressing table with 2^25 slots, keyed on digest bits. When a slot matched, I recomputed
   the stored message's digest and compared its first 6 bytes in full. The first collision came at
   n = 17,368,822, about 2^24.05 evaluations. That fits the expected value of about
   sqrt(pi/2 * 2^48) ≈ 2^24.3. Wall time was about 2 min 24 s in single-threaded Node v24.21.0.
3. Independent recheck: the npm package `js-sha3@0.9.3` (`keccak256`, a separate implementation)
   gave the exact digests in the table above for both inputs.

## Inferences
- The SIMD verifier should accept the pair, as long as it hashes the UTF-8 bytes of the strings and
  uses Keccak-256 (0x01 padding), not SHA3-256. The task says "keccak256", and the inputs do not use
  the `0x` hex prefix, so this reading is the most likely one.

## Uncertainty / unanswered
- I could not inspect the verifier itself. If it used SHA3-256 instead, these inputs would not
  collide. I consider this unlikely given the algorithm name.
- The search script was scratch work and is not part of the submission. The result can be
  reproduced from the table above with any keccak256 implementation.