1const std = @import("../std.zig");
2const mem = std.mem;
3const mulWide = std.math.mulWide;
4
5pub const Poly1305 = struct {
6 pub const block_length: usize = 16;
7 pub const mac_length = 16;
8 pub const key_length = 32;
9
10 // constant multiplier (from the secret key)
11 r: [2]u64,
12 // accumulated hash
13 h: [3]u64 = [_]u64{ 0, 0, 0 },
14 // random number added at the end (from the secret key)
15 end_pad: [2]u64,
16 // how many bytes are waiting to be processed in a partial block
17 leftover: usize = 0,
18 // partial block buffer
19 buf: [block_length]u8 align(16) = undefined,
20
21 pub fn init(key: *const [key_length]u8) Poly1305 {
22 return Poly1305{
23 .r = [_]u64{
24 mem.readInt(u64, key[0..8], .little) & 0x0ffffffc0fffffff,
25 mem.readInt(u64, key[8..16], .little) & 0x0ffffffc0ffffffc,
26 },
27 .end_pad = [_]u64{
28 mem.readInt(u64, key[16..24], .little),
29 mem.readInt(u64, key[24..32], .little),
30 },
31 };
32 }
33
34 fn add(a: u64, b: u64, c: u1) struct { u64, u1 } {
35 const v1 = @addWithOverflow(a, b);
36 const v2 = @addWithOverflow(v1[0], c);
37 return .{ v2[0], v1[1] | v2[1] };
38 }
39
40 fn sub(a: u64, b: u64, c: u1) struct { u64, u1 } {
41 const v1 = @subWithOverflow(a, b);
42 const v2 = @subWithOverflow(v1[0], c);
43 return .{ v2[0], v1[1] | v2[1] };
44 }
45
46 fn blocks(st: *Poly1305, m: []const u8, comptime last: bool) void {
47 const hibit: u64 = if (last) 0 else 1;
48 const r0 = st.r[0];
49 const r1 = st.r[1];
50
51 var h0 = st.h[0];
52 var h1 = st.h[1];
53 var h2 = st.h[2];
54
55 var i: usize = 0;
56
57 while (i + block_length <= m.len) : (i += block_length) {
58 const in0 = mem.readInt(u64, m[i..][0..8], .little);
59 const in1 = mem.readInt(u64, m[i + 8 ..][0..8], .little);
60
61 // Add the input message to H
62 var v = @addWithOverflow(h0, in0);
63 h0 = v[0];
64 v = add(h1, in1, v[1]);
65 h1 = v[0];
66 h2 +%= v[1] +% hibit;
67
68 // Compute H * R
69 const m0 = mulWide(u64, h0, r0);
70 const h1r0 = mulWide(u64, h1, r0);
71 const h0r1 = mulWide(u64, h0, r1);
72 const h2r0 = mulWide(u64, h2, r0);
73 const h1r1 = mulWide(u64, h1, r1);
74 const m3 = mulWide(u64, h2, r1);
75 const m1 = h1r0 +% h0r1;
76 const m2 = h2r0 +% h1r1;
77
78 const t0 = @as(u64, @truncate(m0));
79 v = @addWithOverflow(@as(u64, @truncate(m1)), @as(u64, @truncate(m0 >> 64)));
80 const t1 = v[0];
81 v = add(@as(u64, @truncate(m2)), @as(u64, @truncate(m1 >> 64)), v[1]);
82 const t2 = v[0];
83 v = add(@as(u64, @truncate(m3)), @as(u64, @truncate(m2 >> 64)), v[1]);
84 const t3 = v[0];
85
86 // Partial reduction
87 h0 = t0;
88 h1 = t1;
89 h2 = t2 & 3;
90
91 // Add c*(4+1)
92 const cclo = t2 & ~@as(u64, 3);
93 const cchi = t3;
94 v = @addWithOverflow(h0, cclo);
95 h0 = v[0];
96 v = add(h1, cchi, v[1]);
97 h1 = v[0];
98 h2 +%= v[1];
99 const cc = (cclo | (@as(u128, cchi) << 64)) >> 2;
100 v = @addWithOverflow(h0, @as(u64, @truncate(cc)));
101 h0 = v[0];
102 v = add(h1, @as(u64, @truncate(cc >> 64)), v[1]);
103 h1 = v[0];
104 h2 +%= v[1];
105 }
106 st.h = [_]u64{ h0, h1, h2 };
107 }
108
109 pub fn update(st: *Poly1305, m: []const u8) void {
110 var mb = m;
111
112 // handle leftover
113 if (st.leftover > 0) {
114 const want = @min(block_length - st.leftover, mb.len);
115 const mc = mb[0..want];
116 for (mc, 0..) |x, i| {
117 st.buf[st.leftover + i] = x;
118 }
119 mb = mb[want..];
120 st.leftover += want;
121 if (st.leftover < block_length) {
122 return;
123 }
124 st.blocks(&st.buf, false);
125 st.leftover = 0;
126 }
127
128 // process full blocks
129 if (mb.len >= block_length) {
130 const want = mb.len & ~(block_length - 1);
131 st.blocks(mb[0..want], false);
132 mb = mb[want..];
133 }
134
135 // store leftover
136 if (mb.len > 0) {
137 for (mb, 0..) |x, i| {
138 st.buf[st.leftover + i] = x;
139 }
140 st.leftover += mb.len;
141 }
142 }
143
144 /// Zero-pad to align the next input to the first byte of a block
145 pub fn pad(st: *Poly1305) void {
146 if (st.leftover == 0) {
147 return;
148 }
149 @memset(st.buf[st.leftover..], 0);
150 st.blocks(&st.buf, false);
151 st.leftover = 0;
152 }
153
154 pub fn final(st: *Poly1305, out: *[mac_length]u8) void {
155 if (st.leftover > 0) {
156 var i = st.leftover;
157 st.buf[i] = 1;
158 i += 1;
159 @memset(st.buf[i..], 0);
160 st.blocks(&st.buf, true);
161 }
162
163 var h0 = st.h[0];
164 var h1 = st.h[1];
165 const h2 = st.h[2];
166
167 // H - (2^130 - 5)
168 var v = @subWithOverflow(h0, 0xfffffffffffffffb);
169 const h_p0 = v[0];
170 v = sub(h1, 0xffffffffffffffff, v[1]);
171 const h_p1 = v[0];
172 v = sub(h2, 0x0000000000000003, v[1]);
173
174 // Final reduction, subtract 2^130-5 from H if H >= 2^130-5
175 const mask = @as(u64, v[1]) -% 1;
176 h0 ^= mask & (h0 ^ h_p0);
177 h1 ^= mask & (h1 ^ h_p1);
178
179 // Add the first half of the key, we intentionally don't use @addWithOverflow() here.
180 st.h[0] = h0 +% st.end_pad[0];
181 const c = ((h0 & st.end_pad[0]) | ((h0 | st.end_pad[0]) & ~st.h[0])) >> 63;
182 st.h[1] = h1 +% st.end_pad[1] +% c;
183
184 mem.writeInt(u64, out[0..8], st.h[0], .little);
185 mem.writeInt(u64, out[8..16], st.h[1], .little);
186
187 std.crypto.secureZero(Poly1305, st[0..1]);
188 }
189
190 pub fn create(out: *[mac_length]u8, msg: []const u8, key: *const [key_length]u8) void {
191 var st = Poly1305.init(key);
192 st.update(msg);
193 st.final(out);
194 }
195};
196
197test "rfc7439 vector1" {
198 const expected_mac = "\xa8\x06\x1d\xc1\x30\x51\x36\xc6\xc2\x2b\x8b\xaf\x0c\x01\x27\xa9";
199
200 const msg = "Cryptographic Forum Research Group";
201 const key = "\x85\xd6\xbe\x78\x57\x55\x6d\x33\x7f\x44\x52\xfe\x42\xd5\x06\xa8" ++
202 "\x01\x03\x80\x8a\xfb\x0d\xb2\xfd\x4a\xbf\xf6\xaf\x41\x49\xf5\x1b";
203
204 var mac: [16]u8 = undefined;
205 Poly1305.create(mac[0..], msg, key);
206
207 try std.testing.expectEqualSlices(u8, expected_mac, &mac);
208}
209
210test "requiring a final reduction" {
211 const expected_mac = [_]u8{ 25, 13, 249, 42, 164, 57, 99, 60, 149, 181, 74, 74, 13, 63, 121, 6 };
212 const msg = [_]u8{ 253, 193, 249, 146, 70, 6, 214, 226, 131, 213, 241, 116, 20, 24, 210, 224, 65, 151, 255, 104, 133 };
213 const key = [_]u8{ 190, 63, 95, 57, 155, 103, 77, 170, 7, 98, 106, 44, 117, 186, 90, 185, 109, 118, 184, 24, 69, 41, 166, 243, 119, 132, 151, 61, 52, 43, 64, 250 };
214 var mac: [16]u8 = undefined;
215 Poly1305.create(mac[0..], &msg, &key);
216 try std.testing.expectEqualSlices(u8, &expected_mac, &mac);
217}