shalab — reduced-round SHA-256 experiments (started 2026-10-31)

Step 1 — SAT preimage (sha_sat.py, sweep.txt)

r=17, k unknown message bits: CaDiCaL ~2^0.8k but huge constant; k=16 takes 12 s while brute force 2^16 is microseconds → generic SAT is WORSE than brute force here.

Step 2 — structure miner (cube/)

cube.c : cube tester (XOR-sum of r-round state over 2^d cube assignments, other bits random)

           + hill-climb search. Wall: r=20 strong (z=32), r=21 noise (z≈3.3; noise max ≈3.5-3.9).

ccube.c : CONDITIONAL cube: attacker also picks base message M0 (conditions) and nk key bits.

           r=21: z=56 (T=4096) found, d=6, nk=16; output bit 224 = LSB of h = e18.
           r=22..24: noise. (csearch1.keep has cubes/M0)

Context: literature practical distinguishers on SHA-256 reach ~46 steps (boomerang), collisions 31 steps practical, semi-free-start 39 steps → we are at "calibration" level, not new results yet.

Step 5 — FULL backward peeling (peel/, 2026-10-31, Telegram thread "Mathematik")

Identity e_t = a_t - T2(a_{t-1..t-3}) + a_{t-4} => the r-round state (a..h) is EQUIVALENT to the 8 consecutive values a_{r-7..r}; all of them are computable key-free from the ciphertext:

  a_{r-4-i} = e_{r-i} - a_{r-i} + Sigma0(a_{r-i-1}) + Maj(a_{r-i-1},a_{r-i-2},a_{r-i-3}),  i=0..3

=> an a_t-property gives an r = t+7 distinguisher (step 3 counted only t+4 for a, t+3 for e). peel/scube.c (honest SHACAL-2 game: key = message, secret random per sample; attacker picks plaintext P0 + cube; objective = raw 256 bits + peeled a_{r-4..r-7}; self-check against the true a_{r-7}):

  r=10, 11: deterministic zero-sum on a_{r-7} bit 0 (verify T=4096: z=63-64 = 4096/4096), d=6 and d=8
  r=12..14: noise (verify z 2.8-3.5)
  => honest cube wall 8 -> 11 rounds, purely by better bookkeeping of what the ciphertext reveals.
     Same trick should lift the step-3 derivative miner (needs a-bit properties; its 11-round best is an e-bit).

Aside (peel/peel.c, pcube.c — NOT the honest game, cube in message bits): cube in W15, rest random:

  raw deterministic to r=20, peeled to r=24; trivial because rounds 0-14 never see the cube.
  pcube.c conditional search (key=W0..W3, attacker picks W4..W15 + cube) at r=25/26: noise (psearch1.txt, verify z<=3.6).

Next steps

Smooth objective (bias at r-1/r-2 as gradient, linear combos of output bits, multi-bit masks)
Backward peeling: last rounds partly invertible → measure bias on reconstructed e/a at r-3
Toy family mini-SHA (word size 8/12/16) to measure exponents and test ideas cheaply

Step 3 — baselines + solver variants (2026-10-31, Telegram thread "P=NP")

bf.c (OpenMP brute force, 8 threads): r=17 k=24 0.04 s, k=32 20 s; FULL 64 rounds k=32 80 s (~53 M hash/s).

  → SAT (k=20 timeout 40 s) is ≥10^5× slower than brute force at r=17.

cube.c/cubet (top level, plain cube sums over W0, 40 trials): fraction of nonzero output bits

  r=1..6 for d=16: 0.000 0.078 0.203 0.326 0.453 0.504 → algebraically "random" after ~6 rounds (forward, unconditioned).

exp2.py: CryptoMiniSat plain vs native XOR, r=17: k=16 7–34 s vs 6–17 s; k=20 both timeout 60 s → XOR-awareness ≈ constant factor only.

  cube-and-conquer (c=4 of k=16, CaDiCaL): total CPU 34–36 s vs 12–17 s monolithic; wall ≈2.5 s per cube on 16 cores
  → splitting parallelises, does not lower the exponent (~2^0.8k).

Why r≤16 is trivial: with W1..W15 known every round is invertible (h_t = T1 − S1 − Ch − K − W), so the

  solver peels back to round 0; from r=17 on W16 = W0 + σ0(W1) + W9 + σ1(W14) re-injects the unknown → no peeling.

Step 3 — honest game: SHACAL-2 (compression fn as block cipher, message = secret key), 2026-10-31

The step-2 "21 rounds" find was a flawed game (h_21 = e_18 by shift register; key bits in message). Discarded.
step3/shacal.c cube miner: wall t=5 (e0) -> 8 rounds.
step3/deriv.c k-th order derivative miner (smooth objective; independence check added after the

  D1=D2 degenerate false positive). Best: 11 rounds (k=3, bias 0.25; k=1 bias 0.07).

LEMMA (step3/lemma.c, 6.4M pairs, 0 violations): P' = P xor 2^i in c and g, with conditions

  a_i=b_i, c_i!=g_i, e_i=1 => for EVERY key e_1..e_5 equal and e_6-e'_6 = (c_i ? -2^i : +2^i).
  Proof: c+g sum unchanged in e_2 (d1+h1), ch selects f at round 0, maj unaffected; Δ appears only in
  a_2 (+/-2^i via h1) and reaches e only via d_5 = a_2 -> deterministic 9-round property (h_9 = e_6).
  Rediscovery of the local-collision principle; not new to the literature.

bigrun.sh: long derivative search t=8..11 running in background.

Step 4 — freedom + a-sequence view (2026-10-31, Telegram thread "P=NP")

mini/freesat.py: whole 512-bit message free, only t output bits fixed (word size n, n=32 real).

  r=17 t=32 0.9 s | r=18 t=24 1.3 s, t=32 timeout | r=19/20 t=12 20–24 s, t≥16 timeout (60 s).
  mini-SHA n=16, r=64: t=12 25 s → SAT still far slower than brute force 2^t.

aseq/: a-sequence parametrisation (all W_t forced by a_1..a_r; only schedule equations remain).

  pre17: full 256-bit target for 17-step compression (standard IV, no padding) via one 2^32 scan, ~7 s, verified.
  Known territory: literature preimage results reach far more steps; this is a teaching-level reproduction.

Step 4 — toy family + EXACT algebraic degree (step4/, 2026-10-31)

mini.c: mini-SHACAL-2, word size w, SHA-2 structure (two sigmas, ch, maj, mod-add, round keys), rotations scaled from 32-bit. Lets us compute EXACT Algebraic Normal Form by full Moebius transform when 8w <= 22 (so w=2, nin=16, is the fully-exact case).

Findings (exact, not sampled): - maxdeg of every output bit = nin-1 at all rounds => fixed-key map is a bijection; the full-space

  XOR-sum is 0 for every bit at every round (zerosum.c confirms). This is the TRIVIAL permutation
  zero-sum, not a weakness.

The informative quantity is the MIN degree over output bits (the lowest-degree bit = the one a

  higher-order differential attack rides). Exact w=2 diffusion ladder:
    r : 1 2 3 4 5 6 7 8 9 10 11 12 13 14
  mindeg: 1 1 1 2 3 5 6 8 10 12 13 14 14 14   (nin=16, saturates at 14 = nin-2)
  Reading: at round r a cube of dimension mindeg(r)+1 is a guaranteed zero-sum distinguisher on the
  weakest bit. Degree grows ROUGHLY LINEARLY early (not doubling) because mod-add carry + sigma mix
  slowly bit-by-bit — matches the ~1 extra active-bit-per-round seen in step-3 trail.c.

Single-word-varied degree saturates in 1 round (carry chain alone is full degree in one word):

  diffusion is limited by CROSS-word mixing, not within-word, which is the real design question.

Step 6 — derivative miner x full peeling (peel/sderiv.c, 2026-10-31, thread "Mathematik")

step3/deriv.c with the observable replaced by the r-round ciphertext + key-free a_{r-4..r-7} (384 bits), r = REAL round count. 30k iters, 2 seeds per (r,k), verify on 16384 fresh keys:

  r=12: a_{r-7} bit 0 (= a_5), bias up to -0.35 (z=89), k=2/3/4; k=1 already bias 0.19 (z=48)
  r=13..15: noise (verify z 2.6-4.2 over 384 bits, |bias|<=0.017, no search gradient)

=> honest SHACAL-2 wall: cube 11, derivative 12 rounds (was 8 / 11). longrun13.sh: 300k iters at r=13 (dsearch13_long.txt).

Honest standing (2026-10-31)

Measured, reproducible, nothing new to the literature: SAT loses to brute force; plain cube wall 8 rounds, derivative wall 11 rounds (honest secret-key game); one exact 9-round local-collision lemma rediscovered; exact degree ladder for the w=2 toy. Full SHA-256 (64 rounds) remains far out of reach; practical research frontier is ~31 (collisions) / ~46 (distinguishers). Next candidates: (a) cross-word diffusion exponent vs w (needs nin>22 -> sampled ANF or algebraic bounds); (b) connect the local-collision lemma to a multi-round trail with measured probability.

Step 5 — cross-word mixing + differential-probability decay (step4/, 2026-10-31)

crossdeg.c (EXACT, 2 input words varied, Moebius): max output degree reaches full 2w at round 3 for EVERY w (2..8). => Algebraic DEGREE saturates in a CONSTANT ~3 rounds, independent of word size. This is WHY the degree-based miners (cube step2, higher-order derivative step3) wall out so early: degree is not the bottleneck for SHA-2-like round functions. The long attacks in the literature are differential (probability), not algebraic.

edp2.c (sampled EDP, honest random-key game): best single-bit-input differential probability per round. w=4 (32-bit output, 2^16 samples, floor ~2^-15):

  r:   1    2    3    4    5     6     7     8     9+

-log2:0 1 2 5 6.9 8.9 10.5 14 >=15(floor) => after the first ~3 rounds, EDP decays ~2 bits/round and crosses the random floor near r=8. Interpretation: a differential distinguisher survives only while accumulated -log2(EDP) < output size. This linear-in-rounds decay is the real wall; beating it is exactly what the 31-round collision / 46-round distinguisher papers do with hand-built multi-round trails + message freedom. (w=6,8 scans launched to confirm the slope scales — edp2_w6.txt/edp2_w8.txt.)

Honest conclusion of the arc

Two independent, exactly-measured facts now explain the whole project: 1. algebraic degree saturates in ~3 rounds (constant in w) -> algebraic/cube/HO-derivative attacks die fast; 2. differential probability decays ~2 bits/round -> differential distinguishers die ~linearly. Both match what my miners found (walls at 8 and 11 rounds) and both are consistent with, and far behind, the published frontier. No new algorithm or new weakness in SHA-256 was found; what we built is a correct, reproducible measurement lab that re-derives the known hardness picture from scratch.

Step 7 — mini-SHA word-size scaling (mini/, 2026-10-31, Telegram thread "P=NP", subagent)

Question: on the toy family (word size n, full r=64, whole 512-bit-equiv message free, only t output bits fixed), how does CaDiCaL solve time scale with t and with n? Driver mini/solve_driver.py times ONLY the solve (process_time, median of 5 seeds, 120s cap). Fine t-sweep (mini/fine_results.txt):

  n=4:  t   8     9    10    11    12    13    14     15
      cpu  0.65  2.48  3.02  6.26  6.68  8.02 16.81  62.8(2 TO)
  n=8:  t   8     9    10    11    12      13
      cpu  1.62  1.83 10.24 26.40 42.6(1TO) 32.9

Least-squares log2(time) vs t (clean points only):

  n=4 (t=8..14): slope 0.66 bits/bit, i.e. SAT ~ 2^(0.66 t)
  n=8 (t=8..11): slope 1.46 bits/bit, i.e. SAT ~ 2^(1.46 t)

Brute-force baseline (mini/bruteref.py, random message until t bits match): evals track 2^t exactly; even in SLOW python, n=8 t=16 = 7.9s while SAT already times out (>45s) at t=12. Interpretation (honest): (1) clean EXPONENTIAL scaling in the number of fixed output bits — no hint of sub-exponential/poly behaviour, as expected if the toy has no exploitable structure. (2) The per-bit exponent WORSENS with word size (0.66 -> 1.46 as n: 4 -> 8): wider modular-add carry chains make SAT relatively worse, not better. (3) SAT never beats brute force at any measured point — brute force has slope exactly 1 but a microscopic constant; SAT's constant is ~1s already at t=8. Net: these toys behave like one-way functions should; nothing here points toward P=NP. Matches Step 3's full-size finding.

GRENZWERK