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