# Report: 48-bit truncated keccak256 collision (λ=24)

## Answer
```json
{"algo":"keccak256","lambda":24,"inputA":"idmd-258423","inputB":"idmd-22623167"}
```
Both inputs are interpreted as UTF-8 strings. They are distinct and have the same length.

| input | keccak256 (full, hex) |
|---|---|
| `idmd-258423`   | `89c78021a005`4152c21bf154b1c783892cbefe3e7cddfb6ce7aed8b483c49c06 |
| `idmd-22623167` | `89c78021a005`0bbb1a5d12b4a1d1b5ab83d5f0c6769efa11d8f4f0436942e6bf |

The first 48 bits (`0x89c78021a005`) are identical, and the full digests differ.

## Evidence (facts: observed by running code on 2026-10-05)
1. **Search.** `tools/keccak_collide.c` computed the 48-bit prefixes of keccak256(`idmd-i`) for i = 0 … 39,999,999 and sorted them. It took about 67 s on one core. It found 4 colliding pairs:
   - `idmd-258423` / `idmd-22623167` → `89c78021a005` (the one submitted)
   - `idmd-1974572` / `idmd-18504430` → `892154b32690`
   - `idmd-21945148` / `idmd-23692412` → `3708d128f249`
   - `idmd-23643708` / `idmd-30340703` → `126e44b1a074`
2. **Implementation self-test.** The C implementation returns keccak256("") = `c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470`. This is the well-known Ethereum empty-input hash.
3. **Independent verification with three separate implementations.** All three gave identical full digests for the submitted pair and for the pair `idmd-1974572` / `idmd-18504430`:
   - `tools/verify_collision.py`: a separately written pure-Python Keccak-f[1600] that derives the round constants and rotation offsets from the LFSR and the (x,y) recurrence instead of using hard-coded tables. It also checks the JSON schema, that the inputs differ, and that the prefixes are equal. Output: `OK prefix 89c78021a005`.
   - npm `js-sha3` 0.13.0, `keccak_256`.
   - npm `@noble/hashes` 2.4.0, `sha3.js` `keccak_256`.
   All three also agree on the vectors "" and "abc" (`4e03657a…2d6c45`).

## Inferences
- Expected number of collisions among N = 4·10⁷ random 48-bit values is N²/2^49 ≈ 2.8. Observing 4 fits the birthday bound. The generic cost is about 2^24 evaluations, as the task states.
- The task's verifier ("SIMD") is assumed to use Ethereum Keccak padding (0x01), because the task says "keccak256" and not "sha3-256". Under SHA3-256 (0x06 padding) these inputs would **not** collide.

## Uncertainty / unanswered questions
- I could not see the verifier. Two assumptions are untested against it: (a) that it decodes non-`0x` strings as UTF-8 bytes, and (b) that "first 48 bits MSB" means the first 6 bytes of the digest in standard big-endian hex order. Both inputs are plain ASCII, so encoding is not ambiguous.
- No external citations are used. All claims are reproducible by running the included tools. Test vectors were cross-checked against two published libraries rather than a specification document.

## Reproduce
```
gcc -O3 -o k tools/keccak_collide.c && ./k test && ./k      # ~1 min, ~640 MB RAM
python3 tools/verify_collision.py collision.json
```