betaFeedback

WorksComputer Science

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)O(1) inversion of the low padding byte (W13 mod 256)=0x80(W_{13} \bmod 256) = \mathtt{0x80} that leaves (a5,a6)(a_5, a_6) free for exact context shaping; a causal bit-slice equivalence theorem that prunes 99.74%99.74\% of right-hand candidate nodes across seven stages; and a closed-form F2\mathbf{F}_2 upper-half inverse paired with compact Q0−1Q_0^{-1} lookup tables. One CPU core solves arbitrary 19-step padded targets in 1.21.2–86.486.4 s (median 19.519.5 s) after an 1818 s table build. A 20-step padded preimage costs 246.62^{46.6} CPU-reference evaluations: 191191 node-hours on one 10-core Apple M4 CPU node (16 threads), or 9.09.0–22.222.2 GPU-hours on one NVIDIA L4. A companion Zero-a3a_3 bridge inverts the unpadded 20-step compression function in 238.12^{38.1} evaluations. We provide 46 self-verifying witnesses, including 55-byte preimages of SHA-256("abc") and 02560^{256}. These attacks cover 19–20 of 64 steps and do not threaten full SHA-256.

Introduction

SHA-256 [1] hashes an LL-bit message MM by appending mandatory Merkle–Damgård strengthening (FIPS 180-4 §5.1.1)—a single ’1’ bit (0x80 at a byte boundary), zero padding bits, and the 64-bit big-endian bit length LL in the final two 32-bit words W14W_{14} and W15W_{15}—before applying a 64-step Davies–Meyer compression function initialized to the standard initial value IV.

In the cryptanalysis of step-reduced SHA-256, a persistent divide has separated theoretical attacks from practical (demonstrated) preimages:

  • Theoretical preimage and collision attacks: Splice-and-cut meet-in-the-middle (MitM), partial-matching, biclique, and MILP-assisted attacks respect FIPS 180-4 padding from 24 steps [2] through 41–43 steps [3, 10], 45 steps [4], and 46–47 steps [8], with related differential and semi-free-start collision advances reaching 24–39 steps for SHA-256 (and 40 steps for SHA-224) [11, 12, 14, 15] building on the generalized characteristic framework introduced for SHA-1 in [13]. Unlike SHA-1, where full-round collisions have been practically computed [17, 18], all 24–47-step SHA-256 preimage attacks require between 22402^{240} and 2255.62^{255.6} compression evaluations and remain strictly theoretical.

  • Practical (demonstrated) preimages: Algebraic and SAT-based encodings produced padded preimages up to 16 steps [5] and three mailing-list challenge messages at 17 steps (posted without an attack specification) [16]. More recently, SAT/Cube-and-Conquer [6,

7] produced verified preimages at 18 and 19 steps for the unpadded compression function (where all 16 message words W0,…,W15W_0,\ldots,W_{15} are unconstrained 32-bit degrees of freedom), and Basra [9] introduced algebraic selector saturation and context shaping to solve 19- and 20-step unpadded compression targets as well as a 55-byte 20-step padded preimage for a structured target (padded_r20 in [9], dated 17 October 2026).

For a single-block 55-byte (L=440L = 440-bit) padded message, FIPS 180-4 [1] fixes 72 bits at the end of the message block:

W15=440 (0x000001b8),W14=0 (0x00000000),W13 mod 256=0x80.(1)W_{15} = 440\ (\text{0x000001b8}), \qquad W_{14} = 0\ (\text{0x00000000}), \qquad W_{13} \bmod256 = \text{0x80}. \tag*{(1)}

In backward-and-forward inversion of steps 0..18 (19-step) or 0..19 (20-step), W13,W14,W15W_{13}, W_{14}, W_{15} are tightly coupled with the message schedule expansion W16,…,W19W_{16},\ldots,W_{19} and the internal state window (a5,…,a12)(a_5,\ldots,a_{12}). Satisfying all 72 padding bits simultaneously with the selector-saturation and majority-absorption conditions [9] that decouple the left and right halves of the compression function is the central barrier to inverting arbitrary externally prescribed 256-bit targets for the padded 19- and 20-step hash functions.

Upfront Demonstration of 19-Step and 20-Step Padded SHA-256 Preimages

To illustrate our results concretely before entering the algebraic derivations, below are four self-verifying FIPS 180-4 padded preimages for 20-step and 19-step SHA-256 (SHA25620_{20} and SHA25619_{19} with standard IV, Davies–Meyer feed-forward, and mandatory padding [1]; complete 46-witness verification suite in § 8 and at https://github.com/srw/sha256-19-and-20-step-preimages-with-padding):

  1. 20-Step Single-Block Padded Preimage for FIPS 180-4 Test Vector H∗H^* = SHA-256(“abc”):

Target H*             = ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
55-Byte Message M     = edf6e70a7001ae71b900f18119aaa1fdf6c1179b4268891262a9539
                        be04d41236685e0c102e0ad23165e8b7157669819302ddcb3c68226
Padded Block W0..7    = edf6e70a 7001ae71 b900f181 19aaa1fd f6c1179b 42688912 62a9539b
                        e04d4123
Padded Block W8..15   = 6685e0c1 02e0ad23 165e8b71 57669819 302ddcb3 c6822680 00000000 000001
                        b8
Verification           : SHA256_20(M) == H*  (W13 & 0xff = 0x80, W14 = 0, W15 = 440 bits)
  1. 19-Step Single-Block Padded Preimages for H∗H^* = SHA-256(“abc”) and H∗H^* = 02560^{256}:

'abc' 55B Message      = 8ca254f8d04dd3fb04efaad6b1867588ffe833de49a144fedbf1839
                        422892dc9f5a9158d8fc063290a14a9a6c55dfa245642a0247ec45a
0^256 55B Message      = fc0c9d8eafb2fa329af316940c42a5eb9773cec39e4f7e396182628
                        7ae767638f92d4ce5fc5eb8cabd7606409364dda27a6c1bb5220246
Verification           : SHA256_19(M_abc) == SHA-256("abc") and SHA256_19(M_zero) == 0^256
  1. 20-Step Single-Block Padded Preimage for All-Zero Digest H∗H^* = 0…00\ldots0:

Target H*             = 0000000000000000000000000000000000000000000000000000000000000000
55-Byte Message M     = ec531306c85ad4ad211d2e1a03ece4d0ad4a0e6b4c2b9436b3bab
                        dcbd520597196f52c042b8cd95f1a39f71b58b47b0647c78e65416f
Padded Block W8..15   = 7196f52c 042b8cd9 5f1a39f7 1b58b47b 0647c78e 65416f80 00000000 000001
                        b8
Verification           : SHA256_20(M) == 0^256  (W13 & 0xff = 0x80, W14 = 0, W15 = 440 bits)

20-Step & 19-Step Two-Block (119-Byte, Plain-ASCII Block 1) Padded Preimages for H∗=SHA⁡H^* = \operatorname{SHA}-256(“”):

Target H∗H^* = e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 Block 1 (64B ASCII)= "This first block is plain text; the second one was computed....." 20-Step Block 2 M2 = df28e21bb6b61202ba87baa72096ee0a3ac325cf1f12056e7cfe2ae                     1735b4d106b8f6e0b22eb9b504ed9368991944b0a115a934f17c2c4 19-Step Block 2 M2 = fe409cc930128a720481f86c0503d7a018519a129df449139720bb5                     eef520895f8b515685bb404817be301880f0caabe02fc9e5f1c95c0 Padding Suffix : ...80 00000000 000003b8 (L = 952 bits = 119 bytes; full Merkle-                     Damgard 2-block chaining)

(Note on Table 1.1: In Khovratovich et al. [4], 45 steps is a full hash preimage and 52 steps is a compression pseudo-preimage; in Basra [9], padded_r20 solves a structured digest [c799d851...] constructed with e9=e10=e15=0xfffffff ⁣fe_9 = e_{10} = e_{15} = \mathrm{0xfffffff\!f} and a5=a6=a10a_5 = a_6 = a_{10}. For our solvers, we distinguish a chosen-target 19-step padded preimage—solving a prescribed 19-step digest H19∗H_{19}^* where a12…a19a_{12}\ldots a_{19} are fixed, taking 1.2–86.4 s of single-core search time [median 19.45 s ≈\approx 19.5 s] in src/pre19.c after a 16.8–19.1 s [≈18\approx18 s] one-time 2292^{29}-entry table build—from a 19-step bridge candidate (sol19) generated at 6,242.8 sol19/s on one 10-core Apple M4M4 CPU [16 threads] in solve20_padded_fast.c [or 53,847.5–132,888.7 sol19/s in supplementary 1×L41\times L4 GPU slice telemetry in solve20_padded_cuda.cu] during a 20-step search where a12a_{12} is free. Elapsed-time proxy CPU-ref multiplies wall-clock seconds by the measured same-host 10-core Apple M4M4 CPU [16 threads] 20-step SHA-256 reference rate of 151.25 M evals/s, where 1 node-hour (1 node-h) =238.99= 2^{38.99} CPU-ref; see § 6.5.)

Technical Contributions and Organization

  1. Closed-Form Pivot Inversion of FIPS 180-4 Padding Compatible with Exact Context Shaping (§ 10–§ 4, [E15]–[E22]): Basra [9] showed that the FIPS 180-4 padding words (W15=440W_{15} = 440, W14=0W_{14} = 0, W13 mod 256=0x80W_{13} \bmod256 = \mathrm{0x80}) can be absorbed backward into (a7,a6,a5)(a_7, a_6, a_5) at the cost of three context words and demonstrated a 55-byte 20-step padded witness for a structured target (padded_r20 in [9]). For arbitrary externally prescribed 256-bit targets, we show how to absorb W15=440W_{15} = 440 and W14=0W_{14} = 0 into (a8,a7)(a_8, a_7) while inverting (W13 mod 256)=0x80(W_{13} \bmod256) = \mathrm{0x80} directly via 8 bit-disjoint pivot bits ({18, 25...31}) of Σ1(e13)\Sigma_1(e_{13}) with 100% inner-loop validity—leaving (a5,a6)(a_5, a_6) unconstrained by padding absorption so they can satisfy exact shaping Dshape=a5⊕a6=0D_{\mathrm{shape}} = a_5 \oplus a_6 = 0 alongside Ch-annihilation (e15=0xffffffff,a10=a11e_{15} = \mathrm{0xffffffff}, a_{10} = a_{11}).

  1. Causal Bit-Slice Right-Context Pruning ("Carry-Sudoku," § 5, [E23]–[E25]): We prove Theorem 1 ([E23]): a5=a6a_5 = a_6 decomposes into a lower-triangular carry condition ((S⊕X)∧D)=0((S \oplus X) \land D) = 0 (where D=a8⊕a7D = a_8 \oplus a_7 is the bitwise XOR mask that is completely independent of a6a_6 and Σ0(a9)\Sigma_0(a_9)), and a complementary condition ((a6⊕S)∧¬D)=0((a_6 \oplus S) \land\lnot D) = 0. Pruning e13e_{13} across 7 causal bit-slices reduces the 2242^{24} candidate space to an average of 43,580 node evaluations per a12a_{12} block (385×385\times / 99.74% node reduction across all 7 stages,

evaluating Σ0(a9)\Sigma_0(a_9) only on the ≈1,660\approx1{,}660–2,1492{,}149 full-carry survivors per block, i.e., 99.99% pre-Σ0(a9)\Sigma_0(a_9) pruning) with 100% completeness across each 2242^{24}-candidate a12a_{12} block (and the estimated U≈1.68×107≈224.0U \approx1.68 \times10^7 \approx2^{24.0} exact Dshape=0D_{\mathrm{shape}} = 0 contexts per 20-step target).

  1. Closed-Form F2\mathbb{F}_2 Reconstruction, Compact Q0−1Q_0^{-1} Tables ("Slot-Sudoku"), and T16T_{16} Twin Coalescing (§6, [E27]–[E37], [E42]–[E45]): We prove Theorem 2 ([E28]–[E29]), recovering the upper 16 bits of u∈Q0−1(y)u \in Q_0^{-1}(y) in closed form in registers with zero lookup tables. Pairing this with compact Q0−1Q_0^{-1} tables achieves 6,242.8 sol19/s on our host-verifiable 10-core Apple M4 CPU solver (solve20_padded_fast.c, 16 threads), and 53,847.5–132,888.7 sol19/s on genuine contexts in supplementary 1× NVIDIA L4 GPU slice telemetry (solve20_padded_cuda.cu).

  1. Zero-a3a_3 Bi-Directional Bridge, Complete 46-Witness Suite, and Construction-Specific Bottleneck Analysis (§7–§9, [E38]–[E41]): We present a Zero-a3a_3 bridge for unpadded 20-step compression (§7), provide the complete, un-truncated hex witnesses for all 46 distinct 19-step and 20-step single-block padded, two-block chosen-ASCII-prefix padded, unpadded, and regression benchmarks (§8, 48 checks including "abc" demo/benchmark overlap), and analyze 15 explored sub-2322^{32} algebraic and statistical directions characterizing the degree-of-freedom conservation laws of the Carry-Sudoku / Slot-Sudoku architecture (§9.2).

Preliminaries and the Scalar aa-Sequence Formulation

All arithmetic is modulo 2322^{32}. Denote 32-bit right rotation by ROR⁡(x,n)\operatorname{ROR}(x,n) and logical right shift by SHR⁡(x,n)\operatorname{SHR}(x,n). The SHA-256 boolean and F2\mathbb{F}_2-linear functions [1] are:

Ch⁡(e,f,g)=(e∧f)⊕(¬e∧g),Maj⁡(a,b,c)=(a∧b)⊕(a∧c)⊕(b∧c),Σ0(x)=ROR⁡(x,2)⊕ROR⁡(x,13)⊕ROR⁡(x,22),Σ1(x)=ROR⁡(x,6)⊕ROR⁡(x,11)⊕ROR⁡(x,25),σ0(x)=ROR⁡(x,7)⊕ROR⁡(x,18)⊕SHR⁡(x,3),σ1(x)=ROR⁡(x,17)⊕ROR⁡(x,19)⊕SHR⁡(x,10).(2)\begin{aligned} \operatorname{Ch}(e,f,g) &= (e \land f) \oplus(\lnot e \land g), & \operatorname{Maj}(a,b,c) &= (a \land b) \oplus(a \land c) \oplus(b \land c), \\ \Sigma_0(x) &= \operatorname{ROR}(x,2) \oplus\operatorname{ROR}(x,13) \oplus\operatorname{ROR}(x,22), & \Sigma_1(x) &= \operatorname{ROR}(x,6) \oplus\operatorname{ROR}(x,11) \oplus\operatorname{ROR}(x,25), \\ \sigma_0(x) &= \operatorname{ROR}(x,7) \oplus\operatorname{ROR}(x,18) \oplus\operatorname{SHR}(x,3), & \sigma_1(x) &= \operatorname{ROR}(x,17) \oplus\operatorname{ROR}(x,19) \oplus\operatorname{SHR}(x,10). \tag*{(2)} \end{aligned}

For step indices t≥16t \ge16, the message schedule expands W0,…,W15W_0,\ldots,W_{15} via:

Wt=σ1(Wt−2)+Wt−7+σ0(Wt−15)+Wt−16.(3)W_t = \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16}. \tag*{(3)}

Following [9], we define the coupled schedule operator Q0:Z232→Z232Q_0 : \mathbb{Z}_{2^{32}} \to\mathbb{Z}_{2^{32}} by:

Q0(u)=σ0(u)−u(mod232).(4)Q_0(u) = \sigma_0(u) - u \pmod{2^{32}}. \tag*{(4)}

Reduction to the Scalar aa-Sequence ([E5]–[E7])

References

  1. [1]National Institute of Standards and Technology: Secure Hash Standard (SHS). FIPS PUB 180-4, U.S. Department of Commerce (2015).
  2. [2]Isobe, T., Shibutani, K.: Preimage Attacks on Reduced Tiger and SHA-2. In: Dunkelman, O. (ed.) Fast Software Encryption – FSE 2009, LNCS, vol. 5665, pp. 139–155. Springer (2009).DOI
  3. [3]Aoki, K., Guo, J., Matusiewicz, K., Sasaki, Y., Wang, L.: Preimages for Step-Reduced SHA-2. In: Matsui, M. (ed.) Advances in Cryptology – ASIACRYPT 2009, LNCS, vol. 5912, pp. 578–597. Springer (2009).DOI
  4. [4]Khovratovich, D., Rechberger, C., Savelyeva, A.: Biliques for Preimages: Attacks on Skein-512 and the SHA-2 Family. In: Canteaut, A. (ed.) Fast Software Encryption – FSE 2012, LNCS, vol. 7549, pp. 244–263. Springer (2012).DOI
  5. [5]Homsirikamol, E., Morawiecki, P., Rogawski, M., Srebny, M.: Security Margin Evaluation of SHA-3 Contest Finalists Through SAT-Based Attacks. In: Cortesi, A. et al. (eds.) CISIM 2012, LNCS, vol. 7564, pp. 56–67. Springer (2012) (16-round SHA-256 SAT evaluation in ~1 h, Table 1).
  6. [6]Davydov, V. V., Pikhtovnikov, M. D., Kiryanova, A. P., Zaikin, O. S.: Cryptographic Strength Analysis of the SHA-256 Hash Function Using the SAT Approach. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, vol. 25(3), pp. 428–437 (2025). DOI: 10.17586/2226-1494-2025-25-3-428-437.DOI
  7. [7]Zaikin, O.: Preimage Attacks on Round-Reduced MD5, SHA-1, and SHA-256 Using Parameterized SAT Solver. Constraints (published 23 Jan 2026). DOI: 10.1007/s10601-025-09383-o (19-step unpadded all-ones target in 18 h 33 min on 192 CPU cores, §5 / Table 2).DOI
  8. [8]Guo, J., Li, H., Liu, M., Wang, S., Zhang, T.: Dual-Syncopation Meet-in-the-Middle Attacks: New Results on SHA-2 and MD5. In: Advances in Cryptology – EUROCRYPT 2026. Springer (2026); IACR ePrint 2026/353.DOI
  9. [9]Basra, K. S.: Oracle-Free Preimage Attack on 19-Round Reduced SHA-256, The 20-Round Barrier for Table-Based Preimage Attacks on SHA-256, and README.md, padded_r19/README.md, padded_r20/README.md (structured-target 20-round padded witness, 17 Oct 2026). GitHub repository and manuscripts, https://github.com/kamb-code/sha256- r19-preimage (Aug–Oct 2026).
  10. [10]Sasaki, Y., Wang, L., Aoki, K.: Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512. IACR Cryptology ePrint Archive, Report 2009/479 (2009).
  11. [11]Mendel, F., Nad, T., Schläffer, M.: Improving Local Collisions: New Attacks on Reduced SHA-256. In: Johansson, T., Nguyen, P. Q. (eds.) Advances in Cryptology – EUROCRYPT 2013, LNCS, vol. 7881, pp. 262–278. Springer (2013).DOI
  12. [12]Mendel, F., Nad, T., Schläffer, M.: Finding SHA-2 Characteristics: Searching through a Minefield of Contradictions. In: Lee, D. H., Wang, X. (eds.) Advances in Cryptology – ASIACRYPT 2011, LNCS, vol. 7073, pp. 288–307. Springer (2011).DOI
  13. [13]De Cannière, C., Rechberger, C.: Finding SHA-1 Characteristics: General Results and Applications. In: Lai, X., Chen, K. (eds.) Advances in Cryptology – ASIACRYPT 2006, LNCS, vol. 4284, pp. 1–20. Springer (2006) (generalized characteristic framework introduced for SHA-1 and adapted to SHA-2 in [11, 12]).
  14. [14]Li, Y., Liu, F., Wang, G.: New Records in Collision Attacks on SHA-2. In: Joye, M., Leander, G. (eds.) Advances in Cryptology – EUROCRYPT 2024, LNCS, vol. 14651, pp. 158–186. Springer (2024); IACR ePrint 2024/349 (39-step SHA-256 semi-free-start and 40-step SHA-224 free-start collisions).DOI
  15. [15]Dobraunig, C., Eichlseder, M., Mendel, F.: Analysis of SHA-512/224 and SHA-512/256. In: Iwata, T., Cheon, J. H. (eds.) Advances in Cryptology – ASIACRYPT 2015, LNCS, vol. 9453, pp. 612–630. Springer (2015).DOI
  16. [16]McDair: 17-Step Reduced SHA-256 Preimage Challenge Witnesses. Cryptography Mailing List (metzdowd.com, 2024-April/001334.html), Mar–Apr 2024 (archived mailing-list posts of three 17-step messages without a published attack method).
  17. [17]Stevens, M., Bursztein, E., Karpman, P., Albertini, A., Markov, Y.: The First Collision for Full SHA-1. In: Katz, J., Shacham, H. (eds.) Advances in Cryptology – CRYPTO 2017, LNCS, vol. 10401, pp. 570–596. Springer (2017).DOI
  18. [18]Leurent, G., Peyrin, T.: SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust. In: 29th USENIX Security Symposium (USENIX Security 2020), pp. 1839–1856 (2020).

Paper details

vlnc:W_qvemnyvk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents