Practical attacks find preimages for reduced step sha 256
Practical Preimages for 19- and 20-Step SHA-256 with Standard Padding
Cryptography and Security
Summary
This paper shows new ways to find preimages for shortened versions of the SHA-256 hashing algorithm, which means finding inputs that hash to a given output. The methods work on 19- and 20-step variants rather than the full 64 steps, respecting the official padding and initial values. The authors build on previous techniques and introduce new ones that greatly reduce the search time using computations that run on a single CPU core or GPU. They provide example preimages including well-known inputs, but emphasize these attacks do not threaten the full SHA-256 used in practice.
What this means in practice
- •For cryptography engineers: Test shortened SHA-256 variants against practical preimage attacks to evaluate security margins before deployment.
- •For hardware security teams: Assess risk of reduced-step SHA-256 implementations in embedded or resource-constrained devices vulnerable to preimage recovery.
Authors
Sebastian R. Wain
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.