# SHA-256 truncated to 50 bits: collision report (λ = 25)

## Question

Find two distinct inputs whose SHA-256 digests agree in the first 50 bits
(most significant bit first). Deliver them as `collision.json`.

## Answer

```json
{"algo": "sha256", "lambda": 25, "inputA": "imd-266c7c8969b0e", "inputB": "imd-0545841f91fe3"}
```

Both inputs are plain UTF-8 strings (17 ASCII bytes each, no `0x` prefix, no
trailing newline).

## Evidence (facts, recomputed locally)

| input (UTF-8) | SHA-256 (hex) |
|---|---|
| `imd-266c7c8969b0e` | `be81b9da56ef4c030f47c516229ca204accc285f9bcb47db2221075e43897ae1` |
| `imd-0545841f91fe3` | `be81b9da56ef639f0d1165b3630463c62dcbaee005a399d9fd694e342cbd43bc` |

- The first 12 hex digits (48 bits) are the same: `be81b9da56ef`.
- The 13th hex digit is `4` = `0100` and `6` = `0110`. Their top two bits, `01`,
  match, which brings the shared prefix to 50 bits. The 52nd bit is where the
  digests first differ.
- The shared 50-bit prefix is
  `10111110100000011011100111011010010101101110111101` (hex `0x2fa06e7695bbd`).
- I checked this two ways: with Python 3.12.3 `hashlib.sha256`, and with GNU
  coreutils `sha256sum` (`printf %s imd-266c7c8969b0e | sha256sum`). Both gave
  the same digests. You can repeat either check yourself, and the SIMD verifier
  will recompute it anyway.

## Method

- The script is `tools/find_collision.py`, written in pure Python with no
  third-party packages.
- It runs a parallel collision search using distinguished points (van Oorschot
  & Wiener, "Parallel Collision Search with Cryptanalytic Applications",
  J. Cryptology 12(1), 1999).
- The iteration function is f(x) = top 50 bits of SHA-256(`"imd-"` + 13-digit
  hex of x).
- A point counts as distinguished when its low 12 bits are zero.
- When two chains reach the same distinguished point, the script walks both
  chains again to find where they merge. This gives two distinct preimages with
  the same f value.
- The run took about 11 s of wall time on 4 cores and stored 7,698
  distinguished points before the collision. With an average chain of about
  4,096 steps, that is roughly 3×10⁷ ≈ 2^25 SHA-256 evaluations. This matches
  the expected birthday cost of about √(π/2 · 2^50) ≈ 1.25 · 2^25.

## Inferences and uncertainty

- **Inference:** the evaluation count is estimated from the number of chains
  times the expected chain length. It was not counted directly.
- **Assumption:** the verifier treats strings without a `0x` prefix as UTF-8,
  as the task statement says. The `imd-` prefix was added on purpose so that
  neither input can be mistaken for hex.
- **Not a weakness of SHA-256:** this is a generic birthday-bound collision on
  a 50-bit truncation. It says nothing about the security of full SHA-256.

## Unanswered questions

- None for this task. The random starting points come from `os.urandom`, so
  running the script again will find a different collision.