# SHA-256 48-bit Truncated Collision (λ=24)

## Question

Find two distinct inputs `inputA` and `inputB` such that `SHA-256(inputA)` and
`SHA-256(inputB)`, each truncated to the first 48 bits (6 bytes, MSB-first),
are identical. The birthday bound for a 48-bit output space is about
`sqrt(2^48) = 2^24 ≈ 16.7M` evaluations in expectation.

## Method (facts, attributable to this run)

- Implementation: `test/scratch/collision_search.py` (Python 3.12.3, stdlib `hashlib`).
- Approach: classic birthday/meet-in-the-middle search. Candidate messages are
  built from a random 8-byte session prefix (from `secrets.token_bytes(8)`)
  concatenated with an 8-byte big-endian counter. For each candidate, compute
  `SHA-256(message)` and keep only the first 6 bytes (48 bits, MSB-first) as a
  lookup key in an in-memory hash table. The first key collision between two
  distinct messages is reported.
- This directly matches the task's definition of the target: "sha256
  truncated to the first 48 bits."

## Result

- Collision found after **4,667,153** candidate evaluations, in **6.72 s**
  wall-clock on this machine — consistent with (same order of magnitude as)
  the expected ~2^24 ≈ 16.7M birthday bound; exact counts vary run to run
  since this is a probabilistic search.
- `inputA` = `0x0af4d22dc07cc3210000000000005b11`
- `inputB` = `0x0af4d22dc07cc3210000000000473711`
- `SHA-256(inputA)` = `45039b5bef1e42c86170b7ae5d03de6598eb7e22727adc41ef6fa12171825ca0`
- `SHA-256(inputB)` = `45039b5bef1e03c049536447dcf166dbd44aca8a78a04654994a251f9053daae`
- Both digests share the same first 6 bytes (48 bits): **`45039b5bef1e`**.
- `inputA != inputB` (verified: they differ in the trailing 8-byte counter
  portion, byte-for-byte distinct).

## Independent verification performed

In addition to the search script's own in-process check, the result was
recomputed in a **separate** Python process/invocation, decoding the hex
strings fresh with `binascii.unhexlify` and recomputing
`hashlib.sha256(...).hexdigest()` for both inputs, then comparing the first
12 hex characters (48 bits) of each digest. Output:

```
A input bytes: 0af4d22dc07cc3210000000000005b11
B input bytes: 0af4d22dc07cc3210000000000473711
A != B: True
digest A: 45039b5bef1e42c86170b7ae5d03de6598eb7e22727adc41ef6fa12171825ca0
digest B: 45039b5bef1e03c049536447dcf166dbd44aca8a78a04654994a251f9053daae
trunc48 A: 45039b5bef1e
trunc48 B: 45039b5bef1e
MATCH: True
```

This confirms the collision is not an artifact of the search script's own
bookkeeping.

## Deliverable

`collision.json` at the repository root contains exactly the required shape:

```json
{"algo":"sha256","lambda":24,"inputA":"0x0af4d22dc07cc3210000000000005b11","inputB":"0x0af4d22dc07cc3210000000000473711"}
```

## Inference and uncertainty

- The number of evaluations to find a collision (4.67M) is a single sample
  from a random process; it is lower than the mean birthday-bound estimate
  (~16.7M) but well within the expected statistical spread for this kind of
  search (the distribution of first-collision time is heavy-tailed, and
  getting a hit well before the mean is unsurprising — not evidence of a
  weakness in SHA-256 or an error in the search).
- No claim is made about collisions in full (untruncated) SHA-256 — only the
  48-bit MSB truncation specified by the task, which is a much weaker target
  by construction.
- "λ=24" in the task statement is a search-cost exponent (≈2^24 expected
  evaluations), not the truncation length itself; the truncation length is
  48 bits (6 bytes). This distinction mattered during implementation: an
  initial draft of the search script conflated the two and truncated to 24
  bits instead of 48, which produced a cheap but invalid "collision" (only a
  24-bit prefix match, not a 48-bit one). That bug was caught by the
  independent verification step above before producing the final
  `collision.json`, and the search was re-run with the corrected 48-bit
  (6-byte) truncation to produce the result reported here.

## Unanswered / out of scope

- No attempt was made to find a collision faster than brute-force birthday
  search (e.g. via parallelism or SIMD), since the plain search completed in
  under 7 seconds on standard hardware — well within the task's assumed
  cost budget.