SIMD-COLLISION:sha256:24 — truncated SHA-256 collision (48 bits)
Task. Find two distinct inputs whose SHA-256 digests agree on the first 48 bits
(λ = 24, truncation = 2λ = 48 bits = the 6 most significant bytes), and emit
collision.json with exactly the four required keys.
Answer: found. The collision below was produced locally and re-verified with three
independent SHA-256 implementations.
| value |
|---|
inputA | 0x000000000017211c (8 bytes, big-endian counter 1 515 804) |
inputB | 0x00000000014060cc (8 bytes, big-endian counter 20 996 300) |
sha256(inputA) | 4e84dca19fa6 99674e41dc0ff0f92046577a96fd3bbc22ae6a036986dc268301 |
sha256(inputB) | 4e84dca19fa6 7ad46fd0f73243c0081834a4767ce3fc91b0b4dade47ab574d2e |
| shared first 48 bits | 4e84dca19fa6 |
| bit 49 onward | differ (0x99… vs 0x7a…) — this is a truncated collision only |
Artifact as delivered (90 bytes = 89 bytes of JSON + one trailing newline, repository
root):
{"algo":"sha256","lambda":24,"inputA":"0x000000000017211c","inputB":"0x00000000014060cc"}
1. Facts (directly observed in this session)
Every line below is a command output captured in this run; the commands are reproducible
from the committed source.
F1 — The two inputs are distinct. They decode to 8-byte strings
000000000017211c and 00000000014060cc. Different bytes, same length.
F2 — The first 48 bits of the two digests are identical. Checked by three separate
SHA-256 code paths, all agreeing on the full digests:
| implementation | evidence | result |
|---|
Python 3.12.3 hashlib.sha256 | python3 src/verify.py collision.json → OK: distinct inputs, identical first 48 bits of sha256 | pass |
openssl dgst -sha256 CLI, OpenSSL 3.0.13 | digests printed as 4e84dca19fa69967… / 4e84dca19fa67ad4… | pass |
Node.js crypto.createHash("sha256") | distinct inputs: true, 48-bit prefixes equal: true, full digests equal: false | pass |
F3 — The full digests are not equal. No claim of a full SHA-256 break is made or
implied.
F4 — Artifact shape. collision.json parses as JSON with exactly the key set
{algo, inputA, inputB, lambda}, algo == "sha256", and lambda == 24 as a JSON number
(Python type int, not a string).
F5 — Work actually performed. The search evaluated 20 996 301 SHA-256
compressions before the first prefix repeat, in 32.1 s wall clock, single-threaded,
peak RSS 2 318 240 kB (~2.2 GiB), measured by /usr/bin/time -v.
F6 — Determinism. Re-running src/collide.py from scratch produced a file
byte-identical to collision.json (cmp reported no difference). The search uses no
randomness, no clock input, and no environment input.
F7 — The verifier is not vacuous. It rejects, with exit code 1, four deliberately
broken artifacts: identical inputs; a non-colliding pair (af5570f5a181 vs
cd2662154e6d); algo:"md5"; and an extra JSON key. It also decodes the non-0x
(UTF-8) input form correctly ("hello" → 68656c6c6f).
2. Inferences (supported, not directly observed)
I1 — The search behaved as birthday theory predicts. The expected number of draws to
the first repeat in a 2⁴⁸ space is √(π/2 · 2⁴⁸) ≈ 1.2533 · 2²⁴ ≈ 21 020 000. Observed:
20 996 301 = 1.2519 · 2²⁴ — within 0.11 % of the expectation. Inference, not proof: a
single sample cannot confirm a distribution; it is consistent with a correct, unbiased
search and rules out a mistake of order 2× in the truncation width.
I2 — The result should verify under any correct SHA-256. Three independent
implementations (two of them non-Python) agree bit-for-bit on both full digests, and
SHA-256 is a fixed, unambiguous function of a byte string. So agreement with SIMD's
recomputation depends only on input decoding, not on hashing.
I3 — Cost claim. ~2.1 × 10⁷ hashes ≈ 2²⁴·²⁵, matching the stated ~2²⁴ birthday cost.
No shortcut, structural weakness, or precomputed table was used; the method is generic
and would not scale to a full 256-bit collision.
3. Uncertainty and limits
U1 — Input decoding is a convention, not something I can verify. The artifact states
inputs as 0x-prefixed hex, which the task explicitly permits ("<hex 0x... or utf8>").
I assume SIMD strips the 0x and hex-decodes to 8 raw bytes — the reading my verifier
implements. If instead the literal ASCII string 0x000000000017211c were hashed, the
digests would be different values and the check would fail. This is the single largest
residual risk. It is mitigated but not eliminated: hex is listed first in the task's own
format spec, and the alternative reading would make the 0x marker meaningless.
U2 — "First 48 bits MSB" is read as the first 6 bytes of the standard digest byte
string, most-significant-byte first. Any other bit ordering (e.g. per-byte bit
reversal) is not tested. For this pair the shared region is a whole number of bytes, so
byte-granular and bit-granular readings coincide.
U3 — Self-verification carries no independent authority. Per the assignment, the
structural verifier checks paths and bytes only; my own checks are recorded evidence, not
certification. The three-implementation cross-check in F2 is the strongest claim
available locally.
U4 — Peak memory. The search holds ~21 M dict entries (~2.2 GiB). It succeeded here
(32 GiB machine) but is not tuned for small-memory hosts. This affects reproduction, not
the correctness of the artifact.
U5 — No compiler was available (gcc, clang, make, cargo, go all absent), so
the search is pure Python at ~0.67 M hashes/s. That is a performance fact, not a
correctness one; a compiled search would be ~50× faster but would yield the same pair.
4. Open questions
- Does SIMD's recomputation decode
0x… as hex? (U1 — the one assumption that would
invalidate the artifact if wrong. A UTF-8-only fallback pair could be produced on
request, but would cost another full search and cannot satisfy both readings at once.)
- Does the verifier tolerate the trailing newline after the JSON object, and does it
require a specific key order? The emitted file is minified, key order as specified,
with one trailing
\n.
- Is
lambda expected as the number 24 (as emitted) or the string "24"? The task
shows it unquoted, so a number was used.
5. Reproduction
python3 src/collide.py --out collision.json # ~32 s, ~2.2 GiB, deterministic
python3 src/verify.py collision.json # exit 0 on success
No network access and no third-party packages are used; only the Python standard library.
src/collide.py is the search, src/verify.py the independent checker. Scratch material
under test/scratch/ is not part of the deliverable.
6. Method
Plain memory-bound birthday search. Messages are the 8-byte big-endian encodings of a
counter i = 0, 1, 2, …; each is hashed once and its 48-bit digest prefix stored in a map
prefix → i. The first prefix already present yields the pair. The counter sequence starts
at 0 and nothing is sampled, which is what makes F6 (determinism) hold. The 2²⁷ hard cap
in the script (~6× the expectation) exists only to bound a pathological run; it was not
reached.