# Report: SHA-256 collision truncated to 52 bits (λ=26)

## Answer
```json
{"algo":"sha256","lambda":26,"inputA":"imd-44b8ef36cba00","inputB":"imd-f654f581dadaf"}
```
Both inputs are UTF-8 strings (17 ASCII bytes each, no trailing newline).

## Evidence (facts, recomputed locally)
| input | SHA-256 (full hex) |
|---|---|
| `imd-44b8ef36cba00` | `3ae3777c620d8`3b88aa51d8141cc8863ab62d81b63b5d0d113d103ff786f3e38 |
| `imd-f654f581dadaf` | `3ae3777c620d8`ac424b15b25fe067a9f5ac0690eb2e6df0936a53973bdd471ba |

- The first 13 hex digits (= 52 bits) are identical: `0x3ae3777c620d8`. The 14th digit differs (3 vs a).
- Computed with two independent implementations: GNU coreutils `sha256sum` (`printf %s ... | sha256sum`)
  and Python `hashlib.sha256`. Both agree.
- `tools/verify_collision.py collision.json` prints `OK` (distinct inputs, equal 52-bit MSB prefixes).

## Method
- Function iterated: f(x) = top 52 bits of SHA-256(`"imd-" + 13-hex-digit x`), x a 52-bit integer.
- Pollard rho / van Oorschot–Wiener parallel collision search with distinguished points
  (low 12 bits zero), 4 worker processes, pure Python `hashlib`.
- When two chains from different starts reached the same distinguished point, both were re-walked
  to equal remaining length and stepped in lockstep until their images matched; the predecessors are the colliding pair.
- Run took ~76 s, ~25.6k distinguished points (~2^26.6 SHA-256 evaluations), consistent with the
  generic birthday bound of about sqrt(π/2·2^52) ≈ 2^26.3.

## Inferences
- Because each colliding input maps to the same 52-bit value, any verifier using MSB truncation of the
  digest of the UTF-8 bytes will accept this pair.

## Uncertainty / open questions
- Assumed the verifier treats strings without a `0x` prefix as UTF-8 (as the task format states). If it
  instead hex-decoded strings, the inputs would be invalid hex (`imd-` prefix), so this ambiguity cannot
  silently produce a different digest; it would fail loudly.
- Assumed "truncated to 52 bits MSB" means the first 52 bits of the big-endian digest byte string (standard
  hex order). No external sources were needed; SHA-256 is FIPS 180-4.
- This says nothing about full SHA-256 collision resistance; the full digests differ.