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)
mul64(uint32_t a,uint32_t b)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
mul64(uint32_t a,uint32_t b)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 */
poly1305_process(mbedtls_poly1305_context * ctx,size_t nblocks,const unsigned char * input,uint32_t needs_padding)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 */
poly1305_compute_mac(const mbedtls_poly1305_context * ctx,unsigned char mac[16])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
mbedtls_poly1305_init(mbedtls_poly1305_context * ctx)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
mbedtls_poly1305_free(mbedtls_poly1305_context * ctx)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
mbedtls_poly1305_starts(mbedtls_poly1305_context * ctx,const unsigned char key[32])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
mbedtls_poly1305_update(mbedtls_poly1305_context * ctx,const unsigned char * input,size_t ilen)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
mbedtls_poly1305_finish(mbedtls_poly1305_context * ctx,unsigned char mac[16])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
mbedtls_poly1305_mac(const unsigned char key[32],const unsigned char * input,size_t ilen,unsigned char mac[16])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
mbedtls_poly1305_self_test(int verbose)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