1 /**
2 * \file poly1305.c
3 *
4 * \brief Poly1305 authentication algorithm.
5 *
6 * Copyright (C) 2006-2016, ARM Limited, All Rights Reserved
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 * 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)
mul64(uint32_t a,uint32_t b)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
mul64(uint32_t a,uint32_t b)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 */
poly1305_process(mbedtls_poly1305_context * ctx,size_t nblocks,const unsigned char * input,uint32_t needs_padding)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 */
poly1305_compute_mac(const mbedtls_poly1305_context * ctx,unsigned char mac[16])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
mbedtls_poly1305_init(mbedtls_poly1305_context * ctx)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
mbedtls_poly1305_free(mbedtls_poly1305_context * ctx)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
mbedtls_poly1305_starts(mbedtls_poly1305_context * ctx,const unsigned char key[32])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
mbedtls_poly1305_update(mbedtls_poly1305_context * ctx,const unsigned char * input,size_t ilen)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
mbedtls_poly1305_finish(mbedtls_poly1305_context * ctx,unsigned char mac[16])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
mbedtls_poly1305_mac(const unsigned char key[32],const unsigned char * input,size_t ilen,unsigned char mac[16])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
mbedtls_poly1305_self_test(int verbose)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