# SHA-256 truncated to 48 bits (λ=24): collision found

## Answer

`collision.json`:

```json
{"algo":"sha256","lambda":24,"inputA":"imd-28353144","inputB":"imd-31301013"}
```

Both inputs are plain UTF-8 strings with no trailing newline.

| Input | SHA-256 (full) |
|---|---|
| `imd-28353144` | `10c5146afb50`8a551db97b94ad4ace33198747ed22924a9889e13af51a932af5 |
| `imd-31301013` | `10c5146afb50`4c837e87d402435da1572c2ace50f3cbe36f332c75c575c70950 |

The two hashes share the first 48 bits (12 hex digits): `10c5146afb50`. They differ starting at bit 49 (`8a` vs `4c`), so this is a truncated-prefix collision and not a full SHA-256 collision.

## Evidence (facts: recomputed locally)

1. **Search:** `tools/find_collision.c` contains its own SHA-256 implementation, written from FIPS 180-4 (https://csrc.nist.gov/pubs/fips/180-4/upd1/final). It hashed `imd-0` … `imd-33554431` (2^25 inputs) and stored each 48-bit prefix. It then sorted the prefixes and looked for adjacent equal values. Built with `gcc -O2`, it ran in about 27 s on 2 cores and used about 256 MB.
2. **Independent check 1:** Python `hashlib.sha256` produced the digests in the table above.
3. **Independent check 2:** GNU coreutils `sha256sum` (run as `printf 'imd-28353144' | sha256sum`) produced the same digests.
4. **Script check:** `python3 tools/verify_collision.py collision.json` checks the JSON keys, that the inputs are distinct, and that the 48-bit MSB prefixes are equal. It printed `OK: 48-bit prefix 10c5146afb50 shared`.

All three hash implementations agree, so the collision does not come from a bug in the custom C code.

## Inferences

- **Cost:** for N random inputs, the expected number of colliding pairs is about N²/2^(49). With N = 2^25 that is about 2, so about 2^25 evaluations were needed. This matches the "about 2^24" estimate in the task, give or take a small constant factor.
- **Input format:** "truncated to 48 bits MSB" means the first 6 bytes of the big-endian digest. That is how both the searcher and the verifier read it.

## Uncertainty / open questions

- I don't have the external "SIMD" verifier's exact input-decoding rules. I avoided the problem by using plain ASCII strings that don't start with `0x`, so they can only be read as UTF-8. If the verifier added a newline or other framing to the inputs, the digests would change. Nothing in the task suggests it does that.
- Only the first collision found was reported. The search did not count or list any others.