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

## Answer
A collision exists in keccak256 truncated to its first 48 bits (most significant bits of the 32-byte digest), and was found:

- inputA = `0x00000000009f3c16` (counter n = 10435606, encoded as 8-byte big-endian)
- inputB = `0x0000000000a445ea` (counter n = 10765802, encoded as 8-byte big-endian)
- keccak256(inputA) = `2c705490d17082cd79ae8d94c5190aeab8f9b699ea41122d627c9a513dd74130`
- keccak256(inputB) = `2c705490d170a4f31bde3c1884a8195e8313d5e814b5f8a489ab59e5bb3888d2`
- Both truncate to `2c705490d170` (48 bits). The inputs are distinct.

The deliverable is `collision.json` at the repository root:
`{"algo": "keccak256", "lambda": 24, "inputA": "0x00000000009f3c16", "inputB": "0x0000000000a445ea"}`

## Method
1. `tools/keccak256.h`: a dependency-free C Keccak-256 with original Keccak padding (0x01), not the SHA3-256 padding (0x06). Its output on the empty string and on `"abc"` matches the standard Keccak-256 vectors:
   - `""` → `c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470`
   - `"abc"` → `4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45`
2. `tools/find_collision.c`: a birthday search. It hashes the counters n = 0, 1, 2, … as 8-byte big-endian inputs and stores each counter in an open-addressing table keyed by its 48-bit prefix. The first prefix match yields the pair. The table has 2^26 slots of 4 bytes each (256 MiB).
3. `test/scratch/verify.py`: an independent pure-Python Keccak-f[1600] implementation. It reproduces the empty-string vector, recomputes both digests, and checks the truncated equality and distinctness before writing `collision.json`.

## Evidence (facts, from runs in this session)
- The C search ran in about 19 s wall-clock (14 s user) on one core and returned the pair above at counter 10765802 (the larger counter).
- The Python implementation independently gives the same full digests and the same 48-bit prefix `2c705490d170`.
- The first Python run failed its own known-answer test because of a transcription error in my round constants. I fixed it and reran. The C result did not depend on that file.

## Inferences
- The search is a valid collision search: the table stores only counters, and a match is confirmed by recomputing the prefix of the stored counter, so the reported pair is not a hash-table artifact. The independent Python check is what establishes this.
- The number of evaluations, about 1.08·10^7, is consistent with the stated birthday cost of about 2^24. For a 48-bit output, the expected number of samples for a 50% collision chance is about sqrt(2·ln2·2^48) ≈ 1.97·10^7 ≈ 2^24.2. A single run that stops at 1.08·10^7 is within normal variance. This is one sample, so it says nothing about the distribution of run lengths.

## Uncertainty and limits
- The verifier recomputes with SIMD, and I did not check its Keccak implementation. My two independent implementations agree with each other and with the empty-string and "abc" vectors. Those vectors are the only external checks. I did not re-fetch the Keccak specification or FIPS 202 during this task, so the padding claim rests on my knowledge of the spec, not a fresh source.
- The truncation convention is taken from the task: the first 48 bits, most significant first, of the 32-byte digest. Other conventions (for example, the last 48 bits, or the 48 bits of the hex string) would not match this pair.
- The input encoding (8-byte big-endian counter) is my choice. The task accepts either hex or UTF-8 input.

## Unanswered questions
- Whether the SIMD verifier uses the same Keccak-256 variant (original padding, not SHA3-256). If it used SHA3-256 the pair would not verify. The pair is only for the variant described here.