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):
{"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.
- 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.
- The inputs are distinct. They differ as strings and as byte sequences
(
…35564992 vs …55746276).
- 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.
- 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) |
| 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) |
| 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.