# SHA-256 truncated-48-bit collision (λ=24) ## Answer `collision.json`: ```json {"algo":"sha256","lambda":24,"inputA":"imd-12192837","inputB":"imd-19093962"} ``` Both inputs are plain UTF-8/ASCII strings (no `0x` prefix, no trailing newline). | input | SHA-256 (full) | |---|---| | `imd-12192837` | `c94563ba4883`4c66186fe07f1f2233f777eed615e843ce03144ade7e659074d9 | | `imd-19093962` | `c94563ba4883`0d17ce781584012f36b6502808166df0a05236829c7c1c062211 | The 48 most significant bits (first 12 hex digits) are identical: `c94563ba4883`. The full digests differ from bit 49 onward, and the inputs differ, so this is a genuine truncated collision, not a full SHA-256 collision. ## Evidence (facts) - Digests were computed with Python `hashlib.sha256` and independently with GNU coreutils `sha256sum` (`printf 'imd-12192837' | sha256sum`); both tools gave the identical values shown above. - `python3 tools/verify.py` decodes the inputs (hex if `0x`-prefixed, otherwise UTF-8), truncates to `2·λ = 48` MSB bits, and prints `COLLISION OK`. - Search method (`tools/birthday_search.py`): generic birthday search over messages `imd-`, storing 6-byte digest prefixes in a hash table. Work was split across 4 processes by the low 2 bits of the first digest byte, so each process held ~¼ of the table. The match was found at i = 19,093,962 (≈ 2^24.2 evaluations), ~46 s wall time on 4 cores. ## Inferences - The observed cost agrees with the birthday bound: expected evaluations for a 48-bit collision ≈ √(π/2 · 2^48) ≈ 2.1·10^7, consistent with the task's stated ~2^24. No property of SHA-256 beyond its output length was used. ## Uncertainty / open questions - Assumed the verifier interprets non-`0x` strings as UTF-8 bytes with no newline, and that "truncated to 48 bits MSB" means the first 6 bytes of the big-endian digest. If the verifier instead uses λ bits (24), the collision still holds, since a 48-bit prefix match implies a 24-bit one. - Not checked: the remote SIMD verifier itself (not available here).