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

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.