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

## Answer
| | input (UTF-8, hashed as raw bytes) | SHA-256 (hex) |
|---|---|---|
| A | `identitymd-sha256-48-33470631` | `52b3d5bed12a`c4bf555f73aeccadf4ee8f59b69258cdc319faa44d33648c6cc0 |
| B | `identitymd-sha256-48-39003384` | `52b3d5bed12a`d36c1fe698be56d9f3e61098e9de3f5cf17c642a547907f1f4bf |

The first 12 hex digits (48 bits, MSB first) match: `52b3d5bed12a`. The 13th digit already
differs (`c` vs `d`), so the full digests are different. This is expected, because only the
truncated output collides. The pair is recorded in `collision.json`.

## Facts (observed directly in this run, 2026-10-05)
1. `tools/find_collision.py` hashed `identitymd-sha256-48-<i>` for i = 0, 1, 2, … and kept the
   first 48 bits of each digest in a dict. It stopped at the first repeated value: i = 39003384
   matched i = 33470631. That took 39,003,385 evaluations, 44.8 s, and 3.77 GB peak RSS
   (`/usr/bin/time -v`), using Python 3.12.3 `hashlib`.
2. Three separate SHA-256 implementations give the same digests listed above:
   - Python `hashlib` (`tools/verify_collision.py`, exit 0, "MATCH")
   - `openssl dgst -sha256` (OpenSSL 3.0.13)
   - coreutils `sha256sum`

   The OpenSSL and coreutils runs hashed the strings with `printf '%s'`, so no trailing newline was added.
3. The inputs are different strings. Neither starts with `0x`, so under the task's encoding rule
   both should be read as UTF-8 text.

## Inferences
- The search needed more evaluations than usual. For N = 2^48, the expected number of evaluations
  before the first collision is √(πN/2) ≈ 2.10 × 10^7 (standard birthday bound). This run used
  3.90 × 10^7. The chance of going that far without a collision is exp(−n²/2N) ≈ 0.067.
  So the run was unlucky but not anomalous. It still fits the task's stated cost of "about 2^24".
- Searching sequential counters is a sound method here. SHA-256 behaves like a random function
  on these inputs, and nothing in the method depends on any structural weakness in SHA-256.

## Uncertainty / unanswered
- The downstream "SIMD" verifier was not available, so I could not run it. Its behaviour is
  inferred from the task text only, in particular "truncated to 48 bits MSB" and "hex 0x... or
  utf8". If it treated the strings as something other than UTF-8 (for example, adding a newline),
  it would not reproduce the match.
- The task calls this λ = 24 and also says 48 bits. I read λ as the birthday security level,
  2^(48/2). No external source was consulted on this point. It is the task's own convention.
- No web sources were needed. Every claim above can be checked by re-running the commands in
  `README.md`.