Introduction
SHA-256 [1 ] hashes an L L L -bit message M M M 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 L L L in the final two 32-bit words W 14 W_{14} W 14 and W 15 W_{15} W 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 2 240 2^{240} 2 240 and 2 255.6 2^{255.6} 2 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 W 0 , … , W 15 W_0,\ldots,W_{15} W 0 , … , 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 = 440 L = 440 L = 440 -bit) padded message, FIPS 180-4 [1 ] fixes 72 bits at the end of the message block:
W 15 = 440 ( 0x000001b8 ) , W 14 = 0 ( 0x00000000 ) , W 13 m o d 256 = 0x80 . (1) W_{15} = 440\ (\text{0x000001b8}), \qquad W_{14} = 0\ (\text{0x00000000}), \qquad W_{13} \bmod256 = \text{0x80}. \tag*{(1)} W 15 = 440 ( 0x000001b8 ) , W 14 = 0 ( 0x00000000 ) , W 13 mod 256 = 0x80 . (1)
In backward-and-forward inversion of steps 0..18 (19-step) or 0..19 (20-step), W 13 , W 14 , W 15 W_{13}, W_{14}, W_{15} W 13 , W 14 , W 15 are tightly coupled with the message schedule expansion W 16 , … , W 19 W_{16},\ldots,W_{19} W 16 , … , W 19 and the internal state window ( a 5 , … , a 12 ) (a_5,\ldots,a_{12}) ( a 5 , … , 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} 20 and SHA25619 _{19} 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 ):
20-Step Single-Block Padded Preimage for FIPS 180-4 Test Vector H ∗ 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)
19-Step Single-Block Padded Preimages for H ∗ H^* H ∗ = SHA-256(“abc”) and H ∗ H^* H ∗ = 0 256 0^{256} 0 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
20-Step Single-Block Padded Preimage for All-Zero Digest H ∗ H^* H ∗ = 0 … 0 0\ldots0 0 … 0 :
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} H ∗ = SHA -256(“”):
Target H ∗ 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 e 9 = e 10 = e 15 = 0 x f f f f f f f f e_9 = e_{10} = e_{15} = \mathrm{0xfffffff\!f} e 9 = e 10 = e 15 = 0xfffffff f and a 5 = a 6 = a 10 a_5 = a_6 = a_{10} a 5 = a 6 = a 10 . For our solvers, we distinguish a chosen-target 19-step padded preimage —solving a prescribed 19-step digest H 19 ∗ H_{19}^* H 19 ∗ where a 12 … a 19 a_{12}\ldots a_{19} a 12 … 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 ≈ 18 s] one-time 2 29 2^{29} 2 29 -entry table build—from a 19-step bridge candidate (sol19) generated at 6,242.8 sol19/s on one 10-core Apple M 4 M4 M 4 CPU [16 threads] in solve20_padded_fast.c [or 53,847.5–132,888.7 sol19/s in supplementary 1 × L 4 1\times L4 1 × L 4 GPU slice telemetry in solve20_padded_cuda.cu] during a 20-step search where a 12 a_{12} a 12 is free. Elapsed-time proxy CPU-ref multiplies wall-clock seconds by the measured same-host 10-core Apple M 4 M4 M 4 CPU [16 threads] 20-step SHA-256 reference rate of 151.25 M evals/s, where 1 node-hour (1 node-h) = 2 38.99 = 2^{38.99} = 2 38.99 CPU-ref; see § 6.5 .)
Technical Contributions and Organization
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 (W 15 = 440 W_{15} = 440 W 15 = 440 , W 14 = 0 W_{14} = 0 W 14 = 0 , W 13 m o d 256 = 0 x 80 W_{13} \bmod256 = \mathrm{0x80} W 13 mod 256 = 0x80 ) can be absorbed backward into ( a 7 , a 6 , a 5 ) (a_7, a_6, a_5) ( 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 W 15 = 440 W_{15} = 440 W 15 = 440 and W 14 = 0 W_{14} = 0 W 14 = 0 into ( a 8 , a 7 ) (a_8, a_7) ( a 8 , a 7 ) while inverting ( W 13 m o d 256 ) = 0 x 80 (W_{13} \bmod256) = \mathrm{0x80} ( W 13 mod 256 ) = 0x80 directly via 8 bit-disjoint pivot bits ({18, 25...31}) of Σ 1 ( e 13 ) \Sigma_1(e_{13}) Σ 1 ( e 13 ) with 100% inner-loop validity—leaving ( a 5 , a 6 ) (a_5, a_6) ( a 5 , a 6 ) unconstrained by padding absorption so they can satisfy exact shaping D s h a p e = a 5 ⊕ a 6 = 0 D_{\mathrm{shape}} = a_5 \oplus a_6 = 0 D shape = a 5 ⊕ a 6 = 0 alongside Ch-annihilation (e 15 = 0 x f f f f f f f f , a 10 = a 11 e_{15} = \mathrm{0xffffffff}, a_{10} = a_{11} e 15 = 0xffffffff , a 10 = a 11 ).
Causal Bit-Slice Right-Context Pruning ("Carry-Sudoku," § 5 , [E23]–[E25]): We prove Theorem 1 ([E23]): a 5 = a 6 a_5 = a_6 a 5 = a 6 decomposes into a lower-triangular carry condition ( ( S ⊕ X ) ∧ D ) = 0 ((S \oplus X) \land D) = 0 (( S ⊕ X ) ∧ D ) = 0 (where D = a 8 ⊕ a 7 D = a_8 \oplus a_7 D = a 8 ⊕ a 7 is the bitwise XOR mask that is completely independent of a 6 a_6 a 6 and Σ 0 ( a 9 ) \Sigma_0(a_9) Σ 0 ( a 9 ) ), and a complementary condition ( ( a 6 ⊕ S ) ∧ ¬ D ) = 0 ((a_6 \oplus S) \land\lnot D) = 0 (( a 6 ⊕ S ) ∧ ¬ D ) = 0 . Pruning e 13 e_{13} e 13 across 7 causal bit-slices reduces the 2 24 2^{24} 2 24 candidate space to an average of 43,580 node evaluations per a 12 a_{12} a 12 block (385 × 385\times 385 × / 99.74% node reduction across all 7 stages,
evaluating Σ 0 ( a 9 ) \Sigma_0(a_9) Σ 0 ( a 9 ) only on the ≈ 1,660 \approx1{,}660 ≈ 1 , 660 –2,149 2{,}149 2 , 149 full-carry survivors per block, i.e., 99.99% pre-Σ 0 ( a 9 ) \Sigma_0(a_9) Σ 0 ( a 9 ) pruning) with 100% completeness across each 2 24 2^{24} 2 24 -candidate a 12 a_{12} a 12 block (and the estimated U ≈ 1.68 × 10 7 ≈ 2 24.0 U \approx1.68 \times10^7 \approx2^{24.0} U ≈ 1.68 × 1 0 7 ≈ 2 24.0 exact D s h a p e = 0 D_{\mathrm{shape}} = 0 D shape = 0 contexts per 20-step target).
Closed-Form F 2 \mathbb{F}_2 F 2 Reconstruction, Compact Q 0 − 1 Q_0^{-1} Q 0 − 1 Tables ("Slot-Sudoku"), and T 16 T_{16} T 16 Twin Coalescing (§6, [E27]–[E37], [E42]–[E45]): We prove Theorem 2 ([E28]–[E29]), recovering the upper 16 bits of u ∈ Q 0 − 1 ( y ) u \in Q_0^{-1}(y) u ∈ Q 0 − 1 ( y ) in closed form in registers with zero lookup tables. Pairing this with compact Q 0 − 1 Q_0^{-1} Q 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).
Zero-a 3 a_3 a 3 Bi-Directional Bridge, Complete 46-Witness Suite, and Construction-Specific Bottleneck Analysis (§7–§9, [E38]–[E41]): We present a Zero-a 3 a_3 a 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-2 32 2^{32} 2 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 a a a -Sequence Formulation
All arithmetic is modulo 2 32 2^{32} 2 32 . Denote 32-bit right rotation by ROR ( x , n ) \operatorname{ROR}(x,n) ROR ( x , n ) and logical right shift by SHR ( x , n ) \operatorname{SHR}(x,n) SHR ( x , n ) . The SHA-256 boolean and F 2 \mathbb{F}_2 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} Ch ( e , f , g ) Σ 0 ( x ) σ 0 ( x ) = ( e ∧ f ) ⊕ ( ¬ e ∧ g ) , = ROR ( x , 2 ) ⊕ ROR ( x , 13 ) ⊕ ROR ( x , 22 ) , = ROR ( x , 7 ) ⊕ ROR ( x , 18 ) ⊕ SHR ( x , 3 ) , Maj ( a , b , c ) Σ 1 ( x ) σ 1 ( x ) = ( a ∧ b ) ⊕ ( a ∧ c ) ⊕ ( b ∧ c ) , = ROR ( x , 6 ) ⊕ ROR ( x , 11 ) ⊕ ROR ( x , 25 ) , = ROR ( x , 17 ) ⊕ ROR ( x , 19 ) ⊕ SHR ( x , 10 ) . (2)
For step indices t ≥ 16 t \ge16 t ≥ 16 , the message schedule expands W 0 , … , W 15 W_0,\ldots,W_{15} W 0 , … , W 15 via:
W t = σ 1 ( W t − 2 ) + W t − 7 + σ 0 ( W t − 15 ) + W t − 16 . (3) W_t = \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16}. \tag*{(3)} W t = σ 1 ( W t − 2 ) + W t − 7 + σ 0 ( W t − 15 ) + W t − 16 . (3)
Following [9 ] , we define the coupled schedule operator Q 0 : Z 2 32 → Z 2 32 Q_0 : \mathbb{Z}_{2^{32}} \to\mathbb{Z}_{2^{32}} Q 0 : Z 2 32 → Z 2 32 by:
Q 0 ( u ) = σ 0 ( u ) − u ( m o d 2 32 ) . (4) Q_0(u) = \sigma_0(u) - u \pmod{2^{32}}. \tag*{(4)} Q 0 ( u ) = σ 0 ( u ) − u ( mod 2 32 ) . (4)
Reduction to the Scalar a a a -Sequence ([E5]–[E7])
Let ( a t , b t , c t , d t , e t , f t , g t , h t ) (a_t,b_t,c_t,d_t,e_t,f_t,g_t,h_t) ( a t , b t , c t , d t , e t , f t , g t , h t ) be the 8 working registers after step t − 1 t-1 t − 1 (with t = 0 t=0 t = 0 denoting IV). Because each step shifts b ← a b \leftarrow a b ← a , c ← b c \leftarrow b c ← b , d ← c d \leftarrow c d ← c and f ← e f \leftarrow e f ← e , g ← f g \leftarrow f g ← f , h ← g h \leftarrow g h ← g , the entire 8-register trajectory across R R R steps is uniquely parameterized by a single scalar sequence a − 7 , a − 6 , … , a R a_{-7},a_{-6},\ldots,a_R a − 7 , a − 6 , … , a R [3 , 9 ] :
Initial Boundary (s ∈ { − 7 , … , 0 } s \in\{-7,\ldots,0\} s ∈ { − 7 , … , 0 } ): Fixed uniquely by IV (window_from_state in solve20_padded_fast.c):
( a 0 , a − 1 , a − 2 , a − 3 ) = ( I V 0 , I V 1 , I V 2 , I V 3 ) , ( e 0 , e − 1 , e − 2 , e − 3 ) = ( I V 4 , I V 5 , I V 6 , I V 7 ) . (5) (a_0,a_{-1},a_{-2},a_{-3}) = (\mathrm{IV}_0,\mathrm{IV}_1,\mathrm{IV}_2,\mathrm{IV}_3), \qquad(e_0,e_{-1},e_{-2},e_{-3}) = (\mathrm{IV}_4,\mathrm{IV}_5,\mathrm{IV}_6,\mathrm{IV}_7). \tag*{(5)} ( a 0 , a − 1 , a − 2 , a − 3 ) = ( IV 0 , IV 1 , IV 2 , IV 3 ) , ( e 0 , e − 1 , e − 2 , e − 3 ) = ( IV 4 , IV 5 , IV 6 , IV 7 ) . (5)
Terminal Boundary (s ∈ { R − 7 , … , R } s \in\{R-7,\ldots,R\} s ∈ { R − 7 , … , R } ): For an R R R -step target digest H ∗ = ( H 0 ∗ , … , H 7 ∗ ) H^*=(H_0^*,\ldots,H_7^*) H ∗ = ( H 0 ∗ , … , H 7 ∗ ) , Davies–Meyer feed-forward fixes the terminal state s t i = H i ∗ − I V i st_i=H_i^*-\mathrm{IV}_i s t i = H i ∗ − IV i , which uniquely determines the 8 terminal words a R − 7 , … , a R a_{R-7},\ldots,a_R a R − 7 , … , a R .
For R = 19 : a 12 , a 13 , … , a 19 are fixed by H ∗ − I V , For R = 20 : a 13 , a 14 , … , a 20 are fixed by H ∗ − I V . (6) \begin{aligned}
\text{For } R=19: \quad&a_{12},a_{13},\ldots,a_{19}\text{ are fixed by }H^*-\mathrm{IV},\\
\text{For } R=20: \quad&a_{13},a_{14},\ldots,a_{20}\text{ are fixed by }H^*-\mathrm{IV}. \tag*{(6)}
\end{aligned} For R = 19 : For R = 20 : a 12 , a 13 , … , a 19 are fixed by H ∗ − IV , a 13 , a 14 , … , a 20 are fixed by H ∗ − IV . (6)
Internal State & Message Recovery: For every step index s s s and t ∈ { 0 , … , R − 1 } t \in\{0,\ldots,R-1\} t ∈ { 0 , … , R − 1 } , the e e e -register e s e_s e s is an exact function of five consecutive a a a -words ( a s − 4 , … , a s ) (a_{s-4},\ldots,a_s) ( a s − 4 , … , a s ) , and the message word W t W_t W t is an exact function of a t − 3 a_{t-3} a t − 3 together with five e e e -words ( e t − 3 , … , e t + 1 ) (e_{t-3},\ldots,e_{t+1}) ( e t − 3 , … , e t + 1 ) , spanning nine consecutive a a a -words a t − 7 , … , a t + 1 a_{t-7},\ldots,a_{t+1} a t − 7 , … , a t + 1 when expanded; E_arr and Wt_arr in solve20_padded_fast.c):
e s = a s − Σ 0 ( a s − 1 ) − Maj ( a s − 1 , a s − 2 , a s − 3 ) + a s − 4 , W t = e t + 1 − a t − 3 − e t − 3 − Σ 1 ( e t ) − Ch ( e t , e t − 1 , e t − 2 ) − K t . (7) \begin{aligned}
e_s &= a_s-\Sigma_0(a_{s-1})-\operatorname{Maj}(a_{s-1},a_{s-2},a_{s-3})+a_{s-4},\\
W_t &= e_{t+1}-a_{t-3}-e_{t-3}-\Sigma_1(e_t)-\operatorname{Ch}(e_t,e_{t-1},e_{t-2})-K_t. \tag*{(7)}
\end{aligned} e s W t = a s − Σ 0 ( a s − 1 ) − Maj ( a s − 1 , a s − 2 , a s − 3 ) + a s − 4 , = e t + 1 − a t − 3 − e t − 3 − Σ 1 ( e t ) − Ch ( e t , e t − 1 , e t − 2 ) − K t . (7)
Thus, for R = 20 R=20 R = 20 (resp. R = 19 R=19 R = 19 ), the only free internal state variables between the IV boundary and the target boundary are the 12 words a 1 , a 2 , … , a 12 a_1,a_2,\ldots,a_{12} a 1 , a 2 , … , a 12 (resp. 11 words a 1 , … , a 11 a_1,\ldots,a_{11} a 1 , … , a 11 ). Any assignment to these words automatically hashes to H ∗ H^* H ∗ after R R R steps if and only if the recovered message words W 0 , … , W R − 1 W_0,\ldots,W_{R-1} W 0 , … , W R − 1 from [E7] satisfy the message schedule equations [E3] for t = 16 , … , R − 1 t=16,\ldots,R-1 t = 16 , … , R − 1 and the FIPS 180-4 padding constraints [E1].
Selector Saturation and Exact Context Shaping (D s h a p e = 0 D_{\mathrm{shape}}=0 D shape = 0 )
In general, W 16 , W 17 , W 18 , W 19 W_{16},W_{17},W_{18},W_{19} W 16 , W 17 , W 18 , W 19 depend on the Left variables ( a 1 , a 2 , a 3 , a 4 ) (a_1,a_2,a_3,a_4) ( a 1 , a 2 , a 3 , a 4 ) both through the early message words ( W 0 , W 1 , W 2 , W 3 , W 4 ) (W_0,W_1,W_2,W_3,W_4) ( W 0 , W 1 , W 2 , W 3 , W 4 ) on the right-hand side of [E3] and through ( W 9 , W 10 , W 11 , W 12 , W 14 , W 15 ) (W_9,W_{10},W_{11},W_{12},W_{14},W_{15}) ( W 9 , W 10 , W 11 , W 12 , W 14 , W 15 ) via the state words e 5 , e 6 , e 7 , e 8 e_5,e_6,e_7,e_8 e 5 , e 6 , e 7 , e 8 .
Following Basra’s selector-saturation principle [9 ] , we pin the two middle selector registers:
e 9 = 0 x f f f f f f f f , e 10 = 0 x f f f f f f f f . (8) e_9=0xffffffff,\qquad e_{10}=0xffffffff. \tag*{(8)} e 9 = 0 x f f f f f f f f , e 10 = 0 x f f f f f f f f . (8)
Because Ch ( 0 x f f f f f f f f , y , z ) = y \operatorname{Ch}(0xffffffff,y,z)=y Ch ( 0 x f f f f f f f f , y , z ) = y , setting e 9 = e 10 = 0 x f f f f f f f f e_9=e_{10}=0xffffffff e 9 = e 10 = 0 x f f f f f f f f blocks ( e 7 , e 8 ) (e_7,e_8) ( e 7 , e 8 ) inside Ch ( e 9 , e 8 , e 7 ) = e 8 \operatorname{Ch}(e_9,e_8,e_7)=e_8 Ch ( e 9 , e 8 , e 7 ) = e 8 , Ch ( e 10 , e 9 , e 8 ) = 0 x f f f f f f f f \operatorname{Ch}(e_{10},e_9,e_8)=0xffffffff Ch ( e 10 , e 9 , e 8 ) = 0 x f f f f f f f f , and Ch ( e 11 , e 10 , e 9 ) = 0 x f f f f f f f f \operatorname{Ch}(e_{11},e_{10},e_9)=0xffffffff Ch ( e 11 , e 10 , e 9 ) = 0 x f f f f f f f f . Expanding [E7] at s = 9 , 10 s=9,10 s = 9 , 10 expresses a 5 a_5 a 5 and a 6 a_6 a 6 purely in terms of the Right words ( a 7 , a 8 , a 9 , a 10 ) (a_7,a_8,a_9,a_{10}) ( a 7 , a 8 , a 9 , a 10 ) :
a 5 = 0 x f f f f f f f f − a 9 + Σ 0 ( a 8 ) + Maj ( a 8 , a 7 , a 6 ) , a 6 = 0 x f f f f f f f f − a 10 + Σ 0 ( a 9 ) + Maj ( a 9 , a 8 , a 7 ) . (9) \begin{aligned}
a_5 &= 0xffffffff-a_9+\Sigma_0(a_8)+\operatorname{Maj}(a_8,a_7,a_6),\\
a_6 &= 0xffffffff-a_{10}+\Sigma_0(a_9)+\operatorname{Maj}(a_9,a_8,a_7). \tag*{(9)}
\end{aligned} a 5 a 6 = 0 x f f f f f f f f − a 9 + Σ 0 ( a 8 ) + Maj ( a 8 , a 7 , a 6 ) , = 0 x f f f f f f f f − a 10 + Σ 0 ( a 9 ) + Maj ( a 9 , a 8 , a 7 ) . (9)
Exact Shaping (D s h a p e = a 5 ⊕ a 6 = 0 D_{\mathrm{shape}}=a_5\oplus a_6=0 D shape = a 5 ⊕ a 6 = 0 ) vs. Chosen-Target 19-Step Shaping ([E10]–[E14])
Let D s h a p e : = a 5 ⊕ a 6 D_{\mathrm{shape}}:=a_5\oplus a_6 D shape := a 5 ⊕ a 6 denote the bitwise XOR difference between a 5 a_5 a 5 and a 6 a_6 a 6 (note that D s h a p e = 0 ⟺ a 5 = a 6 ⟺ a 6 − a 5 ≡ 0 ( m o d 2 32 ) D_{\mathrm{shape}}=0\Longleftrightarrow a_5=a_6\Longleftrightarrow a_6-a_5\equiv0\pmod{2^{32}} D shape = 0 ⟺ a 5 = a 6 ⟺ a 6 − a 5 ≡ 0 ( mod 2 32 ) ). Under [E8] (e 9 = e 10 = 0 x f f f f f f f f e_9=e_{10}=0xffffffff e 9 = e 10 = 0 x f f f f f f f f ), Ch ( e 9 , e 8 , e 7 ) = e 8 \operatorname{Ch}(e_9,e_8,e_7)=e_8 Ch ( e 9 , e 8 , e 7 ) = e 8 and Ch ( e 10 , e 9 , e 8 ) = Ch ( e 11 , e 10 , e 9 ) = 0 x f f f f f f f f \operatorname{Ch}(e_{10},e_9,e_8)=\operatorname{Ch}(e_{11},e_{10},e_9)=0xffffffff Ch ( e 10 , e 9 , e 8 ) = Ch ( e 11 , e 10 , e 9 ) = 0 x f f f f f f f f . Expanding [E7] at t = 9 , 10 , 11 , 12 t=9,10,11,12 t = 9 , 10 , 11 , 12 isolates how W 9 , W 10 , W 11 , W 12 W_9,W_{10},W_{11},W_{12} W 9 , W 10 , W 11 , W 12 depend on the Left variables ( a 1 , a 2 , a 3 , a 4 ) (a_1,a_2,a_3,a_4) ( a 1 , a 2 , a 3 , a 4 ) [9 ] :
W 9 = c 9 − a 2 − a 4 + Maj ( a 5 , a 4 , a 3 ) , W 10 = c 10 − a 3 + ( Maj ( a 6 , a 5 , a 4 ) − ( a 6 ∧ a 5 ) ) , W 11 = c 11 − a 4 , W 12 = c 12 = const ( R i g h t ) , (10) \begin{aligned}
W_9 &= c_9-a_2-a_4+\operatorname{Maj}(a_5,a_4,a_3),\\
W_{10} &= c_{10}-a_3+\left(\operatorname{Maj}(a_6,a_5,a_4)-(a_6\mathbin{\wedge}a_5)\right),\\
W_{11} &= c_{11}-a_4,\\
W_{12} &= c_{12}=\operatorname{const}(\mathrm{Right}), \tag*{(10)}
\end{aligned} W 9 W 10 W 11 W 12 = c 9 − a 2 − a 4 + Maj ( a 5 , a 4 , a 3 ) , = c 10 − a 3 + ( Maj ( a 6 , a 5 , a 4 ) − ( a 6 ∧ a 5 ) ) , = c 11 − a 4 , = c 12 = const ( Right ) , (10)
where c 9 , c 10 , c 11 , c 12 c_9,c_{10},c_{11},c_{12} c 9 , c 10 , c 11 , c 12 depend only on the Right context ( a 5 , … , a 13 ) (a_5,\ldots,a_{13}) ( a 5 , … , a 13 ) .
When we enforce exact context shaping :
D s h a p e = a 5 ⊕ a 6 = 0 ⟺ a 5 = a 6 , (11) D_{\mathrm{shape}}=a_5\oplus a_6=0\Longleftrightarrow a_5=a_6, \tag*{(11)} D shape = a 5 ⊕ a 6 = 0 ⟺ a 5 = a 6 , (11)
the majority term in W 10 W_{10} W 10 becomes identically constant for every a 4 ∈ Z 2 32 a_4\in\mathbb{Z}_{2^{32}} a 4 ∈ Z 2 32 because Maj ( a 6 , a 5 , a 4 ) = Maj ( a 5 , a 5 , a 4 ) = a 5 = a 6 ∧ a 5 \operatorname{Maj}(a_6,a_5,a_4)=\operatorname{Maj}(a_5,a_5,a_4)=a_5=a_6\mathbin{\wedge}a_5 Maj ( a 6 , a 5 , a 4 ) = Maj ( a 5 , a 5 , a 4 ) = a 5 = a 6 ∧ a 5 , yielding W 10 = c 10 − a 3 W_{10}=c_{10}-a_3 W 10 = c 10 − a 3 with zero a 4 a_4 a 4 leakage. *(For a chosen 19-step target H 19 ∗ H^*_{19} H 19 ∗ , where a 12 … a 19 a_{12}\ldots a_{19} a 12 … a 19 are all fixed by [E6], we leave a 10 ∈ [ 0 , 2 32 ) a_{10} \in[0,2^{32}) a 10 ∈ [ 0 , 2 32 ) free instead of setting a 10 = a 11 a_{10}=a_{11} a 10 = a 11 , since Step 20 is absent and e 15 = 0 x f f f f f f f f e_{15}=0xffffffff e 15 = 0 x f f f f f f f f is not required. With free a 10 a_{10} a 10 , one can either enforce exact shaping D s h a p e = 0 D_{\mathrm{shape}}=0 D shape = 0 —which produced our 19-step 0 256 0^{256} 0 256 witness in §8.2—or use soft shaping popcount ( a 5 ⊕ a 6 ) ≤ 3 \operatorname{popcount}(a_5 \mathbin{\oplus} a_6) \le3 popcount ( a 5 ⊕ a 6 ) ≤ 3 as in src/pre19.c, which enlarges the context pool by 5,489× and generated the 14 public-label 19-step witnesses in Table 8.3 in 1.2–86.4 s of single-core CPU search time per target after a one-time 16.8–19.1 s table build.)
Table 8.3. Complete 19-step single-block FIPS 180-4 padded benchmark suite (all 14 public-label targets, full 55-byte message_hex, L = 440 L = 440 L = 440 bits, generated by our soft-shaping 19-step padded solver src/pre19.c with D = popcount ( a 5 ⊕ a 6 ) ≤ 3 D = \operatorname{popcount}(a_5 \oplus a_6) \le3 D = popcount ( a 5 ⊕ a 6 ) ≤ 3 and e 9 = e 10 = 0xffffffff e_9 = e_{10} = \texttt{0xffffffff} e 9 = e 10 = 0xffffffff ).
Simultaneously, whenever the remaining nonlinear condition in W 9 W_9 W 9 ([E10]) holds, the middle schedule words reduce to exact affine forms in ( a 2 , a 3 , a 4 ) (a_2,a_3,a_4) ( a 2 , a 3 , a 4 ) while W 12 , W 13 , … , W 19 W_{12},W_{13},\ldots,W_{19} W 12 , W 13 , … , W 19 are 100% independent of ( a 1 , a 2 , a 3 , a 4 ) (a_1,a_2,a_3,a_4) ( a 1 , a 2 , a 3 , a 4 ) :
W 9 = c 9 − a 2 , W 10 = c 10 − a 3 , W 11 = c 11 − a 4 , W 12 = c 12 , (12) W_9=c_9-a_2,\qquad W_{10}=c_{10}-a_3,\qquad W_{11}=c_{11}-a_4,\qquad W_{12}=c_{12}, \tag*{(12)} W 9 = c 9 − a 2 , W 10 = c 10 − a 3 , W 11 = c 11 − a 4 , W 12 = c 12 , (12)
where − a 4 -a_4 − a 4 inside e 8 e_8 e 8 and + Maj ( a 5 , a 4 , a 3 ) = + a 4 +\operatorname{Maj}(a_5,a_4,a_3)=+a_4 + Maj ( a 5 , a 4 , a 3 ) = + a 4 inside e 6 e_6 e 6 cancel identically in W 9 W_9 W 9 under the Level-3 majority-absorption condition:
Maj ( a 5 , a 4 , a 3 ) = a 4 ⟺ ( ( a 4 ⊕ a 5 ) ∧ M 3 ) = 0 , M 3 ≔ ¬ ( a 3 ⊕ a 5 ) . (13) \operatorname{Maj}(a_5,a_4,a_3)=a_4\Longleftrightarrow((a_4\mathbin{\oplus}a_5)\mathbin{\land}M_3)=0,\qquad M_3\coloneqq\neg(a_3\mathbin{\oplus}a_5). \tag*{(13)} Maj ( a 5 , a 4 , a 3 ) = a 4 ⟺ (( a 4 ⊕ a 5 ) ∧ M 3 ) = 0 , M 3 : = ¬ ( a 3 ⊕ a 5 ) . (13)
Table 3.1 summarizes the resulting bit-level state conditions across all 20 steps in the format of [3 , 8 , 11 ] .
Table 3.1 : Bit-level state conditions, neutral/coupled words, and schedule constraints across steps s ∈ { − 7 , … , 20 } s\in\{-7,\ldots,20\} s ∈ { − 7 , … , 20 } .
Table 3.1.
For t ∈ { 1 , 2 , 3 } t\in\{1,2,3\} t ∈ { 1 , 2 , 3 } , rearrangement of [E7] writes a t + 1 = W t + G t ( a 1 , … , a t ) a_{t+1}=W_t+G_t(a_1,\ldots,a_t) a t + 1 = W t + G t ( a 1 , … , a t ) , where G t ( a 1 , … , a t ) ≔ Σ 0 ( a t ) + Maj ( a t , a t − 1 , a t − 2 ) + e t − 3 + Σ 1 ( e t ) + Ch ( e t , e t − 1 , e t − 2 ) + K t G_t(a_1,\ldots,a_t)\coloneqq\Sigma_0(a_t)+\operatorname{Maj}(a_t,a_{t-1},a_{t-2})+e_{t-3}+\Sigma_1(e_t)+\operatorname{Ch}(e_t,e_{t-1},e_{t-2})+K_t G t ( a 1 , … , a t ) : = Σ 0 ( a t ) + Maj ( a t , a t − 1 , a t − 2 ) + e t − 3 + Σ 1 ( e t ) + Ch ( e t , e t − 1 , e t − 2 ) + K t . Setting F 1 ( a 1 ) ≔ G 1 ( a 1 ) − W 0 ( a 1 ) F_1(a_1)\coloneqq G_1(a_1)-W_0(a_1) F 1 ( a 1 ) : = G 1 ( a 1 ) − W 0 ( a 1 ) and substituting a t + 1 = W t + G t a_{t+1}=W_t+G_t a t + 1 = W t + G t together with [E12] (W 9 = c 9 − a 2 , W 10 = c 10 − a 3 , W 11 = c 11 − a 4 W_9=c_9-a_2,\ W_{10}=c_{10}-a_3,\ W_{11}=c_{11}-a_4 W 9 = c 9 − a 2 , W 10 = c 10 − a 3 , W 11 = c 11 − a 4 ) into the message schedule equations [E3] for $t=16,17,18 rewrites them as three chained Q 0 Q_0 Q 0 -inversions:
Level 1 (t = 16 t=16 t = 16 ): Q 0 ( W 1 ) = T 16 + F 1 ( a 1 ) , T 16 ≔ W 16 − σ 1 ( W 14 ) − c 9 , Q_0(W_1)=T_{16}+F_1(a_1),\qquad T_{16}\coloneqq W_{16}-\sigma_1(W_{14})-c_9, Q 0 ( W 1 ) = T 16 + F 1 ( a 1 ) , T 16 : = W 16 − σ 1 ( W 14 ) − c 9 ,
Level 2 (t = 17 t=17 t = 17 ): Q 0 ( W 2 ) = T 17 + G 2 ( a 1 , a 2 ) − W 1 , T 17 ≔ W 17 − σ 1 ( W 15 ) − c 10 , Q_0(W_2)=T_{17}+G_2(a_1,a_2)-W_1,\qquad T_{17}\coloneqq W_{17}-\sigma_1(W_{15})-c_{10}, Q 0 ( W 2 ) = T 17 + G 2 ( a 1 , a 2 ) − W 1 , T 17 : = W 17 − σ 1 ( W 15 ) − c 10 ,
Level 3 (t = 18 t=18 t = 18 ): Q 0 ( W 3 ) = T 18 + G 3 ( a 1 , a 2 , a 3 ) − W 2 , T 18 ≔ W 18 − σ 1 ( W 16 ) − c 11 . Q_0(W_3)=T_{18}+G_3(a_1,a_2,a_3)-W_2,\qquad T_{18}\coloneqq W_{18}-\sigma_1(W_{16})-c_{11}. Q 0 ( W 3 ) = T 18 + G 3 ( a 1 , a 2 , a 3 ) − W 2 , T 18 : = W 18 − σ 1 ( W 16 ) − c 11 . (E14)
Closed-Form Pivot Inversion of FIPS 180-4 Padding (W13..W15)
To construct a valid 55-byte single-block padded message ([E1]), the Right variables ( a 5 , … , a 12 ) (a_5,\ldots,a_{12}) ( a 5 , … , a 12 ) must simultaneously satisfy W 15 = 440 W_{15}=440 W 15 = 440 , W 14 = 0 W_{14}=0 W 14 = 0 , ( W 13 m o d 256 ) = 0 x 80 (W_{13}\bmod256)=0x80 ( W 13 mod 256 ) = 0 x 80 , e 9 = e 10 = 0 x f f f f f f f f e_9=e_{10}=0xffffffff e 9 = e 10 = 0 x f f f f f f f f ([E8]), and a 5 = a 6 a_5=a_6 a 5 = a 6 ([E11]). Basra [9 ] noted that ( W 15 , W 14 , W 13 m o d 256 ) (W_{15},W_{14},W_{13}\bmod256) ( W 15 , W 14 , W 13 mod 256 ) can be absorbed backward into ( a 7 , a 6 , a 5 ) (a_7,a_6,a_5) ( a 7 , a 6 , a 5 ) at the cost of three context words; below we show how to absorb W 15 = 440 W_{15}=440 W 15 = 440 and W 14 = 0 W_{14}=0 W 14 = 0 into ( a 8 , a 7 ) (a_8,a_7) ( a 8 , a 7 ) while inverting ( W 13 m o d 256 ) = 0 x 80 (W_{13}\bmod256)=0x80 ( W 13 mod 256 ) = 0 x 80 directly via 8 bit-disjoint pivot bits of Σ 1 ( e 13 ) \Sigma_1(e_{13}) Σ 1 ( e 13 ) , leaving ( a 5 , a 6 ) (a_5,a_6) ( a 5 , a 6 ) unconstrained by padding absorption so they can satisfy exact shaping a 5 = a 6 a_5=a_6 a 5 = a 6 ([E23]).
Given ( a 10 , a 11 , a 12 ) (a_{10}, a_{11}, a_{12}) ( a 10 , a 11 , a 12 ) (for R = 20 R = 20 R = 20 , where a 13..20 a_{13..20} a 13..20 are fixed by H ∗ H^* H ∗ ), the registers e 16 e_{16} e 16 , e 15 e_{15} e 15 , e 14 e_{14} e 14 are determined via [E7]:
e 16 = a 16 − Σ 0 ( a 15 ) − Maj ( a 15 , a 14 , a 13 ) + a 12 , e 15 = a 15 − Σ 0 ( a 14 ) − Maj ( a 14 , a 13 , a 12 ) + a 11 , e 14 = a 14 − Σ 0 ( a 13 ) − Maj ( a 13 , a 12 , a 11 ) + a 10 . (14) \begin{aligned}
e_{16} &= a_{16} - \Sigma_0(a_{15}) - \operatorname{Maj}(a_{15}, a_{14}, a_{13}) + a_{12},\\
e_{15} &= a_{15} - \Sigma_0(a_{14}) - \operatorname{Maj}(a_{14}, a_{13}, a_{12}) + a_{11},\\
e_{14} &= a_{14} - \Sigma_0(a_{13}) - \operatorname{Maj}(a_{13}, a_{12}, a_{11}) + a_{10}. \tag*{(14)}
\end{aligned} e 16 e 15 e 14 = a 16 − Σ 0 ( a 15 ) − Maj ( a 15 , a 14 , a 13 ) + a 12 , = a 15 − Σ 0 ( a 14 ) − Maj ( a 14 , a 13 , a 12 ) + a 11 , = a 14 − Σ 0 ( a 13 ) − Maj ( a 13 , a 12 , a 11 ) + a 10 . (14)
Expanding W 15 = 440 W_{15} = 440 W 15 = 440 and W 14 = 0 W_{14} = 0 W 14 = 0 via [E7] isolates e 12 e_{12} e 12 and e 11 e_{11} e 11 as closed-form functions of a single 32-bit word e 13 e_{13} e 13 (equivalently a 9 = e 13 − c e 13 a_9 = e_{13} - c_{e_{13}} a 9 = e 13 − c e 13 ):
e 12 = ( e 16 − a 12 − Σ 1 ( e 15 ) − K 15 − 440 ) ⏟ c e 12 − Ch ( e 15 , e 14 , e 13 ) , e 11 = ( e 15 − a 11 − Σ 1 ( e 14 ) − K 14 ) ⏟ c e 11 − Ch ( e 14 , e 13 , e 12 ) . (15) \begin{aligned}
e_{12} &= \underbrace{(e_{16} - a_{12} - \Sigma_1(e_{15}) - K_{15} - 440)}_{c_{e_{12}}} - \operatorname{Ch}(e_{15}, e_{14}, e_{13}),\\
e_{11} &= \underbrace{(e_{15} - a_{11} - \Sigma_1(e_{14}) - K_{14})}_{c_{e_{11}}} - \operatorname{Ch}(e_{14}, e_{13}, e_{12}). \tag*{(15)}
\end{aligned} e 12 e 11 = c e 12 ( e 16 − a 12 − Σ 1 ( e 15 ) − K 15 − 440 ) − Ch ( e 15 , e 14 , e 13 ) , = c e 11 ( e 15 − a 11 − Σ 1 ( e 14 ) − K 14 ) − Ch ( e 14 , e 13 , e 12 ) . (15)
Then a 8 a_8 a 8 and a 7 a_7 a 7 are recovered in closed form:
a 8 = e 12 + Σ 0 ( a 11 ) − a 12 + Maj ( a 11 , a 10 , a 9 ) , a 7 = e 11 + Σ 0 ( a 10 ) − a 11 + Maj ( a 10 , a 9 , a 8 ) . (16) a_8 = e_{12} + \Sigma_0(a_{11}) - a_{12} + \operatorname{Maj}(a_{11}, a_{10}, a_9), \qquad a_7 = e_{11} + \Sigma_0(a_{10}) - a_{11} + \operatorname{Maj}(a_{10}, a_9, a_8). \tag*{(16)} a 8 = e 12 + Σ 0 ( a 11 ) − a 12 + Maj ( a 11 , a 10 , a 9 ) , a 7 = e 11 + Σ 0 ( a 10 ) − a 11 + Maj ( a 10 , a 9 , a 8 ) . (16)
Thus every choice of ( a 12 , a 11 , a 10 , e 13 ) (a_{12}, a_{11}, a_{10}, e_{13}) ( a 12 , a 11 , a 10 , e 13 ) satisfies W 15 = 440 W_{15} = 440 W 15 = 440 and W 14 = 0 W_{14} = 0 W 14 = 0 identically.
Closed-Form Pivot Assignment for ( W 13 mod 256 ) = 0x80 (W_{13} \mathbin{\operatorname{mod}} 256) = \text{0x80} ( W 13 mod 256 ) = 0x80 ([E18]–[E22])
Since e 10 = 0xffffffff e_{10} = \text{0xffffffff} e 10 = 0xffffffff , the formula for W 13 W_{13} W 13 ([E7]) is:
W 13 = ( e 14 − a 10 − 0xffffffff − K 13 ) ⏟ c W 13 − Σ 1 ( e 13 ) − Ch ( e 13 , e 12 , e 11 ) . (17) W_{13} = \underbrace{(e_{14} - a_{10} - \text{0xffffffff} - K_{13})}_{c_{W_{13}}} - \Sigma_1(e_{13}) - \operatorname{Ch}(e_{13}, e_{12}, e_{11}). \tag*{(17)} W 13 = c W 13 ( e 14 − a 10 − 0xffffffff − K 13 ) − Σ 1 ( e 13 ) − Ch ( e 13 , e 12 , e 11 ) . (17)
Reducing [E18] modulo 256:
Because Ch \operatorname{Ch} Ch is bitwise and modular subtraction propagates carries only from lower bits to higher bits, the low 8 bits e 12 , l o : = e 12 mod 256 e_{12,\mathrm{lo}} := e_{12} \mathbin{\operatorname{mod}} 256 e 12 , lo := e 12 mod 256 and e 11 , l o : = e 11 mod 256 e_{11,\mathrm{lo}} := e_{11} \mathbin{\operatorname{mod}} 256 e 11 , lo := e 11 mod 256 in [E16] depend only on the low 8 bits e 13 , l o : = e 13 mod 256 e_{13,\mathrm{lo}} := e_{13} \mathbin{\operatorname{mod}} 256 e 13 , lo := e 13 mod 256 .
Once e 13 , l o ∈ [ 0 , 255 ] e_{13,\mathrm{lo}} \in[0, 255] e 13 , lo ∈ [ 0 , 255 ] is chosen, the required low byte of Σ 1 ( e 13 ) \Sigma_1(e_{13}) Σ 1 ( e 13 ) is fixed:
R l o : = ( c W 13 − Ch ( e 13 , l o , e 12 , l o , e 11 , l o ) − 0x80 ) mod 256. (18) R_{\mathrm{lo}} := (c_{W_{13}} - \operatorname{Ch}(e_{13,\mathrm{lo}}, e_{12,\mathrm{lo}}, e_{11,\mathrm{lo}}) - \text{0x80}) \mathbin{\operatorname{mod}} 256. \tag*{(18)} R lo := ( c W 13 − Ch ( e 13 , lo , e 12 , lo , e 11 , lo ) − 0x80 ) mod 256. (18)
Inspecting bit b ∈ { 0 , … , 7 } b \in\{0, \ldots, 7\} b ∈ { 0 , … , 7 } of Σ 1 ( e 13 ) = ROR ( e 13 , 6 ) ⊕ ROR ( e 13 , 11 ) ⊕ ROR ( e 13 , 25 ) \Sigma_1(e_{13}) = \operatorname{ROR}(e_{13}, 6) \mathbin{\oplus} \operatorname{ROR}(e_{13}, 11) \mathbin{\oplus} \operatorname{ROR}(e_{13}, 25) Σ 1 ( e 13 ) = ROR ( e 13 , 6 ) ⊕ ROR ( e 13 , 11 ) ⊕ ROR ( e 13 , 25 ) :
( Σ 1 ( e 13 ) ) b = ( e 13 ) b + 6 ⊕ ( e 13 ) b + 11 ⊕ ( e 13 ) ( b + 25 ) m o d 32 . (19) \left(\Sigma_1(e_{13})\right)_b = (e_{13})_{b+6} \mathbin{\oplus} (e_{13})_{b+11} \mathbin{\oplus} (e_{13})_{(b+25)\bmod32}. \tag*{(19)} ( Σ 1 ( e 13 ) ) b = ( e 13 ) b + 6 ⊕ ( e 13 ) b + 11 ⊕ ( e 13 ) ( b + 25 ) mod 32 . (19)
For b ∈ { 0 , … , 6 } b \in\{0, \ldots, 6\} b ∈ { 0 , … , 6 } , ( b + 25 ) mod 32 = b + 25 ∈ { 25 , … , 31 } (b + 25) \mathbin{\operatorname{mod}} 32 = b + 25 \in\{25, \ldots, 31\} ( b + 25 ) mod 32 = b + 25 ∈ { 25 , … , 31 } , which appears nowhere else in [E20].
For b = 7 b = 7 b = 7 , ( 7 + 25 ) mod 32 = 0 ∈ { 0 , … , 7 } (7 + 25) \mathbin{\operatorname{mod}} 32 = 0 \in\{0, \ldots, 7\} ( 7 + 25 ) mod 32 = 0 ∈ { 0 , … , 7 } , while ( e 13 ) 7 + 11 = ( e 13 ) 18 (e_{13})_{7+11} = (e_{13})_{18} ( e 13 ) 7 + 11 = ( e 13 ) 18 appears nowhere else in [E20].
Furthermore, bits 19..24 of e 13 e_{13} e 13 do not appear anywhere in [E20] and do not affect e 13 , l o e_{13,\mathrm{lo}} e 13 , lo .
Therefore, for any assignment to bits 0..17 of e 13 e_{13} e 13 (e 13 , b a s e e_{13,\mathrm{base}} e 13 , base ), the 8 pivot bits (bit 18 and bits 25..31) are uniquely determined in closed form:
Δ : = ( R l o ⊕ Σ 1 ( e 13 , b a s e ) ) m o d 256 , e 13 , f i x e d : = e 13 , b a s e ∣ ( ( Δ ∧ 0 x 7 f ) ≪ 25 ) ∣ ( ( ( Δ ≫ 7 ) ∧ 1 ) ≪ 18 ) , (20) \Delta:= (R_{\mathrm{lo}} \oplus\Sigma_{1}(e_{13,\mathrm{base}})) \bmod256,\qquad e_{13,\mathrm{fixed}} := e_{13,\mathrm{base}} \mathbin{|} ((\Delta\mathbin{\wedge} 0\mathrm{x}7\mathrm{f}) \mathbin{\ll} 25) \mathbin{|} (((\Delta\mathbin{\gg} 7) \mathbin{\wedge} 1) \mathbin{\ll} 18), \tag*{(20)} Δ := ( R lo ⊕ Σ 1 ( e 13 , base )) mod 256 , e 13 , fixed := e 13 , base ∣ (( Δ ∧ 0 x 7 f ) ≪ 25 ) ∣ ((( Δ ≫ 7 ) ∧ 1 ) ≪ 18 ) , (20)
while bits 19..24 remain 6 completely free degrees of freedom where 100% of assignments satisfy ( W 13 m o d 256 ) = 0 x 80 (W_{13} \bmod256) = 0\mathrm{x}80 ( W 13 mod 256 ) = 0 x 80 .
Finally, in solve20_padded_fast.c and solve20_padded_cuda.cu, we apply Ch-annihilation by pinning e 15 = 0 x f f f f f f f f e_{15} = 0\mathrm{xffffffff} e 15 = 0 xffffffff (fixing a 11 a_{11} a 11 from a 12 a_{12} a 12 via [E15]) and setting a 10 = a 11 a_{10} = a_{11} a 10 = a 11 . This simultaneously forces Ch ( e 15 , e 14 , e 13 ) = e 14 \operatorname{Ch}(e_{15},e_{14},e_{13}) = e_{14} Ch ( e 15 , e 14 , e 13 ) = e 14 (making e 12 e_{12} e 12 and a 8 a_{8} a 8 100% constant across all 2 24 2^{24} 2 24 choices of e 13 e_{13} e 13 ), simplifies Maj ( a 11 , a 10 , a 9 ) = a 11 \operatorname{Maj}(a_{11},a_{10},a_{9}) = a_{11} Maj ( a 11 , a 10 , a 9 ) = a 11 , and linearizes Maj ( a 10 , a 9 , a 8 ) = ( a 10 ∧ a 8 ) + ( ( a 10 ⊕ a 8 ) ∧ a 9 ) \operatorname{Maj}(a_{10},a_{9},a_{8}) = (a_{10} \mathbin{\wedge} a_{8}) + ((a_{10} \oplus a_{8}) \mathbin{\wedge} a_{9}) Maj ( a 10 , a 9 , a 8 ) = ( a 10 ∧ a 8 ) + (( a 10 ⊕ a 8 ) ∧ a 9 ) :
e 15 = 0 x f f f f f f f f , a 10 = a 11 ⟹ e 12 = c e 12 − e 14 = c o n s t , a 8 = e 12 + Σ 0 ( a 11 ) − a 12 + a 11 = c o n s t . (21) e_{15} = 0\mathrm{xffffffff},\quad a_{10} = a_{11} \Longrightarrow e_{12} = c_{e_{12}} - e_{14} = \mathrm{const},\quad a_{8} = e_{12} + \Sigma_{0}(a_{11}) - a_{12} + a_{11} = \mathrm{const}. \tag*{(21)} e 15 = 0 xffffffff , a 10 = a 11 ⟹ e 12 = c e 12 − e 14 = const , a 8 = e 12 + Σ 0 ( a 11 ) − a 12 + a 11 = const . (21)
Causal Bit-Slice Pruning: 7-Stage Right-Context Search
Even with [E21]–[E22], each a 12 a_{12} a 12 defines 2 24 2^{24} 2 24 padded candidates for e 13 e_{13} e 13 , and testing a 5 = a 6 a_{5} = a_{6} a 5 = a 6 ([E11]) naively requires evaluating Σ 0 ( a 9 ) \Sigma_{0}(a_{9}) Σ 0 ( a 9 ) and a 6 a_{6} a 6 across those candidates. We now prove that causal lower-triangular bit-slice pruning—which we term Carry-Sudoku —reduces the 2 24 2^{24} 2 24 candidate tree to an average of 43,580 node evaluations (99.74% pruning, or 385× \times × fewer evaluations) before Σ 0 ( a 9 ) \Sigma_{0}(a_{9}) Σ 0 ( a 9 ) or a 6 a_{6} a 6 is ever computed.
The Exact Equivalence Theorem ([E23])
Theorem 1 (Carry-Sudoku Exact Equivalence). Under [E9], define X : = 0 x f f f f f f f f − a 9 + Σ 0 ( a 8 ) X := 0\mathrm{xffffffff} - a_{9} + \Sigma_{0}(a_{8}) X := 0 xffffffff − a 9 + Σ 0 ( a 8 ) , the bitwise XOR mask D : = a 8 ⊕ a 7 D := a_{8} \oplus a_{7} D := a 8 ⊕ a 7 , and S : = X + Ch ( D , X , a 8 ) ( m o d 2 32 ) S := X + \operatorname{Ch}(D,X,a_{8}) \pmod{2^{32}} S := X + Ch ( D , X , a 8 ) ( mod 2 32 ) . Then:
a 5 = a 6 ⟺ ( ( ( S ⊕ X ) ∧ D ) = 0 ) ∧ ( ( ( a 6 ⊕ S ) ∧ ¬ D ) = 0 ) . (22) a_{5} = a_{6} \Longleftrightarrow(((S \oplus X) \mathbin{\wedge} D) = 0) \mathbin{\wedge} (((a_{6} \oplus S) \mathbin{\wedge} \neg D) = 0). \tag*{(22)} a 5 = a 6 ⟺ ((( S ⊕ X ) ∧ D ) = 0 ) ∧ ((( a 6 ⊕ S ) ∧ ¬ D ) = 0 ) . (22)
Proof. By [E9], a 5 = X + Maj ( a 8 , a 7 , a 6 ) a_{5} = X + \operatorname{Maj}(a_{8},a_{7},a_{6}) a 5 = X + Maj ( a 8 , a 7 , a 6 ) . Decompose Maj ( a 8 , a 7 , a 6 ) \operatorname{Maj}(a_{8},a_{7},a_{6}) Maj ( a 8 , a 7 , a 6 ) bitwise with respect to D = a 8 ⊕ a 7 D = a_{8} \oplus a_{7} D = a 8 ⊕ a 7 :
On bit positions where D b = 0 D_b = 0 D b = 0 (a 8 , b = a 7 , b a_{8,b} = a_{7,b} a 8 , b = a 7 , b ), Maj ( a 8 , a 7 , a 6 ) b = a 8 , b \operatorname{Maj}(a_{8},a_{7},a_{6})_b = a_{8,b} Maj ( a 8 , a 7 , a 6 ) b = a 8 , b is independent of a 6 a_{6} a 6 .
On bit positions where D b = 1 D_b = 1 D b = 1 (a 8 , b ≠ a 7 , b a_{8,b} \ne a_{7,b} a 8 , b = a 7 , b ), Maj ( a 8 , a 7 , a 6 ) b = a 6 , b \operatorname{Maj}(a_{8},a_{7},a_{6})_b = a_{6,b} Maj ( a 8 , a 7 , a 6 ) b = a 6 , b .
Hence Maj ( a 8 , a 7 , a 6 ) = ( D ∧ a 6 ) ⊕ ( ¬ D ∧ a 8 ) = Ch ( D , a 6 , a 8 ) \operatorname{Maj}(a_{8},a_{7},a_{6}) = (D \mathbin{\wedge} a_{6}) \oplus(\neg D \mathbin{\wedge} a_{8}) = \operatorname{Ch}(D,a_{6},a_{8}) Maj ( a 8 , a 7 , a 6 ) = ( D ∧ a 6 ) ⊕ ( ¬ D ∧ a 8 ) = Ch ( D , a 6 , a 8 ) . Now compare a 5 = X + Ch ( D , a 6 , a 8 ) a_{5} = X + \operatorname{Ch}(D,a_{6},a_{8}) a 5 = X + Ch ( D , a 6 , a 8 ) with S = X + Ch ( D , X , a 8 ) S = X + \operatorname{Ch}(D,X,a_{8}) S = X + Ch ( D , X , a 8 ) by induction from bit b = 0 b = 0 b = 0 to 31:
Suppose a 5 = a 6 a_{5} = a_{6} a 5 = a 6 on bits 0.. b − 1 0..b-1 0.. b − 1 , so the incoming carry c b c_b c b into bit b b b of X + Ch ( D , a 6 , a 8 ) X + \operatorname{Ch}(D,a_{6},a_{8}) X + Ch ( D , a 6 , a 8 ) equals the incoming carry into bit b b b of S = X + Ch ( D , X , a 8 ) S = X + \operatorname{Ch}(D,X,a_{8}) S = X + Ch ( D , X , a 8 ) :
If D b = 1 D_b = 1 D b = 1 , then Ch ( D , a 6 , a 8 ) b = a 6 , b \operatorname{Ch}(D,a_{6},a_{8})_b = a_{6,b} Ch ( D , a 6 , a 8 ) b = a 6 , b , so a 5 , b = X b ⊕ a 6 , b ⊕ c b a_{5,b} = X_b \oplus a_{6,b} \oplus c_b a 5 , b = X b ⊕ a 6 , b ⊕ c b . Thus a 5 , b = a 6 , b ⟺ X b ⊕ c b = 0 a_{5,b} = a_{6,b} \Longleftrightarrow X_b \oplus c_b = 0 a 5 , b = a 6 , b ⟺ X b ⊕ c b = 0 , and when X b ⊕ c b = 0 X_b \oplus c_b = 0 X b ⊕ c b = 0 , the outgoing carry from bit b b b is Maj ( X b , a 6 , b , c b ) = X b = Maj ( X b , X b , c b ) \operatorname{Maj}(X_b,a_{6,b},c_b) = X_b = \operatorname{Maj}(X_b,X_b,c_b) Maj ( X b , a 6 , b , c b ) = X b = Maj ( X b , X b , c b ) , which is identical to the outgoing carry of S = X + Ch ( D , X , a 8 ) S = X + \operatorname{Ch}(D,X,a_{8}) S = X + Ch ( D , X , a 8 ) where S b = X b ⊕ X b ⊕ c b = c b = X b S_b = X_b \oplus X_b \oplus c_b = c_b = X_b S b = X b ⊕ X b ⊕ c b = c b = X b , i.e. ( S b ⊕ X b ) = 0 (S_b \oplus X_b) = 0 ( S b ⊕ X b ) = 0 .
If D b = 0 D_b = 0 D b = 0 , then Ch ( D , a 6 , a 8 ) b = a 8 , b = Ch ( D , X , a 8 ) b \operatorname{Ch}(D,a_{6},a_{8})_b = a_{8,b} = \operatorname{Ch}(D,X,a_{8})_b Ch ( D , a 6 , a 8 ) b = a 8 , b = Ch ( D , X , a 8 ) b , so a 5 , b = S b a_{5,b} = S_b a 5 , b = S b and the outgoing carry is again identical to that of S S S . Thus a 5 , b = a 6 , b ⟺ a 6 , b = S b a_{5,b} = a_{6,b} \Longleftrightarrow a_{6,b} = S_b a 5 , b = a 6 , b ⟺ a 6 , b = S b . ∎
7-Stage Causal Bit-Slice Pruning ([E24]–[E26])
Theorem 1 has a decisive algorithmic consequence: the first condition in [E23],
( ( S ⊕ X ) ∧ D ) = 0 , S = X + Ch ( D , X , a 8 ) , (23) ((S \mathbin{\oplus} X) \mathbin{\land} D) = 0,\qquad S = X + \operatorname{Ch}(D,X,a_{8}), \tag*{(23)} (( S ⊕ X ) ∧ D ) = 0 , S = X + Ch ( D , X , a 8 ) , (23)
does not depend on a 6 a_{6} a 6 or Σ 0 ( a 9 ) \Sigma_{0}(a_{9}) Σ 0 ( a 9 ) at all , and because a 9 = e 13 − c e 13 a_{9}=e_{13}-c_{e13} a 9 = e 13 − c e 13 , X = c a 5 − a 9 X=c_{a5}-a_{9} X = c a 5 − a 9 , and a 7 = c a 7 , f u l l − ( e 14 ∧ e 13 ) + ( ( a 10 ⊕ a 8 ) ∧ a 9 ) a_{7}=c_{a7,\mathrm{full}}-(e_{14}\mathbin{\land}e_{13})+((a_{10}\mathbin{\oplus}a_{8})\mathbin{\land}a_{9}) a 7 = c a 7 , full − ( e 14 ∧ e 13 ) + (( a 10 ⊕ a 8 ) ∧ a 9 ) involve only bitwise operations and modular additions/subtractions, the lowest k k k bits of X , a 7 , D , X,a_{7},D, X , a 7 , D , and S S S depend exclusively on the lowest k k k bits of e 13 e_{13} e 13 .
Consequently, ctx_worker (solve20_padded_fast.c) on CPU and ctx_gen_cuda_kernel / ctx_gen_fast_cuda_kernel (solve20_padded_cuda.cu, solve20_padded_cuda_prod.cu) on GPU assign e 13 e_{13} e 13 from LSB to MSB in 7 exact causal stages (formalized in Algorithm 1):
Stage 1a (bits 0..3): ( ( S ⊕ X ) ∧ D ∧ 0 x f ) = 0 ((S\mathbin{\oplus}X)\mathbin{\land}D\mathbin{\land}0\mathrm{x}f)=0 (( S ⊕ X ) ∧ D ∧ 0 x f ) = 0 ,
Stage 1b (bits 4..7): ( ( S ⊕ X ) ∧ D ∧ 0 x f f ) = 0 ⟹ ((S\mathbin{\oplus}X)\mathbin{\land}D\mathbin{\land}0\mathrm{x}ff)=0 \Longrightarrow (( S ⊕ X ) ∧ D ∧ 0 x f f ) = 0 ⟹ fixes R l o R_{\mathrm{lo}} R lo and ( e 13 ) 18 ⊕ ( e 13 ) 13 (e_{13})_{18}\mathbin{\oplus}(e_{13})_{13} ( e 13 ) 18 ⊕ ( e 13 ) 13 ,
Stage 1c (bits 8..11): ( ( S ⊕ X ) ∧ D ∧ 0 x f f f ) = 0 ((S\mathbin{\oplus}X)\mathbin{\land}D\mathbin{\land}0\mathrm{x}fff)=0 (( S ⊕ X ) ∧ D ∧ 0 x f f f ) = 0 ,
Stage 1d (bits 12..14 + exact bit 18): ( ( S ⊕ X ) ∧ D ∧ 0 x 7 f f f ) = 0 ((S\mathbin{\oplus}X)\mathbin{\land}D\mathbin{\land}0\mathrm{x}7fff)=0 (( S ⊕ X ) ∧ D ∧ 0 x 7 f f f ) = 0 ,
Stage 1e (bits 15..17, checked to bit 18): ( ( S ⊕ X ) ∧ D ∧ 0 x 7 f f f f ) = 0 ⟹ ((S\mathbin{\oplus}X)\mathbin{\land}D\mathbin{\land}0\mathrm{x}7ffff)=0 \Longrightarrow (( S ⊕ X ) ∧ D ∧ 0 x 7 f f f f ) = 0 ⟹ fixes bits 25..31 via [E21],
Stage 2a (bits 19..21): ( ( S ⊕ X ) ∧ D ∧ 0 x 3 f f f f f ) = 0 ((S\mathbin{\oplus}X)\mathbin{\land}D\mathbin{\land}0\mathrm{x}3fffff)=0 (( S ⊕ X ) ∧ D ∧ 0 x 3 f f f f f ) = 0 ,
Stage 2b (bits 22..24): ( ( S ⊕ X ) ∧ D ) = 0 ∧ ( ( a 6 ⊕ S ) ∧ ¬ D ) = 0 ((S\mathbin{\oplus}X)\mathbin{\land}D)=0\ \land\ ((a_{6}\mathbin{\oplus}S)\mathbin{\land}\lnot D)=0 (( S ⊕ X ) ∧ D ) = 0 ∧ (( a 6 ⊕ S ) ∧ ¬ D ) = 0 .
( ( S ⊕ X ) ∧ D ) = 0 ∧ ( ( a 6 ⊕ S ) ∧ ¬ D ) = 0. (24) ((S\mathbin{\oplus}X)\mathbin{\land}D)=0\ \land\ ((a_{6}\mathbin{\oplus}S)\mathbin{\land}\lnot D)=0. \tag*{(24)} (( S ⊕ X ) ∧ D ) = 0 ∧ (( a 6 ⊕ S ) ∧ ¬ D ) = 0. (24)
[Equation (E26) retired in Round 2: former heuristic pre-s19 Σ 0 ( a 9 ) \Sigma_{0}(a_{9}) Σ 0 ( a 9 ) window check omitted for 100% completeness.]
In Stage 1d, once bit 13 of e 13 e_{13} e 13 is chosen, bit 18 of e 13 e_{13} e 13 is immediately determined by ( R l o ≫ 7 ) ⊕ ( e 13 ) 0 ⊕ ( e 13 ) 13 (R_{\mathrm{lo}}\gg7)\mathbin{\oplus}(e_{13})_{0}\mathbin{\oplus}(e_{13})_{13} ( R lo ≫ 7 ) ⊕ ( e 13 ) 0 ⊕ ( e 13 ) 13 ([E20]), allowing Stage 1e to test a 19-bit Carry-Sudoku mask (0x7ffff) on 18 chosen bits before Σ 1 ( e 13 , b a s e ) \Sigma_{1}(e_{13,\mathrm{base}}) Σ 1 ( e 13 , base ) is evaluated. Once Stage 1e fixes bits 25..31 via [E21], Stages 2a and 2b sweep the remaining 6 free bits 19..24 (s19 and s22) using a 22-bit mask (0x3fffff) followed by the full 32-bit Carry-Sudoku check and exact equivalence [E23]. (Note: we do not pre-filter bits 13..15 or 3..4 of a 6 − a 5 a_{6}-a_{5} a 6 − a 5 [[E26]] before s19 and s22 are chosen, because bits 19..24 of e 13 e_{13} e 13 enter Maj ( a 9 , a 8 , a 7 ) \operatorname{Maj}(a_{9},a_{8},a_{7}) Maj ( a 9 , a 8 , a 7 ) and a 9 = e 13 − c e 13 a_{9}=e_{13}-c_{e13} a 9 = e 13 − c e 13 with carry propagation; omitting any pre-s19 window check guarantees 100% completeness across each 2 24 2^{24} 2 24 -candidate a 12 a_{12} a 12 block by Theorem 1 ([E23]–[E25]), confirmed with zero missed contexts against exhaustive bruteforce across 300 × 2 24 300\times2^{24} 300 × 2 24 candidate e 13 e_{13} e 13 blocks and demonstrated on seed block a 12 = 0 x 1 e e 9 c 019 a_{12}=0x1ee9c019 a 12 = 0 x 1 ee 9 c 019 [where 2 of 8 exact D s h a p e = 0 D_{\mathrm{shape}}=0 D shape = 0 contexts were rejected by [E26]] in solve20_padded_fast.c and verify_all_witnesses.py §8.)
Algorithm 1: Causal 7-Stage Carry-Sudoku Right-Context Generator
Input: Target terminal words a_{13}..a_{20} = H* - IV, seed range a_{12} in [0, 2^32)
Output: Reservoir R of exact D_shape = (a_5 ^ a_6) == 0 FIPS 180-4 padded contexts
1. for each seed a_{12} in parallel do
2. Set e_{15}=0xffffff; compute a_{11} via [E15] and set a_{10} = a_{11} // [E22] Ch-annihilation
3. Compute constants e_{16}, e_{14}, e_{12} = c_{e12} - e_{14}, and a_8 = const // [E16]-[E17]
4. Sweep bits 0..3 and 4..7 of e_{13} filtering ((S ^ X) & D & mask) == 0 (masks 0xf, 0xff)
5. Compute low-byte padding target R_lo = (c_{W13} - Ch(e_{13}, e_{12}, e_{11}) - 0x80) mod 256 // [E19]
6. Sweep bits 8..11, 12..14 (fixing bit 18 via [E20]), and 15..17 filtering masks 0xff, 0x7fff, 0x7ffff
7. Fix bits 25..31 of e_{13} in O(1) via Delta = (R_lo ^ Sigma_1(e_{13,base})) mod 256 // [E21]
8. for s_{19} in 0..7 filtering ((S ^ X) & D & 0x3fffff) == 0 do // Stage 2a
9. for s_{22} in 0..7 do // Stage 2b
10. if ((S ^ X) & D) == 0 and ((a_6 ^ S) & ~D) == 0 then // Theorem 1 [E23]
11. Append context (a_5..a_{12}, T_{16}, T_{17}, T_{18}, T_{19}) to Reservoir R
Across 10,000 random a 12 a_{12} a 12 blocks, Algorithm 1 evaluates an average of only 43,580 inner-loop nodes per 2 24 2^{24} 2 24 block (16.0 + 80.4 + 412.9 + 1,043.8 + 3,507.8 + 8,845.4 + 29,673.5), generating 266.8 exact D s h a p e = 0 D_{\mathrm{shape}} = 0 D shape = 0 padded contexts per second on one 10-core Apple M4 CPU node (16 threads, 3.75 ms/context, solve20_padded_fast.c) and 29,310–114,507 contexts per second in supplementary 1× NVIDIA L4 GPU telemetry (solve20_padded_cuda.cu, 8.73–34.1 μ \mu μ s/context).
Slot-Indexed Q 0 − 1 Q_0^{-1} Q 0 − 1 Tables & Closed-Form F 2 \mathbb{F}_2 F 2 Inverse for Left-to-Right Chains
With an exact D = a 5 ⊕ a 6 = 0 D = a_5 \oplus a_6 = 0 D = a 5 ⊕ a 6 = 0 padded Right context in hand, we solve the three chained Q 0 − 1 Q_0^{-1} Q 0 − 1 equations [E14] from Left to Right.
Closed-Form Zero-Table F 2 \mathbb{F}_2 F 2 Inverse (reconstruct_u, [E27]–[E29])
Storing full 32-bit preimages u u u of y = Q 0 ( u ) = σ 0 ( u ) − u y = Q_0(u) = \sigma_0(u) - u y = Q 0 ( u ) = σ 0 ( u ) − u requires 4 bytes per slot. Splitting u = U + u l o u = U + u_{\mathrm{lo}} u = U + u lo where U : = ( u h i ≪ 16 ) U := (u_{\mathrm{hi}} \ll16) U := ( u hi ≪ 16 ) and u l o , u h i ∈ [ 0 , 65535 ] u_{\mathrm{lo}}, u_{\mathrm{hi}} \in[0, 65535] u lo , u hi ∈ [ 0 , 65535 ] , note that U ≡ 0 ( m o d 2 16 ) U \equiv0 \pmod{2^{16}} U ≡ 0 ( mod 2 16 ) , so carry propagation from bits 0..15 into bit 16 of u + y = U + ( u l o + y ) u + y = U + (u_{\mathrm{lo}} + y) u + y = U + ( u lo + y ) is purely additive (XOR) at bit 16: ( u + y ) ≡ U ⊕ ( u l o + y ) ( m o d 2 17 ) (u + y) \equiv U \oplus(u_{\mathrm{lo}} + y) \pmod{2^{17}} ( u + y ) ≡ U ⊕ ( u lo + y ) ( mod 2 17 ) . Since u + y ≡ σ 0 ( u ) = σ 0 ( U ) ⊕ σ 0 ( u l o ) ( m o d 2 17 ) u + y \equiv\sigma_0(u) = \sigma_0(U) \oplus\sigma_0(u_{\mathrm{lo}}) \pmod{2^{17}} u + y ≡ σ 0 ( u ) = σ 0 ( U ) ⊕ σ 0 ( u lo ) ( mod 2 17 ) , rearranging terms yields the exact 17-bit identity:
σ 0 ( U ) ⊕ U ≡ ( u l o + y ) ⊕ σ 0 ( u l o ) ( m o d 2 17 ) . (25) \sigma_0(U) \oplus U \equiv(u_{\mathrm{lo}} + y) \oplus\sigma_0(u_{\mathrm{lo}}) \pmod{2^{17}}. \tag*{(25)} σ 0 ( U ) ⊕ U ≡ ( u lo + y ) ⊕ σ 0 ( u lo ) ( mod 2 17 ) . (25)
Rather than inverting [E27] solely with a 128 KiB lookup table (REC_HI16[rec_idx(u_lo, y)] in solve20_padded_fast.c), we prove that [E27] has an exact register closed form with zero lookup tables:
Theorem 2 (Closed-Form F 2 \mathbb{F}_2 F 2 Inverse of Upper 16 Bits). Let v = ( u l o + y ) ⊕ σ 0 ( u l o ) ( m o d 2 32 ) v = (u_{\mathrm{lo}} + y) \oplus\sigma_0(u_{\mathrm{lo}}) \pmod{2^{32}} v = ( u lo + y ) ⊕ σ 0 ( u lo ) ( mod 2 32 ) , and let U = u h i ≪ 16 ∈ F 32 U = u_{\mathrm{hi}} \ll16 \in\mathbb{F}^{32} U = u hi ≪ 16 ∈ F 32 have bits in positions 16..31 (with U 0..15 = 0 U_{0..15} = 0 U 0..15 = 0 ). Define the linear operator L ( T ) : = T ⊕ ( T ≪ 11 ) ⊕ ( T ≪ 15 ) ( m o d 2 32 ) L(T) := T \oplus(T \ll11) \oplus(T \ll15) \pmod{2^{32}} L ( T ) := T ⊕ ( T ≪ 11 ) ⊕ ( T ≪ 15 ) ( mod 2 32 ) on upper-half words T T T . Then L L L is a triangular bijection on bits 16..31 with U = L ( T ) U = L(T) U = L ( T ) , where T T T is given in closed form by:
b 0 = ( ( v ≪ 15 ) ⊕ ( v ≪ 11 ) ⊕ v ) ∧ 0 x 00010000 , b 12 = ( ( v ≪ 14 ) ⊕ ( v ≪ 3 ) ) ∧ 0 x 00060000 , T = b 0 ∣ b 12 ∣ ( ( v ≪ 18 ) ∧ 0 x f f f 80000 ) . (26) \begin{aligned}
b_0 &= ((v \ll15) \oplus(v \ll11) \oplus v) \land0\mathrm{x}00010000,\\
b_{12} &= ((v \ll14) \oplus(v \ll3)) \land0\mathrm{x}00060000,\\
T &= b_0 \mathbin{|} b_{12} \mathbin{|} ((v \ll18) \land0\mathrm{x}fff80000). \tag*{(26)}
\end{aligned} b 0 b 12 T = (( v ≪ 15 ) ⊕ ( v ≪ 11 ) ⊕ v ) ∧ 0 x 00010000 , = (( v ≪ 14 ) ⊕ ( v ≪ 3 )) ∧ 0 x 00060000 , = b 0 ∣ b 12 ∣ (( v ≪ 18 ) ∧ 0 x f f f 80000 ) . (26) and the full 32-bit preimage is recovered in registers (reconstruct_u_dev in solve20_padded_cuda.cu and reconstruct_u_e28 in test_all_12_theories.c, using 5 logical stages / ~19 bitwise/ALU operations and zero lookup tables):
u = u l o ∣ ( T ⊕ ( T ≪ 11 ) ⊕ ( T ≪ 15 ) ) . (27) u = u_{\mathrm{lo}} \mathbin{|} (T \oplus(T \ll11) \oplus(T \ll15)). \tag*{(27)} u = u lo ∣ ( T ⊕ ( T ≪ 11 ) ⊕ ( T ≪ 15 )) . (27)
Proof. By [E27] and U 0..15 = 0 U_{0..15} = 0 U 0..15 = 0 , v b = ( σ 0 ( U ) ) b v_b = (\sigma_0(U))_b v b = ( σ 0 ( U ) ) b for b ∈ { 0 , … , 15 } b \in\{0,\ldots,15\} b ∈ { 0 , … , 15 } and v 16 = ( σ 0 ( U ) ) 16 ⊕ U 16 v_{16} = (\sigma_0(U))_{16} \oplus U_{16} v 16 = ( σ 0 ( U ) ) 16 ⊕ U 16 . Since U 0..15 = 0 U_{0..15} = 0 U 0..15 = 0 , on bits 0..16 the three terms of σ 0 ( U ) = ROR ( U , 7 ) ⊕ ROR ( U , 18 ) ⊕ ( U ≫ 3 ) \sigma_0(U) = \operatorname{ROR}(U, 7) \oplus\operatorname{ROR}(U, 18) \oplus(U \gg3) σ 0 ( U ) = ROR ( U , 7 ) ⊕ ROR ( U , 18 ) ⊕ ( U ≫ 3 ) are:
ROR ( U , 7 ) b = U b + 7 \operatorname{ROR}(U, 7)_b = U_{b+7} ROR ( U , 7 ) b = U b + 7 for b ∈ { 9 , … , 16 } b \in\{9,\ldots,16\} b ∈ { 9 , … , 16 } and 0 for b ∈ { 0 , … , 8 } b \in\{0,\ldots,8\} b ∈ { 0 , … , 8 } ;
ROR ( U , 18 ) b = U b + 18 \operatorname{ROR}(U, 18)_b = U_{b+18} ROR ( U , 18 ) b = U b + 18 for b ∈ { 0 , … , 13 } b \in\{0,\ldots,13\} b ∈ { 0 , … , 13 } and U b − 14 = 0 U_{b-14} = 0 U b − 14 = 0 for b ∈ { 14 , 15 , 16 } b \in\{14,15,16\} b ∈ { 14 , 15 , 16 } ;
( U ≫ 3 ) b = U b + 3 (U \gg3)_b = U_{b+3} ( U ≫ 3 ) b = U b + 3 for b ∈ { 13 , … , 16 } b \in\{13,\ldots,16\} b ∈ { 13 , … , 16 } and 0 for b ∈ { 0 , … , 12 } b \in\{0,\ldots,12\} b ∈ { 0 , … , 12 } .
Defining T = L − 1 ( U ) T=L^{-1}(U) T = L − 1 ( U ) so that U j = T j U_j=T_j U j = T j for j ∈ { 16 , … , 26 } j\in\{16,\ldots,26\} j ∈ { 16 , … , 26 } , U j = T j ⊕ T j − 11 U_j=T_j\oplus T_{j-11} U j = T j ⊕ T j − 11 for j ∈ { 27 , … , 30 } j\in\{27,\ldots,30\} j ∈ { 27 , … , 30 } , and U 31 = T 31 ⊕ T 20 ⊕ T 16 U_{31}=T_{31}\oplus T_{20}\oplus T_{16} U 31 = T 31 ⊕ T 20 ⊕ T 16 yields:
For b ∈ { 1 , … , 13 } b\in\{1,\ldots,13\} b ∈ { 1 , … , 13 } , v b = ( σ 0 ( U ) ) b = T b + 18 v_b=(\sigma_0(U))_b=T_{b+18} v b = ( σ 0 ( U ) ) b = T b + 18 , giving T 19 … 31 = ( v ≪ 18 ) & 0 xfff80000 T_{19\ldots31}=(v\ll18)\mathbin{\&}0\text{xfff80000} T 19 … 31 = ( v ≪ 18 ) & 0 xfff80000 (in particular, v 1 = U 19 = T 19 v_1=U_{19}=T_{19} v 1 = U 19 = T 19 , v 3 = U 21 v_3=U_{21} v 3 = U 21 , v 4 = U 22 v_4=U_{22} v 4 = U 22 , and v 5 = U 23 v_5=U_{23} v 5 = U 23 ).
For b ∈ { 14 , 15 } b\in\{14,15\} b ∈ { 14 , 15 } , v 14 = U 21 ⊕ U 17 = v 3 ⊕ T 17 v_{14}=U_{21}\oplus U_{17}=v_3\oplus T_{17} v 14 = U 21 ⊕ U 17 = v 3 ⊕ T 17 and v 15 = U 22 ⊕ U 18 = v 4 ⊕ T 18 v_{15}=U_{22}\oplus U_{18}=v_4\oplus T_{18} v 15 = U 22 ⊕ U 18 = v 4 ⊕ T 18 , isolating T 17 … 18 = ( ( v ≪ 14 ) ⊕ ( v ≪ 3 ) ) & 0 x00060000 T_{17\ldots18}=((v\ll14)\oplus(v\ll3))\mathbin{\&}0\text{x00060000} T 17 … 18 = (( v ≪ 14 ) ⊕ ( v ≪ 3 )) & 0 x00060000 .
For b = 16 b=16 b = 16 , ( σ 0 ( U ) ) 16 = ROR ( U , 7 ) 16 ⊕ ROR ( U , 18 ) 16 ⊕ ( U ≫ 3 ) 16 = U 23 ⊕ U 2 ⊕ U 19 = v 5 ⊕ 0 ⊕ v 1 (\sigma_0(U))_{16}=\operatorname{ROR}(U,7)_{16}\oplus\operatorname{ROR}(U,18)_{16}\oplus(U\gg3)_{16}=U_{23}\oplus U_2\oplus U_{19}=v_5\oplus0\oplus v_1 ( σ 0 ( U ) ) 16 = ROR ( U , 7 ) 16 ⊕ ROR ( U , 18 ) 16 ⊕ ( U ≫ 3 ) 16 = U 23 ⊕ U 2 ⊕ U 19 = v 5 ⊕ 0 ⊕ v 1 . Since v 16 = ( σ 0 ( U ) ) 16 ⊕ U 16 = v 5 ⊕ v 1 ⊕ T 16 v_{16}=(\sigma_0(U))_{16}\oplus U_{16}=v_5\oplus v_1\oplus T_{16} v 16 = ( σ 0 ( U ) ) 16 ⊕ U 16 = v 5 ⊕ v 1 ⊕ T 16 , we obtain T 16 = v 1 ⊕ v 5 ⊕ v 16 T_{16}=v_1\oplus v_5\oplus v_{16} T 16 = v 1 ⊕ v 5 ⊕ v 16 , which at bit position 16 is b 0 = ( ( v ≪ 15 ) ⊕ ( v ≪ 11 ) ⊕ v ) & 0 x00010000 b_0=((v\ll15)\oplus(v\ll11)\oplus v)\mathbin{\&}0\text{x00010000} b 0 = (( v ≪ 15 ) ⊕ ( v ≪ 11 ) ⊕ v ) & 0 x00010000 }.
Proved algebraically above for all u ∈ Z 2 32 u\in\mathbb{Z}_{2^{32}} u ∈ Z 2 32 and verified empirically on 10 6 10^6 1 0 6 pseudorandom words plus 3 × 2 16 3\times2^{16} 3 × 2 16 systematic boundary/carry cases (including u = 0 x00400000 u=0\text{x00400000} u = 0 x00400000 ) in test_all_12_theories.c (test_theory_01) with 0 mismatches. □
Slot-Indexed Q 0 − 1 Q_0^{-1} Q 0 − 1 Tables: 6.00 GiB 2-Tier Nested 4-Slot EDF Table & 8.00–32.00 GiB Direct Tables ([E30]–[E33])
Over all 2 32 2^{32} 2 32 inputs u ∈ Z 2 32 u\in\mathbb{Z}_{2^{32}} u ∈ Z 2 32 , the exact, race-free preimage multiplicity histogram of Q 0 ( u ) = σ 0 ( u ) − u ( m o d 2 32 ) Q_0(u)=\sigma_0(u)-u\pmod{2^{32}} Q 0 ( u ) = σ 0 ( u ) − u ( mod 2 32 ) is:
N 0 = 1 , 573 , 363 , 668 N_0=1,573,363,668 N 0 = 1 , 573 , 363 , 668 (36.6327% of y y y have 0 roots, vs. Poisson(1) e − 1 = 36.7879 % e^{-1}=36.7879\% e − 1 = 36.7879% ),
N 1 = 1 , 586 , 605 , 819 N_1=1,586,605,819 N 1 = 1 , 586 , 605 , 819 (36.9410%), N 2 = 793 , 515 , 119 N_2=793,515,119 N 2 = 793 , 515 , 119 (18.4755%), N 3 = 262 , 185 , 142 N_3=262,185,142 N 3 = 262 , 185 , 142 (6.1045%),
N 4 = 64 , 407 , 366 N_4=64,407,366 N 4 = 64 , 407 , 366 (1.4996%), N 5 = 12 , 552 , 261 N_5=12,552,261 N 5 = 12 , 552 , 261 (0.2923%), N 6 = 2 , 022 , 487 N_6=2,022,487 N 6 = 2 , 022 , 487 (0.0471%),
N 7 = 277 , 772 N_7=277,772 N 7 = 277 , 772 (0.0065%), N 8 = 33 , 662 N_8=33,662 N 8 = 33 , 662 (0.0008%), and N ≥ 9 = 4 , 000 N_{\geq9}=4,000 N ≥ 9 = 4 , 000 (0.0001%; specifically N 9 = 3 , 624 N_9=3,624 N 9 = 3 , 624 , N 10 = 338 N_{10}=338 N 10 = 338 , N 11 = 33 N_{11}=33 N 11 = 33 , N 12 = 3 N_{12}=3 N 12 = 3 , N 13 = 1 N_{13}=1 N 13 = 1 , N 14 = 1 N_{14}=1 N 14 = 1 , with tail root weight ∑ k = 9 14 k N k = 36 , 422 \sum_{k=9}^{14}kN_k=36,422 ∑ k = 9 14 k N k = 36 , 422 ),
satisfying the exact conservation identities ∑ k = 0 14 N k = 2 32 = 4 , 294 , 967 , 296 \sum_{k=0}^{14}N_k=2^{32}=4,294,967,296 ∑ k = 0 14 N k = 2 32 = 4 , 294 , 967 , 296 and ∑ k = 0 14 k N k = 2 32 = 4 , 294 , 967 , 296 \sum_{k=0}^{14}kN_k=2^{32}=4,294,967,296 ∑ k = 0 14 k N k = 2 32 = 4 , 294 , 967 , 296 . To avoid conflating distinct sources of root loss, we separate three effects: (i) unconstrained C C C -slot capacity ∑ k = 0 14 min ( k , C ) N k / 2 32 \sum_{k=0}^{14}\min(k,C)N_k/2^{32} ∑ k = 0 14 min ( k , C ) N k / 2 32 , which equals 3 , 856 , 601 , 437 / 2 32 = 89.7935 % 3,856,601,437/2^{32}=89.7935\% 3 , 856 , 601 , 437/ 2 32 = 89.7935% for C = 2 C=2 C = 2 (72.399% 3-level survival), 4 , 198 , 084 , 127 / 2 32 = 97.7443 % 4,198,084,127/2^{32}=97.7443\% 4 , 198 , 084 , 127/ 2 32 = 97.7443% for C = 3 C=3 C = 3 (93.384% 3-level), and 4 , 277 , 381 , 675 / 2 32 = 99.5906 % 4,277,381,675/2^{32}=99.5906\% 4 , 277 , 381 , 675/ 2 32 = 99.5906% for C = 4 C=4 C = 4 (98.777% 3-level); (ii) u_lo = 0 empty-slot sentinel exclusion (1 / 65 , 536 ≈ 0.0015 % 1/65,536\approx0.0015\% 1/65 , 536 ≈ 0.0015% of inputs have u m o d 2 16 = 0 u\bmod2^{16}=0 u mod 2 16 = 0 , shifting the stored root count by at most 65,536, e.g. to 89.7924% for C = 2 C=2 C = 2 , alongside historical pre-CAS finite-pass table builds that recorded 3 , 856 , 410 , 516 / 2 32 = 89.7891 % 3,856,410,516/2^{32}=89.7891\% 3 , 856 , 410 , 516/ 2 32 = 89.7891% for C = 2 C=2 C = 2 and 4 , 276 , 521 , 180 / 2 32 = 99.5705 % 4,276,521,180/2^{32}=99.5705\% 4 , 276 , 521 , 180/ 2 32 = 99.5705% for C = 4 C=4 C = 4 ); and (iii) quad-shared 12-slot sliding/cuckoo eviction in the compact 6.00 GiB format. By Theorem 2 , storing only the lower 16 bits u l o = u m o d 2 16 u_{\mathrm{lo}}=u\bmod2^{16} u lo = u mod 2 16 halves the memory footprint of every table tier:
6.00 GiB 2-Tier Nested 4-Slot EDF + Cuckoo-Sudoku Table (solve20_padded_fast.c): Designed for 16 GiB laptops (3 × 2 30 3\times2^{30} 3 × 2 30 entries of uint16_t = 6.00 GiB), where every 16 consecutive y y y values (a quad q = y ≫ 4 q=y\gg4 q = y ≫ 4 ) share 12 contiguous 16-bit slots:
slide3_off ( y ) = ( y ≫ 1 ) + ( y ≫ 2 ) − ( ROR ( 0 x6AAA6AAA , y & 31 ) ≫ 31 ) . (28) \operatorname{slide3\_off}(y)=(y\gg1)+(y\gg2)-(\operatorname{ROR}(0\text{x6AAA6AAA},y\mathbin{\&}31)\gg31). \tag*{(28)} slide3_off ( y ) = ( y ≫ 1 ) + ( y ≫ 2 ) − ( ROR ( 0 x6AAA6AAA , y & 31 ) ≫ 31 ) . (28)
Cuckoo-Sudoku Eviction & Nested 4th Slot ([E31]): During construction, a cuckoo-relocation pass (sudoku_upgrade_worker_6gb and tier2_nest4_quad_worker) packs displaced preimages across each 12-slot quad, placing any 4th root at b [ ( y ∧ 15 ) ≥ 13 ? − 1 : 3 ] b[(y \mathbin{\wedge} 15) \ge13 ? -1 : 3] b [( y ∧ 15 ) ≥ 13 ? − 1 : 3 ] (probed only when all 3 primary slots are valid roots of y y y ). At Level 3, all 12 slots of the quad (3 x uint64_t) are tested simultaneously via 64-bit SWAR ([E35]):
6.00 G i B C o v e r a g e = 3,563,795,213 2 32 = 82.976 % , 3 - L e v e l S u r v i v a l = ( 0.82976 ) 3 = 57.13 % . (29) 6.00\ \mathrm{GiB\ Coverage} = \frac{3{,}563{,}795{,}213}{2^{32}} = 82.976\%, \quad3\text{-}\mathrm{Level\ Survival} = (0.82976)^3 = 57.13\%. \tag*{(29)} 6.00 GiB Coverage = 2 32 3 , 563 , 795 , 213 = 82.976% , 3 - Level Survival = ( 0.82976 ) 3 = 57.13%. (29)
8.00 GiB / 16.00 GiB Direct-Indexed 2-Way GPU VRAM Tables (solve20_padded_cuda.cu): Built natively in GPU VRAM in 3.11 seconds, storing up to two roots per y y y (unconstrained 2-way capacity 3,856,601,437 / 2 32 = 89.7935 % 3{,}856{,}601{,}437/2^{32} = 89.7935\% 3 , 856 , 601 , 437/ 2 32 = 89.7935% / 3-level survival 72.399%, or 89.7924% with u_lo = 0 sentinel exclusion):
2-Way Direct Capacity = 3,856,601,437 2 32 = 89.7935 % , 3-Level Survival = ( 0.897935 ) 3 = 72.399 % . (30) \text{2-Way Direct Capacity} = \frac{3{,}856{,}601{,}437}{2^{32}} = 89.7935\%, \quad\text{3-Level Survival} = (0.897935)^3 = 72.399\%. \tag*{(30)} 2-Way Direct Capacity = 2 32 3 , 856 , 601 , 437 = 89.7935% , 3-Level Survival = ( 0.897935 ) 3 = 72.399%. (30)
32.00 GiB Direct-Indexed 4-Way Exact CPU Table (H_exact32[y], –table-gb32): Stores up to four 16-bit roots per y y y in one uint64_t (32.00 GiB table + 4.00 GiB count array + 16.00 GiB optional F 1 F_1 F 1 table = 52.00 GiB persistent RAM, 68.00 GiB peak during parallel radix sort), achieving 99.5906% unconstrained 4-way capacity (98.777% 3-level survival, or 4,276,521,180 / 2 32 = 99.5705 % 4{,}276{,}521{,}180/2^{32} = 99.5705\% 4 , 276 , 521 , 180/ 2 32 = 99.5705% / 98.717% 3-level in the pre-CAS u_lo = 0-excluded build):
4-Way Direct Capacity = 4,277,381,675 2 32 = 99.5906 % , 3-Level Survival = ( 0.995906 ) 3 = 98.777 % . (31) \text{4-Way Direct Capacity} = \frac{4{,}277{,}381{,}675}{2^{32}} = 99.5906\%, \quad\text{3-Level Survival} = (0.995906)^3 = 98.777\%. \tag*{(31)} 4-Way Direct Capacity = 2 32 4 , 277 , 381 , 675 = 99.5906% , 3-Level Survival = ( 0.995906 ) 3 = 98.777%. (31)
The 3-Level Tree Search, 64-Bit SWAR Level-3 Filter, and Terminal 20-Step Bijection ([E34]–[E37])
For each a 1 a_1 a 1 and each Right context in a batch of size B B B :
Level 1 (a 1 → W 1 → a 2 a_1 \to W_1 \to a_2 a 1 → W 1 → a 2 ) & Level 2 (a 2 → W 2 → a 3 a_2 \to W_2 \to a_3 a 2 → W 2 → a 3 ) with Early Hamming Pruning ([E34]): From a 1 a_1 a 1 , look up W 1 ∈ Q 0 − 1 ( T 16 + F 1 ( a 1 ) ) W_1 \in Q_0^{-1}(T_{16} + F_1(a_1)) W 1 ∈ Q 0 − 1 ( T 16 + F 1 ( a 1 )) , set a 2 = W 1 + G 1 ( a 1 ) a_2 = W_1 + G_1(a_1) a 2 = W 1 + G 1 ( a 1 ) , look up W 2 ∈ Q 0 − 1 ( T 17 + G 2 ( a 1 , a 2 ) − W 1 ) W_2 \in Q_0^{-1}(T_{17} + G_2(a_1, a_2) - W_1) W 2 ∈ Q 0 − 1 ( T 17 + G 2 ( a 1 , a 2 ) − W 1 ) , and set a 3 = W 2 + G 2 a_3 = W_2 + G_2 a 3 = W 2 + G 2 . Before computing e 3 e_3 e 3 , G 3 G_3 G 3 or issuing Level-3 DRAM loads, we prune any a 3 a_3 a 3 whose majority mask M 3 = ¬ ( a 3 ⊕ a 5 ) M_3 = \neg(a_3 \oplus a_5) M 3 = ¬ ( a 3 ⊕ a 5 ) has Hamming weight exceeding w t h r e s h ∈ { 13 , 14 } w_{\mathrm{thresh}} \in\{13, 14\} w thresh ∈ { 13 , 14 } :
popcount ( ¬ ( a 3 ⊕ a 5 ) ) ≤ w t h r e s h , (32) \operatorname{popcount}(\neg(a_3 \oplus a_5)) \le w_{\mathrm{thresh}}, \tag*{(32)} popcount ( ¬ ( a 3 ⊕ a 5 )) ≤ w thresh , (32)
eliminating 81.15% (w t h r e s h = 13 w_{\mathrm{thresh}} = 13 w thresh = 13 , exact Binomial( 32 , 1 / 2 ) (32, 1/2) ( 32 , 1/2 ) upper tail Pr [ Binomial ( 32 , 1 / 2 ) > 13 ] \Pr[\operatorname{Binomial}(32, 1/2) > 13] Pr [ Binomial ( 32 , 1/2 ) > 13 ] ) to 70.17% (w t h r e s h = 14 w_{\mathrm{thresh}} = 14 w thresh = 14 ) of Level-3 lookups.
Level 3: 64-Bit SWAR Pre-Reconstruction Filter & 19-Step Bridge Candidate Stream ([E35]): Because the majority condition ( ( a 4 ⊕ a 5 ) ∧ M 3 ) = 0 ((a_4 \oplus a_5) \mathbin{\wedge} M_3) = 0 (( a 4 ⊕ a 5 ) ∧ M 3 ) = 0 ([E13]) is lower-triangular on bits 0..14, any candidate u l o u_{\mathrm{lo}} u lo must satisfy ( ( ( u l o + G 3 ) ⊕ a 5 ) ∧ M 3 ∧ 0 x 7 f f f ) = 0 (((u_{\mathrm{lo}} + G_3) \oplus a_5) \mathbin{\wedge} M_3 \mathbin{\wedge} 0\mathrm{x}7fff) = 0 ((( u lo + G 3 ) ⊕ a 5 ) ∧ M 3 ∧ 0 x 7 f f f ) = 0 before u h i u_{\mathrm{hi}} u hi is reconstructed. In the 6.00 GiB table, we test 4 slots at a time in a single 64-bit word w w w using SWAR carry-bit detection (K7 = 0x7fff7fff7fff7fff, K8 = 0x8000800080008000):
d = ( ( ( ( w ∧ K 7 ) + g 64 ) ⊕ A 64 ) ∧ m 64 ) + K 7 , 4 -slot hit mask = ¬ d ∧ K 8 , (33) d = ((((w \mathbin{\wedge} K_7) + g_{64}) \oplus A_{64}) \mathbin{\wedge} m_{64}) + K_7,\quad4\text{-slot hit mask} = \neg d \mathbin{\wedge} K_8, \tag*{(33)} d = (((( w ∧ K 7 ) + g 64 ) ⊕ A 64 ) ∧ m 64 ) + K 7 , 4 -slot hit mask = ¬ d ∧ K 8 , (33)
rejecting > 99 % >99\% > 99% of 12-slot quads in 3 register operations. Every candidate passing the full 32-bit check ( ( a 4 ⊕ a 5 ) ∧ M 3 ) = 0 ((a_4 \oplus a_5) \land M_3)=0 (( a 4 ⊕ a 5 ) ∧ M 3 ) = 0 with Q 0 ( W 3 ) = t 18 Q_0(W_3)=t_{18} Q 0 ( W 3 ) = t 18 is a schedule-consistent 19-step padded bridge candidate (sol19, incremented via local_sol19++) satisfying W 16 , W 17 , W 18 W_{16}, W_{17}, W_{18} W 16 , W 17 , W 18 for the current right-hand context.
σ 0 ( W 4 ) + W 3 ≡ T 19 ( m o d 2 32 ) , T 19 : = W 19 − σ 1 ( W 17 ) − W 12 . (34) \sigma_0(W_4)+W_3 \equiv T_{19}\pmod{2^{32}}, \qquad T_{19}:=W_{19}-\sigma_1(W_{17})-W_{12}. \tag*{(34)} σ 0 ( W 4 ) + W 3 ≡ T 19 ( mod 2 32 ) , T 19 := W 19 − σ 1 ( W 17 ) − W 12 . (34)
Viewing σ 0 ( x ) = ROR ( x , 7 ) ⊕ ROR ( x , 18 ) ⊕ ( x ≫ 3 ) \sigma_0(x)=\operatorname{ROR}(x,7)\oplus\operatorname{ROR}(x,18)\oplus(x\gg3) σ 0 ( x ) = ROR ( x , 7 ) ⊕ ROR ( x , 18 ) ⊕ ( x ≫ 3 ) as a 32 × 32 32\times32 32 × 32 matrix over F 2 \mathbb{F}_2 F 2 , we have det F 2 ( σ 0 ) = 1 \det_{\mathbb{F}_2}(\sigma_0)=1 det F 2 ( σ 0 ) = 1 :
det F 2 ( σ 0 ) = 1 ⟹ W 4 = σ 0 − 1 ( ( T 19 − W 3 ) m o d 2 32 ) is uniquely determined by W 3 and T 19 . (35) \det_{\mathbb{F}_2}(\sigma_0)=1 \Longrightarrow W_4=\sigma_0^{-1}\left((T_{19}-W_3)\bmod2^{32}\right)\text{ is uniquely determined by }W_3\text{ and }T_{19}. \tag*{(35)} F 2 det ( σ 0 ) = 1 ⟹ W 4 = σ 0 − 1 ( ( T 19 − W 3 ) mod 2 32 ) is uniquely determined by W 3 and T 19 . (35)
Exact-T 16 T_{16} T 16 Twin Coalescing, L2 Cache Tiling, and Lower-Triangular Pruning ([E42]–[E45])
To maximize memory-system throughput across Levels 1–3 on GPU (solve20_padded_cuda_prod.cu, solve20_padded_cuda.cu), we combine four techniques (formalized in Algorithm 2 ):
L2-Localized Level-1 Bridge Extraction (extract_l1_bridges_kernel, [E42]): The NVIDIA L4 GPU features a 48 MiB L2 cache. Because F 1 ( a 1 ) = G 1 ( a 1 ) − W 0 ( a 1 ) F_1(a_1)=G_1(a_1)-W_0(a_1) F 1 ( a 1 ) = G 1 ( a 1 ) − W 0 ( a 1 ) includes the 32-bit rotation Σ 1 ( e 1 ( a 1 ) ) \Sigma_1(e_1(a_1)) Σ 1 ( e 1 ( a 1 )) , F 1 F_1 F 1 is not lower-triangular in the 2-adic bit order of a 1 a_1 a 1 (for example, a 1 = 0 ⟹ F 1 = 0d3fffb7 a_1=0\Longrightarrow F_1=\texttt{0d3fffb7} a 1 = 0 ⟹ F 1 = 0d3fffb7 whereas a 1 = 4 ⟹ F 1 = 3ce015b4 a_1=4\Longrightarrow F_1=\texttt{3ce015b4} a 1 = 4 ⟹ F 1 = 3ce015b4 , which differ in bit 0). Instead of assuming lower-triangularity of F 1 F_1 F 1 , extract_l1_bridges_kernel partitions Q 0 − 1 Q_0^{-1} Q 0 − 1 global-memory lookups into address tiles [ T i l e l o , T i l e h i ) [\mathrm{Tile}_{\mathrm{lo}},\mathrm{Tile}_{\mathrm{hi}}) [ Tile lo , Tile hi ) of width Δ t i l e = T i l e h i − T i l e l o \Delta_{\mathrm{tile}}=\mathrm{Tile}_{\mathrm{hi}}-\mathrm{Tile}_{\mathrm{lo}} Δ tile = Tile hi − Tile lo (at 4 bytes per uint32_t entry in the 16.00 GiB 2-Way table, an L2-resident 16–32 MiB tile spans Δ t i l e = 2 22 \Delta_{\mathrm{tile}}=2^{22} Δ tile = 2 22 –2 23 2^{23} 2 23 indices across 512–1024 tile passes, whereas Δ t i l e = 2 29 \Delta_{\mathrm{tile}}=2^{29} Δ tile = 2 29 indices spans a 2.00 GiB slice across 8 passes) and tests the target index t 16 ( a 1 ) = ( T 16 + F 1 ( a 1 ) ) m o d 2 32 t_{16}(a_1)=(T_{16}+F_1(a_1))\bmod2^{32} t 16 ( a 1 ) = ( T 16 + F 1 ( a 1 )) mod 2 32 in registers before issuing a global memory read:
( T 16 + F 1 ( a 1 ) − T i l e l o ) m o d 2 32 < Δ t i l e ⟹ under a uniform index model, a fraction Δ t i l e 2 32 issues a global read per tile pass, (36) (T_{16}+F_1(a_1)-\mathrm{Tile}_{\mathrm{lo}})\bmod2^{32}<\Delta_{\mathrm{tile}}\Longrightarrow\text{ under a uniform index model, a fraction }\frac{\Delta_{\mathrm{tile}}}{2^{32}}\text{ issues a global read per tile pass,} \tag*{(36)} ( T 16 + F 1 ( a 1 ) − Tile lo ) mod 2 32 < Δ tile ⟹ under a uniform index model, a fraction 2 32 Δ tile issues a global read per tile pass, (36)
converting uncoalesced 16.00 GiB DRAM accesses into localized tile passes across the sweep (without reducing total work summed over all passes).
Exact 32-Bit T 16 T_{16} T 16 Twin Coalescing (twin2) vs. 4-Way Reservoir Sampling (single4, [E43]): Across all 2 32 2^{32} 2 32 seeds a 12 a_{12} a 12 , a 20-step target H 20 ∗ H_{20}^{*} H 20 ∗ has an estimated universe of U ≈ 1.68 × 10 7 ≈ 2 24.00 U\approx1.68\times10^7\approx2^{24.00} U ≈ 1.68 × 1 0 7 ≈ 2 24.00 exact D s h a p e = 0 D_{\mathrm{shape}}=0 D shape = 0 right contexts (or U f i l t ≈ 1.014 × 10 7 ≈ 2 23.27 U_{\mathrm{filt}}\approx1.014\times10^7\approx2^{23.27} U filt ≈ 1.014 × 1 0 7 ≈ 2 23.27 if the optional Stage-2 heuristic is enabled). Sorting a reservoir of contexts by T 16 T_{16} T 16 yields N t w i n s ≈ U 2 / 2 33 ≈ 32 , 890 N_{\mathrm{twins}}\approx U^2/2^{33}\approx32,890 N twins ≈ U 2 / 2 33 ≈ 32 , 890 exact 32-bit T 16 T_{16} T 16 twin pairs across U U U (or ≈ 11 , 970 \approx11,970 ≈ 11 , 970 pairs in U f i l t U_{\mathrm{filt}} U filt ) where T 16 ( 2 m ) = T 16 ( 2 m + 1 ) T_{16}^{(2m)}=T_{16}^{(2m+1)} T 16 ( 2 m ) = T 16 ( 2 m + 1 ) (sweep_exact16_cuda_kernel in solve20_padded_cuda_prod.cu and solve20_padded_cuda.cu). Both contexts in each genuine twin pair share the exact same Level-1 lookup Q 0 − 1 ( T 16 + F 1 ( a 1 ) ) Q_0^{-1}(T_{16}+F_1(a_1)) Q 0 − 1 ( T 16 + F 1 ( a 1 )) (0.50 Level-1 lookups/context), solving 12 of our 16 padded 20-step targets directly. For the remaining 4 targets (16/16 total), the non-twin 4-way reservoir kernels (sweep_20_warp_13_prod_kernel in solve20_padded_cuda_prod.cu and sweep_exact16_cuda_kernel in solve20_padded_cuda.cu) sample from the reservoir
U U U using 4-way register-prefetched Level-1 batches (achieving 53,847.5–73,560.5 sol19/s on the 6.00 GiB table and 132,888.7 sol19/s on genuine Exact-T 16 T_{16} T 16 twin pairs in the 16.00 GiB table on 1× L4 GPU):
T 16 ( 2 m ) = T 16 ( 2 m + 1 ) across M = 64 genuine twin pairs ( B = 128 ) ⟹ 0.50 L1 lookups per context. (37) T_{16}^{(2m)} = T_{16}^{(2m+1)} \quad\text{across } M = 64 \text{ genuine twin pairs } (B = 128) \Longrightarrow0.50\ \text{L1 lookups per context.} \tag*{(37)} T 16 ( 2 m ) = T 16 ( 2 m + 1 ) across M = 64 genuine twin pairs ( B = 128 ) ⟹ 0.50 L1 lookups per context. (37)
(Note: whereas 32-bit T 16 T_{16} T 16 collisions occur naturally in U ≈ 2 24.0 U \approx2^{24.0} U ≈ 2 24.0 , joint 64-bit ( T 16 , T 17 ) (T_{16}, T_{17}) ( T 16 , T 17 ) collisions require a birthday pool of 2 32 ≫ U 2^{32} \gg U 2 32 ≫ U contexts; all witness runs and primary complexity figures in this paper use only genuine, unmutated contexts.)
3. Pre-ulo2 16-Bit Lower-Triangular Hamming Pruning ([E44]): Before reconstructing the upper 16 bits of W 2 W_2 W 2 via [E29], we exploit lower-triangularity of modular addition on bits 0..15:
w l o , 2 : = popcount ( ¬ ( ( u l o , 2 + G 2 ) ⊕ a 5 ) ∧ 0xffff ) ≤ w l o , t h r e s h ∈ { 7 , 11 } . (38) w_{\mathrm{lo},2} := \operatorname{popcount}\left(\neg\left((u_{\mathrm{lo},2} + G_2) \mathbin{\oplus} a_5\right) \mathbin{\wedge} \texttt{0xffff}\right) \le w_{\mathrm{lo},\mathrm{thresh}} \in\{7, 11\}. \tag*{(38)} w lo , 2 := popcount ( ¬ ( ( u lo , 2 + G 2 ) ⊕ a 5 ) ∧ 0xffff ) ≤ w lo , thresh ∈ { 7 , 11 } . (38)
For a uniform 16-bit mask, Binomial( 16 , 1 / 2 ) (16, 1/2) ( 16 , 1/2 ) rejects 39,203/65,536 ≈ 59.82 % \approx59.82\% ≈ 59.82% of Level-2 candidates at w l o , t h r e s h = 7 w_{\mathrm{lo},\mathrm{thresh}} = 7 w lo , thresh = 7 and 2,517/65,536 ≈ 3.84 % \approx3.84\% ≈ 3.84% at w l o , t h r e s h = 11 w_{\mathrm{lo},\mathrm{thresh}} = 11 w lo , thresh = 11 prior to upper-half reconstruction.
4. The 4-Round Crossed Carry-Sudoku Spine (a 2 = a 3 = a 4 = a 5 a_2 = a_3 = a_4 = a_5 a 2 = a 3 = a 4 = a 5 , [E45]): Crossing the shaping constraint across 4 consecutive rounds by pinning a 2 = a 3 = a 4 = a 5 a_2 = a_3 = a_4 = a_5 a 2 = a 3 = a 4 = a 5 (cross_round_4step_sudoku_direct_kernel in solve20_padded_cuda.cu) collapses all four majority functions to a 5 a_5 a 5 and makes W 1 W_1 W 1 , W 2 W_2 W 2 , W 3 W_3 W 3 direct functions of a 1 a_1 a 1 with zero Q 0 − 1 Q_0^{-1} Q 0 − 1 table lookups:
a 2 = a 3 = a 4 = a 5 ⟹ Maj ( a 3 , a 2 , a 1 ) = Maj ( a 4 , a 3 , a 2 ) = Maj ( a 5 , a 4 , a 3 ) = Maj ( a 6 , a 5 , a 4 ) = a 5 , e 4 = a 0 − Σ 0 ( a 5 ) , W 3 = c W 3 − Σ 1 ( e 3 ) − Ch ( e 3 , e 2 , e 1 ) , 5-step ( a 1 = a 5 ) : e 3 = a − 1 − Σ 0 ( a 5 ) ⟹ W 3 ( a 0 ) = C 3 − Ch ( e 3 , e 2 , e 1 ) . (39) \begin{aligned}
a_2 = a_3 = a_4 = a_5 \Longrightarrow\ &\operatorname{Maj}(a_3,a_2,a_1) = \operatorname{Maj}(a_4,a_3,a_2) = \operatorname{Maj}(a_5,a_4,a_3) = \operatorname{Maj}(a_6,a_5,a_4) = a_5, \\
&e_4 = a_0 - \Sigma_0(a_5), \quad W_3 = cW_3 - \Sigma_1(e_3) - \operatorname{Ch}(e_3,e_2,e_1), \\
&\text{5-step } (a_1 = a_5):\ e_3 = a_{-1} - \Sigma_0(a_5) \Longrightarrow W_3(a_0) = C_3 - \operatorname{Ch}(e_3,e_2,e_1). \tag*{(39)}
\end{aligned} a 2 = a 3 = a 4 = a 5 ⟹ Maj ( a 3 , a 2 , a 1 ) = Maj ( a 4 , a 3 , a 2 ) = Maj ( a 5 , a 4 , a 3 ) = Maj ( a 6 , a 5 , a 4 ) = a 5 , e 4 = a 0 − Σ 0 ( a 5 ) , W 3 = c W 3 − Σ 1 ( e 3 ) − Ch ( e 3 , e 2 , e 1 ) , 5-step ( a 1 = a 5 ) : e 3 = a − 1 − Σ 0 ( a 5 ) ⟹ W 3 ( a 0 ) = C 3 − Ch ( e 3 , e 2 , e 1 ) . (39)
Because a 2 = a 3 = a 4 = a 5 a_2 = a_3 = a_4 = a_5 a 2 = a 3 = a 4 = a 5 spends 96 Left bits, the 3 schedule equations W 16 W_{16} W 16 , W 17 W_{17} W 17 , W 18 W_{18} W 18 become a 96-bit Right filter, illustrating the degree-of-freedom conservation trade-off (§9.2).
Algorithm 2: Left-to-Right Slot-Sudoku Tree & Terminal 20-Step Preimage Solver
Input: Context batch C of size B=128 (T_{16} twin-coalesced or 4-way batched), 2-way table H_ulo
Output: Stream of 19-step bridge candidates (sol19) and matching 20-step padded preimage M*
1. for each root a_1 in [0, 2^32) and context group in C do
2. Compute F_1(a_1) and G_1(a_1); prefetch Level-1 entries from H_ulo[T_{16} + F_1(a_1)]
// [E14], [E43]
3. for each valid Level-1 root W_1 do
4. Set a_2 = W_1 + G_1(a_1); compute G_2(a_1, a_2); load u_{lo,2} from H_ulo[T_{17} + G_2
- W_1]
5. if popcount((~((u_{lo,2} + G_2) ^ a_5)) & 0xffff) <= w_{lo,thresh} then
// [E44]
6. Reconstruct W_2 via [E28]-[E29]; set a_3 = W_2 + G_2 and M_3 = ~(a_3 ^ a_5)
7. if popcount(M_3) <= 14 then
// [E34]
8. Load u_{lo,3} from H_ulo[T_{18} + G_3 - W_2]; filter (((u_{lo,3}+G_3) ^ a_5) & M_3 &
0x7fff)==0 // [E35]
9. Reconstruct W_3 via [E28]-[E29]; set a_4 = W_3 + G_3
10. if ((a_4 ^ a_5) & M_3) == 0 then
// [E13]
11. Emit 19-step bridge candidate (sol19); compute W_4 via [E7]
12. if sigma_0(W_4) + W_3 == T_{19} (mod 2^32) then return 20-step padded preimage M*
// [E36]
Precomputation vs. Online Time, Memory, and SHA-256-Equivalent Complexity
Following standard cryptographic convention [2 , 3 , 4 , 8 ] , Table 6.1 separates target-independent precomputation (Q 0 − 1 Q_{0}^{-1} Q 0 − 1 table construction) from target-dependent online complexity , reported both in direct wall-clock time (node-h / node-hours denoting wall-clock hours on one 10-core Apple M4 CPU node running 16 threads) and against our measured same-host 10-core Apple M4 CPU reference baseline (1.5125 × 10 8 1.5125 \times10^{8} 1.5125 × 1 0 8 SHA20-eq/s across 16 threads, measured on arbitrary 20-step message blocks, so 1 node-h = 2 38.99 2^{38.99} 2 38.99 CPU-ref). To avoid conflating CPU work factors with cross-hardware elapsed-time conversions, we report:
Table 6.1. Precomputation and online complexities of the proposed 19- and 20-step preimage attacks on genuine contexts.
Host-Verifiable CPU Solver (solve20_padded_fast.c, one 10-core Apple M4 CPU node, 16 threads): Generates 6,242.8 sol19/s (160.2 μ \mu μ s/sol19, measured on a 1 a_{1} a 1 slice sweeps) on genuine unmutated contexts. Against the same-host CPU reference baseline (1.5125 × 10 8 1.5125 \times10^{8} 1.5125 × 1 0 8 SHA20-eq/s), each sol19 costs 24,227.9 ≈ 2 14.56 \approx2^{14.56} ≈ 2 14.56 CPU-ref evaluations, and an expected 20-step padded preimage (2 32 2^{32} 2 32 sol19 = 191.1 node-h [≈ \approx ≈ 191 node-hours] on one 10-core Apple M4 CPU node [16 threads], or 23.9 node-h across 8 CPU nodes) costs 2 46.56 2^{46.56} 2 46.56 CPU-ref (≈ 2 46.6 \approx2^{46.6} ≈ 2 46.6 ) evaluations.
Supplementary GPU Slice Telemetry (solve20_padded_cuda.cu / solve20_padded_cuda_prod.cu, 1× \times × NVIDIA L4 GPU): On genuine unmutated contexts, measured a 1 a_{1} a 1 -slice sweep telemetry (BENCH_4_IDEAS_RESULTS.txt and solve20_padded_cuda.cu) records 53,847.5 sol19/s (Cycle 0, 6.00 GiB 2-Tier EDF, B = 2 B = 2 B = 2 , 22.16 GPU-h [≈ \approx ≈ 22.2 GPU-hours]) to 73,560.5 sol19/s (Cycle 1, 6.00 GiB 2-Tier EDF, B = 8 B = 8 B = 8 , 16.22 GPU-h per 2 32 2^{32} 2 32 sol19 on 1× \times × L4), and 132,888.7 sol19/s on genuine Exact-T16 _{16} 16 twin pairs in the 16.00 GiB Direct 2-Way table (sweep_exact16_cuda_kernel in solve20_padded_cuda_prod.cu and Cycle 1 of solve20_padded_cuda.cu, 8.98 GPU-h [≈ \approx ≈ 9.0 GPU-hours] on 1× \times × L4, or 1.12 h on 8× \times × L4). (The experimental -bench-c2 through -bench-c10 harnesses [Cycles 2, 4, and 7–10 in solve20_padded_cuda.cu, including the 180,831.9 sol19/s / 6.60 GPU-h B = 16 B = 16 B = 16 shared-T16 _{16} 16 run] are architectural microbenchmarks and are excluded from single-target complexity claims; likewise, the 9.62 × 10 9 9.62 \times10^{9} 9.62 × 1 0 9 evals/s GPU rate in Table 9.4 Row 13 is the specialized 4-round crossed-spine kernel rather than an arbitrary-message 20-step SHA-256 baseline. )
Table 9.4. Taxonomy of 15 construction-specific candidate sub-2 32 2^{32} 2 32 directions evaluated against the 20-step terminal filter.
Chosen-Target 19-Step Padded Hash (src/pre19.c, 1 CPU core of 10-core Apple M4): src/pre19.c is a single-threaded C solver using clock() with default m = 29 m = 29 m = 29 (2 29 2^{29} 2 29 entries), where the one-time, target-independent two-pass CSR builder performs 2 × 2 29 = 2 30 2 \times2^{29} = 2^{30} 2 × 2 29 = 2 30 Q 0 Q_{0} Q 0 evaluations in 16.8–19.1 s (≈ \approx ≈ 18 s, or 2 × 2 30 = 2 31 2 \times2^{30} = 2^{31} 2 × 2 30 = 2 31 Q 0 Q_{0} Q 0 evaluations at m = 30 m = 30 m = 30 ) and allocates 4 × 2 29 4 \times2^{29} 4 × 2 29 B = 2.0 GiB for table_values plus 64 MiB for table_offsets (2.0625 GiB persistent RAM). Across our 14 public-label 19-step targets, per-target single-core online search time (excluding the one-time table build) ranges from 1.2 s to 86.4 s (median 19.45 s [≈ \approx ≈ 19.5 s], mean 30.2 s). In direct operation counts, per-target online search is dominated by right-context generation (≈ 1.2 × 10 8 ≈ 2 26.7 – 26.9 \approx1.2 \times10^{8} \approx2^{26.7\text{–}26.9} ≈ 1.2 × 1 0 8 ≈ 2 26.7 – 26.9 trials per usable D ≤ 3 D \le3 D ≤ 3 context, with 1–7 contexts tested per target across the 14 targets, i.e., ≤ 7 × 2 26.9 ≈ 2 29.7 \le7 \times2^{26.9} \approx2^{29.7} ≤ 7 × 2 26.9 ≈ 2 29.7 context trials) plus ≈ 1.8 × 10 6 – 1.2 × 10 8 \approx1.8 \times10^{6\text{–}1.2} \times10^{8} ≈ 1.8 × 1 0 6 – 1.2 × 1 0 8 (2 25.9 – 26.8 2^{25.9\text{–}26.8} 2 25.9 – 26.8 , median ≈ 2 25.5 \approx2^{25.5} ≈ 2 25.5 at m = 29 m = 29 m = 29 ) left chain starts, totaling ≈ 2 26.9 – 29.89 \approx2^{26.9\text{–}29.89} ≈ 2 26.9 – 29.89 online trial/chain operations per target (or ≈ 2 30.95 – 31.55 \approx2^{30.95\text{–}31.55} ≈ 2 30.95 – 31.55 operations when adding the one-time 2 30 – 31 2^{30\text{–}31} 2 30 – 31 Q 0 Q_{0} Q 0 table build at m = 29 , 30 m = 29,30 m = 29 , 30 ). Expressed in the elapsed-time CPU-ref proxy (151.25 M evals/s), the per-target online search alone corresponds to 2 27.4 – 33.6 2^{27.4\text{–}33.6} 2 27.4 – 33.6 CPU-ref (median 2 31.46 2^{31.46} 2 31.46 CPU-ref at 19.45 s, mean 2 32.10 2^{32.10} 2 32.10 CPU-ref at 30.2 s), while a cold-start single-target run including the one-time amortizable table build (≈ \approx ≈ 40.4–51.9 s mean total across m ∈ { 29 , 30 } m \in\{29, 30\} m ∈ { 29 , 30 } , e.g., 18 s + 30.2 s = 48.2 s) corresponds to 2 32.51 – 32.87 2^{32.51\text{–}32.87} 2 32.51 – 32.87 CPU-ref.
Companion Result: 20-Step Unpadded Compression Preimages via the Zero-a 3 a_3 a 3 Bridge
When FIPS 180-4 padding is not required (the 20-step compression-function model studied in [6 , 7 , 9 ] ), we can eliminate the ( 3 / 4 ) 32 ≈ 2 − 13.28 (3/4)^{32} \approx2^{-13.28} ( 3/4 ) 32 ≈ 2 − 13.28 (13.28-bit) majority survival loss of [E13] altogether by placing the state on the Zero-a 3 a_3 a 3 Manifold (solve20_zero_a3.c), where the middle state words are pinned to:
a 3 = 0 , a 5 = 0 , a 6 = 0 , a 8 = 0 , a 9 = 0 , a 10 = 0xffffffff ⇒ e 9 = 0 , e 10 = 0xffffffff . (40) a_3 = 0,\quad a_5 = 0,\quad a_6 = 0,\quad a_8 = 0,\quad a_9 = 0,\quad a_{10} = \texttt{0xffffffff} \mathrel{\Rightarrow} e_9 = 0,\quad e_{10} = \texttt{0xffffffff}. \tag*{(40)} a 3 = 0 , a 5 = 0 , a 6 = 0 , a 8 = 0 , a 9 = 0 , a 10 = 0xffffffff ⇒ e 9 = 0 , e 10 = 0xffffffff . (40)
Because Maj ( 0 , x , 0 ) = 0 \operatorname{Maj}(0,x,0)=0 Maj ( 0 , x , 0 ) = 0 , both majority functions containing a 4 a_4 a 4 vanish identically for 100% of a 4 ∈ [ 0 , 2 32 ) a_4 \in[0,2^{32}) a 4 ∈ [ 0 , 2 32 ) :
Maj ( a 5 , a 4 , a 3 ) = Maj ( 0 , a 4 , 0 ) = 0 , Maj ( a 6 , a 5 , a 4 ) = Maj ( 0 , 0 , a 4 ) = 0. (41) \operatorname{Maj}(a_5,a_4,a_3)=\operatorname{Maj}(0,a_4,0)=0,\qquad\operatorname{Maj}(a_6,a_5,a_4)=\operatorname{Maj}(0,0,a_4)=0. \tag*{(41)} Maj ( a 5 , a 4 , a 3 ) = Maj ( 0 , a 4 , 0 ) = 0 , Maj ( a 6 , a 5 , a 4 ) = Maj ( 0 , 0 , a 4 ) = 0. (41)
Fixing a 3 = 0 a_3=0 a 3 = 0 removes one degree of freedom on the Left, which we restore on the Right by leaving a 7 a_7 a 7 free. Under [E38], e 6 = a 2 e_6=a_2 e 6 = a 2 and Ch ( e 9 , e 8 , e 7 ) = Ch ( 0 , e 8 , e 7 ) = e 7 = a 7 \operatorname{Ch}(e_9,e_8,e_7)=\operatorname{Ch}(0,e_8,e_7)=e_7=a_7 Ch ( e 9 , e 8 , e 7 ) = Ch ( 0 , e 8 , e 7 ) = e 7 = a 7 , so W 9 = W 9 , 0 − a 2 − a 7 W_9=W_{9,0}-a_2-a_7 W 9 = W 9 , 0 − a 2 − a 7 (where W 9 , 0 : = W 9 ∣ a 2 = a 7 = 0 W_{9,0}:=\left.W_9\right|_{a_2=a_7=0} W 9 , 0 := W 9 ∣ a 2 = a 7 = 0 ). Simultaneously, on the Left a 2 = W 1 + G 1 ( a 1 ) a_2=W_1+G_1(a_1) a 2 = W 1 + G 1 ( a 1 ) (with G 1 ( a 1 ) : = − W 1 ∣ a 2 = 0 G_1(a_1):=-\left.W_1\right|_{a_2=0} G 1 ( a 1 ) := − W 1 ∣ a 2 = 0 ), and on the Right W 14 = D 14 ( a 11 , a 12 ) − a 7 W_{14}=D_{14}(a_{11},a_{12})-a_7 W 14 = D 14 ( a 11 , a 12 ) − a 7 (where D 14 ( a 11 , a 12 ) : = W 14 ∣ a 7 = 0 D_{14}(a_{11},a_{12}):=\left.W_{14}\right|_{a_7=0} D 14 ( a 11 , a 12 ) := W 14 ∣ a 7 = 0 ). Substituting − a 2 = − W 1 − G 1 ( a 1 ) -a_2=-W_1-G_1(a_1) − a 2 = − W 1 − G 1 ( a 1 ) and − a 7 = W 14 − D 14 ( a 11 , a 12 ) -a_7=W_{14}-D_{14}(a_{11},a_{12}) − a 7 = W 14 − D 14 ( a 11 , a 12 ) into the step-16 schedule equation W 16 = σ 1 ( W 14 ) + W 9 + σ 0 ( W 1 ) + W 0 ( a 1 ) W_{16}=\sigma_1(W_{14})+W_9+\sigma_0(W_1)+W_0(a_1) W 16 = σ 1 ( W 14 ) + W 9 + σ 0 ( W 1 ) + W 0 ( a 1 ) groups the W 1 W_1 W 1 terms into σ 0 ( W 1 ) − W 1 = Q 0 ( W 1 ) \sigma_0(W_1)-W_1=Q_0(W_1) σ 0 ( W 1 ) − W 1 = Q 0 ( W 1 ) and the W 14 W_{14} W 14 terms into σ 1 ( W 14 ) + W 14 = Q 1 ( W 14 ) \sigma_1(W_{14})+W_{14}=Q_1(W_{14}) σ 1 ( W 14 ) + W 14 = Q 1 ( W 14 ) . Introducing a fixed meeting constant T 16 ∗ = 0x12345678 T^{*}_{16}=\texttt{0x12345678} T 16 ∗ = 0x12345678 decouples step 16 into independent Left (Q 0 Q_0 Q 0 ) and Right (Q 1 Q_1 Q 1 ) table lookups (phase1_left_worker and phase2_right_worker in solve20_zero_a3.c):
Q 0 ( W 1 ) = T 16 ∗ − W 0 ( a 1 ) + G 1 ( a 1 ) , L 17 ( a 1 ) : = σ 0 ( W 2 ) + W 1 , Q 1 ( W 14 ) = W 16 ( a 11 , a 12 ) + D 14 ( a 11 , a 12 ) − W 9 , 0 − T 16 ∗ , a 7 = D 14 ( a 11 , a 12 ) − W 14 . (42) \begin{aligned}
Q_0(W_1)&=T^{*}_{16}-W_0(a_1)+G_1(a_1), & L_{17}(a_1)&:=\sigma_0(W_2)+W_1,\\
Q_1(W_{14})&=W_{16}(a_{11},a_{12})+D_{14}(a_{11},a_{12})-W_{9,0}-T^{*}_{16}, & a_7&=D_{14}(a_{11},a_{12})-W_{14}. \tag*{(42)}
\end{aligned} Q 0 ( W 1 ) Q 1 ( W 14 ) = T 16 ∗ − W 0 ( a 1 ) + G 1 ( a 1 ) , = W 16 ( a 11 , a 12 ) + D 14 ( a 11 , a 12 ) − W 9 , 0 − T 16 ∗ , L 17 ( a 1 ) a 7 := σ 0 ( W 2 ) + W 1 , = D 14 ( a 11 , a 12 ) − W 14 . (42)
Precomputing 16 GiB tables for Q 0 − 1 Q_0^{-1} Q 0 − 1 , Q 1 − 1 Q_1^{-1} Q 1 − 1 , and the Left bridge L 17 ( a 1 ) ↦ a 1 L_{17}(a_1)\mapsto a_1 L 17 ( a 1 ) ↦ a 1 satisfying a 3 = 0 a_3=0 a 3 = 0 (48.0 GiB total, 45 s one-time build, 100% independent of H ∗ H^{*} H ∗ ), solve20_zero_a3.c achieves zero β \beta β -filter loss (63.37% survival per bridge hit) and 2.16 million exact 19-step compression solutions per second (0.46 us/sol19) on one 10-core Apple M4 CPU node (16 threads). At 2.16 × 10 6 2.16 \times10^6 2.16 × 1 0 6 sol19/s, the expected online search time for 2 32 2^{32} 2 32 19-step solutions is 1,988.4 s ≈ \approx ≈ 33.14 minutes (≈ 2 38.13 ≈ 2 38.1 \approx2^{38.13}\approx2^{38.1} ≈ 2 38.13 ≈ 2 38.1 scalar CPU SHA20-eq at 151.25 M evals/s, specifically 2 38.01 2^{38.01} 2 38.01 ). For the target deadbeef …, the solver found a 20-step unpadded preimage after 2 32.01 2^{32.01} 2 32.01 outer ( a 11 , a 12 ) (a_{11},a_{12}) ( a 11 , a 12 ) trials (2.735 × 10 9 ≈ 2 31.35 2.735 \times10^9 \approx2^{31.35} 2.735 × 1 0 9 ≈ 2 31.35 19-step solutions):
Expected 20-Step Unpadded Online Time = 1,988.4 s ( 33.14 min ) ; Observed Run = 1,266.26 s ( 21.10 min , 10 -core Apple M4 CPU ) . (43) \text{Expected 20-Step Unpadded Online Time}=1{,}988.4\ \text{s}\ (33.14\ \text{min});\quad\text{Observed Run}=1{,}266.26\ \text{s}\ (21.10\ \text{min},\ 10\text{-core Apple M4 CPU}). \tag*{(43)} Expected 20-Step Unpadded Online Time = 1 , 988.4 s ( 33.14 min ) ; Observed Run = 1 , 266.26 s ( 21.10 min , 10 -core Apple M4 CPU ) . (43)
Verified 19-Step and 20-Step Padded SHA-256 Preimage Witnesses
All 46 distinct 20-step and 19-step witnesses below (verified via 48 checks in verify_all_witnesses.py, where "abc" appears in both the flagship demonstration §8.2 and the 14-label benchmark suite § 8.4 : comprising 16 distinct 20-step padded witnesses, 16 distinct 19-step padded witnesses, 13 distinct 20-step unpadded compression witnesses, and 1 Stage-2 completeness regression witness) are archived together with all C/CUDA solvers (src/pre19.c, solve20_padded_fast.c, solve20_padded_cuda.cu, solve20_padded_cuda_prod.cu, solve20_zero_a3.c, test_all_12_theories.c) at https://github.com/srw/sha256-19-and-20-step-preimages-with-padding and are independently verified in under 1 second by running python3 verify_all_witnesses.py. Complete machine-readable witness files are provided in demos_20step.txt, examples_abc_hello_20step.txt, witnesses_20step.txt, and FOUND_20ROUND_PREIMAGE.txt (in display blocks below and in § 1.1 , 110-hex-character 55-byte messages are wrapped across two 55-character lines for readability, while Tables 8.2 and 8.3 print single-line 110-character hex strings).
Witness 1: First Demonstrated 20-Step Padded SHA-256 Preimage (H 20 ∗ = 0000 … 0000 H^*_{20} = 0000\ldots0000 H 20 ∗ = 0000 … 0000 )
Found by solve20_padded_cuda.cu on Sweep 62 (ctx=5, after 70,661,112 exact 19-step bridge candidates; recorded in FOUND_20ROUND_PREIMAGE.txt):
55-Byte Message M M M (440 bits, big-endian hex, split into two 55-hex-char lines):
ec531306c85ad4a4ad211d2e1a03ece4d0ad4a0e6b4c2b9436b3bab
dcbd520597196f52c042b8cd95f1a39f71b58b47b0647c78e65416f
W[ 0.. 3] = ec531306 c85ad4a4 ad211d2e 1a03ece4
W[ 4.. 7] = d0ad4a0e 6b4c2b94 36b3babd cbd52059
W[ 8..11] = 7196f52c 042b8cd9 5f1a39f7 1b58b47b
W[12..15] = 0647c78e 65416f80 00000000 000001b8
(Note the mandatory FIPS 180-4 padding [1 ] : W 13 W_{13} W 13 mod 256 = 0x80, W 14 W_{14} W 14 = 0x00000000, and W 15 W_{15} W 15 = 0x000001b8 = 440 bits. )
Table 8.1. Complete 20-step internal state trajectory ( a t , e t , W t − 1 ) (a_t,e_t,W_{t-1}) ( a t , e t , W t − 1 ) of the 20-step padded witness for H 20 ∗ H^*_{20} H 20 ∗ = 0000…0000.
Table 1.
Witness 2: Flagship 20-Step & 19-Step Single-Block Padded Preimages for H ∗ = 0000 … 0000 H^* = 0000\ldots0000 H ∗ = 0000 … 0000 , SHA-256(abc''), and SHA-256(hello'')
Recorded in demos_20step.txt, examples_abc_hello_20step.txt, and verify_all_witnesses.py (55-byte hex strings split into two 55-hex-char lines):
Target Digest H 19 ∗ = 0000 … 0000 H^*_{19} = 0000\ldots0000 H 19 ∗ = 0000 … 0000 (All-Zero 256-Bit Digest, 19-Step Padded with Exact a 5 = a 6 a_5 = a_6 a 5 = a 6 ):
0000000000000000000000000000000000000000000000000000000000000000
19-Step Padded 55-Byte Preimage (H 19 ( M ) = 0000 … 0000 H_{19}(M) = 0000\ldots0000 H 19 ( M ) = 0000 … 0000 ):
fc0c9d8eafb2fa329af316940c42a5eb9773cec39e4f7e396182628 7ae767638f92d4ce5fc5eb8cabd7606409364dda27a6c1bb5220246
W[ 0.. 7] = fc0c9d8e afb2fa32 9af31694 0c42a5eb 9773cec3 9e4f7e39 61826287 ae767638
W[ 8..15] = f92d4ce5 fc5eb8ca bd760640 9364dda2 7a6c1bb5 22024680 00000000 000001b8
(Invariants verified: a 5 = a 6 = 3 d b b 85 b 8 a_5 = a_6 = \mathrm{3dbb85b8} a 5 = a 6 = 3dbb85b8 [D = 0 D = 0 D = 0 ], e 9 = e 10 = 0 x f f f f f f f f e_9 = e_{10} = \mathrm{0xffffffff} e 9 = e 10 = 0xffffffff , W 13 m o d 256 = 0 x 80 W_{13} \bmod256 = \mathrm{0x80} W 13 mod 256 = 0x80 , W 14 = 0 W_{14} = 0 W 14 = 0 , W 15 = 440 W_{15} = 440 W 15 = 440 .)
20-Step Padded 55-Byte Preimage (H 20 ( M ) = SHA-256(“abc”) H_{20}(M) = \text{SHA-256(``abc'')} H 20 ( M ) = SHA-256(“abc”) ):
edf6e70a7001ae71b900f18119aaa1fdf6c1179b4268891262a9539 be04d41236685e0c102e0ad23165e8b7157669819302ddcb3c68226
W[ 0.. 7] = edf6e70a 7001ae71 b900f181 19aaa1fd f6c1179b 42688912 62a9539b e04d4123
W[ 8..15] = 6685e0c1 02e0ad23 165e8b71 57669819 302ddcb3 c6822680 00000000 000001b8
(Invariants verified: a 5 = a 6 = 4 a d e 1 a f a a_5 = a_6 = \mathrm{4ade1afa} a 5 = a 6 = 4ade1afa , a 10 = a 11 = a c f 3 c 908 a_{10} = a_{11} = \mathrm{ac f3c908} a 10 = a 11 = acf3c908 , e 9 = e 10 = e 15 = 0 x f f f f f f f f e_9 = e_{10} = e_{15} = \mathrm{0xffffffff} e 9 = e 10 = e 15 = 0xffffffff .)
19-Step Padded 55-Byte Preimage (H 19 ( M ) = SHA-256(“abc”) H_{19}(M) = \text{SHA-256(``abc'')} H 19 ( M ) = SHA-256(“abc”) ):
8ca254f8d04dd3fb04efaad6b1867588ffe833de49a144fedbf1839 422892dc9f5a9158d8fc063290a14a9a6c55dfa245642a0247ec45a
Witness 3: Flagship 20-Step & 19-Step Two-Block (119-Byte, Plain-ASCII First Block) Padded Preimages (H ∗ H^* H ∗ = SHA-256(“”))
Demonstrating full Merkle–Damgård multi-block chaining with an arbitrary human-readable 64-byte plain-ASCII first block ("This first block is plain text; the second one was computed.....") followed by a 55-byte computed second block with FIPS 180-4 padding [1 ] (W 13 ( 2 ) m o d 256 = 0 x 80 W^{(2)}_{13} \bmod256 = 0x80 W 13 ( 2 ) mod 256 = 0 x 80 , W 14 ( 2 ) = 0 W^{(2)}_{14} = 0 W 14 ( 2 ) = 0 , W 15 ( 2 ) = 0 x 000003 b 8 = 952 W^{(2)}_{15} = 0x000003b8 = 952 W 15 ( 2 ) = 0 x 000003 b 8 = 952 bits, recorded in demos_20step.txt):
Block 1 (64 Bytes Plain ASCII, identical for both 20-step and 19-step demos): "This first block is plain text; the second one was computed....."
W^(1)[ 0.. 7] = 54686973 20666972 73742062 6c6f636b 20697320 706c6169 6e207465 78743b20 W^(1)[ 8..15] = 74686520 7365636f 6e64206f 6e652077 61732063 6f6d7075 7465642e 2e2e2e2e
20-Step Block 2 (55 Computed Bytes + 9-Byte FIPS 180-4 Padding, L = 952 L = 952 L = 952 bits = 0x3b8, chaining from $H^{(1)}_{20} = 9743298d4cdedcbb11eab6931270fe130dd0420fff6255433a223586f586f980):
W_20^(2)[ 0.. 7] = df28e21b b6b61202 ba87baa7 2096ee0a 3ac325cf 1f12056e 7cfe2ae1 735b4d10 W_20^(2)[ 8..15] = 6b8f6e0b 22eb9b50 4ed93689 91944b0a 115a934f 17c2c480 00000000 000003b8
19-Step Block 2 (55 Computed Bytes + 9-Byte FIPS 180-4 Padding, L = 952 L = 952 L = 952 bits = 0x3b8):
W_19^(2)[ 0.. 7] = fe409cc9 30128a72 0481f86c 0503d7a0 18519a12 9df44913 9720bb5e ef520895 W_19^(2)[ 8..15] = f8b51568 5bb40481 7be30188 0f0caabe 02fc9e5f 1c95c080 00000000 000003b8
Witness 4: Complete 20-Step and 19-Step Padded Benchmark Suites (14 Targets Each) & Unpadded Suite (13 Targets)
Matching every public-label target in the benchmark suite (H ∗ H^* H ∗ = SHA-256(label)), Table 8.2 lists the complete, untruncated 55-byte (110-hex-character) 20-step FIPS 180-4 padded preimages [padded], where appending 8000000000000001b8 forms the 512-bit block W 0 … W 15 W_0 \ldots W_{15} W 0 … W 15 , and Table 8.3 lists the corresponding complete 55-byte 19-step FIPS 180-4 padded preimages .
Table 8.2: Complete 20-step single-block FIPS 180-4 padded benchmark suite (all 14 public-label targets, full 55-byte message_hex, L = 440 L = 440 L = 440 bits).
Demonstrated 20-Step Unpadded Compression Preimage (deadbeef..., Zero-a 3 a_3 a 3 Bridge solve20_zero_a3.c, plus all 12 [comp] targets "unpadded test 1"… "unpadded test 11" and "hand-off cross-check 2026-09-29" in witnesses_20step.txt):
W[ 0.. 7] = 4334d956 6eccece1 6727a1b2 d85811af 890c5399 79018a3b d346b94d 5f26009b
W[ 8..15] = 7562d311 0bfd80d5 1f8c38f4 16d8315d e0353aa2 6adf4bd2 a2bf14a2 801ae8f7
Experimental Ablation, Scope, and Structural Complexity Bounds
Algorithmic Ablation Across CPU and GPU
Table 9.1 summarizes the algorithmic ablation of our solver on genuine, unmutated right-hand contexts from soft-shaped CSR tables to the full Carry-Sudoku / Slot-Sudoku architecture (see Table 1.1 in §1.1 for the comparison against prior reduced-step SHA-256 preimage attacks). For CPU configurations, we report CPU-ref per sol19 against our measured same-host 10-core scalar CPU reference baseline (1.5125 × 10 8 1.5125 \times10^{8} 1.5125 × 1 0 8 SHA20-eq/s on arbitrary 20-step message blocks). Supplementary GPU telemetry on 1× NVIDIA L4 (solve20_padded_cuda.cu, solve20_padded_cuda_prod.cu) is reported in direct GPU wall-clock time on genuine contexts.
Table 1.1. Comparison of theoretical and practical (demonstrated) preimage attacks on step-reduced SHA-256.
Table 9.1. Algorithmic ablation of 19-step bridge candidate (sol19) and 20-step padded preimage throughput on genuine unmutated contexts.
(Note: The experimental –bench-c2 through –bench-c10 harnesses in solve20_padded_cuda.cu [Cycles 2, 4, and 7–10, including run_bench_cycle2 which recorded 180,831.9 sol19/s / 6.60 GPU-h by forcing 16 contexts to share a single T 16 T_{16} T 16 ] are synthetic architectural microbenchmarks; we exclude those figures from Table 9.1 and report only genuine-context rates.)
Scope, Terminology, and Limitations: Subspace-Restricted Preimages, Degree-of-Freedom Budget, Exact-T 16 T_{16} T 16 Twin Capacity, and Construction-Specific Bottleneck Analysis
To situate our results accurately within the SHA-256 cryptanalysis literature, we distinguish three notions of restriction in reduced-step preimage attacks:
Unpadded Compression Function vs. Structured-Target Padded vs. Arbitrary-Target Full FIPS 180-4 Padded Hash Function: Prior practical 18-, 19-, and 20-step results [6 , 7 ] and the unpadded solvers in [9 ] restrict their claims to the unpadded compression function (W 0 , … , W 15 ∈ { 0 , 1 } 512 W_0,\ldots,W_{15} \in\{0,1\}^{512} W 0 , … , W 15 ∈ { 0 , 1 } 512 unconstrained); Zaïkin [7 ] specifies that Merkle–Damgård padding is omitted while keeping the standard IV and feed-forward. Başra [9 ] additionally demonstrated a 55-byte 20-step padded preimage for a structured target (padded r20/README.md in [9 ] , dated 17 October 2026). Our 19- and 20-step solvers (src/pre19.c, solve20_padded_fast.c, solve20_padded_cuda.cu, solve20_padded_cuda_prod.cu) satisfy all 72 bits of single-block FIPS 180-4 padding [1 ] (W 13 m o d 256 = 0x80 W_{13} \bmod256 = \texttt{0x80} W 13 mod 256 = 0x80 , W 14 = 0 W_{14} = 0 W 14 = 0 , W 15 = 440 W_{15} = 440 W 15 = 440 ) for arbitrary externally prescribed 256-bit targets , producing valid 55-byte (and 119-byte two-block) messages across all 16 padded 20-step and 16 padded 19-step targets in §8.
Subspace-Restricted Preimages, Exact-T 16 T_{16} T 16 Twin Capacity, and the Degree-of-Freedom Budget: Like all splice-and-cut MitM and biclique attacks on padded SHA-256 [2 , 3 , 4 , 8 , 10 ] , which fix message lengths in ( W 14 , W 15 ) (W_{14}, W_{15}) ( W 14 , W 15 ) and pin internal state registers (“neutral words” / “initial structures”) to decouple forward and backward chunks, our solver restricts its search to a structured 55-byte single-block internal-state manifold defined by [E8], [E11], [E13], and [E22]. Because a 55-byte message contains 440 free
message bits against a 256-bit target digest H ∗ H^* H ∗ , the unconstrained 55-byte padded message space holds 2 440 − 256 = 2 184 2^{440-256}=2^{184} 2 440 − 256 = 2 184 expected preimages per 256-bit target for both the 19-step and 20-step hash functions. When searching for a 20-step preimage, the solver enumerates 19-step bridge candidates (sol19) that satisfy Steps 1–19 of the 20-step target (leaving the 32-bit terminal equation σ 0 ( W 4 ) + W 3 = T 19 \sigma_0(W_4)+W_3=T_{19} σ 0 ( W 4 ) + W 3 = T 19 open), so under a heuristic 2 − 32 2^{-32} 2 − 32 terminal survival model the expected number of sol19 bridge candidates for a given 20-step target is 2 32 2^{32} 2 32 times the expected number of 20-step preimages inside the same restricted family. Table 9.3 tracks these model expectations across the 20-step manifold constraints.
Table 9.3. Distributional degree-of-freedom budget across the 20-step 55-byte single-block padded manifold.
Carry-Sudoku Context Universe (U ≈ 1.68 × 10 7 U\approx1.68\times10^7 U ≈ 1.68 × 1 0 7 ) vs. Exact-T 16 T_{16} T 16 Twin Capacity (single4 Mode): Across all 2 32 2^{32} 2 32 values of a 12 a_{12} a 12 for a given 20-step target H 20 ∗ H^*_{20} H 20 ∗ , the complete 7-stage Carry-Sudoku cascade ([E22]–[E25], Algorithm 1) produces an estimated universe of U ≈ 1.68 × 10 7 ≈ 2 24.00 U\approx1.68\times10^7\approx2^{24.00} U ≈ 1.68 × 1 0 7 ≈ 2 24.00 valid right-hand contexts (or U f i l t ≈ 1.014 × 10 7 ≈ 2 23.27 U_{\mathrm{filt}}\approx1.014\times10^7\approx2^{23.27} U filt ≈ 1.014 × 1 0 7 ≈ 2 23.27 when the retired heuristic Σ 0 ( a 9 ) \Sigma_0(a_9) Σ 0 ( a 9 ) window check [E26] was enabled). In our 2-way table configuration ([E32]), each context yields an empirical average of ≈ 1.06 × 10 5 ≈ 2 16.69 \approx1.06\times10^5\approx2^{16.69} ≈ 1.06 × 1 0 5 ≈ 2 16.69 19-step bridge candidates (sol19) across a 1 ∈ [ 0 , 2 32 ) a_1\in[0,2^{32}) a 1 ∈ [ 0 , 2 32 ) , so the estimated universe U U U yields ≈ 2 24.00 × 2 16.69 = 2 40.69 \approx2^{24.00}\times2^{16.69}=2^{40.69} ≈ 2 24.00 × 2 16.69 = 2 40.69 reachable sol19 bridge candidates (≈ 413 = 2 8.69 \approx413=2^{8.69} ≈ 413 = 2 8.69 expected 20-step padded preimages per target under the 2 − 32 2^{-32} 2 − 32 terminal model out of the 2 10.60 ≈ 1,552 2^{10.60}\approx1{,}552 2 10.60 ≈ 1 , 552 unfiltered manifold expectation, or ≈ 250 = 2 7.97 \approx250=2^{7.97} ≈ 250 = 2 7.97 when restricted to U f i l t U_{\mathrm{filt}} U filt ). Under a uniform birthday model over U ≈ 1.68 × 10 7 U\approx1.68\times10^7 U ≈ 1.68 × 1 0 7 contexts, the expected number of natural Exact-T 16 T_{16} T 16 twin pairs (T 16 ( i ) = T 16 ( j ) T_{16}^{(i)}=T_{16}^{(j)} T 16 ( i ) = T 16 ( j ) ) is N t w i n s ≈ U 2 / 2 33 ≈ 32,890 N_{\mathrm{twins}}\approx U^2/2^{33}\approx32{,}890 N twins ≈ U 2 / 2 33 ≈ 32 , 890 pairs (65,780 contexts), yielding ≈ 65,780 × 1.06 × 10 5 ≈ 1.62 × 2 32 \approx65{,}780\times1.06\times10^5\approx1.62\times2^{32} ≈ 65 , 780 × 1.06 × 1 0 5 ≈ 1.62 × 2 32 sol19 candidates (1 − e − 1.62 ≈ 80.3 % 1-e^{-1.62}\approx80.3\% 1 − e − 1.62 ≈ 80.3% Poisson success probability from natural twins alone; if restricted to U f i l t U_{\mathrm{filt}} U filt , N t w i n s ≈ 11,970 N_{\mathrm{twins}}\approx11{,}970 N twins ≈ 11 , 970 pairs yielding ≈ 0.59 × 2 32 \approx0.59\times2^{32} ≈ 0.59 × 2 32 sol19 candidates or 44.6% Poisson success). Across our 16 padded 20-step targets, twin2 (sweep_exact16_cuda_kernel) solved 12 targets directly; when natural twin pairs in a sampled pool are exhausted, the non-twin 4-way reservoir kernels (single4 via sweep_20_warp_13_prod_kernel in solve20_padded_cuda_prod.cu and sweep_exact16_cuda_kernel in solve20_padded_cuda.cu) sample directly from the full context reservoir, solving the remaining 4 targets (16/16 total).
Binary 55-Byte Output Format vs. Two-Block Chosen-ASCII Prefix (119 Bytes): In a single 55-byte block, W 0 , … , W 10 W_0,\ldots,W_{10} W 0 , … , W 10 and the upper 24 bits of W 13 W_{13} W 13 are determined algebraically by the state trajectory. As demonstrated in §8.3, a 119-byte two-block message (W 15 ( 2 ) = 952 = 0 x 3 b 8 W_{15}^{(2)}=952=0x3b8 W 15 ( 2 ) = 952 = 0 x 3 b 8 ) allows the first 64-byte block B 1 B_1 B 1 to be arbitrary ASCII text while Block 2 is solved from chaining state I V ′ = Compress 20 ( I V , B 1 ) \mathrm{IV}'=\operatorname{Compress}_{20}(\mathrm{IV},B_1) IV ′ = Compress 20 ( IV , B 1 ) at identical complexity.
Construction-Specific Bottleneck Analysis and 15 Explored Sub-2 32 2^{32} 2 32 Directions
Within our decoupled Left/Right bridge architecture ([E8]–[E14]), each step beyond Step 19 adds one schedule relation W t = σ 1 ( W t − 2 ) + W t − 7 + σ 0 ( W t − 15 ) + W t − 16 W_t=\sigma_1(W_{t-2})+W_{t-7}+\sigma_0(W_{t-15})+W_{t-16} W t = σ 1 ( W t − 2 ) + W t − 7 + σ 0 ( W t − 15 ) + W t − 16 . By [E37], σ 0 \sigma_0 σ 0 is an F 2 \mathbb{F}_2 F 2 -linear bijection on ( F 2 ) 32 (\mathbb{F}_2)^{32} ( F 2 ) 32 (rank F 2 ( σ 0 ) = 32 \operatorname{rank}_{\mathbb{F}_2}(\sigma_0)=32 rank F 2 ( σ 0 ) = 32 ), so for any fixed Right context and Level-3 bridge leaf ( W 1 , W 2 , W 3 ) (W_1,W_2,W_3) ( W 1 , W 2 , W 3 ) , the terminal relation σ 0 ( W 4 ) = T 19 − W 3 ( m o d 2 32 ) \sigma_0(W_4)=T_{19}-W_3\pmod{2^{32}} σ 0 ( W 4 ) = T 19 − W 3 ( mod 2 32 ) uniquely determines W 4 = σ 0 − 1 ( T 19 − W 3 ( m o d 2 32 ) ) W_4=\sigma_0^{-1}(T_{19}-W_3\pmod{2^{32}}) W 4 = σ 0 − 1 ( T 19 − W 3 ( mod 2 32 )) , acting as an exact 32-bit point filter against the value of W 4 W_4 W 4 determined by ( a 1 , a 2 , a 3 , a 4 ) (a_1,a_2,a_3,a_4) ( a 1 , a 2 , a 3 , a 4 ) (though det F 2 ( σ 0 ) = 1 \det_{\mathbb{F}_2}(\sigma_0)=1 det F 2 ( σ 0 ) = 1 alone does not prove statistical uniformity of T 19 T_{19} T 19 across the bridge stream). To investigate whether an algebraic, differential, polynomial, cross-round, or multi-block modification could bypass this 32-bit terminal filter within our framework, we formulated and evaluated 15 candidate sub-2 32 2^{32} 2 32 attack directions (test_all_12_theories.c, Table 9.4 ). We emphasize that Table 9.4 is a taxonomy of construction-specific negative results and surrogate empirical checks rather than a universal impossibility proof over all conceivable algorithms.
• Analysis of Direction 15 (Two-Block Feed-Forward Locking): In a two-block 119-byte padded message M = B 1 ∥ B 2 M=B_{1}\parallel B_{2} M = B 1 ∥ B 2 , Block 1 (B 1 ∈ { 0 , 1 } 512 B_{1}\in\{0,1\}^{512} B 1 ∈ { 0 , 1 } 512 ) maps I V ↦ V = Compress 20 ( I V , B 1 ) \mathrm{IV}\mapsto V=\operatorname{Compress}_{20}(\mathrm{IV},B_{1}) IV ↦ V = Compress 20 ( IV , B 1 ) , and Block 2 maps V ↦ S 20 ( 2 ) V\mapsto S_{20}^{(2)} V ↦ S 20 ( 2 ) with Davies–Meyer feed-forward H 20 ∗ = V + S 20 ( 2 ) H_{20}^{*}=V+S_{20}^{(2)} H 20 ∗ = V + S 20 ( 2 ) (mod 2 32 2^{32} 2 32 ) ⟺ \Longleftrightarrow ⟺ S 20 ( 2 ) = H 20 ∗ − V S_{20}^{(2)}=H_{20}^{*}-V S 20 ( 2 ) = H 20 ∗ − V (mod 2 32 2^{32} 2 32 ). Because V V V enters Block 2 at both boundaries simultaneously (Step 0 as V V V and Step 20 as H 20 ∗ − V H_{20}^{*}-V H 20 ∗ − V ), choosing B 1 B_{1} B 1 first fixes both boundaries and reduces Block 2 to a single-block 20-step padded problem, while choosing Block 2’s terminal state S 20 ( 2 ) S_{20}^{(2)} S 20 ( 2 ) first uniquely locks all 256 bits of V = H 20 ∗ − S 20 ( 2 ) V=H_{20}^{*}-S_{20}^{(2)} V = H 20 ∗ − S 20 ( 2 ) , requiring a full 256-bit 20-step compression preimage on Block 1.
• Resulting Construction-Specific Scaling: While the unconstrained 55-byte padded message space (2 440 2^{440} 2 440 messages) has 2 440 − 256 = 2 184 2^{440-256}=2^{184} 2 440 − 256 = 2 184 expected preimages per 256-bit digest at any step count R R R , within our fixed-wall Left/Right bridge construction ([E8]+[E11]+[E13]), 19-step bridge candidates (sol19) are generated in O ( 1 ) O(1) O ( 1 ) amortized work (24,228 ≈ 2 14.56 \approx2^{14.56} ≈ 2 14.56 CPU-ref evaluations per sol19, or 1.2-86.4 s for a standalone chosen-target 19-step padded preimage in src/pre19.c), whereas 20-step padded preimages require testing the terminal schedule relation σ 0 ( W 4 ) + W 3 ≡ T 19 \sigma_{0}(W_{4})+W_{3}\equiv T_{19} σ 0 ( W 4 ) + W 3 ≡ T 19 (mod 2 32 2^{32} 2 32 ), costing an expected 2 32 2^{32} 2 32 sol19 candidates under a uniform terminal residual model (191.1 node-h / 2 46.56 2^{46.56} 2 46.56 CPU-ref on 1× CPU node, or 8.98-22.16 GPU-h in supplementary 1× L4 GPU slice telemetry). Extending this same fixed-wall architecture beyond 20 steps shifts the terminal state boundary ( a R − 7 , … , a R ) (a_{R-7},\ldots,a_{R}) ( a R − 7 , … , a R ) rightward and introduces additional schedule equations W 19 , … , W R − 1 W_{19},\ldots,W_{R-1} W 19 , … , W R − 1 that each impose an additional 32-bit constraint unless new algebraic degrees of freedom are opened.
Disclosure, Attribution & Code Availability
Code and Witness Availability: All C/CUDA solvers (src/pre19.c, solve20_padded_fast.c, solve20_padded_cuda_prod.c, solve20_padded_cuda.c, solve20_zero_a3.c, test_all_12_theories.c), standalone zero-dependency Python verifiers (verify/verify_standalone.py, paper_19_20_padded_sudoku/verify_all_witnesses.py), and all 46 distinct 19and 20-step preimage witnesses are publicly available under the MIT License at https://github.com/srw/sha256-19-and-20-step-preimages-with-padding .
The selector-saturation and context-shaping principle (e 9 = e 10 = 0 x f f f f f f f f e_9 = e_{10} = 0xffffffff e 9 = e 10 = 0 x f f f f f f f f , a 5 ≈ a 6 a_5 \approx a_6 a 5 ≈ a 6 ), together with the observation that the FIPS 180-4 padding words (W 13 , W 14 , W 15 W_{13}, W_{14}, W_{15} W 13 , W 14 , W 15 ) can be absorbed backward into (a 7 , a 6 , a 5 a_7, a_6, a_5 a 7 , a 6 , a 5 ) at the cost of three context words and a 20-step padded witness for a structured target, is due to K. S. Basra [9 ] (README.md, padded_r19/README.md, padded_r20/README.md, and paper/sha256_r19_preimage.pdf in https://github.com/kamb-code/sha256-r19-preimage ), whose manuscripts note substantial assistance from AI tools.
AI Methodology & Multi-Agent Review Disclosure: Approximately one month of prior exploration using Anthropic Claude Fable 5.1 Max did not yield a working chosen-target padded solution. Upon switching to Google DeepMind Gemini 4 Argon , the model discovered the algebraic reductions in this work (closed-form O ( 1 ) O(1) O ( 1 ) W 13 W_{13} W 13 padding pivot inversion, Theorem 1 / Carry-Sudoku, Theorem 2 / closed-form F 2 \mathrm{F}_2 F 2 upper-half reconstruction, Slot-Sudoku tables, and the Zero-a 3 a_3 a 3 bi-directional bridge), engineered the C/CUDA solvers, generated all 46 preimage witnesses, and drafted the manuscript. The manuscript, mathematical proofs, and verification suite then underwent three rounds of independent adversarial audit and peer review using OpenAI GPT 6.1 Sol Ultra and Anthropic Claude Fable 5.1 Max , which independently re-verified all arithmetic claims and witnesses and significantly improved the exposition.