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

## Answer

```json
{"algo":"sha256","lambda":24,"inputA":"0xbfd761c04ce7","inputB":"0x616a13e2a7d4"}
```

| input (6 raw bytes, hex) | SHA-256 digest |
|---|---|
| `bfd761c04ce7` | `85f9e86fb02c`301cb51e0b0cba989f06fb64b18e2f5989e9a4db9f7ca46b89b7 |
| `616a13e2a7d4` | `85f9e86fb02c`49a2140d6294ac6ff280d7881f7099438c830385afc3e8821c58 |

The first 48 bits match: `0x85f9e86fb02c`. The full digests differ starting at bit 49.

## Facts (checked locally, reproducible)

- I computed both digests with two independent implementations, and they agree:
  - Python `hashlib.sha256`
  - `openssl dgst -sha256`, fed the raw bytes on stdin
- The inputs are distinct, and their 12-hex-character (48-bit) prefixes are identical. A script asserts both conditions.
- `collision.json` has exactly the keys `algo`, `lambda`, `inputA`, `inputB`.
- To reproduce:
  ```
  python3 -c "import hashlib;print(hashlib.sha256(bytes.fromhex('bfd761c04ce7')).hexdigest()[:12])"
  ```
  Run it again with `616a13e2a7d4`. Both print `85f9e86fb02c`.

## Method

- **Search:** I used parallel collision search with distinguished points (van Oorschot & Wiener, "Parallel Collision Search with Cryptanalytic Applications", J. Cryptology 12(1), 1999).
  - The iterated map is f(x) = SHA-256(x)[:6] over 6-byte strings.
  - A distinguished point is any value whose low 12 bits are zero.
  - When two chains reach the same distinguished point, they are re-walked to find where they merge. That merge point is the collision.
- **Run:** 4 processes, about 5 s wall time.
  - About 1.6×10⁷ evaluations (≈2^23.9), across 3,931 stored distinguished points.
  - This is consistent with the birthday bound √(π/2·2^48) ≈ 2^24.3.

## Inferences / uncertainty

- **Input encoding:** the task allows inputs as "hex 0x... or utf8". I assumed a `0x`-prefixed value is hex-decoded to bytes before hashing. If the verifier instead hashed the literal ASCII string `"0xbfd761c04ce7"`, the pair would not collide.
- **Truncation convention:** "first 48 bits, MSB" is read as the first 6 bytes of the standard big-endian digest output, i.e. the first 12 hex characters.

## Open questions

- I did not test against the actual SIMD verifier. Its decoding rules are known only from the task text.