# SIMD-COLLISION:sha256:24 — 48-bit truncated SHA-256 collision

## Task

Find two distinct inputs `inputA` and `inputB` such that `SHA-256(inputA)` and
`SHA-256(inputB)`, each truncated to the first 48 bits (most-significant 6
bytes of the 32-byte digest), are identical. Birthday-bound cost for a 48-bit
output space is ≈ 2^24 evaluations.

## Method (facts, directly observed)

- Implemented a straightforward birthday search in Python
  (`hashlib.sha256`): generate inputs of the form
  `b"imd-collision-" + struct.pack(">Q", i)` for increasing integer `i`,
  compute the full SHA-256 digest, truncate to the first 6 bytes (48 bits,
  MSB-first), and store `truncated_digest -> input` in a hash table.
- On each new input, check the table for an existing entry with the same
  48-bit prefix but a different underlying message. The first such match is
  the collision.
- Script: `test/scratch/find_collision.py` (scratch workspace; not part of
  the delivered output, kept for attributability/reproducibility of the
  method only).

## Result (facts, reproducible)

- Collision found after **33,000,439** candidate evaluations, in **90.8
  seconds** on a single CPU core (Python, no parallelism).
- This is within normal statistical variance of the ≈2^24 (≈16.8M)
  birthday-bound expectation — the realized distribution of collision times
  has a long tail, and factor-of-2 deviations are common for a single trial.
- `inputA` = `0x696d642d636f6c6c6973696f6e2d00000000002fa789`
  (ASCII prefix `"imd-collision-"` + 8-byte big-endian counter `0x2fa789` = 3,110,281)
- `inputB` = `0x696d642d636f6c6c6973696f6e2d0000000001f78bf6`
  (same ASCII prefix + counter `0x1f78bf6` = 33,096,694)
- Full digests:
  - `SHA-256(inputA)` = `f63922e7c69a7ce7b54ff132fdd176e6e05371898e5d5eb7734ff94aa19cd480`
  - `SHA-256(inputB)` = `f63922e7c69a0bb06f5550f8086cad4053da47ea4f677001017d209b3ac1113b`
- First 48 bits (6 bytes, MSB) of both digests: `f63922e7c69a` — **identical**.
- `inputA ≠ inputB` (different counter values, confirmed by direct byte
  comparison).

## Independent re-verification (fact)

After generating `collision.json`, the file was re-read from disk in a fresh
Python process (separate from the search script) and independently
recomputed:

```
full digestA: f63922e7c69a7ce7b54ff132fdd176e6e05371898e5d5eb7734ff94aa19cd480
full digestB: f63922e7c69a0bb06f5550f8086cad4053da47ea4f677001017d209b3ac1113b
first 48 bits A: f63922e7c69a
first 48 bits B: f63922e7c69a
MATCH (48-bit MSB truncation): True
```

This confirms the delivered `collision.json` satisfies the stated
acceptance rule (distinct inputs, matching 48-bit MSB truncated digests)
using only the standard library `hashlib` SHA-256 implementation — the same
algorithm family any SIMD-based verifier would be checking against.

## Deliverable

`collision.json` (repository root):

```json
{"algo":"sha256","lambda":24,"inputA":"0x696d642d636f6c6c6973696f6e2d00000000002fa789","inputB":"0x696d642d636f6c6c6973696f6e2d0000000001f78bf6"}
```

## Inferences

- The chosen input format (ASCII tag + big-endian 64-bit counter, hex-encoded
  with `0x` prefix) was an arbitrary but convenient way to enumerate a large,
  distinct search space; nothing about the collision depends on this
  specific encoding beyond producing two distinct byte strings.
- A brute-force birthday search (no SIMD/GPU acceleration) was sufficient to
  find the collision in under two minutes, which is consistent with the
  problem's stated 2^24 birthday cost being tractable on commodity hardware.

## Uncertainty / unanswered questions

- No cryptographic property of full SHA-256 is implicated here: this is a
  collision only in the 48-bit truncation, as required by the task, not in
  the full 256-bit digest (the full digests above are, as expected,
  completely different beyond the shared 6-byte prefix).
- The exact iteration count (33M vs. the ~16.8M expectation) is a single
  empirical trial and should not be read as evidence of any weakness or
  strength in SHA-256's truncated output; birthday collision times have high
  variance.
- Not independently checked: behavior of the actual grading/SIMD verifier
  implementation (its own SHA-256 and truncation logic were not available to
  inspect) — verification above used Python's standard `hashlib`, which is a
  conformant, independently-implemented SHA-256.