nx_sha1.nx source
↩ module page · 318 lines · 11150 B
1// sha1.nx -- SHA-1 (FIPS 180-4 §6.1), 160-bit hash.
2//
3// NOT cryptographically safe for new protocols -- SHAttered (2017)
4// produced chosen-prefix collisions; any signature scheme using
5// SHA-1 is considered broken. But SHA-1 remains on the wire:
6// - TLS 1.0/1.1 MAC (legacy handshake interop)
7// - WebSocket handshake (RFC 6455 uses it in Sec-WebSocket-Accept;
8// collision resistance is not relied on here -- just the
9// mixing property, so it's safe in this specific use)
10// - git object IDs (migrating to SHA-256 slowly)
11// - HMAC-SHA1 (still fine; HMAC is collision-agnostic)
12// - OAuth 1.0, PBKDF2, old certificates
13//
14// So we ship it for protocol interop, never for new signatures.
15//
16// Algorithm (FIPS 180-4 §6.1):
17// - Pad: append 1 bit, zero-pad, append 64-bit big-endian
18// length so total length is a multiple of 512 bits.
19// - Process in 512-bit blocks using 80 rounds.
20// - State is 5 words (H0..H4) initialised to the FIPS constants.
21//
22// Invariants:
23// S1 Matches FIPS 180-4 test vectors.
24// S2 Empty input hashes to da39a3ee5e6b4b0d3255bfef95601890afd80709.
25// S3 State mmap'd per call -- no globals.
26//
27// license_tier: INDEPENDENT_REDERIVE
28// genealogy_id: international-research-sources/nist/fips_180_4
29//
30
31// nx_safety_envelope:
32// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
33// sil_target: SIL1
34// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
35// verdict: NOT_YET_EVALUATED
36
37import "nx_syscalls.nx"
38
39const SHA1_H0: i64 = 0x67452301
40const SHA1_H1: i64 = 0xEFCDAB89
41const SHA1_H2: i64 = 0x98BADCFE
42const SHA1_H3: i64 = 0x10325476
43const SHA1_H4: i64 = 0xC3D2E1F0
44
45const SHA1_K0: i64 = 0x5A827999
46const SHA1_K1: i64 = 0x6ED9EBA1
47const SHA1_K2: i64 = 0x8F1BBCDC
48const SHA1_K3: i64 = 0xCA62C1D6
49
50const SHA1_MASK32: i64 = 0xFFFFFFFF
51
52// 32-bit left rotate.
53//
54// BUG FIX (2026-05-15): the original `hi` mask `(1 << (32-k)) - 1` was
55// inverted -- for ROTL by k it kept only the LOW (32-k) bits of the
56// shifted-down top, dropping the actual rotated-in bits. This made
57// every SHA-1 digest wrong for inputs that hit `_wsx_rotl(b, 30)` in
58// the round-function -- which is every input. Just mask to MASK32
59// (the shifted-down value is at most 32 bits anyway). Verified
60// against the RFC 6455 example vector + sha1sum(1) on the same input.
61func sha1_rotl(x: i64, k: i64) -> i64 {
62 let x32: i64 = x & SHA1_MASK32
63 let lo: i64 = (x32 << k) & SHA1_MASK32
64 let hi: i64 = (x32 >> (32 - k)) & SHA1_MASK32
65 return lo | hi
66}
67
68// Process one 64-byte block at buf[off..off+64] into state[0..5]. The 80-word schedule `w`
69// is caller-owned scratch reused across blocks (perf 2026-06-10: was an mmap syscall PER block).
70func sha1_process_block(buf: *u8, off: i64, state: *i64, w: *i64) -> i64 {
71 var t: i64 = 0
72 while t < 16 {
73 let b0: i64 = buf[off + t * 4]
74 let b1: i64 = buf[off + t * 4 + 1]
75 let b2: i64 = buf[off + t * 4 + 2]
76 let b3: i64 = buf[off + t * 4 + 3]
77 w[t] = ((b0 << 24) | (b1 << 16) | (b2 << 8) | b3) & SHA1_MASK32
78 t = t + 1
79 }
80 t = 16
81 while t < 80 {
82 let v: i64 = w[t-3] ^ w[t-8] ^ w[t-14] ^ w[t-16]
83 w[t] = ((v << 1) | (v >> 31)) & SHA1_MASK32 // inline rotl(v,1)
84 t = t + 1
85 }
86
87 var a: i64 = state[0]
88 var b: i64 = state[1]
89 var c: i64 = state[2]
90 var d: i64 = state[3]
91 var e: i64 = state[4]
92
93 t = 0
94 while t < 80 {
95 var f: i64 = 0
96 var k: i64 = 0
97 if t < 20 {
98 f = (b & c) | ((b ^ SHA1_MASK32) & d)
99 k = SHA1_K0
100 }
101 if t >= 20 {
102 if t < 40 {
103 f = b ^ c ^ d
104 k = SHA1_K1
105 }
106 }
107 if t >= 40 {
108 if t < 60 {
109 f = (b & c) | (b & d) | (c & d)
110 k = SHA1_K2
111 }
112 }
113 if t >= 60 {
114 f = b ^ c ^ d
115 k = SHA1_K3
116 }
117
118 let ar5: i64 = ((a << 5) | (a >> 27)) & SHA1_MASK32 // inline rotl(a,5)
119 let temp: i64 = (ar5 + f + e + k + w[t]) & SHA1_MASK32
120 e = d
121 d = c
122 c = ((b << 30) | (b >> 2)) & SHA1_MASK32 // inline rotl(b,30)
123 b = a
124 a = temp
125 t = t + 1
126 }
127
128 state[0] = (state[0] + a) & SHA1_MASK32
129 state[1] = (state[1] + b) & SHA1_MASK32
130 state[2] = (state[2] + c) & SHA1_MASK32
131 state[3] = (state[3] + d) & SHA1_MASK32
132 state[4] = (state[4] + e) & SHA1_MASK32
133 return 0
134}
135
136// Forward decl -- used inside sha1().
137func if_ge(a: i64, b: i64, v1: i64, v2: i64) -> i64;
138
139// ============================================================================================
140// 2026-08-01 -- ZERO-ALLOCATION VARIANT (the layer BELOW the HMAC fix).
141//
142// sha1() performs THREE sys_mmap calls per invocation (state, message schedule, pad) and frees none.
143// HMAC calls sha1 TWICE, and PBKDF2 calls HMAC once per iteration, so a 16.7M-iteration PBKDF2 makes
144// ~100M unfreed mappings. ★★★★★FIXING THE ALLOCATOR AT ONE LAYER LEAVES THE LAYER BELOW LEAKING --
145// COUNT ALLOCATIONS ALONG THE WHOLE CALL PATH, NOT IN THE FUNCTION YOU EDITED. I hoisted HMAC's four
146// buffers first and measured 4.8 GB still consumed over 200k iterations; these three were why.
147// ⚠Note the comment on w_raw below: a previous fix already removed a per-BLOCK mmap here and stopped at
148// the per-CALL boundary. ★THE PREVIOUS FIXER STOPPED AT EXACTLY THE LAYER I STOPPED AT -- a per-call
149// allocation looks like "the small constant one" from inside the function and like a leak from the loop
150// above it.
151//
152// Scratch is a FIXED size independent of input length (unlike HMAC's, which scales with msg_len):
153// [0 .. 64) state (5 x i64)
154// [64 .. 704) w schedule (80 x i64)
155// [704 .. 832) pad (128)
156// Caller-owned, NOT `static`: sha1 must stay reentrant (see the reasoning in nx_hmac_sha1.nx).
157// ADDITIVE (Rule 19) -- sha1() keeps its exact signature and is now a wrapper.
158// ============================================================================================
159const SHA1_SCRATCH_BYTES: i64 = 1024
160const S1_OFF_STATE: i64 = 0
161const S1_OFF_W: i64 = 64
162const S1_OFF_PAD: i64 = 704
163
164func sha1_into(scratch: *u8, scratch_cap: i64, data: *u8, n: i64, out: *u8) -> i64 {
165 if scratch_cap < SHA1_SCRATCH_BYTES { return 0 - 1 }
166 let state: *i64 = (((scratch as i64) + S1_OFF_STATE) as *i64)
167 let wsch: *i64 = (((scratch as i64) + S1_OFF_W) as *i64)
168 let pad_raw: *u8 = ((scratch as i64) + S1_OFF_PAD) as *u8
169
170 state[0] = SHA1_H0
171 state[1] = SHA1_H1
172 state[2] = SHA1_H2
173 state[3] = SHA1_H3
174 state[4] = SHA1_H4
175
176 let full_blocks: i64 = n / 64
177 var i: i64 = 0
178 while i < full_blocks {
179 sha1_process_block(data, i * 64, state, wsch)
180 i = i + 1
181 }
182
183 let tail_off: i64 = full_blocks * 64
184 let tail_len: i64 = n - tail_off
185 var j: i64 = 0
186 while j < tail_len { pad_raw[j] = data[tail_off + j]; j = j + 1 }
187 pad_raw[tail_len] = 0x80
188 j = tail_len + 1
189 let blocks_needed: i64 = if_ge(tail_len + 1, 57, 2, 1)
190 let total_padded: i64 = blocks_needed * 64
191 while j < total_padded - 8 { pad_raw[j] = 0; j = j + 1 }
192 let bits: i64 = n * 8
193 pad_raw[total_padded - 8] = (bits >> 56) & 0xFF
194 pad_raw[total_padded - 7] = (bits >> 48) & 0xFF
195 pad_raw[total_padded - 6] = (bits >> 40) & 0xFF
196 pad_raw[total_padded - 5] = (bits >> 32) & 0xFF
197 pad_raw[total_padded - 4] = (bits >> 24) & 0xFF
198 pad_raw[total_padded - 3] = (bits >> 16) & 0xFF
199 pad_raw[total_padded - 2] = (bits >> 8) & 0xFF
200 pad_raw[total_padded - 1] = bits & 0xFF
201
202 var bb: i64 = 0
203 while bb < blocks_needed {
204 sha1_process_block(pad_raw, bb * 64, state, wsch)
205 bb = bb + 1
206 }
207
208 var k: i64 = 0
209 while k < 5 {
210 out[k * 4] = (state[k] >> 24) & 0xFF
211 out[k * 4 + 1] = (state[k] >> 16) & 0xFF
212 out[k * 4 + 2] = (state[k] >> 8) & 0xFF
213 out[k * 4 + 3] = state[k] & 0xFF
214 k = k + 1
215 }
216 return 0
217}
218
219// Compute SHA-1 of data[0..n] into out[0..20].
220func sha1(data: *u8, n: i64, out: *u8) -> i64 {
221 let state_raw: *u8 = sys_mmap(40)
222 let state: *i64 = state_raw as *i64
223 state[0] = SHA1_H0
224 state[1] = SHA1_H1
225 state[2] = SHA1_H2
226 state[3] = SHA1_H3
227 state[4] = SHA1_H4
228
229 // 80-word message-schedule scratch, allocated ONCE and reused for every block
230 // (was an mmap syscall per block -> for a 1 MB input that was ~16k syscalls).
231 let w_raw: *u8 = sys_mmap(80 * 8)
232 let w: *i64 = w_raw as *i64
233
234 // Process full 64-byte blocks.
235 let full_blocks: i64 = n / 64
236 var i: i64 = 0
237 while i < full_blocks {
238 sha1_process_block(data, i * 64, state, w)
239 i = i + 1
240 }
241
242 // Last partial block + padding.
243 let tail_off: i64 = full_blocks * 64
244 let tail_len: i64 = n - tail_off
245
246 // Pad buffer up to 64 or 128 bytes.
247 let pad_size: i64 = 128
248 let pad_raw: *u8 = sys_mmap(pad_size)
249 var j: i64 = 0
250 while j < tail_len {
251 pad_raw[j] = data[tail_off + j]
252 j = j + 1
253 }
254 pad_raw[tail_len] = 0x80
255 j = tail_len + 1
256
257 // We need room for 8-byte length at the end. If tail_len+1 > 56
258 // we need a second block.
259 let blocks_needed: i64 = if_ge(tail_len + 1, 57, 2, 1)
260 let total_padded: i64 = blocks_needed * 64
261 while j < total_padded - 8 {
262 pad_raw[j] = 0
263 j = j + 1
264 }
265 // 64-bit BE bit-length.
266 let bits: i64 = n * 8
267 pad_raw[total_padded - 8] = (bits >> 56) & 0xFF
268 pad_raw[total_padded - 7] = (bits >> 48) & 0xFF
269 pad_raw[total_padded - 6] = (bits >> 40) & 0xFF
270 pad_raw[total_padded - 5] = (bits >> 32) & 0xFF
271 pad_raw[total_padded - 4] = (bits >> 24) & 0xFF
272 pad_raw[total_padded - 3] = (bits >> 16) & 0xFF
273 pad_raw[total_padded - 2] = (bits >> 8) & 0xFF
274 pad_raw[total_padded - 1] = bits & 0xFF
275
276 // Process 1 or 2 more blocks.
277 var b: i64 = 0
278 while b < blocks_needed {
279 sha1_process_block(pad_raw, b * 64, state, w)
280 b = b + 1
281 }
282
283 // Write big-endian state[0..5] to out.
284 var w: i64 = 0
285 while w < 5 {
286 out[w * 4] = (state[w] >> 24) & 0xFF
287 out[w * 4 + 1] = (state[w] >> 16) & 0xFF
288 out[w * 4 + 2] = (state[w] >> 8) & 0xFF
289 out[w * 4 + 3] = state[w] & 0xFF
290 w = w + 1
291 }
292 return 0
293}
294
295// Helper: if a >= b, return v1, else v2.
296func if_ge(a: i64, b: i64, v1: i64, v2: i64) -> i64 {
297 if a >= b { return v1 }
298 return v2
299}
300
301// Compile-only smoke -- hash "" should give da39a3ee5e6b4b0d...
302func main() -> i64 {
303 let out: *u8 = sys_mmap(32)
304 sha1(0 as *u8, 0, out)
305 // Expected first 4 bytes: 0xDA 0x39 0xA3 0xEE
306 if out[0] != 0xDA { return 1 }
307 if out[1] != 0x39 { return 2 }
308 if out[2] != 0xA3 { return 3 }
309 if out[3] != 0xEE { return 4 }
310
311 // "abc" -> a9993e364706816aba3e25717850c26c9cd0d89d
312 sha1("abc", 3, out)
313 if out[0] != 0xA9 { return 5 }
314 if out[1] != 0x99 { return 6 }
315 if out[2] != 0x3E { return 7 }
316 if out[3] != 0x36 { return 8 }
317 return 0
318}