md5.nx source
↩ module page · 284 lines · 8797 B
1// md5.nx -- RFC 1321 MD5 hash.
2//
3// BROKEN cryptographically (collisions constructible in seconds
4// on a laptop since Wang 2004). Never use for signatures. Still
5// needed for interop:
6// - HTTP Digest authentication (RFC 7616 default)
7// - ETag generation in legacy servers (when not using sha)
8// - .iso / .zip / .torrent integrity checks
9// - git-lfs pointer checksums
10// - Content-MD5 header (deprecated but still seen)
11//
12// Algorithm (RFC 1321):
13// Padding: append 1 bit, zero-pad, append 64-bit LE length
14// until total length is multiple of 512 bits.
15// Process in 512-bit blocks; 64 rounds over 4-word state
16// (A, B, C, D) each updated through F/G/H/I round functions.
17//
18// Invariants:
19// M1 Empty string hashes to d41d8cd98f00b204e9800998ecf8427e.
20// M2 State mmap'd per call; no globals.
21// M3 Output is 16 bytes.
22
23import "syscalls.nx"
24
25const MD5_MASK32: i64 = 0xFFFFFFFF
26
27// 32-bit left rotate.
28func md5_rotl(x: i64, k: i64) -> i64 {
29 let x32: i64 = x & MD5_MASK32
30 let lo: i64 = (x32 << k) & MD5_MASK32
31 let hi: i64 = (x32 >> (32 - k)) & ((1 << (32 - k)) - 1)
32 return lo | hi
33}
34
35// Per-round shift amounts (4 per round, 16 rounds each quadrant).
36func md5_s(i: i64) -> i64 {
37 // Round 1: 7, 12, 17, 22
38 if i < 16 {
39 let m: i64 = i % 4
40 if m == 0 { return 7 }
41 if m == 1 { return 12 }
42 if m == 2 { return 17 }
43 return 22
44 }
45 if i < 32 {
46 let m: i64 = i % 4
47 if m == 0 { return 5 }
48 if m == 1 { return 9 }
49 if m == 2 { return 14 }
50 return 20
51 }
52 if i < 48 {
53 let m: i64 = i % 4
54 if m == 0 { return 4 }
55 if m == 1 { return 11 }
56 if m == 2 { return 16 }
57 return 23
58 }
59 let m: i64 = i % 4
60 if m == 0 { return 6 }
61 if m == 1 { return 10 }
62 if m == 2 { return 15 }
63 return 21
64}
65
66// Per-round K constants. Reference: RFC 1321 ยง3.4.
67func md5_k(i: i64) -> i64 {
68 if i == 0 { return 0xD76AA478 }
69 if i == 1 { return 0xE8C7B756 }
70 if i == 2 { return 0x242070DB }
71 if i == 3 { return 0xC1BDCEEE }
72 if i == 4 { return 0xF57C0FAF }
73 if i == 5 { return 0x4787C62A }
74 if i == 6 { return 0xA8304613 }
75 if i == 7 { return 0xFD469501 }
76 if i == 8 { return 0x698098D8 }
77 if i == 9 { return 0x8B44F7AF }
78 if i == 10 { return 0xFFFF5BB1 }
79 if i == 11 { return 0x895CD7BE }
80 if i == 12 { return 0x6B901122 }
81 if i == 13 { return 0xFD987193 }
82 if i == 14 { return 0xA679438E }
83 if i == 15 { return 0x49B40821 }
84 if i == 16 { return 0xF61E2562 }
85 if i == 17 { return 0xC040B340 }
86 if i == 18 { return 0x265E5A51 }
87 if i == 19 { return 0xE9B6C7AA }
88 if i == 20 { return 0xD62F105D }
89 if i == 21 { return 0x02441453 }
90 if i == 22 { return 0xD8A1E681 }
91 if i == 23 { return 0xE7D3FBC8 }
92 if i == 24 { return 0x21E1CDE6 }
93 if i == 25 { return 0xC33707D6 }
94 if i == 26 { return 0xF4D50D87 }
95 if i == 27 { return 0x455A14ED }
96 if i == 28 { return 0xA9E3E905 }
97 if i == 29 { return 0xFCEFA3F8 }
98 if i == 30 { return 0x676F02D9 }
99 if i == 31 { return 0x8D2A4C8A }
100 if i == 32 { return 0xFFFA3942 }
101 if i == 33 { return 0x8771F681 }
102 if i == 34 { return 0x6D9D6122 }
103 if i == 35 { return 0xFDE5380C }
104 if i == 36 { return 0xA4BEEA44 }
105 if i == 37 { return 0x4BDECFA9 }
106 if i == 38 { return 0xF6BB4B60 }
107 if i == 39 { return 0xBEBFBC70 }
108 if i == 40 { return 0x289B7EC6 }
109 if i == 41 { return 0xEAA127FA }
110 if i == 42 { return 0xD4EF3085 }
111 if i == 43 { return 0x04881D05 }
112 if i == 44 { return 0xD9D4D039 }
113 if i == 45 { return 0xE6DB99E5 }
114 if i == 46 { return 0x1FA27CF8 }
115 if i == 47 { return 0xC4AC5665 }
116 if i == 48 { return 0xF4292244 }
117 if i == 49 { return 0x432AFF97 }
118 if i == 50 { return 0xAB9423A7 }
119 if i == 51 { return 0xFC93A039 }
120 if i == 52 { return 0x655B59C3 }
121 if i == 53 { return 0x8F0CCC92 }
122 if i == 54 { return 0xFFEFF47D }
123 if i == 55 { return 0x85845DD1 }
124 if i == 56 { return 0x6FA87E4F }
125 if i == 57 { return 0xFE2CE6E0 }
126 if i == 58 { return 0xA3014314 }
127 if i == 59 { return 0x4E0811A1 }
128 if i == 60 { return 0xF7537E82 }
129 if i == 61 { return 0xBD3AF235 }
130 if i == 62 { return 0x2AD7D2BB }
131 return 0xEB86D391
132}
133
134// Pick message-block word index for round i.
135func md5_g(i: i64) -> i64 {
136 if i < 16 { return i }
137 if i < 32 { return (5 * i + 1) % 16 }
138 if i < 48 { return (3 * i + 5) % 16 }
139 return (7 * i) % 16
140}
141
142// Process one 64-byte block at buf[off..off+64] updating state[0..4].
143func md5_process_block(buf: *u8, off: i64, state: *i64) -> i64 {
144 // Decode 16 little-endian words.
145 let m_raw: *u8 = sys_mmap(16 * 8)
146 let m: *i64 = m_raw as *i64
147 var i: i64 = 0
148 while i < 16 {
149 let b0: i64 = buf[off + i*4]
150 let b1: i64 = buf[off + i*4 + 1]
151 let b2: i64 = buf[off + i*4 + 2]
152 let b3: i64 = buf[off + i*4 + 3]
153 m[i] = b0 | (b1 << 8) | (b2 << 16) | (b3 << 24)
154 i = i + 1
155 }
156
157 var a: i64 = state[0]
158 var b: i64 = state[1]
159 var c: i64 = state[2]
160 var d: i64 = state[3]
161
162 i = 0
163 while i < 64 {
164 var f: i64 = 0
165 if i < 16 {
166 // F = (b & c) | (~b & d)
167 f = (b & c) | ((b ^ MD5_MASK32) & d)
168 }
169 if i >= 16 {
170 if i < 32 {
171 // G = (d & b) | (~d & c)
172 f = (d & b) | ((d ^ MD5_MASK32) & c)
173 }
174 }
175 if i >= 32 {
176 if i < 48 {
177 // H = b ^ c ^ d
178 f = b ^ c ^ d
179 }
180 }
181 if i >= 48 {
182 // I = c ^ (b | ~d)
183 f = c ^ (b | (d ^ MD5_MASK32))
184 }
185 let g: i64 = md5_g(i)
186 let temp: i64 = d
187 let val: i64 = (a + f + md5_k(i) + m[g]) & MD5_MASK32
188 d = c
189 c = b
190 b = (b + md5_rotl(val, md5_s(i))) & MD5_MASK32
191 a = temp
192 i = i + 1
193 }
194
195 state[0] = (state[0] + a) & MD5_MASK32
196 state[1] = (state[1] + b) & MD5_MASK32
197 state[2] = (state[2] + c) & MD5_MASK32
198 state[3] = (state[3] + d) & MD5_MASK32
199 return 0
200}
201
202// Compute MD5 of data[0..n] into out[0..16].
203func md5(data: *u8, n: i64, out: *u8) -> i64 {
204 let state_raw: *u8 = sys_mmap(40)
205 let state: *i64 = state_raw as *i64
206 state[0] = 0x67452301
207 state[1] = 0xEFCDAB89
208 state[2] = 0x98BADCFE
209 state[3] = 0x10325476
210
211 let full_blocks: i64 = n / 64
212 var i: i64 = 0
213 while i < full_blocks {
214 md5_process_block(data, i * 64, state)
215 i = i + 1
216 }
217
218 let tail_off: i64 = full_blocks * 64
219 let tail_len: i64 = n - tail_off
220
221 let pad_size: i64 = 128
222 let pad_raw: *u8 = sys_mmap(pad_size)
223 var j: i64 = 0
224 while j < tail_len {
225 pad_raw[j] = data[tail_off + j]
226 j = j + 1
227 }
228 pad_raw[tail_len] = 0x80
229 j = tail_len + 1
230
231 // Need room for 8-byte LE length at end.
232 var blocks_needed: i64 = 1
233 if tail_len + 1 > 56 { blocks_needed = 2 }
234 let total_padded: i64 = blocks_needed * 64
235 while j < total_padded - 8 {
236 pad_raw[j] = 0
237 j = j + 1
238 }
239 // 64-bit little-endian bit length.
240 let bits: i64 = n * 8
241 pad_raw[total_padded - 8] = bits & 0xFF
242 pad_raw[total_padded - 7] = (bits >> 8) & 0xFF
243 pad_raw[total_padded - 6] = (bits >> 16) & 0xFF
244 pad_raw[total_padded - 5] = (bits >> 24) & 0xFF
245 pad_raw[total_padded - 4] = (bits >> 32) & 0xFF
246 pad_raw[total_padded - 3] = (bits >> 40) & 0xFF
247 pad_raw[total_padded - 2] = (bits >> 48) & 0xFF
248 pad_raw[total_padded - 1] = (bits >> 56) & 0xFF
249
250 var b: i64 = 0
251 while b < blocks_needed {
252 md5_process_block(pad_raw, b * 64, state)
253 b = b + 1
254 }
255
256 // Little-endian state output.
257 var w: i64 = 0
258 while w < 4 {
259 out[w * 4] = state[w] & 0xFF
260 out[w * 4 + 1] = (state[w] >> 8) & 0xFF
261 out[w * 4 + 2] = (state[w] >> 16) & 0xFF
262 out[w * 4 + 3] = (state[w] >> 24) & 0xFF
263 w = w + 1
264 }
265 return 0
266}
267
268// Compile-only smoke -- empty string + "abc".
269func main() -> i64 {
270 let out: *u8 = sys_mmap(32)
271
272 // "" -> d41d8cd98f00b204e9800998ecf8427e
273 md5(0 as *u8, 0, out)
274 if out[0] != 0xD4 { return 1 }
275 if out[1] != 0x1D { return 2 }
276 if out[15] != 0x7E { return 3 }
277
278 // "abc" -> 900150983cd24fb0d6963f7d28e17f72
279 md5("abc", 3, out)
280 if out[0] != 0x90 { return 4 }
281 if out[1] != 0x01 { return 5 }
282 if out[15] != 0x72 { return 6 }
283 return 0
284}