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