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

## Question

Find two distinct inputs whose SHA-256 digests agree on the first 48 bits
(most-significant bits, i.e. the first 6 digest bytes), and deliver them as
`collision.json`.

## Answer

`collision.json` (repository root):

```json
{"algo": "sha256", "lambda": 24, "inputA": "identitymd-sha256-48-33470631", "inputB": "identitymd-sha256-48-39003384"}
```

Both inputs are plain UTF-8 (ASCII) strings with no trailing newline.

| input | full SHA-256 digest |
|---|---|
| `identitymd-sha256-48-33470631` | `52b3d5bed12a`c4bf555f73aeccadf4ee8f59b69258cdc319faa44d33648c6cc0 |
| `identitymd-sha256-48-39003384` | `52b3d5bed12a`d36c1fe698be56d9f3e61098e9de3f5cf17c642a547907f1f4bf |

The first 48 bits are `0x52b3d5bed12a` for both. The digests differ from the 49th
bit onward (`c4…` vs `d3…`).

## Evidence (facts — reproduced locally on 2026-10-05)

1. **The search.** `tools/find_collision.py` hashes `"identitymd-sha256-48-" + n`
   for n = 0, 1, 2, … using Python 3.12.3 `hashlib.sha256`. It keeps the first 6
   digest bytes in a dict and stops at the first repeat. It stopped after
   39,003,385 evaluations (n = 39,003,384 matched n = 33,470,631), taking 46 s
   wall-clock and about 3.8 GB peak RSS. The search is deterministic, so
   running it again gives the same pair.
2. **Independent recomputation** with two other implementations:
   ```
   $ printf '%s' identitymd-sha256-48-33470631 | sha256sum
   52b3d5bed12ac4bf555f73aeccadf4ee8f59b69258cdc319faa44d33648c6cc0  -
   $ printf '%s' identitymd-sha256-48-39003384 | sha256sum
   52b3d5bed12ad36c1fe698be56d9f3e61098e9de3f5cf17c642a547907f1f4bf  -
   $ printf '%s' identitymd-sha256-48-33470631 | openssl dgst -sha256 -r
   52b3d5bed12ac4bf555f73aeccadf4ee8f59b69258cdc319faa44d33648c6cc0 *stdin
   $ printf '%s' identitymd-sha256-48-39003384 | openssl dgst -sha256 -r
   52b3d5bed12ad36c1fe698be56d9f3e61098e9de3f5cf17c642a547907f1f4bf *stdin
   ```
3. **Format check.** A Python check loaded `collision.json` and confirmed that:
   - the keys are exactly `algo`, `lambda`, `inputA` and `inputB`
   - `algo == "sha256"` and `lambda == 24`
   - `inputA != inputB`
   - `digest >> (256-48)` is equal for both inputs (`0x52b3d5bed12a`)
   - the full digests differ

SHA-256 itself is the function specified in NIST FIPS 180-4, *Secure Hash
Standard* (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf). The
tools above are standard implementations of that function. I did not check them
against the FIPS test vectors in this work.

## Inferences (derived, not measured)

- **Expected cost.** For an n-bit ideal hash, a birthday search needs about
  √(π·2ⁿ/2) evaluations on average. For n = 48 that is about 21.0 M
  (≈ 1.25 · 2²⁴). The 50% point is √(2 ln 2 · 2⁴⁸) ≈ 19.8 M. This matches the
  task's "about 2^24" estimate.
- **This run was unlucky but not anomalous.** The probability of seeing no
  collision within 39.0 M evaluations is about exp(−k²/2·2⁴⁸) ≈ 6.7%. So a
  search this long happens roughly once in 15 runs. It says nothing about
  SHA-256 itself.
- **No weakness of SHA-256 is shown.** This is a generic attack on a 48-bit
  truncation and works equally well against any 48-bit function. Collisions on
  the full 256-bit SHA-256 would need about 2¹²⁸ work by the same method.

## Uncertainty and open questions

- **Verifier conventions (unconfirmed).** I don't know exactly how the
  downstream "SIMD" verifier parses inputs. I assumed:
  - strings without a `0x` prefix are hashed as their raw UTF-8 bytes
  - "truncated to 48 bits MSB" means the first 6 bytes of the big-endian digest

  If the verifier instead hex-decodes everything or uses a different bit order,
  the result may not verify. The inputs contain only ASCII letters, digits and
  `-`, so no Unicode normalization issue can arise.
- **Not independently reviewed.** The checks were run by the same agent that
  produced the result. They have no independent authority. Anyone can confirm
  the result with the two `printf | sha256sum` commands above.