# 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.