1"""Avalanche / diffusion analysis of the SHA-256 compression function, steps r = 1..64 (no feed-forward).23Research question C1 (diffusion). For a single-bit input difference we measure, after every step t = 1..64,4the fraction of the 256 state bits that flip, averaged over N random messages (seeded). Four configurations:5 W0, W5, W15 : one random bit of message word W_j is flipped (the difference is tracked through the message6 schedule, so for t >= 16 several expanded words differ);7 IV : one random bit of the 256-bit initial state is flipped (message unchanged).8Negative control: a 256-bit random oracle (hashlib SHA-256 over a secret os.urandom salt and the input) evaluated on9the same input pairs — its flip ratio must be ~0.5 with sd ~ 0.5/sqrt(256) = 0.031 from the start.1011Outputs (JSON via wp34.provenance.record): per configuration the [64 x 256] mean-flip matrix, the per-step mean and sd12of the Hamming weight of the state difference, and `full_diffusion_step` = first step with mean flip ratio >= 0.49.13Only one trace per message pair is needed: the state after r steps without feed-forward is trace[r-1].1415Usage: PYTHONPATH=src .venv/bin/python experiments/reduced_round_sha256/diffusion.py --seed 1 --n 2000 \16 --out results/reduced_round_sha256/diffusion.json17"""18from __future__ import annotations19import argparse, os, random, sys, time20import numpy as np21from common import S, provenance, random_block, state_to_int, int_to_bits, random_oracle, peak_rss_mb, bootstrap_ci2223CONFIGS = ["W0", "W5", "W15", "IV"]242526def flip_block_bit(block: bytes, word: int, bit: int) -> bytes:27 words = S.bytes_to_words(block)28 words[word] ^= 1 << bit29 return S.words_to_bytes(words)303132def run(seed: int, n: int, threshold: float):33 rng = random.Random(seed)34 salt = os.urandom(32) # secret salt for the random-oracle control (never saved)35 out = {}36 stats = {"compress_calls": 0}37 for cfg in CONFIGS:38 flips = np.zeros((64, 256), dtype=np.int64)39 hw = np.zeros((n, 64), dtype=np.int64)40 ro_flips = np.zeros(n, dtype=np.int64)41 in_pos = []42 for i in range(n):43 block = random_block(rng)44 state = list(S.H0)45 if cfg == "IV":46 w, b = rng.randrange(8), rng.randrange(32)47 state2 = list(state)48 state2[w] ^= 1 << b49 block2 = block50 in_pos.append(("IV", w, b))51 x1, x2 = S.words_to_bytes(state) + block, S.words_to_bytes(state2) + block52 else:53 j = int(cfg[1:])54 b = rng.randrange(32)55 state2 = state56 block2 = flip_block_bit(block, j, b)57 in_pos.append(("W", j, b))58 x1, x2 = block, block259 tr1, tr2 = [], []60 S.compress(state, block, 64, feedforward=False, trace=tr1)61 S.compress(state2, block2, 64, feedforward=False, trace=tr2)62 stats["compress_calls"] += 263 for t in range(64):64 d = state_to_int(tr1[t]) ^ state_to_int(tr2[t])65 bits = int_to_bits(d, 256)66 flips[t] += bits67 hw[i, t] = sum(bits)68 ro_flips[i] = bin(random_oracle(salt, x1) ^ random_oracle(salt, x2)).count("1")69 mean_matrix = flips / n70 ratio = mean_matrix.mean(axis=1) # mean flip ratio per step71 full = next((t + 1 for t in range(64) if ratio[t] >= threshold), None)72 brng = random.Random(seed + 1000)73 out[cfg] = {74 "n": n,75 "mean_flip_matrix": mean_matrix.round(5).tolist(),76 "mean_flip_ratio_by_step": ratio.round(6).tolist(),77 "hamming_mean_by_step": hw.mean(axis=0).round(4).tolist(),78 "hamming_sd_by_step": hw.std(axis=0, ddof=1).round(4).tolist(),79 "hamming_ci95_step64": bootstrap_ci(hw[:, 63].tolist(), brng),80 "full_diffusion_step": full,81 "threshold": threshold,82 "random_oracle_control": {83 "flip_ratio_mean": float(ro_flips.mean() / 256),84 "flip_ratio_sd": float(ro_flips.std(ddof=1) / 256),85 "hamming_mean": float(ro_flips.mean()),86 "hamming_sd": float(ro_flips.std(ddof=1)),87 },88 "input_bit_positions_sample": in_pos[:20],89 }90 print(f"[{cfg}] full diffusion (>= {threshold}) at step {full}; ratio by step:",91 " ".join("%.3f" % x for x in ratio[:24]), "...", file=sys.stderr)92 return out, stats939495def main():96 ap = argparse.ArgumentParser()97 ap.add_argument("--seed", type=int, default=1)98 ap.add_argument("--n", type=int, default=2000)99 ap.add_argument("--threshold", type=float, default=0.49)100 ap.add_argument("--out", default="results/reduced_round_sha256/diffusion.json")101 a = ap.parse_args()102 t0 = time.time()103 meas, stats = run(a.seed, a.n, a.threshold)104 stats["wall_s"] = round(time.time() - t0, 3)105 stats["peak_rss_mb"] = peak_rss_mb()106 provenance.record("sha256_diffusion", {"n": a.n, "steps": 64, "threshold": a.threshold, "configs": CONFIGS,107 "feedforward": False, "iv": "standard H0"},108 meas, seed=a.seed, extra={"op_stats": stats}, out=a.out, started=t0)109 print("wrote", a.out, "in", stats["wall_s"], "s")110111112if __name__ == "__main__":113 main()114