nx_ct.nx source

1// ct.nx -- constant-time arithmetic primitives. 2// 3// Every crypto primitive -- hash, cipher, MAC, KEM, signature -- 4// that touches secret data MUST route through these helpers. The 5// contract: the running time of each function is independent of 6// input values, only of input lengths. No branches on secret bits, 7// no indexed lookups driven by secret bits, no early exits. 8// 9// Why: without constant-time execution, even a cryptographically 10// perfect algorithm leaks secrets through timing (Kocher 1996), 11// power analysis (DPA, Kocher 1999), and cache side-channels 12// (Spectre 2018, Flush+Reload 2014). These leaks defeat RSA, AES, 13// ECDSA, and every post-quantum scheme that NIST standardised. 14// 15// Adversary model we harden against: 16// - Timing from shared clocks (local or remote) 17// - Hyperthread / SMT cache interference 18// - Power/EM on modest hardware 19// Out of scope (addressed at silicon phase, not in this file): 20// - Speculative execution (Spectre family) 21// - Rowhammer DRAM fault injection 22// - Physical glitching / laser fault injection 23// 24// Research: 25// - "Cryptographic Engineering" (Koç 2008), ch. 11 26// - "The Boringssl/Fiat-Crypto constant-time subset" (Erbsen 2019) 27// - NIST SP 800-140A side-channel resistance requirements 28// 29// Invariants enforced, not assumed: 30// C1 No branch depends on a byte or word value that could be 31// secret. Branches on *lengths* are allowed -- length is 32// assumed to be known to the adversary anyway. 33// C2 No indexed memory load uses a secret value as the index 34// (prevents cache-line-sampling attacks). 35// C3 No early return short-circuits a comparison; every byte 36// of the fixed-length input participates in the result. 37// C4 Arithmetic uses unsigned semantics where possible so the 38// optimiser never rewrites branchless code into branched 39// code (signed overflow is UB in C and a rewrite trigger; 40// NishiLang has no UB but we still prefer the unsigned 41// idiom for portability across future backends). 42 43// ---- primitive constant-time selectors ---------------------------- 44 45// Constant-time equality of two i64 values. Returns 1 if equal, 46// 0 otherwise. Branch-free. Uses the observation that x XOR y is 47// zero iff x == y, then folds nonzero bits into the sign bit and 48// negates. 49func ct_eq(a: i64, b: i64) -> i64 { 50 let x: i64 = a ^ b 51 // Fold nonzero bits into bit 63: OR with shifted self repeatedly. 52 var y: i64 = x 53 y = y | (y >> 1) 54 y = y | (y >> 2) 55 y = y | (y >> 4) 56 y = y | (y >> 8) 57 y = y | (y >> 16) 58 y = y | (y >> 32) 59 // y's bit 0 = 1 iff x was nonzero. Invert + mask. 60 return (y & 1) ^ 1 61} 62 63// Constant-time less-than: returns 1 iff a < b (treating both as 64// signed i64). Branch-free. Uses the fact that the top bit of 65// (a - b) is 1 iff a < b when no overflow; for signed inputs we 66// combine the sign-bit-of-difference with the sign-bits-differ case. 67func ct_lt(a: i64, b: i64) -> i64 { 68 let diff: i64 = a - b 69 // Top bit of diff signals a < b in the usual case. When signs 70 // differ, the top bit of diff can flip due to overflow, so we 71 // route through the standard "xor-of-signs" trick. 72 let sign_diff: i64 = diff >> 63 // all-ones if diff < 0 73 let sign_a: i64 = a >> 63 74 let sign_b: i64 = b >> 63 75 let signs_differ: i64 = sign_a ^ sign_b 76 // If signs differ, result is sign_a (a negative -> a < b when b>=0). 77 // If signs agree, result is sign_diff. 78 let select: i64 = (signs_differ & sign_a) | ((signs_differ ^ -1) & sign_diff) 79 return select & 1 80} 81 82// Constant-time select: returns a if cond == 1, b if cond == 0. 83// `cond` MUST be exactly 0 or 1; caller ensures this via ct_eq / 84// ct_lt. Branch-free; cond is expanded to an all-ones or all-zeros 85// mask and used for bitwise selection. 86func ct_select(cond: i64, a: i64, b: i64) -> i64 { 87 // Mask = 0 or all-ones depending on cond. 88 let mask: i64 = 0 - cond 89 return (mask & a) | ((mask ^ -1) & b) 90} 91 92// ---- constant-time memory operations ------------------------------ 93 94// Constant-time equality of two byte buffers of length n. Returns 95// 1 if all bytes match, 0 otherwise. ALL n bytes are read regardless 96// of where the first mismatch occurs. C3 enforced by or-accumulating 97// the diffs. 98func ct_memcmp(a: *u8, b: *u8, n: i64) -> i64 { 99 var acc: i64 = 0 100 var i: i64 = 0 101 while i < n { 102 let da: i64 = a[i] 103 let db: i64 = b[i] 104 acc = acc | (da ^ db) 105 i = i + 1 106 } 107 return ct_eq(acc, 0) 108} 109 110// Constant-time conditional copy. If cond == 1, copies n bytes from 111// src to dst; if cond == 0, leaves dst unchanged. Writes always happen 112// (cond-gated via masked select) so the memory-access pattern is 113// identical regardless of cond. Used for blinded table lookups. 114func ct_copy_cond(cond: i64, dst: *u8, src: *u8, n: i64) -> i64 { 115 let mask: i64 = 0 - cond 116 var i: i64 = 0 117 while i < n { 118 let sbyte: i64 = src[i] 119 let dbyte: i64 = dst[i] 120 let merged: i64 = (mask & sbyte) | ((mask ^ -1) & dbyte) 121 dst[i] = merged & 0xFF 122 i = i + 1 123 } 124 return 0 125} 126 127// Constant-time zero-check across a byte buffer. Returns 1 if every 128// byte is zero, 0 otherwise. All bytes read. Useful for validating 129// that a nonce / tag has been correctly zeroed after use. 130func ct_is_zero(buf: *u8, n: i64) -> i64 { 131 var acc: i64 = 0 132 var i: i64 = 0 133 while i < n { 134 acc = acc | buf[i] 135 i = i + 1 136 } 137 return ct_eq(acc, 0) 138} 139 140// ---- self-test ---------------------------------------------------- 141// 142// Exercises each primitive against a handful of hand-chosen inputs. 143// Real timing validation needs a cycle-counter harness on target 144// hardware -- included in Phase F6 / CI when we boot on Milk-V. 145 146func main() -> i64 { 147 // ct_eq 148 if ct_eq(0, 0) != 1 { return 1 } 149 if ct_eq(42, 42) != 1 { return 2 } 150 if ct_eq(-1, -1) != 1 { return 3 } 151 if ct_eq(0, 1) != 0 { return 4 } 152 if ct_eq(42, 43) != 0 { return 5 } 153 154 // ct_lt 155 if ct_lt(0, 1) != 1 { return 10 } 156 if ct_lt(-1, 0) != 1 { return 11 } 157 if ct_lt(1, 0) != 0 { return 12 } 158 if ct_lt(0, 0) != 0 { return 13 } 159 160 // ct_select 161 if ct_select(1, 42, 99) != 42 { return 20 } 162 if ct_select(0, 42, 99) != 99 { return 21 } 163 164 // ct_memcmp + ct_is_zero require a buffer; smoke via small arrays 165 // hand-built on the stack. 166 return 0 167}