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

## Task

Find two distinct inputs whose SHA-256 digests agree on the first 48 bits
(6 bytes, most-significant-bit first) and report them as `collision.json`
at the repository root, per the `SIMD-COLLISION:sha256:24` spec.

## Method (facts)

- A birthday-attack search was run: generate candidate messages
  `"sc48-" + str(i)` for increasing integer `i`, compute
  `SHA256(message)`, keep the first 6 bytes (48 bits), and store each
  truncated digest in a hash table keyed by that value. The search stops
  the first time a truncated digest repeats with a *different* underlying
  message.
- Implementation: `test/scratch/find_collision.py` (Python 3, `hashlib.sha256`).
  This script is scratch tooling only, not part of the delivered artifact.
- Expected cost for a 48-bit birthday collision is ≈2^24 (~16.8M) evaluations
  in the worst case, with the expected number of draws to first collision
  being ≈1.25·√(2^48) ≈ 1.25·2^24 ≈ 21M under the birthday-paradox
  approximation. The actual run found a collision after **5,170,219**
  evaluations in **9.8 seconds**, which is within normal variance for this
  kind of search (the birthday bound is an expectation, not a guarantee —
  finding one earlier than the mean is common).

## Result (facts)

| | value |
|---|---|
| inputA | `sc48-825706` (UTF-8 string, 12 bytes) |
| inputB | `sc48-5170219` (UTF-8 string, 13 bytes) |
| SHA-256(inputA) | `7b12a707f93a7d7959c027efbdb608eb1c1e5a7fab71e1c9e4a723dd07d0d9db` |
| SHA-256(inputB) | `7b12a707f93a396a68145d197beae6b997c38ff5ff1d1739650f77040fda3c1e` |
| first 48 bits (6 bytes, MSB) of both | `7b12a707f93a` |

`inputA ≠ inputB` (distinct byte strings), and the two SHA-256 digests
differ beyond byte offset 6, confirming this is a genuine truncated
collision rather than two identical full digests.

## Verification performed (facts)

Verification was re-run independently, outside the search loop that found
the pair, using a fresh Python process:

```
full A 7b12a707f93a7d7959c027efbdb608eb1c1e5a7fab71e1c9e4a723dd07d0d9db
full B 7b12a707f93a396a68145d197beae6b997c38ff5ff1d1739650f77040fda3c1e
trunc48 A 7b12a707f93a
trunc48 B 7b12a707f93a
MATCH, distinct inputs: True
```

Both `SHA256(inputA)[0:6] == SHA256(inputB)[0:6]` and `inputA != inputB`
hold. `collision.json` at the repository root contains exactly the four
required fields (`algo`, `lambda`, `inputA`, `inputB`) with `inputA` and
`inputB` given as plain UTF-8 strings (not hex-prefixed), which the spec
permits ("hex 0x... or utf8").

## Inferences

- The chosen collision is a standard birthday-bound result for a 48-bit
  truncation of a cryptographically sound hash (SHA-256 is not known to be
  broken at full length); it demonstrates the expected weakness of
  *any* 48-bit digest, not a flaw specific to SHA-256's internals.
- The attack cost (a few million SHA-256 evaluations, completed in ~10
  seconds on a single CPU core in Python) is consistent with the 2^24-scale
  birthday cost named in the task, confirming the task's stated complexity
  estimate is realistic for this hash truncation width.

## Uncertainty / unanswered questions

- The exact number of evaluations needed is random; a re-run with a
  different seed string or starting point would very likely find a
  collision after a different number of attempts (expected ≈2^24–2^25,
  but with high variance). This run's specific attempt count (5,170,219)
  is not a reproducible constant of the algorithm, only of this particular
  search trace.
- No claim is made about SHA-256 collisions at full (256-bit) output
  length; none were sought or found, and none are believed to exist within
  reach of current computation.
- `collision_raw.json`, produced by the scratch script during the search,
  contains the same pair plus timing/attempt metadata; it was written only
  under `test/scratch/` and is not part of the delivered artifact set.