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