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