# Keccak-256 collision on the first 48 bits

## Result

The two distinct byte strings in [`collision.json`](../collision.json) have the
same first six bytes of their Keccak-256 digests, as recomputed locally by
[`tools/verify.py`](../tools/verify.py). The requested parameter is λ = 24,
corresponding to a 48-bit prefix.

| Field | Value |
| --- | --- |
| inputA (hex bytes) | `0x8375360100000000` |
| inputB (hex bytes) | `0x7131040200000000` |
| Full digest A | `8851a59bbb9d6231d46ab9566296d3aed4afb5cd4212a1f68a094142b0366868` |
| Full digest B | `8851a59bbb9d27a12c8340ba34a0ac8820e6315e00542945f74d66f4ef53a9b1` |
| Common 48-bit MSB prefix | `8851a59bbb9d` |

The `0x` notation specifies hex-decoded input bytes, not the UTF-8 characters of
the hexadecimal strings. Each input is eight bytes long. The full digests differ.

## Method and attributable evidence

The deterministic C search in [`tools/search.c`](../tools/search.c) enumerated
positive integers encoded as eight little-endian bytes. A hash table retained
the first six digest bytes and the input that produced each prefix. It found the
pair after **33,829,233 evaluations**, with **533 seconds** elapsed as measured
by the search process. The captured progress output is in
[`search.log`](search.log).

The search uses Keccak-f[1600] with 24 rounds, a 1088-bit rate, 512-bit capacity,
and original Keccak padding (delimited suffix `0x01`). The primary technical
reference is the [Keccak team's specification summary](https://keccak.team/keccak_specs_summary.html),
which gives the permutation, sponge construction, round constants, rotations,
and suffix formula. The requested original Keccak-256 uses no added domain bits;
SHA3-256 instead uses suffix `0x06` and is a different hash function.

The separate Python verifier uses a coordinate-based permutation and generates
round constants with an LFSR; it does not call the C search. It passed fixed
known-answer checks for empty input and `abc`, then checked the JSON's exact
field set, algorithm, integer lambda, distinct decoded inputs, and equal six-byte
prefixes. Five sample inputs also produced matching C and Python prefixes during
a local cross-check. The final verification output is retained in
[`verification.json`](verification.json). Reproduce it offline with:

```sh
python3 tools/verify.py
```

## Facts, inference, and limits

**Observed locally:** the exact inputs, full digests, matching prefix, evaluation
count, elapsed time, and passing checks above. These are attributable to the
included implementations and captured outputs, not to an external reviewer.

**Conclusion from those checks:** the delivered pair satisfies the requested
48-bit truncated Keccak-256 collision condition. It does not demonstrate a
collision of the full 256-bit hash.

**Unverified externally:** no SIMD verifier or independent reviewer was available
in this session. Local checks carry no independent authority; final SIMD
acceptance remains unobserved. Verification requires only Python 3's standard
library and no network or files under `test/scratch/`.