# Report: 48-bit truncated SHA-256 collision (SIMD-COLLISION:sha256:24)

## Answer

A collision was found. Both inputs are UTF-8 strings (23 ASCII bytes each, no
trailing newline, no `0x` prefix):

```json
{"algo":"sha256","lambda":24,"inputA":"simd-sha256-48:35564992","inputB":"simd-sha256-48:55746276"}
```

| | Input (UTF-8) | SHA-256 |
| --- | --- | --- |
| A | `simd-sha256-48:35564992` | `0b196da85087` `35960f9d2153031c2fda6c6784ea3f9bd09e2df94fd5e16d8226` |
| B | `simd-sha256-48:55746276` | `0b196da85087` `f2379c1b094e3dc0921906abd042548b149d76c57602e7ab04af` |

The first 12 hex digits (48 bits, most significant first) are `0b196da85087` in
both. The 13th hex digit differs (`3` vs `f`), so the digests agree on exactly
48 leading bits and are otherwise unrelated.

The same JSON is committed at the repository root as `collision.json` (100 bytes,
one line, keys in the order the task gives).

## Facts (observed in this run)

Each item below was produced by a command run in this workspace on 2026-10-05.

1. **The digests above were computed three ways and agree.**
   - Python 3.14.4 `hashlib.sha256` via `tools/verify_collision.py` — printed both
     digests and `OK: distinct inputs, first 48 bits equal (0b196da85087)`, exit 0.
   - `printf '<input>' | sha256sum` (uutils coreutils 0.10.0) — same two digests.
   - `printf '<input>' | openssl dgst -sha256` (OpenSSL 3.5.5) — same two digests.
   - The search itself used a fourth route, Node.js v24.21.0 `crypto.createHash`,
     and reported the same 48-bit prefix.
2. **The inputs are distinct.** They differ as strings and as byte sequences
   (`…35564992` vs `…55746276`).
3. **The verifier rejects a non-collision.** Fed `{"inputA":"a","inputB":"b"}` it
   printed `FAIL: first 48 bits differ` and exited 1, so its pass is not vacuous.
4. **Search cost.** `tools/find_collision.js 26` hashed 67,108,864 (2^26) inputs
   `simd-sha256-48:0` … `simd-sha256-48:67108863` in 159.4 s on a 4-core machine
   (single-threaded), then sorted the 48-bit prefixes and took the first equal
   adjacent pair. The colliding counters are 35,564,992 and 55,746,276.

## Method

A plain birthday search: hash many distinct inputs, keep the 48-bit prefix of
each, look for a repeated prefix. The prefix of each digest was read as a
big-endian 6-byte integer, which fits exactly in a double, so all 2^26 values sit
in one `Float64Array` (512 MB) plus a sorted copy. The repeated value is mapped
back to its two counters by scanning the unsorted array. No dependencies beyond
the Node.js standard library; the search is deterministic and reproducible with
the command in `README.md`.

## Sources

| Claim | Source |
| --- | --- |
| Definition of SHA-256 (§6.2) | NIST FIPS 180-4, *Secure Hash Standard* — <https://csrc.nist.gov/pubs/fips/180-4/upd1/final> ([PDF](https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf)) |
| Truncation means taking the left-most bits, and the left-most bit is the most significant; truncating to λ bits reduces expected collision resistance to λ/2 bits (§5.1, and the "Bit string" definition) | NIST SP 800-107 Rev. 1 — <https://csrc.nist.gov/pubs/sp/800/107/r1/final> ([PDF](https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-107r1.pdf)) |
| A birthday attack finds a collision on an n-bit hash in about 2^(n/2) operations (Fact 9.33, Definition 9.34, §9.7.1, Algorithm 9.92) | Menezes, van Oorschot, Vanstone, *Handbook of Applied Cryptography*, ch. 9 — <https://cacr.uwaterloo.ca/hac/about/chap9.pdf> |

All three documents were fetched on 2026-10-05 and the cited passages were located
in the fetched text. One time-sensitive point: the SP 800-107 Rev. 1 landing page
states that NIST has decided to withdraw the document once replacement
implementation guidance is published. It was still served on that date. It is
cited here only for the definition of truncation and the λ/2 rule, neither of
which the withdrawal notice disputes.

Note on notation: SP 800-107 uses λ for the *truncated length* in bits. The task
uses λ=24 for the *collision security level*, with a truncated length of 2λ = 48
bits. The two are consistent (48/2 = 24); only the letter is reused.

## Inferences

- **The collision is an ordinary birthday collision, not a weakness in SHA-256.**
  Among N = 2^26 values drawn uniformly from 2^48, the expected number of
  colliding pairs is about N²/2 ÷ 2^48 = 8. Finding at least one is what the
  birthday bound predicts if the truncated output behaves like a random function.
  One successful run is consistent with that model; it does not test it.
- **2^26 rather than the nominal 2^24 was a deliberate margin.** At N = 2^24 the
  expected pair count is 0.5, so a fixed-size batch fails about 61% of the time
  (e^-0.5). At 2^26 the failure chance is about e^-8 ≈ 0.03%. The task's "about
  2^24" is the order of magnitude, and this run cost four times that.
- **The interpretation of the input encoding.** The task allows "hex 0x... or
  utf8". These inputs contain non-hex characters and do not start with `0x`, so
  the only reading the stated format permits is UTF-8 text. I infer the verifier
  hashes the UTF-8 bytes of the string as given.

## Uncertainty

- **Verifier conventions I could not observe.** The SIMD verifier's code is not
  in this repository. If it appends a newline or terminator, normalises the string,
  or applies some other encoding before hashing, the digests would change and the
  collision would not hold. The checks above cover the plain reading: SHA-256 over
  the exact UTF-8 bytes, compared on the first 6 digest bytes.
- **Self-verification only.** All four SHA-256 implementations ran on one machine
  in one session, operated by the party that produced the result. Agreement among
  them makes an implementation bug very unlikely, but no independent reviewer has
  recomputed the digests.

## Unanswered questions

- **How many collisions exist in this 2^26-input set, and which is found first?**
  The search stops at the first repeated value in sorted order, so it reports the
  collision with the numerically smallest prefix, not the one a sequential search
  would hit earliest, and it does not count the others (about 8 expected).
- **Does a pair exist that collides under both readings of the input format**
  (as UTF-8 text and as `0x` hex)? Not attempted; it would amount to a 96-bit
  joint collision, roughly 2^48 evaluations.