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

## Answer

```json
{"algo":"keccak256","lambda":24,"inputA":"imd-9804673","inputB":"imd-17368822"}
```

Both inputs are UTF-8/ASCII strings (they have no `0x` prefix).

| Input | keccak256 digest |
|---|---|
| `imd-9804673`  | `2f72fe059bc2`493e489ac23cd5bb0119eee739455c6ba49cfd31f75a2b7be703 |
| `imd-17368822` | `2f72fe059bc2`f734345293e1223f429e97aea53934f75f186ac1c57ca5f1d550 |

The shared 48-bit prefix is `0x2f72fe059bc2`. The inputs are distinct.

## Facts (observed and reproducible)

1. `tools/collide.c` hashed the strings `imd-0`, `imd-1`, … and stored each 48-bit prefix in a hash table. The first repeated prefix appeared after **17,368,823 evaluations** (≈2^24.05). The run took about 21 seconds on a single core.
2. The C implementation reproduces the standard keccak256 test vectors. `keccak256("")` gives `c5d24601…5d85a470`, and `keccak256("abc")` gives `4e03657a…a12d6c45`. Its self-test passes before the search starts.
3. `tools/verify.py` is a second, independently written pure-Python Keccak. It derives the round constants and rotation offsets from the specification's LFSR and recurrence instead of copying tables. It passes the same two vectors and recomputes both digests above. Its output is `COLLISION OK` with exit code 0.
4. For contrast, `hashlib.sha3_256(b"imd-9804673")` gives `e4d8b7ee…`. So FIPS-202 SHA3-256 is a different function, and this pair is **not** claimed to collide under it.

## Inferences

- The evaluation count fits the birthday bound. For a 48-bit output, the expected number of draws before the first collision is about √(π/2 · 2^48) ≈ 2.1·10^7, and 1.74·10^7 is well within the normal spread. This fits keccak256's prefix behaving like a random function. It is not evidence of any structural weakness.
- Two independent implementations agree, and both match the known vectors. So the collision is very likely to hold under any correct keccak256 implementation, including the SIMD verifier.

## Uncertainty and open questions

- **Which function the verifier uses:** I assumed "keccak256" means Ethereum-style Keccak-256 (padding byte 0x01). If the verifier uses SHA3-256 (padding 0x06), this pair would fail. I did not search for a SHA3-256 collision.
- **How inputs are decoded:** I assumed strings without `0x` are hashed as their UTF-8 bytes, as the task format suggests. Plain ASCII was chosen to avoid any encoding ambiguity.
- **Library cross-check:** No external library (pycryptodome, eth-hash) was installed, so neither check uses one. Both checks are code written for this task, anchored only to the published test vectors.

## Sources

- Keccak team, *The Keccak reference*, v3.0 (https://keccak.team/files/Keccak-reference-3.0.pdf). Source for the Keccak-f[1600] round function, the round-constant LFSR, and the ρ offsets.
- NIST FIPS 202 (https://doi.org/10.6028/NIST.FIPS.202). Defines the SHA3-256 domain-separation padding (0x06) that distinguishes it from Keccak-256.
- The test vectors for `""` and `"abc"` are the widely published Ethereum keccak256 values, for example Ethereum's empty-code hash `0xc5d2…a470`. They are hard-coded in both tools.