# Report: keccak256 collision truncated to 48 bits (λ=24)

## Answer

```json
{"algo":"keccak256","lambda":24,"inputA":"0x00000000007004e7","inputB":"0x00000000016de6f6"}
```

| Input (8 raw bytes, hex) | keccak256 digest |
|---|---|
| `0x00000000007004e7` | `02649afb324c`833597b7b240aee29067ae1ed85092e64569eeaaf3cadd56861f |
| `0x00000000016de6f6` | `02649afb324c`9eef48aff7d4de0563498952e8c85a9f706c8eb25a2c4661eff4 |

The first 48 bits (`0x02649afb324c`) are identical. The inputs are distinct, and the
digests differ from byte 7 onward, so this is a real truncated collision and not
the same input written twice.

## Facts (observed directly in this run)

1. **The implementation was checked against known vectors.** `tools/keccak_collide.c selftest`
   produced keccak256("") = `c5d24601…5d85a470` and keccak256("abc") = `4e03657a…a12d6c45`.
   These are the standard Ethereum Keccak-256 vectors. With 0x06 padding, the same sponge
   reproduced Python `hashlib.sha3_256` exactly for "" and "abc". That confirms the
   permutation and rate (136 bytes) are correct.
2. **The search found 9 collisions.** It hashed the 2^26 inputs `0x0000000000000000`
   through `0x0000000003ffffff` (8-byte big-endian counters), sorted the 48-bit
   prefixes and found 9 colliding pairs. Wall time was 11.7 s on 32 cores. All 9 pairs
   are listed in the program output; the first one by prefix order was chosen.
3. **A separate library confirmed the chosen pair.** The npm package `js-sha3`
   v0.9.3 (`keccak256`), written independently of this code, gave the same full digests
   for both inputs. It also gave the correct digest for keccak256("").

## Inference

- The expected number of collisions among N = 2^26 random 48-bit values is about
  N²/2^49 = 8. Finding 9 is consistent with keccak256 behaving like a random function
  on this truncation. That fits the stated birthday cost of about 2^24 evaluations
  for a 48-bit output.

## Uncertainty and open questions

- **Which "keccak256" does the verifier use?** I assume the Ethereum/original-Keccak
  padding (0x01). If the SIMD verifier uses FIPS-202 SHA3-256 instead, this pair is
  not a collision. I could not check this, because the verifier's source was not
  available to me.
- **How does the verifier parse inputs?** I assume `0x…` strings are decoded as raw
  bytes, as the task format suggests ("hex 0x... or utf8"). If they were hashed as
  UTF-8 text instead, the pair would not collide.
- No external web sources were needed. Every claim above comes from computation
  that can be reproduced with `tools/keccak_collide.c`.

## Reproduction

```
gcc -O3 -fopenmp -o kc tools/keccak_collide.c
./kc selftest
./kc search 26          # lists all 9 collisions
./kc hash 0x00000000007004e7
./kc hash 0x00000000016de6f6
```