# 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 ```json {"algo": "sha256", "lambda": 24, "inputA": "0xcfc944ab2e1c", "inputB": "0x408f1b45687d"} ``` | | Input bytes (hex) | Full SHA-256 digest | |---|---|---| | A | `cfc944ab2e1c` | `2417e9dafc1a`**`1181a2f7813ee65ae982e166e70b23fa437449f214f9d2551ce6`** | | B | `408f1b45687d` | `2417e9dafc1a`**`97b1c28da5d74d80aeaa64600a79cb62fd74c77787f26b34de2f`** | 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.