# Report: 48-bit truncated Keccak-256 collision (λ = 24)

## Answer

`collision.json` (repository root):

```json
{"algo":"keccak256","lambda":24,"inputA":"identitymd-7412922","inputB":"identitymd-49446283"}
```

Both inputs are plain UTF-8/ASCII strings with no `0x` prefix, so they are read as UTF-8.

| Input | Keccak-256 digest |
|---|---|
| `identitymd-7412922`  | `06f8602cde14`eaa97a7264115761fc9eebb12fcd6cb8080f1dd6134b7de84bc4 |
| `identitymd-49446283` | `06f8602cde14`d101876298776c73b65f60c20eb683748c28de306acd36858d84 |

The first 48 bits (6 bytes, MSB first) are `0x06f8602cde14` for both inputs. The inputs are different, and the full digests are different at byte 7 and after.

## Facts (checked in this session)

1. **Hash function.** The hash is Keccak-256 with the original Keccak padding (domain byte `0x01`, then `0x80` at the end of the 136-byte block). This is the variant Ethereum calls `keccak256`. Two implementations reproduce the known test vectors:
   - `keccak256("")` = `c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470`
   - `keccak256("abc")` = `4e03657aea45a94fc7d47ba826c8d667c0d1e6e33a64a036ec44f58fa12d6c45`
2. **Search.** `tools/keccak256_birthday.c` (C, `gcc -O3`) hashed the 2^26 strings `identitymd-0` … `identitymd-67108863`. It stored each 48-bit prefix and sorted them to find duplicates. It finished in about 2 min 25 s on 4 cores (single-threaded) and found 5 colliding pairs. The first pair is the one submitted. The other four were:
   - `identitymd-51640271` / `identitymd-53212469` → `22d143cd1c0f`
   - `identitymd-32089584` / `identitymd-46380380` → `4bbe9d21a877`
   - `identitymd-33320706` / `identitymd-47021571` → `7a2e7927bfa1`
   - `identitymd-920291` / `identitymd-13453043` → `82e59b2eea88`
3. **Independent check.** `tools/verify_collision.py` is a separate pure-Python Keccak-f[1600] implementation. It computes the round constants with the FIPS 202 LFSR and the rotation offsets with the spec's recurrence, rather than using hard-coded tables. It checks the test vectors above, then loads `collision.json`, checks its keys and values, decodes both inputs, and confirms that the inputs differ and the 48-bit prefixes match. Output: `48-bit prefixes equal: True`.

## Inferences

- About 5 collisions is what the birthday bound predicts: with n = 2^26 samples in a space of 2^48, the expected number of pairs is n²/2^49 = 2^52/2^49 = 8. Five is a normal result. Only about 2^24 samples are needed for an even chance, so the run used more than it needed but stayed cheap.
- The C and Python code share no source, and they agree on both test vectors and on both full digests. That makes an implementation error unlikely to be the cause of the match.

## Uncertainty / open questions

- **Which "keccak256" the verifier uses.** I assumed Ethereum-style Keccak-256 (`0x01` padding), because that is what the name usually means. If the verifier actually uses NIST **SHA3-256** (`0x06` padding), this pair does **not** collide. SHA3-256 gives `c4630a5e…` and `d7490bb6…`. Re-running the search with that padding would take about 2 minutes.
- **How "truncated to 48 bits MSB" is read.** I took it as the first 6 bytes of the standard big-endian digest output. Other readings, such as the low bits or a little-endian word, were not tested.
- **Input encoding.** I assumed that a string without a `0x` prefix is hashed as its UTF-8 bytes, with no trailing newline.

## Sources

- FIPS 202, SHA-3 Standard (Keccak-f permutation, round-constant LFSR, rotation offsets): https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
- Keccak team reference / the original Keccak padding (`pad10*1` with no SHA-3 domain bits): https://keccak.team/keccak_specs_summary.html
- The test vectors above are the widely published Ethereum `keccak256` values. Both local implementations reproduced them, but I did not fetch them from the web in this session.

## Reproduce

```sh
gcc -O3 -o kb tools/keccak256_birthday.c && ./kb test && ./kb   # ~2.5 min
python3 tools/verify_collision.py collision.json
```