sha256-cas

A small, from-scratch C/CUDA toolkit for differential collision analysis of round-reduced SHA-256: a bit-exact reduced-round oracle, a trustless collision verifier, CPU and GPU conforming-message search, message-modification measurement tools, and a generalized-condition / constraint-algebra (CAS) propagation substrate.

This is educational cryptanalysis research. It targets step-reduced SHA-256 (≤ ~38 of 64 rounds), which is standard academic territory and poses no threat to full SHA-256. Nothing here breaks deployed cryptography.

The full write-up — method, measurements and the structural conclusion — is in REPORT.md.

What it does

• Bit-exact oracle (sha2.c) — reduced-round SHA-256 compression, verified against the full-round SHA256("abc") test vector.
• Trustless verifier (verify_pair) — recomputes the N-step digest of two messages and reports whether they genuinely collide. Any wrong/fabricated pair simply fails here.
• Seeded conforming search (collide_search) — fix a message XOR-difference δ, sample messages M1, set M2 = M1 ⊕ δ, and check for a collision. ~7.5M pairs/s per core. Supports a fixed base + word-mask (neighborhood search) and a custom IV (semi-free-start).
• GPU conforming search (gpu_collide.cu) — the same search on CUDA at ~6.2 G tries/s on an RTX 5090, about 100× an 8-core CPU run. Self-tests bit-exact against the CPU oracle, with a positive control (δ placed in an unused message word, where every candidate must collide).
• Characteristic profiler (charac_derive) — traces a known conforming pair and prints the per-round active-bit profile, separating controllable rounds from residual ones.
• Message modification, three instruments:
  • neutral_search — single message bits that can be flipped without breaking the collision;
  • construct_mm — solves W_i to force each e_i in rounds 0–15 and counts the resulting free bits, which is the real modification freedom;
  • mm2 — coordinated flip pairs, the second-order freedom a single-bit scan cannot see.
• CAS propagation substrate (gc, charac, prop, step, word, gf2, twobit, cas, extract, search) — generalized ("1.5-bit") condition propagation over the state and message-expansion equations, a parity union-find with checkpoint/restore, and an incremental GF(2) linear layer. Sound (validated against thousands of real message pairs).

Verified results

The oracle independently verifies these known published reduced-round collisions (re-derived digests are equal for two distinct messages):

# of steps	model	reference
23	real IV	Nikolić–Biryukov / Sanadhya–Sarkar era
28	real IV	Mendel–Nad–Schläffer, EUROCRYPT 2013
38	semi-free-start	Mendel–Nad–Schläffer, EUROCRYPT 2013

These are verifications / reproductions of the state-of-the-art results, not new attacks. Exact hex (IVs, message pairs, differences) is in sha_results.txt. The engine additionally generates fresh, never-published 23-step collisions at ~11 000/s, by neighborhood search where the characteristic leaves a message word free.

The measured wall

A fresh collision at 28+ steps needs message modification — deterministically satisfying the characteristic's conditions on message values rather than sampling and hoping. That layer is implemented here, and the interesting result is what it measures: for the published 28-step characteristic there is almost nothing to modify.

measurement	28-step (P2)	23-step (P1), as control
GPU brute force, δ fixed	2⁴⁴·³³ candidates, 0 collisions	—
neutral bits	2	—
single-step free bits (construct_mm)	3	32
compensating flip-pairs (mm2)	0 of 130 816	—

The 23-step column validates the instrument: it finds freedom where freedom exists. The 28-step conforming set really is about 2³ messages — a near-rigid point, agreed on independently by all three modification tools.

So the wall is not "the search needs more compute". It is structural, and §6 of the report states it: message modification and characteristic search are not separable. Modification only has leverage on a loose characteristic; obtaining one means searching the space of characteristics, which cannot be evaluated with these tools and requires a guess-and-determine engine over generalized conditions. Modification can exploit a loose characteristic, never bootstrap one.

That engine is the missing piece, and it is the part the field spent years on. The CAS substrate here is the right foundation for it; the blind version stalls past ~18 steps.

Build & use

# needs gcc; -std=gnu11 (not c11: a trigraph in a string literal)
make                       # builds all tools + runs the self-tests

# verify a claimed N-step collision
./verify_pair 28 <m1hex:128> <m2hex:128> [ivhex:64]

# search for conforming pairs given a fixed message difference
./collide_search 23 <deltahex:128> [seed] [base_m1|random] [wordmask_hex] [iv|standard]

# measure message-modification freedom of a characteristic
./construct_mm 28 <m1hex> <deltahex> standard    # -> 3 free bits
./mm2          28 <m1hex> <deltahex> standard    # -> 0 compensating pairs

# GPU brute force (optional, needs CUDA)
nvcc -O3 -arch=native gpu_collide.cu -o gpu_collide
./gpu_collide 28 <deltahex> standard 3600

License

MIT — see LICENSE.