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):

{"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.