Practical Preimages for 19- and 20-Step SHA-256 with Standard Padding

Sebastian R. Wain

Oct 31, 2026arXiv:2611.00512v1

cs.CR

Scorecard· 16/16

4.5/10 impact

Verifiable, well-engineered incremental extension of practical reduced-round SHA-256 preimages to padded arbitrary targets at 19–20 steps, with limited reach beyond a niche subfield.

Abstract

We present practical preimage attacks on 19- and 20-step SHA-256 that respect the standard IV, Davies-Meyer feed-forward, and full FIPS 180-4 padding, for arbitrary prescribed 256-bit targets. Building on Basra's algebraic selector saturation and backward padding absorption, we introduce three techniques: an exact $O (1)$ inversion of the low padding byte $(W_{13} \bmod 256) = \mathtt{0x80}$ that leaves $(a_{5}, a_{6})$ free for exact context shaping; a causal bit-slice equivalence theorem that prunes $99.74\%$ of right-hand candidate nodes across seven stages; and a closed-form $\mathbf{F}_2$ upper-half inverse paired with compact $Q_0^{-1}$ lookup tables. One CPU core solves arbitrary 19-step padded targets in $1.2$ -- $86.4$ s (median $19.5$ s) after an $18$ s table build. A 20-step padded preimage costs $2^{46.6}$ CPU-reference evaluations: $191$ node-hours on one 10-core Apple M4 CPU node (16 threads), or $9.0$ -- $22.2$ GPU-hours on one NVIDIA L4. A companion Zero- $a_{3}$ bridge inverts the unpadded 20-step compression function in $2^{38.1}$ evaluations. We provide 46 self-verifying witnesses, including 55-byte preimages of SHA-256("abc") and $0^{256}$ . These attacks cover 19--20 of 64 steps and do not threaten full SHA-256.

AI Impact Assessments

(1 model)

Core Contribution

The paper claims practical preimages for 19- and 20-step SHA-256 (of 64) that respect the standard IV, feed-forward and full FIPS 180-4 padding, for arbitrary prescribed 256-bit targets. It builds on Basra's selector saturation and context shaping, which previously handled only unpadded targets and one structured padded 20-step target. The new pieces are:

an O(1) closed-form inversion of the padding byte (W13 mod 256 = 0x80) through 8 bit-disjoint pivot bits of Σ1(e13);

a causal bit-slice equivalence theorem ("Carry-Sudoku") that prunes about 99.7% of right-context candidates;

a closed-form F2 inverse of the upper 16 bits of Q0^-1, which lets the tables store only 16-bit entries;

a Zero-a3 bridge for the unpadded 20-step compression function (2^38.1);

46 self-verifying witnesses and a code release.

The headline numbers are 19-step padded preimages in about 20 s on one core, and 20-step padded preimages at 2^46.6 reference evaluations (about 191 M4 node-hours, or 9–22 L4 GPU-hours).

Methodological Rigor

The strongest feature is verifiability. Preimages of step-reduced hashes are checkable in under a second, so the central claims, that the witnesses hash to the targets with correct padding, are falsifiable and appear sound. Theorem 1 (a carry-induction equivalence) and Theorem 2 (a triangular F2 inversion) have short, plausible proofs, and Theorem 2 is backed by exhaustive and boundary tests. The complexity accounting is detailed. It separates precomputation from online cost, distinguishes genuine from synthetic microbenchmarks, and honestly excludes the synthetic ones. Section 9.2 candidly states that the work is restricted to a structured subspace.

Weaknesses:

Cost is reported in a nonstandard "CPU-ref" unit tied to one machine.

The 2^-32 terminal survival model is heuristic.

There is no baseline comparison on identical hardware against Basra, Zaikin or SAT approaches. The comparison table mixes different objects, targets and hardware.

The 20-step padded solution counts rest on a "twin" coalescing trick whose accounting is intricate. The first 20-step result was found only after about 7×10^7 bridge candidates, which is consistent with the model.

The disclosure section describes an AI-driven discovery and review process, with model names that cannot be verified. Because the results are checkable, this matters little for correctness, but it affects provenance and trust in the prose claims.

The paper's own Table 9.4 reports that none of the 15 attempted sub-2^32 directions worked.

Potential Impact

Security impact is nil: 19–20 of 64 steps is far from threatening SHA-256, and the paper says so. Its value is as a milestone in practical reduced-round cryptanalysis. It pushes padded, arbitrary-target practical preimages from 16–17 steps to 20, and gives a reusable set of algebraic techniques (selector saturation, carry-sudoku pruning, compact inverse tables for the schedule operator). It could serve as a benchmark for SAT/CP-style cryptanalysis and as a testbed for AI-assisted cryptanalysis. The techniques are specific to the SHA-256 message schedule and the first ~20 steps. They do not extend obviously to more steps, as the paper's own degree-of-freedom analysis shows. They are unlikely to feed into attacks on full or even substantially more rounds, which limits broader influence.

Timeliness & Relevance

Interest in practical reduced-round SHA-256 preimages has grown recently (Zaikin 2025/26, Davydov et al., Basra). Incremental extensions to padded hashes with arbitrary targets fit that thread. The AI-assisted discovery angle is timely, but it is a side note rather than something the paper evaluates.

Strengths & Limitations

Strengths:

Concrete, independently checkable witnesses, including for the "abc" and all-zero digests.

A full open-source implementation (C/CUDA/Python) and a verifier script.

A genuinely stronger result than prior padded 20-step work, since it handles arbitrary targets.

Clever algebraic closed forms that cut table memory and pruning cost.

A clear and honest scope discussion.

Limitations:

The marginal advance over Basra is a single step count plus generality of target, so it is incremental.

The paper is extremely dense, with a heavy equation-tag and filename style, internal "rounds" and "retired" equations, and many overlapping benchmark variants, which hurts readability.

It is hardware-specific (a 6–52 GiB table requirement) and uses nonstandard units.

The chosen-target 19-step solver relies on soft shaping rather than exact shaping.

The "arbitrary target" claim is established by about 14–16 targets rather than by proof.

The results do not extend to a security-relevant number of steps.

It was not peer reviewed in an established venue, and the stated AI authorship process raises some credibility questions.

Overall this is a competent, verifiable, niche incremental advance with modest long-term influence beyond the reduced-round SHA-256 community.

Rating:4.5/ 10

Significance 4Rigor 5.5Novelty 5Clarity 3.5

Generated Nov 3, 2026

Comparison History (0)

No comparisons yet.

Scorecard· 16/16

4.5/10 impact

Verifiable, well-engineered incremental extension of practical reduced-round SHA-256 preimages to padded arbitrary targets at 19–20 steps, with limited reach beyond a niche subfield.