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