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

## Answer

```json
{"algo":"sha256","lambda":24,"inputA":"imd-12192837","inputB":"imd-19093962"}
```

Both inputs are UTF-8 strings (no `0x` prefix). The same file is at `collision.json` (repo root) and
`artifacts/collision.json`.

## Evidence (facts, reproduced locally)

| Input (UTF-8)   | SHA-256 (full)                                                     |
|-----------------|--------------------------------------------------------------------|
| `imd-12192837`  | `c94563ba4883`4c66186fe07f1f2233f777eed615e843ce03144ade7e659074d9 |
| `imd-19093962`  | `c94563ba4883`0d17ce781584012f36b6502808166df0a05236829c7c1c062211 |

- The first 48 bits (6 bytes, 12 hex digits, most significant first) are `c94563ba4883` for both.
- The inputs are distinct, and the full digests differ after byte 6, so this is a prefix collision
  and not a full SHA-256 collision.
- The digests were computed three separate ways and all agree: Python `hashlib` (`scripts/verify_collision.py`),
  GNU coreutils `sha256sum`, and `openssl dgst -sha256`. Inputs were hashed as raw bytes with no trailing newline.

Reproduce:

```sh
python3 scripts/verify_collision.py collision.json
printf '%s' imd-12192837 | sha256sum
printf '%s' imd-19093962 | sha256sum
```

## Method

`scripts/find_collision.py` runs a plain birthday search. It hashes `imd-0`, `imd-1`, … and stores each
6-byte digest prefix in a dictionary until a prefix repeats. The first repeat came at message index
19,093,962 (about 2^24.19 evaluations), matching index 12,192,837. The run took about 66 s on one CPU core
and used a few GB of RAM.

## Inference

- The expected birthday cost for a 48-bit output is about √(π/2 · 2^48) ≈ 1.25 · 2^24 ≈ 21M evaluations.
  We needed 19.1M, which fits that estimate and the task's "about 2^24" figure.
- Nothing here weakens full SHA-256. A 48-bit truncation only gives 24-bit collision resistance,
  as the generic birthday bound predicts.

## Uncertainty and open questions

- **Truncation convention.** We assume "first 48 bits, MSB" means the first 6 bytes of the standard
  big-endian digest output. If the verifier truncates some other way (for example, the low-order bits),
  this pair would not count. That is unlikely given the wording, but not confirmed.
- **Input encoding.** We assume strings without `0x` are read as UTF-8 bytes, as the task format says.
  The inputs are pure ASCII, so this also holds under Latin-1 or ASCII decoding.
- **Not tested.** We did not run the external "SIMD" verifier. Our checks are local recomputations
  and have no independent authority.

## Sources

- FIPS 180-4, *Secure Hash Standard* (defines SHA-256): https://csrc.nist.gov/pubs/fips/180-4/upd1/final
  (cited for the algorithm definition; the evidence above is computational, not taken from the document).