1 /**
2 * \file poly1305.c
3 *
4 * \brief Poly1305 authentication algorithm.
5 *
6 * Copyright The Mbed TLS Contributors
7 * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
8 */
9 #include "common.h"
10
11 #if defined(MBEDTLS_POLY1305_C)
12
13 #include "mbedtls/poly1305.h"
14 #include "mbedtls/platform_util.h"
15 #include "mbedtls/error.h"
16
17 #include <string.h>
18
19 #include "mbedtls/platform.h"
20
21 #if !defined(MBEDTLS_POLY1305_ALT)
22
23 /* Parameter validation macros */
24 #define POLY1305_VALIDATE_RET(cond) \
25 MBEDTLS_INTERNAL_VALIDATE_RET(cond, MBEDTLS_ERR_POLY1305_BAD_INPUT_DATA)
26 #define POLY1305_VALIDATE(cond) \
27 MBEDTLS_INTERNAL_VALIDATE(cond)
28
29 #define POLY1305_BLOCK_SIZE_BYTES (16U)
30
31 /*
32 * Our implementation is tuned for 32-bit platforms with a 64-bit multiplier.
33 * However we provided an alternative for platforms without such a multiplier.
34 */
35 #if defined(MBEDTLS_NO_64BIT_MULTIPLICATION)
mul64(uint32_t a,uint32_t b)36 static uint64_t mul64(uint32_t a, uint32_t b)
37 {
38 /* a = al + 2**16 ah, b = bl + 2**16 bh */
39 const uint16_t al = (uint16_t) a;
40 const uint16_t bl = (uint16_t) b;
41 const uint16_t ah = a >> 16;
42 const uint16_t bh = b >> 16;
43
44 /* ab = al*bl + 2**16 (ah*bl + bl*bh) + 2**32 ah*bh */
45 const uint32_t lo = (uint32_t) al * bl;
46 const uint64_t me = (uint64_t) ((uint32_t) ah * bl) + (uint32_t) al * bh;
47 const uint32_t hi = (uint32_t) ah * bh;
48
49 return lo + (me << 16) + ((uint64_t) hi << 32);
50 }
51 #else
mul64(uint32_t a,uint32_t b)52 static inline uint64_t mul64(uint32_t a, uint32_t b)
53 {
54 return (uint64_t) a * b;
55 }
56 #endif
57
58
59 /**
60 * \brief Process blocks with Poly1305.
61 *
62 * \param ctx The Poly1305 context.
63 * \param nblocks Number of blocks to process. Note that this
64 * function only processes full blocks.
65 * \param input Buffer containing the input block(s).
66 * \param needs_padding Set to 0 if the padding bit has already been
67 * applied to the input data before calling this
68 * function. Otherwise, set this parameter to 1.
69 */
poly1305_process(mbedtls_poly1305_context * ctx,size_t nblocks,const unsigned char * input,uint32_t needs_padding)70 static void poly1305_process(mbedtls_poly1305_context *ctx,
71 size_t nblocks,
72 const unsigned char *input,
73 uint32_t needs_padding)
74 {
75 uint64_t d0, d1, d2, d3;
76 uint32_t acc0, acc1, acc2, acc3, acc4;
77 uint32_t r0, r1, r2, r3;
78 uint32_t rs1, rs2, rs3;
79 size_t offset = 0U;
80 size_t i;
81
82 r0 = ctx->r[0];
83 r1 = ctx->r[1];
84 r2 = ctx->r[2];
85 r3 = ctx->r[3];
86
87 rs1 = r1 + (r1 >> 2U);
88 rs2 = r2 + (r2 >> 2U);
89 rs3 = r3 + (r3 >> 2U);
90
91 acc0 = ctx->acc[0];
92 acc1 = ctx->acc[1];
93 acc2 = ctx->acc[2];
94 acc3 = ctx->acc[3];
95 acc4 = ctx->acc[4];
96
97 /* Process full blocks */
98 for (i = 0U; i < nblocks; i++) {
99 /* The input block is treated as a 128-bit little-endian integer */
100 d0 = MBEDTLS_GET_UINT32_LE(input, offset + 0);
101 d1 = MBEDTLS_GET_UINT32_LE(input, offset + 4);
102 d2 = MBEDTLS_GET_UINT32_LE(input, offset + 8);
103 d3 = MBEDTLS_GET_UINT32_LE(input, offset + 12);
104
105 /* Compute: acc += (padded) block as a 130-bit integer */
106 d0 += (uint64_t) acc0;
107 d1 += (uint64_t) acc1 + (d0 >> 32U);
108 d2 += (uint64_t) acc2 + (d1 >> 32U);
109 d3 += (uint64_t) acc3 + (d2 >> 32U);
110 acc0 = (uint32_t) d0;
111 acc1 = (uint32_t) d1;
112 acc2 = (uint32_t) d2;
113 acc3 = (uint32_t) d3;
114 acc4 += (uint32_t) (d3 >> 32U) + needs_padding;
115
116 /* Compute: acc *= r */
117 d0 = mul64(acc0, r0) +
118 mul64(acc1, rs3) +
119 mul64(acc2, rs2) +
120 mul64(acc3, rs1);
121 d1 = mul64(acc0, r1) +
122 mul64(acc1, r0) +
123 mul64(acc2, rs3) +
124 mul64(acc3, rs2) +
125 mul64(acc4, rs1);
126 d2 = mul64(acc0, r2) +
127 mul64(acc1, r1) +
128 mul64(acc2, r0) +
129 mul64(acc3, rs3) +
130 mul64(acc4, rs2);
131 d3 = mul64(acc0, r3) +
132 mul64(acc1, r2) +
133 mul64(acc2, r1) +
134 mul64(acc3, r0) +
135 mul64(acc4, rs3);
136 acc4 *= r0;
137
138 /* Compute: acc %= (2^130 - 5) (partial remainder) */
139 d1 += (d0 >> 32);
140 d2 += (d1 >> 32);
141 d3 += (d2 >> 32);
142 acc0 = (uint32_t) d0;
143 acc1 = (uint32_t) d1;
144 acc2 = (uint32_t) d2;
145 acc3 = (uint32_t) d3;
146 acc4 = (uint32_t) (d3 >> 32) + acc4;
147
148 d0 = (uint64_t) acc0 + (acc4 >> 2) + (acc4 & 0xFFFFFFFCU);
149 acc4 &= 3U;
150 acc0 = (uint32_t) d0;
151 d0 = (uint64_t) acc1 + (d0 >> 32U);
152 acc1 = (uint32_t) d0;
153 d0 = (uint64_t) acc2 + (d0 >> 32U);
154 acc2 = (uint32_t) d0;
155 d0 = (uint64_t) acc3 + (d0 >> 32U);
156 acc3 = (uint32_t) d0;
157 d0 = (uint64_t) acc4 + (d0 >> 32U);
158 acc4 = (uint32_t) d0;
159
160 offset += POLY1305_BLOCK_SIZE_BYTES;
161 }
162
163 ctx->acc[0] = acc0;
164 ctx->acc[1] = acc1;
165 ctx->acc[2] = acc2;
166 ctx->acc[3] = acc3;
167 ctx->acc[4] = acc4;
168 }
169
170 /**
171 * \brief Compute the Poly1305 MAC
172 *
173 * \param ctx The Poly1305 context.
174 * \param mac The buffer to where the MAC is written. Must be
175 * big enough to contain the 16-byte MAC.
176 */
poly1305_compute_mac(const mbedtls_poly1305_context * ctx,unsigned char mac[16])177 static void poly1305_compute_mac(const mbedtls_poly1305_context *ctx,
178 unsigned char mac[16])
179 {
180 uint64_t d;
181 uint32_t g0, g1, g2, g3, g4;
182 uint32_t acc0, acc1, acc2, acc3, acc4;
183 uint32_t mask;
184 uint32_t mask_inv;
185
186 acc0 = ctx->acc[0];
187 acc1 = ctx->acc[1];
188 acc2 = ctx->acc[2];
189 acc3 = ctx->acc[3];
190 acc4 = ctx->acc[4];
191
192 /* Before adding 's' we ensure that the accumulator is mod 2^130 - 5.
193 * We do this by calculating acc - (2^130 - 5), then checking if
194 * the 131st bit is set. If it is, then reduce: acc -= (2^130 - 5)
195 */
196
197 /* Calculate acc + -(2^130 - 5) */
198 d = ((uint64_t) acc0 + 5U);
199 g0 = (uint32_t) d;
200 d = ((uint64_t) acc1 + (d >> 32));
201 g1 = (uint32_t) d;
202 d = ((uint64_t) acc2 + (d >> 32));
203 g2 = (uint32_t) d;
204 d = ((uint64_t) acc3 + (d >> 32));
205 g3 = (uint32_t) d;
206 g4 = acc4 + (uint32_t) (d >> 32U);
207
208 /* mask == 0xFFFFFFFF if 131st bit is set, otherwise mask == 0 */
209 mask = (uint32_t) 0U - (g4 >> 2U);
210 mask_inv = ~mask;
211
212 /* If 131st bit is set then acc=g, otherwise, acc is unmodified */
213 acc0 = (acc0 & mask_inv) | (g0 & mask);
214 acc1 = (acc1 & mask_inv) | (g1 & mask);
215 acc2 = (acc2 & mask_inv) | (g2 & mask);
216 acc3 = (acc3 & mask_inv) | (g3 & mask);
217
218 /* Add 's' */
219 d = (uint64_t) acc0 + ctx->s[0];
220 acc0 = (uint32_t) d;
221 d = (uint64_t) acc1 + ctx->s[1] + (d >> 32U);
222 acc1 = (uint32_t) d;
223 d = (uint64_t) acc2 + ctx->s[2] + (d >> 32U);
224 acc2 = (uint32_t) d;
225 acc3 += ctx->s[3] + (uint32_t) (d >> 32U);
226
227 /* Compute MAC (128 least significant bits of the accumulator) */
228 MBEDTLS_PUT_UINT32_LE(acc0, mac, 0);
229 MBEDTLS_PUT_UINT32_LE(acc1, mac, 4);
230 MBEDTLS_PUT_UINT32_LE(acc2, mac, 8);
231 MBEDTLS_PUT_UINT32_LE(acc3, mac, 12);
232 }
233
mbedtls_poly1305_init(mbedtls_poly1305_context * ctx)234 void mbedtls_poly1305_init(mbedtls_poly1305_context *ctx)
235 {
236 POLY1305_VALIDATE(ctx != NULL);
237
238 mbedtls_platform_zeroize(ctx, sizeof(mbedtls_poly1305_context));
239 }
240
mbedtls_poly1305_free(mbedtls_poly1305_context * ctx)241 void mbedtls_poly1305_free(mbedtls_poly1305_context *ctx)
242 {
243 if (ctx == NULL) {
244 return;
245 }
246
247 mbedtls_platform_zeroize(ctx, sizeof(mbedtls_poly1305_context));
248 }
249
mbedtls_poly1305_starts(mbedtls_poly1305_context * ctx,const unsigned char key[32])250 int mbedtls_poly1305_starts(mbedtls_poly1305_context *ctx,
251 const unsigned char key[32])
252 {
253 POLY1305_VALIDATE_RET(ctx != NULL);
254 POLY1305_VALIDATE_RET(key != NULL);
255
256 /* r &= 0x0ffffffc0ffffffc0ffffffc0fffffff */
257 ctx->r[0] = MBEDTLS_GET_UINT32_LE(key, 0) & 0x0FFFFFFFU;
258 ctx->r[1] = MBEDTLS_GET_UINT32_LE(key, 4) & 0x0FFFFFFCU;
259 ctx->r[2] = MBEDTLS_GET_UINT32_LE(key, 8) & 0x0FFFFFFCU;
260 ctx->r[3] = MBEDTLS_GET_UINT32_LE(key, 12) & 0x0FFFFFFCU;
261
262 ctx->s[0] = MBEDTLS_GET_UINT32_LE(key, 16);
263 ctx->s[1] = MBEDTLS_GET_UINT32_LE(key, 20);
264 ctx->s[2] = MBEDTLS_GET_UINT32_LE(key, 24);
265 ctx->s[3] = MBEDTLS_GET_UINT32_LE(key, 28);
266
267 /* Initial accumulator state */
268 ctx->acc[0] = 0U;
269 ctx->acc[1] = 0U;
270 ctx->acc[2] = 0U;
271 ctx->acc[3] = 0U;
272 ctx->acc[4] = 0U;
273
274 /* Queue initially empty */
275 mbedtls_platform_zeroize(ctx->queue, sizeof(ctx->queue));
276 ctx->queue_len = 0U;
277
278 return 0;
279 }
280
mbedtls_poly1305_update(mbedtls_poly1305_context * ctx,const unsigned char * input,size_t ilen)281 int mbedtls_poly1305_update(mbedtls_poly1305_context *ctx,
282 const unsigned char *input,
283 size_t ilen)
284 {
285 size_t offset = 0U;
286 size_t remaining = ilen;
287 size_t queue_free_len;
288 size_t nblocks;
289 POLY1305_VALIDATE_RET(ctx != NULL);
290 POLY1305_VALIDATE_RET(ilen == 0 || input != NULL);
291
292 if ((remaining > 0U) && (ctx->queue_len > 0U)) {
293 queue_free_len = (POLY1305_BLOCK_SIZE_BYTES - ctx->queue_len);
294
295 if (ilen < queue_free_len) {
296 /* Not enough data to complete the block.
297 * Store this data with the other leftovers.
298 */
299 memcpy(&ctx->queue[ctx->queue_len],
300 input,
301 ilen);
302
303 ctx->queue_len += ilen;
304
305 remaining = 0U;
306 } else {
307 /* Enough data to produce a complete block */
308 memcpy(&ctx->queue[ctx->queue_len],
309 input,
310 queue_free_len);
311
312 ctx->queue_len = 0U;
313
314 poly1305_process(ctx, 1U, ctx->queue, 1U); /* add padding bit */
315
316 offset += queue_free_len;
317 remaining -= queue_free_len;
318 }
319 }
320
321 if (remaining >= POLY1305_BLOCK_SIZE_BYTES) {
322 nblocks = remaining / POLY1305_BLOCK_SIZE_BYTES;
323
324 poly1305_process(ctx, nblocks, &input[offset], 1U);
325
326 offset += nblocks * POLY1305_BLOCK_SIZE_BYTES;
327 remaining %= POLY1305_BLOCK_SIZE_BYTES;
328 }
329
330 if (remaining > 0U) {
331 /* Store partial block */
332 ctx->queue_len = remaining;
333 memcpy(ctx->queue, &input[offset], remaining);
334 }
335
336 return 0;
337 }
338
mbedtls_poly1305_finish(mbedtls_poly1305_context * ctx,unsigned char mac[16])339 int mbedtls_poly1305_finish(mbedtls_poly1305_context *ctx,
340 unsigned char mac[16])
341 {
342 POLY1305_VALIDATE_RET(ctx != NULL);
343 POLY1305_VALIDATE_RET(mac != NULL);
344
345 /* Process any leftover data */
346 if (ctx->queue_len > 0U) {
347 /* Add padding bit */
348 ctx->queue[ctx->queue_len] = 1U;
349 ctx->queue_len++;
350
351 /* Pad with zeroes */
352 memset(&ctx->queue[ctx->queue_len],
353 0,
354 POLY1305_BLOCK_SIZE_BYTES - ctx->queue_len);
355
356 poly1305_process(ctx, 1U, /* Process 1 block */
357 ctx->queue, 0U); /* Already padded above */
358 }
359
360 poly1305_compute_mac(ctx, mac);
361
362 return 0;
363 }
364
mbedtls_poly1305_mac(const unsigned char key[32],const unsigned char * input,size_t ilen,unsigned char mac[16])365 int mbedtls_poly1305_mac(const unsigned char key[32],
366 const unsigned char *input,
367 size_t ilen,
368 unsigned char mac[16])
369 {
370 mbedtls_poly1305_context ctx;
371 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
372 POLY1305_VALIDATE_RET(key != NULL);
373 POLY1305_VALIDATE_RET(mac != NULL);
374 POLY1305_VALIDATE_RET(ilen == 0 || input != NULL);
375
376 mbedtls_poly1305_init(&ctx);
377
378 ret = mbedtls_poly1305_starts(&ctx, key);
379 if (ret != 0) {
380 goto cleanup;
381 }
382
383 ret = mbedtls_poly1305_update(&ctx, input, ilen);
384 if (ret != 0) {
385 goto cleanup;
386 }
387
388 ret = mbedtls_poly1305_finish(&ctx, mac);
389
390 cleanup:
391 mbedtls_poly1305_free(&ctx);
392 return ret;
393 }
394
395 #endif /* MBEDTLS_POLY1305_ALT */
396
397 #if defined(MBEDTLS_SELF_TEST)
398
399 static const unsigned char test_keys[2][32] =
400 {
401 {
402 0x85, 0xd6, 0xbe, 0x78, 0x57, 0x55, 0x6d, 0x33,
403 0x7f, 0x44, 0x52, 0xfe, 0x42, 0xd5, 0x06, 0xa8,
404 0x01, 0x03, 0x80, 0x8a, 0xfb, 0x0d, 0xb2, 0xfd,
405 0x4a, 0xbf, 0xf6, 0xaf, 0x41, 0x49, 0xf5, 0x1b
406 },
407 {
408 0x1c, 0x92, 0x40, 0xa5, 0xeb, 0x55, 0xd3, 0x8a,
409 0xf3, 0x33, 0x88, 0x86, 0x04, 0xf6, 0xb5, 0xf0,
410 0x47, 0x39, 0x17, 0xc1, 0x40, 0x2b, 0x80, 0x09,
411 0x9d, 0xca, 0x5c, 0xbc, 0x20, 0x70, 0x75, 0xc0
412 }
413 };
414
415 static const unsigned char test_data[2][127] =
416 {
417 {
418 0x43, 0x72, 0x79, 0x70, 0x74, 0x6f, 0x67, 0x72,
419 0x61, 0x70, 0x68, 0x69, 0x63, 0x20, 0x46, 0x6f,
420 0x72, 0x75, 0x6d, 0x20, 0x52, 0x65, 0x73, 0x65,
421 0x61, 0x72, 0x63, 0x68, 0x20, 0x47, 0x72, 0x6f,
422 0x75, 0x70
423 },
424 {
425 0x27, 0x54, 0x77, 0x61, 0x73, 0x20, 0x62, 0x72,
426 0x69, 0x6c, 0x6c, 0x69, 0x67, 0x2c, 0x20, 0x61,
427 0x6e, 0x64, 0x20, 0x74, 0x68, 0x65, 0x20, 0x73,
428 0x6c, 0x69, 0x74, 0x68, 0x79, 0x20, 0x74, 0x6f,
429 0x76, 0x65, 0x73, 0x0a, 0x44, 0x69, 0x64, 0x20,
430 0x67, 0x79, 0x72, 0x65, 0x20, 0x61, 0x6e, 0x64,
431 0x20, 0x67, 0x69, 0x6d, 0x62, 0x6c, 0x65, 0x20,
432 0x69, 0x6e, 0x20, 0x74, 0x68, 0x65, 0x20, 0x77,
433 0x61, 0x62, 0x65, 0x3a, 0x0a, 0x41, 0x6c, 0x6c,
434 0x20, 0x6d, 0x69, 0x6d, 0x73, 0x79, 0x20, 0x77,
435 0x65, 0x72, 0x65, 0x20, 0x74, 0x68, 0x65, 0x20,
436 0x62, 0x6f, 0x72, 0x6f, 0x67, 0x6f, 0x76, 0x65,
437 0x73, 0x2c, 0x0a, 0x41, 0x6e, 0x64, 0x20, 0x74,
438 0x68, 0x65, 0x20, 0x6d, 0x6f, 0x6d, 0x65, 0x20,
439 0x72, 0x61, 0x74, 0x68, 0x73, 0x20, 0x6f, 0x75,
440 0x74, 0x67, 0x72, 0x61, 0x62, 0x65, 0x2e
441 }
442 };
443
444 static const size_t test_data_len[2] =
445 {
446 34U,
447 127U
448 };
449
450 static const unsigned char test_mac[2][16] =
451 {
452 {
453 0xa8, 0x06, 0x1d, 0xc1, 0x30, 0x51, 0x36, 0xc6,
454 0xc2, 0x2b, 0x8b, 0xaf, 0x0c, 0x01, 0x27, 0xa9
455 },
456 {
457 0x45, 0x41, 0x66, 0x9a, 0x7e, 0xaa, 0xee, 0x61,
458 0xe7, 0x08, 0xdc, 0x7c, 0xbc, 0xc5, 0xeb, 0x62
459 }
460 };
461
462 /* Make sure no other definition is already present. */
463 #undef ASSERT
464
465 #define ASSERT(cond, args) \
466 do \
467 { \
468 if (!(cond)) \
469 { \
470 if (verbose != 0) \
471 mbedtls_printf args; \
472 \
473 return -1; \
474 } \
475 } \
476 while (0)
477
mbedtls_poly1305_self_test(int verbose)478 int mbedtls_poly1305_self_test(int verbose)
479 {
480 unsigned char mac[16];
481 unsigned i;
482 int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
483
484 for (i = 0U; i < 2U; i++) {
485 if (verbose != 0) {
486 mbedtls_printf(" Poly1305 test %u ", i);
487 }
488
489 ret = mbedtls_poly1305_mac(test_keys[i],
490 test_data[i],
491 test_data_len[i],
492 mac);
493 ASSERT(0 == ret, ("error code: %i\n", ret));
494
495 ASSERT(0 == memcmp(mac, test_mac[i], 16U), ("failed (mac)\n"));
496
497 if (verbose != 0) {
498 mbedtls_printf("passed\n");
499 }
500 }
501
502 if (verbose != 0) {
503 mbedtls_printf("\n");
504 }
505
506 return 0;
507 }
508
509 #endif /* MBEDTLS_SELF_TEST */
510
511 #endif /* MBEDTLS_POLY1305_C */
512