# SIMD-COLLISION:sha256:24 — truncated SHA-256 collision (48 bits)

**Task.** Find two distinct inputs whose SHA-256 digests agree on the first 48 bits
(λ = 24, truncation = 2λ = 48 bits = the 6 most significant bytes), and emit
`collision.json` with exactly the four required keys.

**Answer: found.** The collision below was produced locally and re-verified with three
independent SHA-256 implementations.

| | value |
|---|---|
| `inputA` | `0x000000000017211c` (8 bytes, big-endian counter 1 515 804) |
| `inputB` | `0x00000000014060cc` (8 bytes, big-endian counter 20 996 300) |
| `sha256(inputA)` | `4e84dca19fa6` `99674e41dc0ff0f92046577a96fd3bbc22ae6a036986dc268301` |
| `sha256(inputB)` | `4e84dca19fa6` `7ad46fd0f73243c0081834a4767ce3fc91b0b4dade47ab574d2e` |
| shared first 48 bits | `4e84dca19fa6` |
| bit 49 onward | differ (`0x99…` vs `0x7a…`) — this is a *truncated* collision only |

Artifact as delivered (90 bytes = 89 bytes of JSON + one trailing newline, repository
root):

```json
{"algo":"sha256","lambda":24,"inputA":"0x000000000017211c","inputB":"0x00000000014060cc"}
```

---

## 1. Facts (directly observed in this session)

Every line below is a command output captured in this run; the commands are reproducible
from the committed source.

**F1 — The two inputs are distinct.** They decode to 8-byte strings
`000000000017211c` and `00000000014060cc`. Different bytes, same length.

**F2 — The first 48 bits of the two digests are identical.** Checked by three separate
SHA-256 code paths, all agreeing on the full digests:

| implementation | evidence | result |
|---|---|---|
| Python 3.12.3 `hashlib.sha256` | `python3 src/verify.py collision.json` → `OK: distinct inputs, identical first 48 bits of sha256` | pass |
| `openssl dgst -sha256` CLI, OpenSSL 3.0.13 | digests printed as `4e84dca19fa69967…` / `4e84dca19fa67ad4…` | pass |
| Node.js `crypto.createHash("sha256")` | `distinct inputs: true`, `48-bit prefixes equal: true`, `full digests equal: false` | pass |

**F3 — The full digests are *not* equal.** No claim of a full SHA-256 break is made or
implied.

**F4 — Artifact shape.** `collision.json` parses as JSON with exactly the key set
`{algo, inputA, inputB, lambda}`, `algo == "sha256"`, and `lambda == 24` as a JSON number
(Python type `int`, not a string).

**F5 — Work actually performed.** The search evaluated **20 996 301** SHA-256
compressions before the first prefix repeat, in 32.1 s wall clock, single-threaded,
peak RSS 2 318 240 kB (~2.2 GiB), measured by `/usr/bin/time -v`.

**F6 — Determinism.** Re-running `src/collide.py` from scratch produced a file
byte-identical to `collision.json` (`cmp` reported no difference). The search uses no
randomness, no clock input, and no environment input.

**F7 — The verifier is not vacuous.** It rejects, with exit code 1, four deliberately
broken artifacts: identical inputs; a non-colliding pair (`af5570f5a181` vs
`cd2662154e6d`); `algo:"md5"`; and an extra JSON key. It also decodes the non-`0x`
(UTF-8) input form correctly (`"hello"` → `68656c6c6f`).

## 2. Inferences (supported, not directly observed)

**I1 — The search behaved as birthday theory predicts.** The expected number of draws to
the first repeat in a 2⁴⁸ space is √(π/2 · 2⁴⁸) ≈ 1.2533 · 2²⁴ ≈ 21 020 000. Observed:
20 996 301 = 1.2519 · 2²⁴ — within 0.11 % of the expectation. *Inference, not proof*: a
single sample cannot confirm a distribution; it is consistent with a correct, unbiased
search and rules out a mistake of order 2× in the truncation width.

**I2 — The result should verify under any correct SHA-256.** Three independent
implementations (two of them non-Python) agree bit-for-bit on both full digests, and
SHA-256 is a fixed, unambiguous function of a byte string. So agreement with SIMD's
recomputation depends only on input *decoding*, not on hashing.

**I3 — Cost claim.** ~2.1 × 10⁷ hashes ≈ 2²⁴·²⁵, matching the stated ~2²⁴ birthday cost.
No shortcut, structural weakness, or precomputed table was used; the method is generic
and would not scale to a full 256-bit collision.

## 3. Uncertainty and limits

**U1 — Input decoding is a convention, not something I can verify.** The artifact states
inputs as `0x`-prefixed hex, which the task explicitly permits (`"<hex 0x... or utf8>"`).
I assume SIMD strips the `0x` and hex-decodes to 8 raw bytes — the reading my verifier
implements. If instead the *literal ASCII string* `0x000000000017211c` were hashed, the
digests would be different values and the check would fail. This is the single largest
residual risk. It is mitigated but not eliminated: hex is listed first in the task's own
format spec, and the alternative reading would make the `0x` marker meaningless.

**U2 — "First 48 bits MSB" is read as the first 6 bytes of the standard digest byte
string**, most-significant-byte first. Any other bit ordering (e.g. per-byte bit
reversal) is not tested. For this pair the shared region is a whole number of bytes, so
byte-granular and bit-granular readings coincide.

**U3 — Self-verification carries no independent authority.** Per the assignment, the
structural verifier checks paths and bytes only; my own checks are recorded evidence, not
certification. The three-implementation cross-check in F2 is the strongest claim
available locally.

**U4 — Peak memory.** The search holds ~21 M dict entries (~2.2 GiB). It succeeded here
(32 GiB machine) but is not tuned for small-memory hosts. This affects reproduction, not
the correctness of the artifact.

**U5 — No compiler was available** (`gcc`, `clang`, `make`, `cargo`, `go` all absent), so
the search is pure Python at ~0.67 M hashes/s. That is a performance fact, not a
correctness one; a compiled search would be ~50× faster but would yield the same pair.

## 4. Open questions

1. Does SIMD's recomputation decode `0x…` as hex? (U1 — the one assumption that would
   invalidate the artifact if wrong. A UTF-8-only fallback pair could be produced on
   request, but would cost another full search and cannot satisfy both readings at once.)
2. Does the verifier tolerate the trailing newline after the JSON object, and does it
   require a specific key order? The emitted file is minified, key order as specified,
   with one trailing `\n`.
3. Is `lambda` expected as the number `24` (as emitted) or the string `"24"`? The task
   shows it unquoted, so a number was used.

## 5. Reproduction

```bash
python3 src/collide.py --out collision.json   # ~32 s, ~2.2 GiB, deterministic
python3 src/verify.py collision.json          # exit 0 on success
```

No network access and no third-party packages are used; only the Python standard library.
`src/collide.py` is the search, `src/verify.py` the independent checker. Scratch material
under `test/scratch/` is not part of the deliverable.

## 6. Method

Plain memory-bound birthday search. Messages are the 8-byte big-endian encodings of a
counter i = 0, 1, 2, …; each is hashed once and its 48-bit digest prefix stored in a map
prefix → i. The first prefix already present yields the pair. The counter sequence starts
at 0 and nothing is sampled, which is what makes F6 (determinism) hold. The 2²⁷ hard cap
in the script (~6× the expectation) exists only to bound a pathological run; it was not
reached.