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
{"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
"<hex 0x... or utf8>", 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
- 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.
- 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.
- 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.
- 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
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.