sha1.nx source
↩ module page · 217 lines · 6614 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
27import "syscalls.nx"
28
29const SHA1_H0: i64 = 0x67452301
30const SHA1_H1: i64 = 0xEFCDAB89
31const SHA1_H2: i64 = 0x98BADCFE
32const SHA1_H3: i64 = 0x10325476
33const SHA1_H4: i64 = 0xC3D2E1F0
34
35const SHA1_K0: i64 = 0x5A827999
36const SHA1_K1: i64 = 0x6ED9EBA1
37const SHA1_K2: i64 = 0x8F1BBCDC
38const SHA1_K3: i64 = 0xCA62C1D6
39
40const SHA1_MASK32: i64 = 0xFFFFFFFF
41
42// 32-bit left rotate.
43func sha1_rotl(x: i64, k: i64) -> i64 {
44 let x32: i64 = x & SHA1_MASK32
45 let lo: i64 = (x32 << k) & SHA1_MASK32
46 let hi: i64 = (x32 >> (32 - k)) & ((1 << (32 - k)) - 1)
47 return lo | hi
48}
49
50// Process one 64-byte block at buf[off..off+64] into state[0..5].
51func sha1_process_block(buf: *u8, off: i64, state: *i64) -> i64 {
52 // Expand into 80 words.
53 let w_raw: *u8 = sys_mmap(80 * 8)
54 let w: *i64 = w_raw as *i64
55
56 var t: i64 = 0
57 while t < 16 {
58 let b0: i64 = buf[off + t * 4]
59 let b1: i64 = buf[off + t * 4 + 1]
60 let b2: i64 = buf[off + t * 4 + 2]
61 let b3: i64 = buf[off + t * 4 + 3]
62 w[t] = ((b0 << 24) | (b1 << 16) | (b2 << 8) | b3) & SHA1_MASK32
63 t = t + 1
64 }
65 t = 16
66 while t < 80 {
67 let v: i64 = w[t-3] ^ w[t-8] ^ w[t-14] ^ w[t-16]
68 w[t] = sha1_rotl(v, 1)
69 t = t + 1
70 }
71
72 var a: i64 = state[0]
73 var b: i64 = state[1]
74 var c: i64 = state[2]
75 var d: i64 = state[3]
76 var e: i64 = state[4]
77
78 t = 0
79 while t < 80 {
80 var f: i64 = 0
81 var k: i64 = 0
82 if t < 20 {
83 f = (b & c) | ((b ^ SHA1_MASK32) & d)
84 k = SHA1_K0
85 }
86 if t >= 20 {
87 if t < 40 {
88 f = b ^ c ^ d
89 k = SHA1_K1
90 }
91 }
92 if t >= 40 {
93 if t < 60 {
94 f = (b & c) | (b & d) | (c & d)
95 k = SHA1_K2
96 }
97 }
98 if t >= 60 {
99 f = b ^ c ^ d
100 k = SHA1_K3
101 }
102
103 let temp: i64 = (sha1_rotl(a, 5) + f + e + k + w[t]) & SHA1_MASK32
104 e = d
105 d = c
106 c = sha1_rotl(b, 30)
107 b = a
108 a = temp
109 t = t + 1
110 }
111
112 state[0] = (state[0] + a) & SHA1_MASK32
113 state[1] = (state[1] + b) & SHA1_MASK32
114 state[2] = (state[2] + c) & SHA1_MASK32
115 state[3] = (state[3] + d) & SHA1_MASK32
116 state[4] = (state[4] + e) & SHA1_MASK32
117 return 0
118}
119
120// Forward decl -- used inside sha1().
121func if_ge(a: i64, b: i64, v1: i64, v2: i64) -> i64;
122
123// Compute SHA-1 of data[0..n] into out[0..20].
124func sha1(data: *u8, n: i64, out: *u8) -> i64 {
125 let state_raw: *u8 = sys_mmap(40)
126 let state: *i64 = state_raw as *i64
127 state[0] = SHA1_H0
128 state[1] = SHA1_H1
129 state[2] = SHA1_H2
130 state[3] = SHA1_H3
131 state[4] = SHA1_H4
132
133 // Process full 64-byte blocks.
134 let full_blocks: i64 = n / 64
135 var i: i64 = 0
136 while i < full_blocks {
137 sha1_process_block(data, i * 64, state)
138 i = i + 1
139 }
140
141 // Last partial block + padding.
142 let tail_off: i64 = full_blocks * 64
143 let tail_len: i64 = n - tail_off
144
145 // Pad buffer up to 64 or 128 bytes.
146 let pad_size: i64 = 128
147 let pad_raw: *u8 = sys_mmap(pad_size)
148 var j: i64 = 0
149 while j < tail_len {
150 pad_raw[j] = data[tail_off + j]
151 j = j + 1
152 }
153 pad_raw[tail_len] = 0x80
154 j = tail_len + 1
155
156 // We need room for 8-byte length at the end. If tail_len+1 > 56
157 // we need a second block.
158 let blocks_needed: i64 = if_ge(tail_len + 1, 57, 2, 1)
159 let total_padded: i64 = blocks_needed * 64
160 while j < total_padded - 8 {
161 pad_raw[j] = 0
162 j = j + 1
163 }
164 // 64-bit BE bit-length.
165 let bits: i64 = n * 8
166 pad_raw[total_padded - 8] = (bits >> 56) & 0xFF
167 pad_raw[total_padded - 7] = (bits >> 48) & 0xFF
168 pad_raw[total_padded - 6] = (bits >> 40) & 0xFF
169 pad_raw[total_padded - 5] = (bits >> 32) & 0xFF
170 pad_raw[total_padded - 4] = (bits >> 24) & 0xFF
171 pad_raw[total_padded - 3] = (bits >> 16) & 0xFF
172 pad_raw[total_padded - 2] = (bits >> 8) & 0xFF
173 pad_raw[total_padded - 1] = bits & 0xFF
174
175 // Process 1 or 2 more blocks.
176 var b: i64 = 0
177 while b < blocks_needed {
178 sha1_process_block(pad_raw, b * 64, state)
179 b = b + 1
180 }
181
182 // Write big-endian state[0..5] to out.
183 var w: i64 = 0
184 while w < 5 {
185 out[w * 4] = (state[w] >> 24) & 0xFF
186 out[w * 4 + 1] = (state[w] >> 16) & 0xFF
187 out[w * 4 + 2] = (state[w] >> 8) & 0xFF
188 out[w * 4 + 3] = state[w] & 0xFF
189 w = w + 1
190 }
191 return 0
192}
193
194// Helper: if a >= b, return v1, else v2.
195func if_ge(a: i64, b: i64, v1: i64, v2: i64) -> i64 {
196 if a >= b { return v1 }
197 return v2
198}
199
200// Compile-only smoke -- hash "" should give da39a3ee5e6b4b0d...
201func main() -> i64 {
202 let out: *u8 = sys_mmap(32)
203 sha1(0 as *u8, 0, out)
204 // Expected first 4 bytes: 0xDA 0x39 0xA3 0xEE
205 if out[0] != 0xDA { return 1 }
206 if out[1] != 0x39 { return 2 }
207 if out[2] != 0xA3 { return 3 }
208 if out[3] != 0xEE { return 4 }
209
210 // "abc" -> a9993e364706816aba3e25717850c26c9cd0d89d
211 sha1("abc", 3, out)
212 if out[0] != 0xA9 { return 5 }
213 if out[1] != 0x99 { return 6 }
214 if out[2] != 0x3E { return 7 }
215 if out[3] != 0x36 { return 8 }
216 return 0
217}