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

## Answer

A collision on Keccak-256 truncated to its first 48 bits (MSB) was found:

| | input (hex) | keccak256 digest | first 48 bits |
|---|---|---|---|
| inputA | `0x8375360100000000` | prefix `8851a59bbb9d` (full 256-bit digest not printed by the search) | `8851a59bbb9d` |
| inputB | `0x7131040200000000` | prefix `8851a59bbb9d` (full 256-bit digest not printed by the search) | `8851a59bbb9d` |

Both inputs are 8-byte messages, distinct, and their digests agree on the first 6 bytes.

Deliverable: `collision.json` at the repository root:

```json
{"algo":"keccak256","lambda":24,"inputA":"0x8375360100000000","inputB":"0x7131040200000000"}
```

## Method (facts)

- Hash: Keccak-256 with original Keccak padding (`0x01`), rate 136 bytes, as used by Ethereum. Not NIST SHA3-256 (which uses `0x06`).
- Search: birthday attack. Inputs were the 8-byte little-endian encoding of a counter `i = 0, 1, 2, …`. Each digest's 48-bit prefix was stored in an open-addressing hash table (2^26 slots). The first prefix repeat between two different counters was taken as the collision.
- Implementation: `test/scratch/keccak_birthday.c`, compiled with `gcc -O3 -march=native`. Single thread.
- Result: collision after **33,829,234** evaluations (counters 0 through 33,829,233), 1 min 4 s wall time.
- The program recomputed both digests from the inputs and checked that the inputs differ and that their 48-bit prefixes match before reporting.

## Verification

- **Implementation check (fact):** the Keccak-256 routine reproduces the published test vectors:
  - `keccak256("")` = `c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470` (matches)
  - `keccak256("abc")` = `4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45` (matches)
- **Pair check (fact):** the program's output shows both digests with prefix `8851a59bbb9d`; the inputs are distinct.
- **Not done:** an independent second Keccak implementation. pycryptodome could not be installed (no `pip`), and OpenSSL 3.0.13 here has no Keccak digest. The pair was therefore checked only by the same code that found it, plus the published vectors. The SIMD verifier that recomputes the digests is the independent check the task names; I have not seen its result.

## Inferences and uncertainty

- The 2^24 birthday estimate matched the observed cost: a collision is expected after about √(π/2 · 2^48) ≈ 2.1·10^7 evaluations, and 3.4·10^7 is within the usual variance for a single run.
- Whether the SIMD verifier uses the same padding and byte order (8-byte little-endian input, MSB-first truncation) is an assumption. If it hashes the hex as ASCII, or uses NIST SHA3-256, this pair will not verify. The task specifies `keccak256` and a hex `0x…` input, which I read as raw bytes.
- The collision is a 48-bit truncation collision only. It says nothing about full 256-bit collision resistance, which is untouched.

## Unanswered

- Whether the external verifier accepts this pair under its exact input-decoding rule (raw bytes vs. ASCII of the hex string). I did not test that rule against the verifier.

## Sources

- Keccak test vectors above are the standard published Keccak-256 values, checked here against the implementation. No web sources were consulted; the padding and rate choices are from the Keccak specification and the Ethereum Keccak-256 convention.