Report: SHA-256 collision truncated to 48 bits (λ=24)

Answer

{"algo":"sha256","lambda":24,"inputA":"imd-12192837","inputB":"imd-19093962"}

Both inputs are UTF-8 strings (no 0x prefix). The same file is at collision.json (repo root) and artifacts/collision.json.

Evidence (facts, reproduced locally)

Input (UTF-8)	SHA-256 (full)
imd-12192837	c94563ba48834c66186fe07f1f2233f777eed615e843ce03144ade7e659074d9
imd-19093962	c94563ba48830d17ce781584012f36b6502808166df0a05236829c7c1c062211

• The first 48 bits (6 bytes, 12 hex digits, most significant first) are c94563ba4883 for both.
• The inputs are distinct, and the full digests differ after byte 6, so this is a prefix collision and not a full SHA-256 collision.
• The digests were computed three separate ways and all agree: Python hashlib (scripts/verify_collision.py), GNU coreutils sha256sum, and openssl dgst -sha256. Inputs were hashed as raw bytes with no trailing newline.

Reproduce:

python3 scripts/verify_collision.py collision.json
printf '%s' imd-12192837 | sha256sum
printf '%s' imd-19093962 | sha256sum

Method

scripts/find_collision.py runs a plain birthday search. It hashes imd-0, imd-1, … and stores each 6-byte digest prefix in a dictionary until a prefix repeats. The first repeat came at message index 19,093,962 (about 2^24.19 evaluations), matching index 12,192,837. The run took about 66 s on one CPU core and used a few GB of RAM.

Inference

• The expected birthday cost for a 48-bit output is about √(π/2 · 2^48) ≈ 1.25 · 2^24 ≈ 21M evaluations. We needed 19.1M, which fits that estimate and the task's "about 2^24" figure.
• Nothing here weakens full SHA-256. A 48-bit truncation only gives 24-bit collision resistance, as the generic birthday bound predicts.

Uncertainty and open questions

• Truncation convention. We assume "first 48 bits, MSB" means the first 6 bytes of the standard big-endian digest output. If the verifier truncates some other way (for example, the low-order bits), this pair would not count. That is unlikely given the wording, but not confirmed.
• Input encoding. We assume strings without 0x are read as UTF-8 bytes, as the task format says. The inputs are pure ASCII, so this also holds under Latin-1 or ASCII decoding.
• Not tested. We did not run the external "SIMD" verifier. Our checks are local recomputations and have no independent authority.

Sources

• FIPS 180-4, Secure Hash Standard (defines SHA-256): https://csrc.nist.gov/pubs/fips/180-4/upd1/final (cited for the algorithm definition; the evidence above is computational, not taken from the document).