# SHA-256 48-bit truncated collision (λ=24) — findings report **Task ID:** `[SIMD-COLLISION:sha256:24]` **Question:** Find two distinct inputs whose SHA-256 digests are identical when truncated to the first (most-significant) 48 bits, and report them as `collision.json`. **Date of run:** 2026-10-05 **Status:** Answered. A collision was found and verified against four independent SHA-256 implementations. --- ## 1. Answer ```json {"algo":"sha256","lambda":24,"inputA":"0x19688697e11d","inputB":"0x750293ffd1bf"} ``` Delivered as `collision.json` (122 bytes, trailing newline). | | value | |---|---| | `inputA` | `0x19688697e11d` (6 raw bytes) | | `inputB` | `0x750293ffd1bf` (6 raw bytes) | | `sha256(inputA)` | `9378a7ecb4cb` `31da3757efee0802c863c66525359462f68cb78e87c8dcb42793` | | `sha256(inputB)` | `9378a7ecb4cb` `2655c297afe1c9661fbbc59d5629aa148699407b5674e1a38aff` | | shared 48-bit MSB prefix | `9378a7ecb4cb` | --- ## 2. Facts — directly observed and reproducible Each item below was produced by a command run in this workspace. The commands are in `tools/`; the transcript of each is summarised here. **F1. The two inputs are distinct.** `19688697e11d` ≠ `750293ffd1bf` as byte strings and as JSON string literals. Both are 6 bytes long. **F2. The leading 48 bits of the two SHA-256 digests are identical.** Both digests begin `9378a7ecb4cb`. Verified bit-by-bit (not only byte-by-byte) by `tools/verify_collision.py`, which expands the digest to a bit string and compares the first `lambda * 2 = 48` characters. **F3. Four independent SHA-256 implementations agree on both digests.** All four produced byte-identical digests: | Implementation | Provenance | Result | |---|---|---| | Python 3.12.3 `hashlib.sha256` | CPython, OpenSSL-backed (`_hashlib.openssl_md_meth_names` present) | agrees | | `openssl dgst -sha256` | OpenSSL 3.0.13 CLI | agrees | | `sha256sum` | GNU coreutils 9.4 (gnulib implementation, not OpenSSL) | agrees | | from-scratch FIPS 180-4 implementation | written for this check; self-tested against the published NIST vectors for `""`, `"abc"`, and the 56-byte `"abcdbcde…nopq"` vector before use | agrees | The fourth implementation shares no code with the first three, which is the evidence that matters: the result does not depend on a single hash library being correct. **F4. The full digests differ.** This is a 48-bit *truncated* collision, not a full SHA-256 collision. No full SHA-256 collision is claimed. **F5. The digests actually agree on 51 leading bits, not exactly 48.** `0x31 ^ 0x26 = 0x17`, which has 3 leading zero bits in its byte, so the common prefix runs 48 + 3 = 51 bits before diverging. This exceeds the requirement and does not conflict with it. **F6. The search is deterministic and was reproduced.** The finder takes its starting point from `sha256("IMD-SIMD-COLLISION:sha256:24:seed=0")[:6] = 0x4f30b8dfffb2`. Re-running `tools/find_collision.py` from scratch produced a **byte-identical** `collision.json` (confirmed with `cmp`), the same walk statistics, and the same digests. Anyone with the script and no other input can regenerate this exact answer. **F7. Measured cost of the search.** | metric | value | |---|---| | SHA-256 evaluations | 37,595,223 (= 2.241 × 2²⁴) | | wall clock | 35.7 s (second run: 38.5 s), single-threaded | | throughput | ≈ 1.05 M evaluations/s | | peak memory | O(1) — a handful of 6-byte values | | rho tail length μ | 6,795,315 | | rho cycle length λ_cycle | 7,807,993 | | rho length ρ = μ + λ_cycle | 14,603,308 | (`λ_cycle` here is the graph-theoretic cycle length. It is unrelated to the task's `lambda = 24`, which is the truncation parameter. The name collision is in the source material, not introduced here.) **F8. Method.** Pollard's rho with Brent's cycle detection on the self-map `f(x) = sha256(x)[:6]` over the 6-byte domain. Since the domain and codomain are both 2⁴⁸, `f` is a self-map; the point where its functional graph's tail joins its cycle has two distinct predecessors, and those are the colliding inputs. Source: `tools/find_collision.py`. **F9. The rho logic was validated before the expensive run.** The same code was run at 16-, 24- and 32-bit truncation across 8 distinct seeds each — 24 trials, all 24 produced collisions that independently re-verified. This tested the algorithm at widths where the expected answer is cheap to obtain, so a positive 48-bit result is not the first time the code had ever produced output. **F10. Environment constraints that shaped the approach.** No C compiler (`gcc`/`cc`/`make` absent) and no `numpy` in this environment; 8 cores, ~29 GB RAM available. --- ## 3. Inferences — supported by the facts, but one step removed **I1. The cost observed is consistent with the birthday bound, which is weak corroboration that nothing went wrong.** For a random self-map on N = 2⁴⁸, E[ρ] = √(πN/2) ≈ 21,027,122. The observed ρ = 14,603,308 = 0.870·√N. Under the standard approximation P(ρ ≤ x·√N) ≈ 1 − exp(−x²/2), a value this short or shorter occurs ~32% of the time, so the run is unremarkable. The 37.6M total evaluations ≈ 2.24 × 2²⁴ reflect Brent's constant factor (the walk is traversed roughly twice over, plus a μ-finding pass) on top of ρ itself. *This is a consistency check, not proof of correctness — correctness rests on F2/F3.* **I2. Rho was the right choice here, not merely a working one.** A birthday table needs ≈1.25 × 2²⁴ ≈ 21M stored digests. In pure Python a `dict` of that size costs on the order of 2 GB; even a packed open-addressing table costs a few hundred MB. Rho trades roughly a 2.2× increase in hash evaluations (F7) for O(1) memory, and 36 s of single-threaded work is well inside any plausible budget. With a C compiler available, a parallel table-based search would likely have finished in ~1 s, but it was not available (F10). **I3. This result says nothing about SHA-256's security.** Truncating to 48 bits reduces the output space to 2⁴⁸, where a generic birthday attack costs ~2²⁴ work — about 36 seconds on one core. This exercises the truncation, not SHA-256. Finding a full 256-bit SHA-256 collision remains infeasible, and no shortcut to one is implied or used. SHA-256 has no known collision attack better than generic birthday search as of the May 2026 knowledge cutoff; this run provides no evidence either way on that point. **I4. The answer should survive the verifier's recomputation.** The task states that SIMD recomputes `digest(sha256, inputA)` and `digest(sha256, inputB)` and compares 48 MSB. Given F3 (four implementations, one of them from scratch), the digest values are not in question. The residual risk is encoding, not hashing — see U1. --- ## 4. Uncertainty — known, bounded, and stated **U1. Input decoding convention (the main residual risk).** The format permits `""`, and `0x`-prefixed hex was chosen. This report assumes the verifier decodes `0x19688697e11d` to the 6 raw bytes `19 68 86 97 e1 1d` and hashes those bytes, which is the reading `tools/verify_collision.py` implements. If the verifier instead hashed the ASCII string `"0x19688697e11d"` literally, the check would fail — but it would then fail for the hex option generally, which the format explicitly offers, so this reading is the reasonable one. Not independently confirmed against SIMD's actual decoder; SIMD's source was not available in this workspace. **U2. Whether `lambda` means "bits/2" in general.** λ=24 with a 48-bit truncation is consistent with λ being a security-parameter half-width (birthday cost 2^λ), and the task states both numbers explicitly, so nothing was guessed for this instance. The general rule mapping λ to truncation width for other λ values is not established here. **U3. Timings are machine-specific.** 1.05 M SHA-256/s is for short messages in a Python loop on this host (Linux 6.8.0-136, 8 cores); Python interpreter overhead dominates, not SHA-256 itself. Do not read F7 as a hardware benchmark. **U4. `hashlib` and `openssl dgst` are not fully independent of each other.** Python's `hashlib` is OpenSSL-backed on this system (verified, F3), so rows 1–2 of the F3 table are substantially one implementation. Independence rests on `sha256sum` (gnulib) and the from-scratch FIPS 180-4 implementation. This is why the from-scratch oracle was written. **U5. No claim of minimality or canonicity.** The inputs are 6 bytes because that is the natural domain for the rho map, not because short inputs are required. Infinitely many 48-bit-truncated collisions exist; this is one, with no special property beyond F1–F5. --- ## 5. Unanswered questions 1. **What exactly does SIMD's decoder do with a `0x`-prefixed value?** Unresolved (U1). It could be settled by reading the verifier's source, which was not accessible here. A UTF-8 variant could be produced instead if the hex path turns out to be rejected. 2. **Does SIMD impose constraints not stated in the task** — minimum/maximum input length, printable-ASCII only, or a ban on inputs that are themselves hash outputs? Nothing in the task text suggests any of these, and none were tested against. 3. **Is a stricter-than-48-bit match treated as valid?** F5 shows 51 matching bits. Reading the requirement as "the first 48 bits are identical", this passes; it would only matter under an implausible "exactly 48, no more" reading. 4. **Would a tighter cost be reachable in this environment?** Not pursued. Multiprocessing across the 8 available cores with a van Oorschot–Wiener distinguished-point search would cut wall clock substantially, but 36 s did not justify the added complexity. --- ## 6. How to re-verify ```bash python3 tools/verify_collision.py collision.json # 8 checks, exit 0 on success python3 tools/find_collision.py -o /tmp/repro.json # ~36 s; reproduces byte-identically ``` Reproduced result of the first command at the time of writing: **8/8 checks PASS**. ## 7. Evidence provenance Every fact in §2 comes from a command executed in this workspace on 2026-10-05; no claim is carried over from prior knowledge or from an external source. Two items are grounded outside this run and are attributed as such: the NIST FIPS 180-4 known-answer vectors used to self-test the from-scratch implementation (F3), and the standard random-mapping statistics E[ρ] = √(πN/2) and P(ρ ≤ x√N) ≈ 1 − exp(−x²/2) used in I1. No citation in this report is synthetic; no step was reported as done that was not run.