nx_poly1305_wasm.nx source
↩ module page · 323 lines · 12493 B
1// nx_poly1305_wasm.nx -- Poly1305 MAC (RFC 7539 §2.5) for WAT target.
2//
3// One-time MAC over arbitrary input bytes using a 256-bit key (r || s).
4// Output is 16 bytes (128 bits).
5//
6// Per RFC 7539:
7// r' = clamp(r): r &= 0x0ffffffc0ffffffc0ffffffc0fffffff
8// acc = 0
9// for each 16-byte block (with padding 0x01 byte appended):
10// n = little-endian integer of block bytes
11// acc = ((acc + n) * r') mod (2^130 - 5)
12// tag = ((acc + s) mod 2^128) as 16 LE bytes
13//
14// Representation:
15// r' is stored as 5 26-bit limbs (h[0..4]; each fits in 26 bits)
16// acc is stored as 5 i64 limbs that may overflow temporarily during
17// multiply-then-reduce, fitting comfortably in i64 with headroom for
18// the partial-product carries.
19//
20// Reduction:
21// 2^130 mod (2^130 - 5) = 5
22// so anything carried out of bit 130 multiplies by 5 and adds back
23// to the low limbs. After one round of reduce-by-5 the value fits
24// back in 5*26 bits with at most 1 bit of carry, which we clean up.
25//
26// API for the embedder:
27//
28// nx_poly1305_one_shot(key_ptr, msg_ptr, msg_len, scratch_ptr,
29// out_ptr) -> i64
30// key_ptr -- 32 bytes (r || s)
31// msg_ptr -- message bytes
32// msg_len -- input length
33// scratch_ptr -- >=128 bytes work area
34// out_ptr -- 16-byte tag destination
35//
36// scratch layout (caller need not zero):
37// bytes 0.. 39 : r as 5 i64 (40 B) (clamped, only low 26 bits used)
38// bytes 40.. 79 : acc as 5 i64
39// bytes 80..127 : block scratch (16 bytes + 1 padding byte fits)
40//
41// Verified against RFC 7539 §2.5.2 + Poly1305 reference.
42//
43// license_tier: INDEPENDENT_REDERIVE
44// genealogy_id: international-research-sources/ietf/rfc_7539 +
45// daniel_j_bernstein/poly1305-aes_2005
46// lineage_id: nishi_poly1305_wasm_q11
47
48const M26: i64 = 0x3ffffff // 2^26 - 1
49
50// Read i64 limb at (base + idx*8) from a u8 buffer treated as packed i64s.
51func _i64_get(buf: *u8, idx: i64) -> i64 {
52 let off: i64 = idx * 8
53 return (buf[off] as i64) |
54 ((buf[off + 1] as i64) << 8) |
55 ((buf[off + 2] as i64) << 16) |
56 ((buf[off + 3] as i64) << 24) |
57 ((buf[off + 4] as i64) << 32) |
58 ((buf[off + 5] as i64) << 40) |
59 ((buf[off + 6] as i64) << 48) |
60 ((buf[off + 7] as i64) << 56)
61}
62func _i64_set(buf: *u8, idx: i64, v: i64) -> i64 {
63 let off: i64 = idx * 8
64 buf[off] = v & 0xFF
65 buf[off + 1] = (v >> 8) & 0xFF
66 buf[off + 2] = (v >> 16) & 0xFF
67 buf[off + 3] = (v >> 24) & 0xFF
68 buf[off + 4] = (v >> 32) & 0xFF
69 buf[off + 5] = (v >> 40) & 0xFF
70 buf[off + 6] = (v >> 48) & 0xFF
71 buf[off + 7] = (v >> 56) & 0xFF
72 return 0
73}
74
75// Read a 32-bit little-endian word from bytes at offset.
76func _le32_read(buf: *u8, off: i64) -> i64 {
77 return ((buf[off] as i64) |
78 ((buf[off + 1] as i64) << 8) |
79 ((buf[off + 2] as i64) << 16) |
80 ((buf[off + 3] as i64) << 24)) & 0xFFFFFFFF
81}
82
83// Clamp `r` per RFC 7539 §2.5.1: clear high 4 bits of bytes 3,7,11,15
84// and the low 2 bits of bytes 4, 8, 12. We do this on the raw key
85// bytes BEFORE we slice into 26-bit limbs.
86//
87// AND mask 0x0ffffffc 0ffffffc 0ffffffc 0fffffff applied LE.
88// r is the first 16 bytes of the 32-byte key.
89func _clamp_and_split_r(key_ptr: *u8, r_lims: *u8) -> i64 {
90 // Build the 128-bit clamped r as 4 LE 32-bit words.
91 let r0: i64 = _le32_read(key_ptr, 0) & 0x0fffffff
92 let r1: i64 = _le32_read(key_ptr, 4) & 0x0ffffffc
93 let r2: i64 = _le32_read(key_ptr, 8) & 0x0ffffffc
94 let r3: i64 = _le32_read(key_ptr, 12) & 0x0ffffffc
95
96 // Repack as 5 26-bit limbs: little-endian bit positions
97 // limb 0 = bits 0..25 (low 26 of r0)
98 // limb 1 = bits 26..51 (high 6 of r0 || low 20 of r1)
99 // limb 2 = bits 52..77 (high 12 of r1 || low 14 of r2)
100 // limb 3 = bits 78..103 (high 18 of r2 || low 8 of r3)
101 // limb 4 = bits 104..127 (high 24 of r3) -- top 2 bits zero from clamp
102 let l0: i64 = r0 & M26
103 let l1: i64 = ((r0 >> 26) | (r1 << 6)) & M26
104 let l2: i64 = ((r1 >> 20) | (r2 << 12)) & M26
105 let l3: i64 = ((r2 >> 14) | (r3 << 18)) & M26
106 let l4: i64 = (r3 >> 8) & M26
107 _i64_set(r_lims, 0, l0)
108 _i64_set(r_lims, 1, l1)
109 _i64_set(r_lims, 2, l2)
110 _i64_set(r_lims, 3, l3)
111 _i64_set(r_lims, 4, l4)
112 return 0
113}
114
115// Add a 16-byte block (or shorter, with hi_bit appended) to acc
116// represented as 5 26-bit limbs, then multiply acc by r and reduce
117// mod (2^130 - 5). hi_bit is the value of the bit just above the
118// final byte (1 for normal blocks, 0 for the partial-final without
119// padding -- but caller usually passes 1 with manual zero-padding).
120func _poly_block(acc_lims: *u8, r_lims: *u8, blk: *u8, blk_len: i64, hi_bit: i64) -> i64 {
121 // Read the 17-byte block (16 + 1 padding byte) as 5 26-bit limbs.
122 // We pad missing bytes with zero then set the hi_bit at bit (blk_len*8).
123 var bb: *u8 = blk
124 // Construct a 17-byte representation: bytes 0..15 are the message,
125 // byte 16 holds the hi_bit at bit 0. For the schedule below we treat
126 // hi_bit as bit position (blk_len*8) when blk_len < 16; for full
127 // blocks hi_bit lives at bit 128.
128
129 // Build local b[0..4] limbs of the input n in 26-bit chunks.
130 // The input has up to 130 bits (128 message + 1 hi_bit + room).
131 let b_le: *u8 = (bb as i64) as *u8
132 // Pack via 4 LE i32 reads:
133 var w0: i64 = 0
134 var w1: i64 = 0
135 var w2: i64 = 0
136 var w3: i64 = 0
137 var i: i64 = 0
138 while i < 4 {
139 let o: i64 = i * 4
140 if o + 3 < blk_len {
141 let w: i64 = _le32_read(b_le, o)
142 if i == 0 { w0 = w } else { if i == 1 { w1 = w } else { if i == 2 { w2 = w } else { w3 = w } } }
143 } else {
144 // Partial: read byte-by-byte, pad with zeros.
145 var v: i64 = 0
146 var jj: i64 = 0
147 while jj < 4 {
148 if o + jj < blk_len {
149 v = v | ((b_le[o + jj] as i64) << (jj * 8))
150 }
151 jj = jj + 1
152 }
153 if i == 0 { w0 = v } else { if i == 1 { w1 = v } else { if i == 2 { w2 = v } else { w3 = v } } }
154 }
155 i = i + 1
156 }
157 let n0: i64 = w0 & M26
158 let n1: i64 = ((w0 >> 26) | (w1 << 6)) & M26
159 let n2: i64 = ((w1 >> 20) | (w2 << 12)) & M26
160 let n3: i64 = ((w2 >> 14) | (w3 << 18)) & M26
161 // Top 24 bits of w3 -> bits 104..127; bit 128 = hi_bit
162 let n4: i64 = ((w3 >> 8) & M26) | (hi_bit << 24)
163
164 // acc += n (limbwise; values fit in 27 bits then)
165 let a0: i64 = _i64_get(acc_lims, 0) + n0
166 let a1: i64 = _i64_get(acc_lims, 1) + n1
167 let a2: i64 = _i64_get(acc_lims, 2) + n2
168 let a3: i64 = _i64_get(acc_lims, 3) + n3
169 let a4: i64 = _i64_get(acc_lims, 4) + n4
170
171 let r0: i64 = _i64_get(r_lims, 0)
172 let r1: i64 = _i64_get(r_lims, 1)
173 let r2: i64 = _i64_get(r_lims, 2)
174 let r3: i64 = _i64_get(r_lims, 3)
175 let r4: i64 = _i64_get(r_lims, 4)
176
177 // Pre-multiply r1..r4 by 5 for cross-product reductions
178 // (since 2^130 = 5 mod p, anything at bit position >= 130 wraps
179 // with a factor of 5).
180 let s1: i64 = r1 * 5
181 let s2: i64 = r2 * 5
182 let s3: i64 = r3 * 5
183 let s4: i64 = r4 * 5
184
185 // Polynomial multiply: d[i] = sum a[j]*r[i-j] + a[j]*5*r[5+i-j]
186 let d0: i64 = a0*r0 + a1*s4 + a2*s3 + a3*s2 + a4*s1
187 let d1: i64 = a0*r1 + a1*r0 + a2*s4 + a3*s3 + a4*s2
188 let d2: i64 = a0*r2 + a1*r1 + a2*r0 + a3*s4 + a4*s3
189 let d3: i64 = a0*r3 + a1*r2 + a2*r1 + a3*r0 + a4*s4
190 let d4: i64 = a0*r4 + a1*r3 + a2*r2 + a3*r1 + a4*r0
191
192 // Reduce: each d[i] is < ~2^57 (since a[i] < 2^27 and r[i] < 2^26).
193 // Carry-propagate down then back.
194 var c: i64 = 0
195 var e0: i64 = (d0 + c) & M26; c = (d0 + c) >> 26
196 var e1: i64 = (d1 + c) & M26; c = (d1 + c) >> 26
197 var e2: i64 = (d2 + c) & M26; c = (d2 + c) >> 26
198 var e3: i64 = (d3 + c) & M26; c = (d3 + c) >> 26
199 var e4: i64 = (d4 + c) & M26; c = (d4 + c) >> 26
200 // Carry from limb 4 wraps via 2^130 -> 5 into limb 0.
201 e0 = e0 + c * 5
202 let c2: i64 = e0 >> 26
203 e0 = e0 & M26
204 e1 = e1 + c2
205
206 _i64_set(acc_lims, 0, e0)
207 _i64_set(acc_lims, 1, e1)
208 _i64_set(acc_lims, 2, e2)
209 _i64_set(acc_lims, 3, e3)
210 _i64_set(acc_lims, 4, e4)
211 return 0
212}
213
214// Compute Poly1305 MAC for `msg_len` bytes into `out_ptr` (16 B).
215// Exported as `nx_poly1305_one_shot`.
216func nx_poly1305_one_shot(key_ptr: *u8, msg_ptr: *u8, msg_len: i64,
217 scratch_ptr: *u8, out_ptr: *u8) -> i64 {
218 let r_lims: *u8 = scratch_ptr
219 let acc: *u8 = (scratch_ptr as i64 + 40) as *u8
220 let blk: *u8 = (scratch_ptr as i64 + 80) as *u8
221
222 // Init r (clamped) and acc.
223 _clamp_and_split_r(key_ptr, r_lims)
224 var i: i64 = 0
225 while i < 5 { _i64_set(acc, i, 0); i = i + 1 }
226
227 // Process full 16-byte blocks.
228 var pos: i64 = 0
229 while pos + 16 <= msg_len {
230 var bi: i64 = 0
231 while bi < 16 { blk[bi] = msg_ptr[pos + bi]; bi = bi + 1 }
232 _poly_block(acc, r_lims, blk, 16, 1)
233 pos = pos + 16
234 }
235 // Final partial block (if any) -- pad with 0x01 then zeros.
236 let rem: i64 = msg_len - pos
237 if rem > 0 {
238 var bj: i64 = 0
239 while bj < 16 { blk[bj] = 0; bj = bj + 1 }
240 var bk: i64 = 0
241 while bk < rem { blk[bk] = msg_ptr[pos + bk]; bk = bk + 1 }
242 blk[rem] = 1
243 // hi_bit = 0 because the 1 byte we just wrote is part of the 16-byte block now.
244 _poly_block(acc, r_lims, blk, 16, 0)
245 }
246
247 // Final reduce: ensure acc is fully in [0, 2^130 - 5).
248 // Carry-propagate one more time then apply minus-(2^130 - 5) if acc >= p.
249 let h0a: i64 = _i64_get(acc, 0)
250 let h1a: i64 = _i64_get(acc, 1)
251 let h2a: i64 = _i64_get(acc, 2)
252 let h3a: i64 = _i64_get(acc, 3)
253 let h4a: i64 = _i64_get(acc, 4)
254
255 var h0: i64 = h0a
256 var h1: i64 = h1a
257 var h2: i64 = h2a
258 var h3: i64 = h3a
259 var h4: i64 = h4a
260
261 // One more carry sweep just in case.
262 var cc: i64 = h1 >> 26; h1 = h1 & M26; h2 = h2 + cc
263 cc = h2 >> 26; h2 = h2 & M26; h3 = h3 + cc
264 cc = h3 >> 26; h3 = h3 & M26; h4 = h4 + cc
265 cc = h4 >> 26; h4 = h4 & M26; h0 = h0 + cc * 5
266 cc = h0 >> 26; h0 = h0 & M26; h1 = h1 + cc
267
268 // Compute h - p (p = 2^130 - 5). If h >= p, use h - p; else use h.
269 var g0: i64 = h0 + 5
270 cc = g0 >> 26; g0 = g0 & M26
271 var g1: i64 = h1 + cc; cc = g1 >> 26; g1 = g1 & M26
272 var g2: i64 = h2 + cc; cc = g2 >> 26; g2 = g2 & M26
273 var g3: i64 = h3 + cc; cc = g3 >> 26; g3 = g3 & M26
274 var g4: i64 = h4 + cc - (1 << 26)
275 // mask = 0xFFFFFFFF... if g4 >= 0 else 0
276 var mask: i64 = 0
277 if g4 >= 0 { mask = 0xFFFFFFFFFFFFFFFF as i64 }
278 // Select g (when mask=1) or h (when mask=0) using XOR-and-XOR.
279 h0 = (h0 & (~mask & 0xFFFFFFFFFFFFFFFF)) | (g0 & mask)
280 h1 = (h1 & (~mask & 0xFFFFFFFFFFFFFFFF)) | (g1 & mask)
281 h2 = (h2 & (~mask & 0xFFFFFFFFFFFFFFFF)) | (g2 & mask)
282 h3 = (h3 & (~mask & 0xFFFFFFFFFFFFFFFF)) | (g3 & mask)
283 h4 = (h4 & (~mask & 0xFFFFFFFFFFFFFFFF)) | (g4 & mask)
284
285 // Convert to 4 LE 32-bit words.
286 let f0: i64 = ( h0 | (h1 << 26)) & 0xFFFFFFFF
287 let f1: i64 = ((h1 >> 6) | (h2 << 20)) & 0xFFFFFFFF
288 let f2: i64 = ((h2 >> 12) | (h3 << 14)) & 0xFFFFFFFF
289 let f3: i64 = ((h3 >> 18) | (h4 << 8)) & 0xFFFFFFFF
290
291 // Add s (the second half of the key) as 4 LE 32-bit words; mod 2^128.
292 let s0: i64 = _le32_read(key_ptr, 16)
293 let s1k: i64 = _le32_read(key_ptr, 20)
294 let s2k: i64 = _le32_read(key_ptr, 24)
295 let s3k: i64 = _le32_read(key_ptr, 28)
296
297 var t0: i64 = (f0 + s0) & 0xFFFFFFFF
298 var carry: i64 = (f0 + s0) >> 32
299 var t1: i64 = (f1 + s1k + carry) & 0xFFFFFFFF
300 carry = (f1 + s1k + carry) >> 32
301 var t2: i64 = (f2 + s2k + carry) & 0xFFFFFFFF
302 carry = (f2 + s2k + carry) >> 32
303 var t3: i64 = (f3 + s3k + carry) & 0xFFFFFFFF
304
305 // Write 16-byte tag LE.
306 out_ptr[0] = t0 & 0xFF
307 out_ptr[1] = (t0 >> 8) & 0xFF
308 out_ptr[2] = (t0 >> 16) & 0xFF
309 out_ptr[3] = (t0 >> 24) & 0xFF
310 out_ptr[4] = t1 & 0xFF
311 out_ptr[5] = (t1 >> 8) & 0xFF
312 out_ptr[6] = (t1 >> 16) & 0xFF
313 out_ptr[7] = (t1 >> 24) & 0xFF
314 out_ptr[8] = t2 & 0xFF
315 out_ptr[9] = (t2 >> 8) & 0xFF
316 out_ptr[10] = (t2 >> 16) & 0xFF
317 out_ptr[11] = (t2 >> 24) & 0xFF
318 out_ptr[12] = t3 & 0xFF
319 out_ptr[13] = (t3 >> 8) & 0xFF
320 out_ptr[14] = (t3 >> 16) & 0xFF
321 out_ptr[15] = (t3 >> 24) & 0xFF
322 return 0
323}