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

## Answer

| | inputA | inputB |
|---|---|---|
| Input (UTF-8, no trailing newline) | `idmd-1974572` | `idmd-18504430` |
| Input hex | `0x69646d642d31393734353732` | `0x69646d642d3138353034343330` |
| keccak256 | `892154b3269003f016f7918156408c79d15e0e8c5ac0a3b517ea0221f4a4e340` | `892154b32690b9e1abdd0ddd29547c464e32738f56cdadceb66de3d32c49a271` |
| First 48 bits (6 bytes, MSB first) | **`892154b32690`** | **`892154b32690`** |

The inputs are different, and the first 48 bits of their digests are the same (`892154b32690`). After byte 6 the digests differ (`03f0…` vs `b9e1…`), so this collision is only on the truncated digest. The full digests do not collide.

Deliverable: `collision.json` (repository root, with an identical copy in `artifacts/collision.json`):

```json
{"algo":"keccak256","lambda":24,"inputA":"idmd-1974572","inputB":"idmd-18504430"}
```

## Evidence (facts, reproduced locally on 2026-10-05)

1. **Hash definition.** "keccak256" here means the original Keccak[r=1088, c=512] with the Keccak padding byte `0x01`, as used by Ethereum. It is not FIPS-202 SHA3-256, which uses the domain byte `0x06`. Node's built-in `sha3-256` is the FIPS-202 version, so I wrote my own implementation (`artifacts/keccak.js`).
2. **Implementation check.** `artifacts/keccak.js` gives the published keccak256 values for these inputs:
   - `""` → `c5d24601…5d85a470`
   - `"abc"` → `4e03657a…a12d6c45`
   - `"hello world"` → `47173285…4cb01fad`
3. **Independent cross-check.** I hashed both colliding inputs with two third-party libraries: `js-sha3` 0.13.0 (`keccak256`) and `@noble/hashes` 2.4.0 (`keccak_256`). I installed them in `/tmp` and did not commit them. Both libraries gave exactly the digests in the table above.
4. **Search.** `artifacts/find_collision.js` hashes `"idmd-" + n` for n = 0, 1, 2, … and stores each 48-bit prefix in an open-addressing hash table with 2^26 slots, built from typed arrays. It stops at the first repeated prefix. Run: `node --max-old-space-size=4096 artifacts/find_collision.js`. Result: the collision appeared after **18,504,431 evaluations** (about 2^24.14), taking about 300 s on one Node 24 thread.

## Inferences

- **Expected cost.** By the birthday bound, the expected number of evaluations before the first collision in a 48-bit space is about √(π/2 · 2^48) ≈ 1.25 · 2^24 ≈ 21.0 M. The observed 18.5 M is consistent with that and with the "about 2^24" figure in the task.
- **No structural weakness used.** This is a plain generic birthday search. It says nothing about the collision resistance of the full 256-bit keccak256.

## Uncertainty / open questions

- **How the verifier reads the inputs (hex vs. UTF-8).** The task says inputs may be "hex 0x... or utf8". Neither input starts with `0x`, and both contain non-hex characters (`i`, `m`, `-`), so the only sensible reading is UTF-8 bytes. I am assuming the verifier hashes the raw UTF-8 bytes and adds no newline or other framing; the task does not state this.
- **Which keccak256 the verifier uses.** I assume "keccak256" means Keccak with `0x01` padding (Ethereum), not SHA3-256. If the verifier actually used SHA3-256, this pair would almost certainly not collide. I did not test that case.
- **External verification.** The SIMD verifier has not been run here. The evidence above is my own recomputation plus two independent libraries; it is not independent certification.