# SIMD-COLLISION:keccak256:24 — 48-bit truncated keccak256 collision

## Result

A collision for keccak256 truncated to the first 48 bits (lambda = 24)
was found by birthday search. Delivered in `collision.json`:

| Field | Value |
|---|---|
| inputA | `imd-c24-00000000007712cc` (UTF-8) |
| inputB | `imd-c24-0000000001bc5f42` (UTF-8) |
| keccak256(inputA) | `181e3ab6fb1c8ee22d110fd530ea726c3136b7ed2c277eff3c9ae3ce8b4b93c7` |
| keccak256(inputB) | `181e3ab6fb1ca2fe107ffeac1ffdcaa34339c24e9ebb0fa47964e809636c743c` |
| truncated 48-bit MSB | `181e3ab6fb1c` (identical for both) |

The inputs are distinct ASCII strings; digests were computed over the raw
UTF-8 bytes with no length prefix or encoding wrapper.

## Method and evidence

- **Search**: single-shot keccak256 (Keccak-f[1600], rate 136 bytes,
  `pad10*1` domain byte `0x01` — original Keccak, not SHA3's `0x06`)
  over counter strings `imd-c24-%016x`, implemented in C
  (`tools/find_collision.c`, self-contained, no external deps).
- **Collision detection**: open-addressed table of 2^26 slots indexed by
  the low 26 bits of the 48-bit prefix; on a candidate tag match the full
  48-bit prefix is recomputed and compared byte-for-byte, eliminating
  false positives from probing displacement.
- **Work performed**: 29,122,371 evaluations (~1.74 x 2^24), consistent
  with the expected birthday cost of ~2^24 for a 48-bit target.
- **Correctness of the hash**: the C implementation reproduces the
  published keccak256 test vectors `keccak256("")` =
  `c5d2460186f7...5d85a470` and `keccak256("abc")` =
  `4e03657aea45...2d6c45`.
- **Independent verification**: the reported pair was re-checked with
  PyCryptodome `Crypto.Hash.keccak` (digest_bits=256), which reproduced
  both digests above and confirmed `dA[:6] == dB[:6]`. PyCryptodome's
  `keccak` was itself validated against the same test vectors, so the
  C code and the reference library agree on Keccak (0x01) padding.

## Facts / inferences / uncertainty

- **Fact**: `keccak256(inputA)[0:6] == keccak256(inputB)[0:6] ==
  181e3ab6fb1c`, confirmed by two independent implementations.
- **Fact**: inputA and inputB are distinct byte strings.
- **Inference**: "keccak256" is taken to mean original Keccak-256
  (Ethereum-style, domain byte `0x01`), not NIST SHA3-256 (`0x06`);
  this matches the task's literal spelling and standard tooling naming.
- **Uncertainty**: if the verifier were to use SHA3-256 instead, the
  pair would not collide — but the task names `keccak256` explicitly.
- **Unanswered**: none material to acceptance; verification is
  recomputed by the harness.

## Reproducing the check

```python
from Crypto.Hash import keccak
def k256(b):
    k = keccak.new(digest_bits=256); k.update(b); return k.digest()
A = b"imd-c24-00000000007712cc"
B = b"imd-c24-0000000001bc5f42"
assert A != B and k256(A)[:6] == k256(B)[:6]
```

Search tool: `tools/find_collision.c` — `gcc -O2 -o find_collision
tools/find_collision.c && ./find_collision` (single-threaded, <1 GB RAM,
deterministic counter domain; the same pair is found on every run).