1"""Statistical regularity tests on r-step SHA-256 (single block, standard IV, with feed-forward), C1.23For N random 512-bit messages (seeded) and r in R = {1,2,3,4,5,6,8,10,12,16,20,24,32,64}:4 (i) bias of each of the 256 output bits, |mean - 0.5|; summary = max and number above the 4-sigma level5 4 * 0.5/sqrt(N);6 (ii) linear correlation c(i,j) = E[(-1)^(x_i xor y_j)] between each of 64 randomly sampled input bits7 (from W_0..W_15) and every output bit; count of pairs with |c| > 4/sqrt(N) (under H0: c ~ N(0, 1/N), so the8 expected count under uniformity is 64*256*P(|Z|>4) ~ 1.04);9 (iii) chi-square uniformity test on each of the 32 output bytes (255 d.f.), min p-value and number of bytes10 rejected at alpha = 0.01 / 32 (Bonferroni).11Controls: r = 64 (full compression) and a random oracle (hashlib SHA-256 over a secret salt and the message).12One 64-step trace per message gives every r at once (state after r steps + IV feed-forward).1314Usage: PYTHONPATH=src .venv/bin/python experiments/reduced_round_sha256/bias_test.py --seed 1 --n 20000 \15 --out results/reduced_round_sha256/bias.json16"""17from __future__ import annotations18import argparse, os, random, sys, time19import numpy as np20from scipy import stats as sps21from common import S, provenance, random_block, state_to_int, random_oracle, peak_rss_mb, MASK2223R_LIST = [1, 2, 3, 4, 5, 6, 8, 10, 12, 16, 20, 24, 32, 64]242526def bits_matrix(ints, nbits=256) -> np.ndarray:27 """N x nbits uint8 matrix, column 0 = most significant bit."""28 arr = np.array([[(v >> (nbits - 1 - i)) & 1 for i in range(nbits)] for v in ints], dtype=np.uint8)29 return arr303132def analyse(Y: np.ndarray, X: np.ndarray, n: int, label: str):33 thr = 4 * 0.5 / n ** 0.534 bias = np.abs(Y.mean(axis=0) - 0.5)35 Xs = 1.0 - 2.0 * X.astype(np.float64)36 Ys = 1.0 - 2.0 * Y.astype(np.float64)37 C = Xs.T @ Ys / n # 64 x 25638 cthr = 4 / n ** 0.539 big = int((np.abs(C) > cthr).sum())40 # chi-square per output byte41 pvals, chis = [], []42 for byte in range(32):43 cols = Y[:, byte * 8:(byte + 1) * 8].astype(np.int64)44 vals = (cols * (1 << np.arange(7, -1, -1))).sum(axis=1)45 counts = np.bincount(vals, minlength=256)46 chi, p = sps.chisquare(counts)47 pvals.append(float(p)); chis.append(float(chi))48 alpha = 0.01 / 3249 res = {50 "max_bit_bias": float(bias.max()), "mean_bit_bias": float(bias.mean()),51 "bias_threshold_4sigma": thr, "n_bits_bias_over_4sigma": int((bias > thr).sum()),52 "bit_bias": bias.round(6).tolist(),53 "max_abs_corr": float(np.abs(C).max()), "corr_threshold_4sigma": cthr,54 "n_pairs_corr_over_4sigma": big, "expected_pairs_under_null": float(64 * 256 * 2 * sps.norm.sf(4)),55 "argmax_corr_pair": [int(x) for x in np.unravel_index(np.abs(C).argmax(), C.shape)],56 "chi2_min_p": float(min(pvals)), "chi2_n_bytes_rejected_bonferroni": int(sum(p < alpha for p in pvals)),57 "chi2_p_by_byte": pvals, "chi2_stat_by_byte": chis,58 }59 print(f"[{label}] max bias {res['max_bit_bias']:.4f} (#>4s {res['n_bits_bias_over_4sigma']}), "60 f"max|corr| {res['max_abs_corr']:.4f} (#>4s {big}), chi2 min p {res['chi2_min_p']:.3g} "61 f"(rejected {res['chi2_n_bytes_rejected_bonferroni']}/32)", file=sys.stderr)62 return res636465def main():66 ap = argparse.ArgumentParser()67 ap.add_argument("--seed", type=int, default=1)68 ap.add_argument("--n", type=int, default=20000)69 ap.add_argument("--n-input-bits", type=int, default=64)70 ap.add_argument("--out", default="results/reduced_round_sha256/bias.json")71 a = ap.parse_args()72 t0 = time.time()73 rng = random.Random(a.seed)74 salt = os.urandom(32)75 in_bits = sorted(rng.sample(range(512), a.n_input_bits))76 blocks = [random_block(rng) for _ in range(a.n)]77 traces = []78 for blk in blocks:79 tr = []80 S.compress(S.H0, blk, 64, feedforward=False, trace=tr)81 traces.append(tr)82 msg_ints = [int.from_bytes(b, "big") for b in blocks]83 X = bits_matrix(msg_ints, 512)[:, in_bits]84 meas = {"input_bits_sampled": in_bits, "by_r": {}}85 for r in R_LIST:86 outs = [state_to_int([(x + y) & MASK for x, y in zip(S.H0, tr[r - 1])]) for tr in traces]87 meas["by_r"][str(r)] = analyse(bits_matrix(outs), X, a.n, f"r={r}")88 ro = [random_oracle(salt, b) for b in blocks]89 meas["random_oracle_control"] = analyse(bits_matrix(ro), X, a.n, "RO")90 stats = {"compress_calls": a.n, "wall_s": round(time.time() - t0, 3), "peak_rss_mb": peak_rss_mb()}91 provenance.record("sha256_bias_test", {"n": a.n, "r_list": R_LIST, "n_input_bits": a.n_input_bits,92 "feedforward": True, "iv": "standard H0"},93 meas, seed=a.seed, extra={"op_stats": stats}, out=a.out, started=t0)94 print("wrote", a.out, stats)959697if __name__ == "__main__":98 main()99