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