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

Question

Find distinct inputs A and B where SHA-256(A) and SHA-256(B), each truncated to the first 48 bits (most significant first), are identical. Report the pair as collision.json.

Answer

{"algo": "sha256", "lambda": 24, "inputA": "0xcfc944ab2e1c", "inputB": "0x408f1b45687d"}

	Input bytes (hex)	Full SHA-256 digest
A	cfc944ab2e1c	2417e9dafc1a1181a2f7813ee65ae982e166e70b23fa437449f214f9d2551ce6
B	408f1b45687d	2417e9dafc1a97b1c28da5d74d80aeaa64600a79cb62fd74c77787f26b34de2f

The first 12 hex digits (48 bits) match: 2417e9dafc1a. The digests differ after that (bold).

Evidence (facts, observed in this run)

1. Search output. python3 tools/rho_collision.py (Python 3.12.3, stdlib hashlib) printed start=0xdba72ac7993c mu=2461544 lambda=14948527 evals=51597357 time=17.3s and truncated digest: 2417e9dafc1a. The script's own assert a != b and f(a) == f(b) passed.
2. Independent recheck. python3 tools/verify_collision.py collision.json exited 0. It parses the JSON, checks the exact key set, decodes the 0x inputs, checks they differ, and compares int(digest) >> (256-48). It printed trunc48: A=2417e9dafc1a B=2417e9dafc1a equal=True.
3. Second implementation. GNU coreutils sha256sum over the raw bytes (printf 'cfc944ab2e1c' | xxd -r -p | sha256sum, and the same for B) produced the full digests in the table above. They match Python's output byte for byte.
4. Negative controls. The verifier rejected two bad files: one with inputB changed by one bit (...687e, which gives truncated digest a94f52cd11bd, exit 1) and one with identical inputs (AssertionError "inputs are not distinct").

Anyone can reproduce items 2 and 3 offline in under a second. Item 1 is deterministic and takes about 17 s.

Method

• Iterate the map f(x) = SHA-256(x)[0:6] over 6-byte strings, so the domain and range are the same. The start point is SHA-256("IdentityMD-SIMD-COLLISION-sha256-24")[0:6].
• Brent's cycle detection finds the cycle length λ_c = 14,948,527 and then the tail length μ = 2,461,544. Because μ > 0, the two predecessors of the cycle's entry point are distinct inputs with the same image. That pair is the collision. This approach uses constant memory, so no hash table of ~2^24 entries is needed.
• Total work was 51,597,357 ≈ 2^25.6 evaluations of SHA-256.

Inferences (reasoned, not measured)

• The work matches generic birthday behaviour. For a random function on N = 2^48 points, the expected μ + λ_c is about sqrt(πN/2) ≈ 2^24.3 ≈ 2.1×10^7. Here μ + λ_c = 1.74×10^7. Brent's method costs a small constant multiple of μ + λ_c, which explains ≈ 3× that number of evaluations.
• So this result shows nothing about SHA-256 beyond its 48-bit truncation behaving like a random function at this scale. Generic attacks on an n-bit truncation cost about 2^(n/2).

Uncertainty and open questions

• Input encoding. The task says inputs are "hex 0x... or utf8". I chose 0x hex, meaning the 6 raw bytes. I have assumed the external SIMD verifier decodes 0x-prefixed strings as hex. If it hashed the literal 14-character text instead, the pair would not collide. I did not observe the verifier, so this remains unconfirmed.
• Truncation convention. I took "first 48 bits MSB" to mean digest bytes 0–5, in the standard big-endian byte order of SHA-256 output. Since 48 is a multiple of 8, bit-ordering within bytes does not matter.
• Not tested: the external SIMD verifier itself, and any other JSON formatting it might need (for example, whitespace). The file is valid JSON with exactly the four required keys.

Sources

• SHA-256 definition: NIST FIPS 180-4, Secure Hash Standard, §6.2 — https://csrc.nist.gov/pubs/fips/180-4/upd1/final
• Brent's cycle detection: R. P. Brent, "An improved Monte Carlo factorization algorithm", BIT 20 (1980) 176–184 — https://doi.org/10.1007/BF01933190
• Rho-style collision search for hash functions: van Oorschot & Wiener, "Parallel Collision Search with Cryptanalytic Applications", J. Cryptology 12 (1999) 1–28 — https://doi.org/10.1007/PL00003816

Note: I cited these sources from background knowledge. I did not re-fetch them during this task. The collision does not depend on them. It rests only on the recomputation evidence above.