# 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.