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