nx_sha3.nx source

1// sha3.nx -- FIPS 202 SHA3-256 (Keccak-f[1600], rate=1088 bits). 2// 3// license_tier: INDEPENDENT_REDERIVE 4// genealogy_id: international-research-sources/nist/fips_202 5// 6// Quantum-safe companion to sha256.nx. Under Grover's algorithm both 7// SHA-256 and SHA3-256 have ~128-bit collision resistance on a quantum 8// adversary, which remains secure -- but SHA-3 is the primitive used 9// internally by NIST post-quantum schemes (ML-KEM FIPS 203, ML-DSA 10// FIPS 204, SLH-DSA FIPS 205), so shipping it here is the prerequisite 11// for every quantum-safe KEM/signature we'll add later. 12// 13// Design: 14// - State: 25 * u64 = 1600 bits, laid out as a 5x5 lane grid A[x,y] 15// - Permutation: 24 rounds of theta, rho, pi, chi, iota 16// - Padding: SHA-3 domain separation byte 0x06, trailing 0x80 17// - Rate for SHA3-256: r = 1088 bits = 136 bytes; capacity c = 512 18// - Output: 32 bytes (first 256 bits of the state after finalisation) 19// 20// Reference: FIPS PUB 202, sections 3.2-3.3. Known answer: 21// sha3_256("abc") = 22// 3a985da74fe225b2045c172d6bd390bd855f086e3e9d525b46bfe24511431532 23// 24// This implementation: 25// - Pure NishiLang; no C interop; no libc. 26// - Uses only arithmetic + bit ops (XOR, AND, NOT, rotate-left) 27// defined on i64; 1600-bit state lives in a 25-entry i64 array. 28// - Sequential round loop; no table lookups on secret data. 29// 30// Timing-side-channel stance: Keccak-f is naturally constant-time 31// when compiled straight from the spec. The only operations are 32// XOR, AND, NOT, and rotate-left -- all secret-independent in time. 33// No S-box table, no conditional on state bits. Safe to handle 34// secret data directly. 35// 36// nx_safety_envelope: 37// intended_use: "SHA-3 / Keccak hash + SHAKE XOF -- post- 38// SHA-2-collision migration target, also 39// used as CSPRNG output stream" 40// sil_target: SIL3 41// asil_target: QM 42// dal_target: DAL B 43// evidence: [FIPS_202_canonical_basis, no_FP, 44// constant_time_keccak_f_permutation, 45// no_table_lookup_on_secret_data] 46// hazard_register: [bug-tape-state-not-cleared-after-use, 47// bug-tape-SHAKE-output-truncation] 48// residual_risk: "SHA-3 is the substrate's recommended hash 49// for new code; SHA-256 remains for legacy 50// TLS / RFC interop." 51// verdict: NOT_YET_EVALUATED 52 53import "nx_syscalls.nx" 54import "nx_bits.nx" 55 56// Round constants -- FIPS 202 Appendix A. 24 u64 constants. 57// Stored as a static table; no secret-dependent index -- only the 58// round counter (0..24) is used. 59// Rewritten 2026-05-20: of the 17 RC constants stored as hand- 60// converted negative-decimal i64 representations, multiple had 61// arithmetic errors (RC6, RC14, RC15, RC16 confirmed wrong; others 62// converted just for consistency). Silent SHA-3 output corruption 63// followed for an unknown duration with no external-reference KAT 64// to catch it. Per [[feedback-canonical-constants-kat-against- 65// reference-not-hand-converted]] -- hex literals only. 66const RC0: i64 = 0x0000000000000001 67const RC1: i64 = 0x0000000000008082 68const RC2: i64 = 0x800000000000808A 69const RC3: i64 = 0x8000000080008000 70const RC4: i64 = 0x000000000000808B 71const RC5: i64 = 0x0000000080000001 72const RC6: i64 = 0x8000000080008081 73const RC7: i64 = 0x8000000000008009 74const RC8: i64 = 0x000000000000008A 75const RC9: i64 = 0x0000000000000088 76const RC10: i64 = 0x0000000080008009 77const RC11: i64 = 0x000000008000000A 78const RC12: i64 = 0x000000008000808B 79const RC13: i64 = 0x800000000000008B 80const RC14: i64 = 0x8000000000008089 81const RC15: i64 = 0x8000000000008003 82const RC16: i64 = 0x8000000000008002 83const RC17: i64 = 0x8000000000000080 84const RC18: i64 = 0x000000000000800A 85const RC19: i64 = 0x800000008000000A 86const RC20: i64 = 0x8000000080008081 87const RC21: i64 = 0x8000000000008080 88const RC22: i64 = 0x0000000080000001 89const RC23: i64 = 0x8000000080008008 90 91// Read one round constant by index 0..24. 92func sha3_rc(r: i64) -> i64 { 93 if r == 0 { return RC0 } 94 if r == 1 { return RC1 } 95 if r == 2 { return RC2 } 96 if r == 3 { return RC3 } 97 if r == 4 { return RC4 } 98 if r == 5 { return RC5 } 99 if r == 6 { return RC6 } 100 if r == 7 { return RC7 } 101 if r == 8 { return RC8 } 102 if r == 9 { return RC9 } 103 if r == 10 { return RC10 } 104 if r == 11 { return RC11 } 105 if r == 12 { return RC12 } 106 if r == 13 { return RC13 } 107 if r == 14 { return RC14 } 108 if r == 15 { return RC15 } 109 if r == 16 { return RC16 } 110 if r == 17 { return RC17 } 111 if r == 18 { return RC18 } 112 if r == 19 { return RC19 } 113 if r == 20 { return RC20 } 114 if r == 21 { return RC21 } 115 if r == 22 { return RC22 } 116 return RC23 117} 118 119// Rotation offsets for the ρ step, indexed by (5 * y + x). Derived 120// from FIPS 202 Table 2. Constant; indexed only by public lane-pos. 121func sha3_rho(i: i64) -> i64 { 122 if i == 0 { return 0 } 123 if i == 1 { return 1 } 124 if i == 2 { return 62 } 125 if i == 3 { return 28 } 126 if i == 4 { return 27 } 127 if i == 5 { return 36 } 128 if i == 6 { return 44 } 129 if i == 7 { return 6 } 130 if i == 8 { return 55 } 131 if i == 9 { return 20 } 132 if i == 10 { return 3 } 133 if i == 11 { return 10 } 134 if i == 12 { return 43 } 135 if i == 13 { return 25 } 136 if i == 14 { return 39 } 137 if i == 15 { return 41 } 138 if i == 16 { return 45 } 139 if i == 17 { return 15 } 140 if i == 18 { return 21 } 141 if i == 19 { return 8 } 142 if i == 20 { return 18 } 143 if i == 21 { return 2 } 144 if i == 22 { return 61 } 145 if i == 23 { return 56 } 146 return 14 // i == 24 147} 148 149// Delegated to nx_bits_rotl64 (rolq/rol intrinsic). Keccak does 24 150// rounds * 25 lanes * 1 rotate per lane = 600 rotates per permutation; 151// every speedup compounds. 152func rotl64(x: i64, r: i64) -> i64 { 153 return nx_bits_rotl64(x, r) 154} 155 156// Read/write one lane at (x, y) in a 25-u64 state array. 157func lane_at(state: *i64, x: i64, y: i64) -> i64 { 158 return state[y * 5 + x] 159} 160 161func lane_set(state: *i64, x: i64, y: i64, v: i64) -> i64 { 162 state[y * 5 + x] = v 163 return 0 164} 165 166// One round of Keccak-f[1600]. state is 25 i64. scratch is 25 i64 167// used as working storage so the round's reads don't overlap writes. 168func keccak_round(state: *i64, scratch: *i64, round_idx: i64) -> i64 { 169 // theta: compute column parities C[x] = xor over y of A[x,y], 170 // then D[x] = C[x-1] xor rotl(C[x+1], 1). Apply A[x,y] ^= D[x]. 171 var x: i64 = 0 172 while x < 5 { 173 var c: i64 = lane_at(state, x, 0) 174 c = c ^ lane_at(state, x, 1) 175 c = c ^ lane_at(state, x, 2) 176 c = c ^ lane_at(state, x, 3) 177 c = c ^ lane_at(state, x, 4) 178 scratch[x] = c 179 x = x + 1 180 } 181 x = 0 182 while x < 5 { 183 let xm: i64 = (x + 4) % 5 184 let xp: i64 = (x + 1) % 5 185 let d: i64 = scratch[xm] ^ rotl64(scratch[xp], 1) 186 var y: i64 = 0 187 while y < 5 { 188 let v: i64 = lane_at(state, x, y) ^ d 189 lane_set(state, x, y, v) 190 y = y + 1 191 } 192 x = x + 1 193 } 194 195 // rho + pi: each lane gets rotated by its offset and moved to 196 // a permuted position. B[y, 2x+3y mod 5] = rotl(A[x,y], rho). 197 var yy: i64 = 0 198 while yy < 5 { 199 var xx: i64 = 0 200 while xx < 5 { 201 let r: i64 = sha3_rho(yy * 5 + xx) 202 let a: i64 = lane_at(state, xx, yy) 203 let nx: i64 = yy 204 let ny: i64 = (2 * xx + 3 * yy) % 5 205 scratch[ny * 5 + nx] = rotl64(a, r) 206 xx = xx + 1 207 } 208 yy = yy + 1 209 } 210 var k: i64 = 0 211 while k < 25 { state[k] = scratch[k]; k = k + 1 } 212 213 // chi: A[x,y] = A[x,y] xor ((not A[x+1,y]) and A[x+2,y]). 214 var y2: i64 = 0 215 while y2 < 5 { 216 var xxx: i64 = 0 217 while xxx < 5 { 218 scratch[xxx] = lane_at(state, xxx, y2) 219 xxx = xxx + 1 220 } 221 xxx = 0 222 while xxx < 5 { 223 let nx1: i64 = (xxx + 1) % 5 224 let nx2: i64 = (xxx + 2) % 5 225 let v: i64 = scratch[xxx] ^ ((scratch[nx1] ^ -1) & scratch[nx2]) 226 lane_set(state, xxx, y2, v) 227 xxx = xxx + 1 228 } 229 y2 = y2 + 1 230 } 231 232 // iota: A[0,0] ^= RC[round_idx] 233 let a00: i64 = lane_at(state, 0, 0) 234 lane_set(state, 0, 0, a00 ^ sha3_rc(round_idx)) 235 return 0 236} 237 238// Run all 24 rounds of the Keccak-f[1600] permutation. 239func keccak_permute(state: *i64, scratch: *i64) -> i64 { 240 var r: i64 = 0 241 while r < 24 { 242 keccak_round(state, scratch, r) 243 r = r + 1 244 } 245 return 0 246} 247 248// SHA3-256 absorb. `in_bytes` of length `n`; rate is 136 bytes. 249// Fully-filled blocks are XORed into the state then permuted. 250// Final partial block is padded with SHA-3 domain separator 0x06 at 251// the end of the message + 0x80 at position (rate - 1). Writes the 252// 32-byte digest to `out`. 253func sha3_256(in_bytes: *u8, n: i64, out: *u8) -> i64 { 254 // State: 25 * 8 = 200 bytes, zero-initialised. 255 let state_raw: *u8 = sys_mmap(200) 256 let state: *i64 = state_raw as *i64 257 var i: i64 = 0 258 while i < 25 { state[i] = 0; i = i + 1 } 259 260 let scratch_raw: *u8 = sys_mmap(200) 261 let scratch: *i64 = scratch_raw as *i64 262 263 let rate: i64 = 136 // bytes per block for SHA3-256 264 265 var pos: i64 = 0 266 // Absorb full blocks. 267 while n - pos >= rate { 268 var b: i64 = 0 269 while b < rate { 270 // XOR byte b of this block into state byte b. 271 let byte_idx: i64 = b 272 let lane_idx: i64 = byte_idx / 8 273 let shift: i64 = (byte_idx % 8) * 8 274 let in_b: i64 = in_bytes[pos + b] 275 state[lane_idx] = state[lane_idx] ^ (in_b << shift) 276 b = b + 1 277 } 278 keccak_permute(state, scratch) 279 pos = pos + rate 280 } 281 282 // Final partial block. Build a 136-byte scratch buffer with the 283 // remaining message bytes, 0x06 domain separator, zeros, 0x80. 284 let last_raw: *u8 = sys_mmap(rate) 285 var j: i64 = 0 286 while j < rate { last_raw[j] = 0; j = j + 1 } 287 let remaining: i64 = n - pos 288 j = 0 289 while j < remaining { last_raw[j] = in_bytes[pos + j]; j = j + 1 } 290 last_raw[remaining] = 0x06 291 last_raw[rate - 1] = last_raw[rate - 1] | 0x80 292 293 // Absorb the padded last block. 294 var b2: i64 = 0 295 while b2 < rate { 296 let lane_idx: i64 = b2 / 8 297 let shift: i64 = (b2 % 8) * 8 298 let lb: i64 = last_raw[b2] 299 state[lane_idx] = state[lane_idx] ^ (lb << shift) 300 b2 = b2 + 1 301 } 302 keccak_permute(state, scratch) 303 304 // Squeeze 32 bytes from the start of the state. 305 var k: i64 = 0 306 while k < 32 { 307 let lane_idx: i64 = k / 8 308 let shift: i64 = (k % 8) * 8 309 let v: i64 = (state[lane_idx] >> shift) & 0xFF 310 out[k] = v 311 k = k + 1 312 } 313 return 0 314} 315 316// Compile-only smoke. Real KAT ("abc" -> 3a985d...) requires a 317// execution harness we'll wire into f6_gate.sh once qemu-riscv64 is 318// available on the dev host. 319func main() -> i64 { 320 let msg: *u8 = "abc" 321 let digest: *u8 = sys_mmap(32) 322 sha3_256(msg, 3, digest) 323 return digest[0] as i64 324}