1 |
|
|
/* $OpenBSD: poly1305-donna.c,v 1.3 2014/06/12 15:49:30 deraadt Exp $ */ |
2 |
|
|
/* |
3 |
|
|
* Public Domain poly1305 from Andrew Moon |
4 |
|
|
* Based on poly1305-donna.c, poly1305-donna-32.h and poly1305-donna.h from: |
5 |
|
|
* https://github.com/floodyberry/poly1305-donna |
6 |
|
|
*/ |
7 |
|
|
|
8 |
|
|
#include <stddef.h> |
9 |
|
|
|
10 |
|
|
static inline void poly1305_init(poly1305_context *ctx, |
11 |
|
|
const unsigned char key[32]); |
12 |
|
|
static inline void poly1305_update(poly1305_context *ctx, |
13 |
|
|
const unsigned char *m, size_t bytes); |
14 |
|
|
static inline void poly1305_finish(poly1305_context *ctx, |
15 |
|
|
unsigned char mac[16]); |
16 |
|
|
|
17 |
|
|
/* |
18 |
|
|
* poly1305 implementation using 32 bit * 32 bit = 64 bit multiplication |
19 |
|
|
* and 64 bit addition. |
20 |
|
|
*/ |
21 |
|
|
|
22 |
|
|
#define poly1305_block_size 16 |
23 |
|
|
|
24 |
|
|
/* 17 + sizeof(size_t) + 14*sizeof(unsigned long) */ |
25 |
|
|
typedef struct poly1305_state_internal_t { |
26 |
|
|
unsigned long r[5]; |
27 |
|
|
unsigned long h[5]; |
28 |
|
|
unsigned long pad[4]; |
29 |
|
|
size_t leftover; |
30 |
|
|
unsigned char buffer[poly1305_block_size]; |
31 |
|
|
unsigned char final; |
32 |
|
|
} poly1305_state_internal_t; |
33 |
|
|
|
34 |
|
|
/* interpret four 8 bit unsigned integers as a 32 bit unsigned integer in little endian */ |
35 |
|
|
static unsigned long |
36 |
|
|
U8TO32(const unsigned char *p) |
37 |
|
|
{ |
38 |
|
195816 |
return (((unsigned long)(p[0] & 0xff)) | |
39 |
|
97908 |
((unsigned long)(p[1] & 0xff) << 8) | |
40 |
|
97908 |
((unsigned long)(p[2] & 0xff) << 16) | |
41 |
|
48954 |
((unsigned long)(p[3] & 0xff) << 24)); |
42 |
|
|
} |
43 |
|
|
|
44 |
|
|
/* store a 32 bit unsigned integer as four 8 bit unsigned integers in little endian */ |
45 |
|
|
static void |
46 |
|
|
U32TO8(unsigned char *p, unsigned long v) |
47 |
|
|
{ |
48 |
|
7008 |
p[0] = (v) & 0xff; |
49 |
|
3504 |
p[1] = (v >> 8) & 0xff; |
50 |
|
3504 |
p[2] = (v >> 16) & 0xff; |
51 |
|
3504 |
p[3] = (v >> 24) & 0xff; |
52 |
|
3504 |
} |
53 |
|
|
|
54 |
|
|
static inline void |
55 |
|
|
poly1305_init(poly1305_context *ctx, const unsigned char key[32]) |
56 |
|
|
{ |
57 |
|
1752 |
poly1305_state_internal_t *st = (poly1305_state_internal_t *)ctx; |
58 |
|
|
|
59 |
|
|
/* r &= 0xffffffc0ffffffc0ffffffc0fffffff */ |
60 |
|
876 |
st->r[0] = (U8TO32(&key[0])) & 0x3ffffff; |
61 |
|
876 |
st->r[1] = (U8TO32(&key[3]) >> 2) & 0x3ffff03; |
62 |
|
876 |
st->r[2] = (U8TO32(&key[6]) >> 4) & 0x3ffc0ff; |
63 |
|
876 |
st->r[3] = (U8TO32(&key[9]) >> 6) & 0x3f03fff; |
64 |
|
876 |
st->r[4] = (U8TO32(&key[12]) >> 8) & 0x00fffff; |
65 |
|
|
|
66 |
|
|
/* h = 0 */ |
67 |
|
876 |
st->h[0] = 0; |
68 |
|
876 |
st->h[1] = 0; |
69 |
|
876 |
st->h[2] = 0; |
70 |
|
876 |
st->h[3] = 0; |
71 |
|
876 |
st->h[4] = 0; |
72 |
|
|
|
73 |
|
|
/* save pad for later */ |
74 |
|
876 |
st->pad[0] = U8TO32(&key[16]); |
75 |
|
876 |
st->pad[1] = U8TO32(&key[20]); |
76 |
|
876 |
st->pad[2] = U8TO32(&key[24]); |
77 |
|
876 |
st->pad[3] = U8TO32(&key[28]); |
78 |
|
|
|
79 |
|
876 |
st->leftover = 0; |
80 |
|
876 |
st->final = 0; |
81 |
|
876 |
} |
82 |
|
|
|
83 |
|
|
static void |
84 |
|
|
poly1305_blocks(poly1305_state_internal_t *st, const unsigned char *m, size_t bytes) |
85 |
|
|
{ |
86 |
|
5094 |
const unsigned long hibit = (st->final) ? 0 : (1 << 24); /* 1 << 128 */ |
87 |
|
|
unsigned long r0, r1, r2, r3, r4; |
88 |
|
|
unsigned long s1, s2, s3, s4; |
89 |
|
|
unsigned long h0, h1, h2, h3, h4; |
90 |
|
|
unsigned long long d0, d1, d2, d3, d4; |
91 |
|
|
unsigned long c; |
92 |
|
|
|
93 |
|
2547 |
r0 = st->r[0]; |
94 |
|
2547 |
r1 = st->r[1]; |
95 |
|
2547 |
r2 = st->r[2]; |
96 |
|
2547 |
r3 = st->r[3]; |
97 |
|
2547 |
r4 = st->r[4]; |
98 |
|
|
|
99 |
|
2547 |
s1 = r1 * 5; |
100 |
|
2547 |
s2 = r2 * 5; |
101 |
|
2547 |
s3 = r3 * 5; |
102 |
|
2547 |
s4 = r4 * 5; |
103 |
|
|
|
104 |
|
2547 |
h0 = st->h[0]; |
105 |
|
2547 |
h1 = st->h[1]; |
106 |
|
2547 |
h2 = st->h[2]; |
107 |
|
2547 |
h3 = st->h[3]; |
108 |
|
2547 |
h4 = st->h[4]; |
109 |
|
|
|
110 |
✓✓ |
21522 |
while (bytes >= poly1305_block_size) { |
111 |
|
|
/* h += m[i] */ |
112 |
|
8214 |
h0 += (U8TO32(m + 0)) & 0x3ffffff; |
113 |
|
8214 |
h1 += (U8TO32(m + 3) >> 2) & 0x3ffffff; |
114 |
|
8214 |
h2 += (U8TO32(m + 6) >> 4) & 0x3ffffff; |
115 |
|
8214 |
h3 += (U8TO32(m + 9) >> 6) & 0x3ffffff; |
116 |
|
8214 |
h4 += (U8TO32(m + 12) >> 8) | hibit; |
117 |
|
|
|
118 |
|
|
/* h *= r */ |
119 |
|
16428 |
d0 = ((unsigned long long)h0 * r0) + |
120 |
|
16428 |
((unsigned long long)h1 * s4) + |
121 |
|
16428 |
((unsigned long long)h2 * s3) + |
122 |
|
16428 |
((unsigned long long)h3 * s2) + |
123 |
|
8214 |
((unsigned long long)h4 * s1); |
124 |
|
16428 |
d1 = ((unsigned long long)h0 * r1) + |
125 |
|
16428 |
((unsigned long long)h1 * r0) + |
126 |
|
16428 |
((unsigned long long)h2 * s4) + |
127 |
|
16428 |
((unsigned long long)h3 * s3) + |
128 |
|
8214 |
((unsigned long long)h4 * s2); |
129 |
|
16428 |
d2 = ((unsigned long long)h0 * r2) + |
130 |
|
16428 |
((unsigned long long)h1 * r1) + |
131 |
|
16428 |
((unsigned long long)h2 * r0) + |
132 |
|
16428 |
((unsigned long long)h3 * s4) + |
133 |
|
8214 |
((unsigned long long)h4 * s3); |
134 |
|
16428 |
d3 = ((unsigned long long)h0 * r3) + |
135 |
|
16428 |
((unsigned long long)h1 * r2) + |
136 |
|
16428 |
((unsigned long long)h2 * r1) + |
137 |
|
16428 |
((unsigned long long)h3 * r0) + |
138 |
|
8214 |
((unsigned long long)h4 * s4); |
139 |
|
16428 |
d4 = ((unsigned long long)h0 * r4) + |
140 |
|
16428 |
((unsigned long long)h1 * r3) + |
141 |
|
16428 |
((unsigned long long)h2 * r2) + |
142 |
|
16428 |
((unsigned long long)h3 * r1) + |
143 |
|
8214 |
((unsigned long long)h4 * r0); |
144 |
|
|
|
145 |
|
|
/* (partial) h %= p */ |
146 |
|
8214 |
c = (unsigned long)(d0 >> 26); |
147 |
|
8214 |
h0 = (unsigned long)d0 & 0x3ffffff; |
148 |
|
8214 |
d1 += c; |
149 |
|
8214 |
c = (unsigned long)(d1 >> 26); |
150 |
|
8214 |
h1 = (unsigned long)d1 & 0x3ffffff; |
151 |
|
8214 |
d2 += c; |
152 |
|
8214 |
c = (unsigned long)(d2 >> 26); |
153 |
|
8214 |
h2 = (unsigned long)d2 & 0x3ffffff; |
154 |
|
8214 |
d3 += c; |
155 |
|
8214 |
c = (unsigned long)(d3 >> 26); |
156 |
|
8214 |
h3 = (unsigned long)d3 & 0x3ffffff; |
157 |
|
8214 |
d4 += c; |
158 |
|
8214 |
c = (unsigned long)(d4 >> 26); |
159 |
|
8214 |
h4 = (unsigned long)d4 & 0x3ffffff; |
160 |
|
8214 |
h0 += c * 5; |
161 |
|
8214 |
c = (h0 >> 26); |
162 |
|
8214 |
h0 = h0 & 0x3ffffff; |
163 |
|
8214 |
h1 += c; |
164 |
|
|
|
165 |
|
8214 |
m += poly1305_block_size; |
166 |
|
8214 |
bytes -= poly1305_block_size; |
167 |
|
|
} |
168 |
|
|
|
169 |
|
2547 |
st->h[0] = h0; |
170 |
|
2547 |
st->h[1] = h1; |
171 |
|
2547 |
st->h[2] = h2; |
172 |
|
2547 |
st->h[3] = h3; |
173 |
|
2547 |
st->h[4] = h4; |
174 |
|
2547 |
} |
175 |
|
|
|
176 |
|
|
static inline void |
177 |
|
|
poly1305_update(poly1305_context *ctx, const unsigned char *m, size_t bytes) |
178 |
|
|
{ |
179 |
|
4188 |
poly1305_state_internal_t *st = (poly1305_state_internal_t *)ctx; |
180 |
|
|
size_t i; |
181 |
|
|
|
182 |
|
|
/* handle leftover */ |
183 |
✓✓ |
2094 |
if (st->leftover) { |
184 |
|
249 |
size_t want = (poly1305_block_size - st->leftover); |
185 |
✓✓ |
249 |
if (want > bytes) |
186 |
|
15 |
want = bytes; |
187 |
✓✓ |
3654 |
for (i = 0; i < want; i++) |
188 |
|
1578 |
st->buffer[st->leftover + i] = m[i]; |
189 |
|
249 |
bytes -= want; |
190 |
|
249 |
m += want; |
191 |
|
249 |
st->leftover += want; |
192 |
✓✓ |
249 |
if (st->leftover < poly1305_block_size) |
193 |
|
15 |
return; |
194 |
|
234 |
poly1305_blocks(st, st->buffer, poly1305_block_size); |
195 |
|
234 |
st->leftover = 0; |
196 |
✓✓ |
234 |
} |
197 |
|
|
|
198 |
|
|
/* process full blocks */ |
199 |
✓✓ |
2079 |
if (bytes >= poly1305_block_size) { |
200 |
|
1587 |
size_t want = (bytes & ~(poly1305_block_size - 1)); |
201 |
|
1587 |
poly1305_blocks(st, m, want); |
202 |
|
1587 |
m += want; |
203 |
|
1587 |
bytes -= want; |
204 |
|
1587 |
} |
205 |
|
|
|
206 |
|
|
/* store leftover */ |
207 |
✓✓ |
2079 |
if (bytes) { |
208 |
✓✓ |
17808 |
for (i = 0; i < bytes; i++) |
209 |
|
7944 |
st->buffer[st->leftover + i] = m[i]; |
210 |
|
960 |
st->leftover += bytes; |
211 |
|
960 |
} |
212 |
|
4173 |
} |
213 |
|
|
|
214 |
|
|
static inline void |
215 |
|
|
poly1305_finish(poly1305_context *ctx, unsigned char mac[16]) |
216 |
|
|
{ |
217 |
|
1752 |
poly1305_state_internal_t *st = (poly1305_state_internal_t *)ctx; |
218 |
|
|
unsigned long h0, h1, h2, h3, h4, c; |
219 |
|
|
unsigned long g0, g1, g2, g3, g4; |
220 |
|
|
unsigned long long f; |
221 |
|
|
unsigned long mask; |
222 |
|
|
|
223 |
|
|
/* process the remaining block */ |
224 |
✓✓ |
876 |
if (st->leftover) { |
225 |
|
|
size_t i = st->leftover; |
226 |
|
726 |
st->buffer[i++] = 1; |
227 |
✓✓ |
11676 |
for (; i < poly1305_block_size; i++) |
228 |
|
5112 |
st->buffer[i] = 0; |
229 |
|
726 |
st->final = 1; |
230 |
|
726 |
poly1305_blocks(st, st->buffer, poly1305_block_size); |
231 |
|
726 |
} |
232 |
|
|
|
233 |
|
|
/* fully carry h */ |
234 |
|
876 |
h0 = st->h[0]; |
235 |
|
876 |
h1 = st->h[1]; |
236 |
|
876 |
h2 = st->h[2]; |
237 |
|
876 |
h3 = st->h[3]; |
238 |
|
876 |
h4 = st->h[4]; |
239 |
|
|
|
240 |
|
876 |
c = h1 >> 26; |
241 |
|
876 |
h1 = h1 & 0x3ffffff; |
242 |
|
876 |
h2 += c; |
243 |
|
876 |
c = h2 >> 26; |
244 |
|
876 |
h2 = h2 & 0x3ffffff; |
245 |
|
876 |
h3 += c; |
246 |
|
876 |
c = h3 >> 26; |
247 |
|
876 |
h3 = h3 & 0x3ffffff; |
248 |
|
876 |
h4 += c; |
249 |
|
876 |
c = h4 >> 26; |
250 |
|
876 |
h4 = h4 & 0x3ffffff; |
251 |
|
876 |
h0 += c * 5; |
252 |
|
876 |
c = h0 >> 26; |
253 |
|
876 |
h0 = h0 & 0x3ffffff; |
254 |
|
876 |
h1 += c; |
255 |
|
|
|
256 |
|
|
/* compute h + -p */ |
257 |
|
876 |
g0 = h0 + 5; |
258 |
|
876 |
c = g0 >> 26; |
259 |
|
876 |
g0 &= 0x3ffffff; |
260 |
|
876 |
g1 = h1 + c; |
261 |
|
876 |
c = g1 >> 26; |
262 |
|
876 |
g1 &= 0x3ffffff; |
263 |
|
876 |
g2 = h2 + c; |
264 |
|
876 |
c = g2 >> 26; |
265 |
|
876 |
g2 &= 0x3ffffff; |
266 |
|
876 |
g3 = h3 + c; |
267 |
|
876 |
c = g3 >> 26; |
268 |
|
876 |
g3 &= 0x3ffffff; |
269 |
|
876 |
g4 = h4 + c - (1 << 26); |
270 |
|
|
|
271 |
|
|
/* select h if h < p, or h + -p if h >= p */ |
272 |
|
876 |
mask = (g4 >> ((sizeof(unsigned long) * 8) - 1)) - 1; |
273 |
|
876 |
g0 &= mask; |
274 |
|
876 |
g1 &= mask; |
275 |
|
876 |
g2 &= mask; |
276 |
|
876 |
g3 &= mask; |
277 |
|
876 |
g4 &= mask; |
278 |
|
876 |
mask = ~mask; |
279 |
|
876 |
h0 = (h0 & mask) | g0; |
280 |
|
876 |
h1 = (h1 & mask) | g1; |
281 |
|
876 |
h2 = (h2 & mask) | g2; |
282 |
|
876 |
h3 = (h3 & mask) | g3; |
283 |
|
876 |
h4 = (h4 & mask) | g4; |
284 |
|
|
|
285 |
|
|
/* h = h % (2^128) */ |
286 |
|
876 |
h0 = ((h0) | (h1 << 26)) & 0xffffffff; |
287 |
|
876 |
h1 = ((h1 >> 6) | (h2 << 20)) & 0xffffffff; |
288 |
|
876 |
h2 = ((h2 >> 12) | (h3 << 14)) & 0xffffffff; |
289 |
|
876 |
h3 = ((h3 >> 18) | (h4 << 8)) & 0xffffffff; |
290 |
|
|
|
291 |
|
|
/* mac = (h + pad) % (2^128) */ |
292 |
|
876 |
f = (unsigned long long)h0 + st->pad[0]; |
293 |
|
|
h0 = (unsigned long)f; |
294 |
|
876 |
f = (unsigned long long)h1 + st->pad[1] + (f >> 32); |
295 |
|
|
h1 = (unsigned long)f; |
296 |
|
876 |
f = (unsigned long long)h2 + st->pad[2] + (f >> 32); |
297 |
|
|
h2 = (unsigned long)f; |
298 |
|
876 |
f = (unsigned long long)h3 + st->pad[3] + (f >> 32); |
299 |
|
|
h3 = (unsigned long)f; |
300 |
|
|
|
301 |
|
876 |
U32TO8(mac + 0, h0); |
302 |
|
876 |
U32TO8(mac + 4, h1); |
303 |
|
876 |
U32TO8(mac + 8, h2); |
304 |
|
876 |
U32TO8(mac + 12, h3); |
305 |
|
|
|
306 |
|
|
/* zero out the state */ |
307 |
|
876 |
st->h[0] = 0; |
308 |
|
876 |
st->h[1] = 0; |
309 |
|
876 |
st->h[2] = 0; |
310 |
|
876 |
st->h[3] = 0; |
311 |
|
876 |
st->h[4] = 0; |
312 |
|
876 |
st->r[0] = 0; |
313 |
|
876 |
st->r[1] = 0; |
314 |
|
876 |
st->r[2] = 0; |
315 |
|
876 |
st->r[3] = 0; |
316 |
|
876 |
st->r[4] = 0; |
317 |
|
876 |
st->pad[0] = 0; |
318 |
|
876 |
st->pad[1] = 0; |
319 |
|
876 |
st->pad[2] = 0; |
320 |
|
876 |
st->pad[3] = 0; |
321 |
|
876 |
} |