2 * Diffie-Hellman-Merkle key exchange
4 * Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
5 * SPDX-License-Identifier: Apache-2.0
7 * Licensed under the Apache License, Version 2.0 (the "License"); you may
8 * not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
11 * http://www.apache.org/licenses/LICENSE-2.0
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
15 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
19 * This file is part of mbed TLS (https://tls.mbed.org)
22 * The following sources were referenced in the design of this implementation
23 * of the Diffie-Hellman-Merkle algorithm:
25 * [1] Handbook of Applied Cryptography - 1997, Chapter 12
26 * Menezes, van Oorschot and Vanstone
30 #if !defined(MBEDTLS_CONFIG_FILE)
31 #include "mbedtls/config.h"
33 #include MBEDTLS_CONFIG_FILE
36 #if defined(MBEDTLS_DHM_C)
38 #include "mbedtls/dhm.h"
39 #include "mbedtls/platform_util.h"
43 #if defined(MBEDTLS_PEM_PARSE_C)
44 #include "mbedtls/pem.h"
47 #if defined(MBEDTLS_ASN1_PARSE_C)
48 #include "mbedtls/asn1.h"
51 #if defined(MBEDTLS_PLATFORM_C)
52 #include "mbedtls/platform.h"
56 #define mbedtls_printf printf
57 #define mbedtls_calloc calloc
58 #define mbedtls_free free
61 #if !defined(MBEDTLS_DHM_ALT)
63 #define DHM_VALIDATE_RET( cond ) \
64 MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_DHM_BAD_INPUT_DATA )
65 #define DHM_VALIDATE( cond ) \
66 MBEDTLS_INTERNAL_VALIDATE( cond )
69 * helper to validate the mbedtls_mpi size and import it
71 static int dhm_read_bignum( mbedtls_mpi *X,
73 const unsigned char *end )
78 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
80 n = ( (*p)[0] << 8 ) | (*p)[1];
83 if( (int)( end - *p ) < n )
84 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
86 if( ( ret = mbedtls_mpi_read_binary( X, *p, n ) ) != 0 )
87 return( MBEDTLS_ERR_DHM_READ_PARAMS_FAILED + ret );
95 * Verify sanity of parameter with regards to P
97 * Parameter should be: 2 <= public_param <= P - 2
99 * This means that we need to return an error if
100 * public_param < 2 or public_param > P-2
102 * For more information on the attack, see:
103 * http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf
104 * http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2005-2643
106 static int dhm_check_range( const mbedtls_mpi *param, const mbedtls_mpi *P )
111 mbedtls_mpi_init( &L ); mbedtls_mpi_init( &U );
113 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &L, 2 ) );
114 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &U, P, 2 ) );
116 if( mbedtls_mpi_cmp_mpi( param, &L ) < 0 ||
117 mbedtls_mpi_cmp_mpi( param, &U ) > 0 )
119 ret = MBEDTLS_ERR_DHM_BAD_INPUT_DATA;
123 mbedtls_mpi_free( &L ); mbedtls_mpi_free( &U );
127 void mbedtls_dhm_init( mbedtls_dhm_context *ctx )
129 DHM_VALIDATE( ctx != NULL );
130 memset( ctx, 0, sizeof( mbedtls_dhm_context ) );
134 * Parse the ServerKeyExchange parameters
136 int mbedtls_dhm_read_params( mbedtls_dhm_context *ctx,
138 const unsigned char *end )
141 DHM_VALIDATE_RET( ctx != NULL );
142 DHM_VALIDATE_RET( p != NULL && *p != NULL );
143 DHM_VALIDATE_RET( end != NULL );
145 if( ( ret = dhm_read_bignum( &ctx->P, p, end ) ) != 0 ||
146 ( ret = dhm_read_bignum( &ctx->G, p, end ) ) != 0 ||
147 ( ret = dhm_read_bignum( &ctx->GY, p, end ) ) != 0 )
150 if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
153 ctx->len = mbedtls_mpi_size( &ctx->P );
159 * Setup and write the ServerKeyExchange parameters
161 int mbedtls_dhm_make_params( mbedtls_dhm_context *ctx, int x_size,
162 unsigned char *output, size_t *olen,
163 int (*f_rng)(void *, unsigned char *, size_t),
169 DHM_VALIDATE_RET( ctx != NULL );
170 DHM_VALIDATE_RET( output != NULL );
171 DHM_VALIDATE_RET( olen != NULL );
172 DHM_VALIDATE_RET( f_rng != NULL );
174 if( mbedtls_mpi_cmp_int( &ctx->P, 0 ) == 0 )
175 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
178 * Generate X as large as possible ( < P )
182 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &ctx->X, x_size, f_rng, p_rng ) );
184 while( mbedtls_mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
185 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &ctx->X, 1 ) );
188 return( MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED );
190 while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
193 * Calculate GX = G^X mod P
195 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
196 &ctx->P , &ctx->RP ) );
198 if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
204 #define DHM_MPI_EXPORT( X, n ) \
206 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( ( X ), \
209 *p++ = (unsigned char)( ( n ) >> 8 ); \
210 *p++ = (unsigned char)( ( n ) ); \
214 n1 = mbedtls_mpi_size( &ctx->P );
215 n2 = mbedtls_mpi_size( &ctx->G );
216 n3 = mbedtls_mpi_size( &ctx->GX );
219 DHM_MPI_EXPORT( &ctx->P , n1 );
220 DHM_MPI_EXPORT( &ctx->G , n2 );
221 DHM_MPI_EXPORT( &ctx->GX, n3 );
230 return( MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED + ret );
236 * Set prime modulus and generator
238 int mbedtls_dhm_set_group( mbedtls_dhm_context *ctx,
239 const mbedtls_mpi *P,
240 const mbedtls_mpi *G )
243 DHM_VALIDATE_RET( ctx != NULL );
244 DHM_VALIDATE_RET( P != NULL );
245 DHM_VALIDATE_RET( G != NULL );
247 if( ( ret = mbedtls_mpi_copy( &ctx->P, P ) ) != 0 ||
248 ( ret = mbedtls_mpi_copy( &ctx->G, G ) ) != 0 )
250 return( MBEDTLS_ERR_DHM_SET_GROUP_FAILED + ret );
253 ctx->len = mbedtls_mpi_size( &ctx->P );
258 * Import the peer's public value G^Y
260 int mbedtls_dhm_read_public( mbedtls_dhm_context *ctx,
261 const unsigned char *input, size_t ilen )
264 DHM_VALIDATE_RET( ctx != NULL );
265 DHM_VALIDATE_RET( input != NULL );
267 if( ilen < 1 || ilen > ctx->len )
268 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
270 if( ( ret = mbedtls_mpi_read_binary( &ctx->GY, input, ilen ) ) != 0 )
271 return( MBEDTLS_ERR_DHM_READ_PUBLIC_FAILED + ret );
277 * Create own private value X and export G^X
279 int mbedtls_dhm_make_public( mbedtls_dhm_context *ctx, int x_size,
280 unsigned char *output, size_t olen,
281 int (*f_rng)(void *, unsigned char *, size_t),
285 DHM_VALIDATE_RET( ctx != NULL );
286 DHM_VALIDATE_RET( output != NULL );
287 DHM_VALIDATE_RET( f_rng != NULL );
289 if( olen < 1 || olen > ctx->len )
290 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
292 if( mbedtls_mpi_cmp_int( &ctx->P, 0 ) == 0 )
293 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
296 * generate X and calculate GX = G^X mod P
300 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &ctx->X, x_size, f_rng, p_rng ) );
302 while( mbedtls_mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
303 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &ctx->X, 1 ) );
306 return( MBEDTLS_ERR_DHM_MAKE_PUBLIC_FAILED );
308 while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
310 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
311 &ctx->P , &ctx->RP ) );
313 if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
316 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &ctx->GX, output, olen ) );
321 return( MBEDTLS_ERR_DHM_MAKE_PUBLIC_FAILED + ret );
327 * Use the blinding method and optimisation suggested in section 10 of:
328 * KOCHER, Paul C. Timing attacks on implementations of Diffie-Hellman, RSA,
329 * DSS, and other systems. In : Advances in Cryptology-CRYPTO'96. Springer
330 * Berlin Heidelberg, 1996. p. 104-113.
332 static int dhm_update_blinding( mbedtls_dhm_context *ctx,
333 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
338 * Don't use any blinding the first time a particular X is used,
339 * but remember it to use blinding next time.
341 if( mbedtls_mpi_cmp_mpi( &ctx->X, &ctx->pX ) != 0 )
343 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &ctx->pX, &ctx->X ) );
344 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &ctx->Vi, 1 ) );
345 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &ctx->Vf, 1 ) );
351 * Ok, we need blinding. Can we re-use existing values?
352 * If yes, just update them by squaring them.
354 if( mbedtls_mpi_cmp_int( &ctx->Vi, 1 ) != 0 )
356 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx->Vi, &ctx->Vi, &ctx->Vi ) );
357 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx->Vi, &ctx->Vi, &ctx->P ) );
359 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx->Vf, &ctx->Vf, &ctx->Vf ) );
360 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx->Vf, &ctx->Vf, &ctx->P ) );
366 * We need to generate blinding values from scratch
369 /* Vi = random( 2, P-1 ) */
373 MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &ctx->Vi, mbedtls_mpi_size( &ctx->P ), f_rng, p_rng ) );
375 while( mbedtls_mpi_cmp_mpi( &ctx->Vi, &ctx->P ) >= 0 )
376 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &ctx->Vi, 1 ) );
379 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE );
381 while( mbedtls_mpi_cmp_int( &ctx->Vi, 1 ) <= 0 );
383 /* Vf = Vi^-X mod P */
384 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &ctx->Vf, &ctx->Vi, &ctx->P ) );
385 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx->Vf, &ctx->Vf, &ctx->X, &ctx->P, &ctx->RP ) );
392 * Derive and export the shared secret (G^Y)^X mod P
394 int mbedtls_dhm_calc_secret( mbedtls_dhm_context *ctx,
395 unsigned char *output, size_t output_size, size_t *olen,
396 int (*f_rng)(void *, unsigned char *, size_t),
401 DHM_VALIDATE_RET( ctx != NULL );
402 DHM_VALIDATE_RET( output != NULL );
403 DHM_VALIDATE_RET( olen != NULL );
405 if( output_size < ctx->len )
406 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA );
408 if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
411 mbedtls_mpi_init( &GYb );
413 /* Blind peer's value */
416 MBEDTLS_MPI_CHK( dhm_update_blinding( ctx, f_rng, p_rng ) );
417 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &GYb, &ctx->GY, &ctx->Vi ) );
418 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &GYb, &GYb, &ctx->P ) );
421 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &GYb, &ctx->GY ) );
423 /* Do modular exponentiation */
424 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx->K, &GYb, &ctx->X,
425 &ctx->P, &ctx->RP ) );
427 /* Unblind secret value */
430 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx->K, &ctx->K, &ctx->Vf ) );
431 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx->K, &ctx->K, &ctx->P ) );
434 *olen = mbedtls_mpi_size( &ctx->K );
436 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &ctx->K, output, *olen ) );
439 mbedtls_mpi_free( &GYb );
442 return( MBEDTLS_ERR_DHM_CALC_SECRET_FAILED + ret );
448 * Free the components of a DHM key
450 void mbedtls_dhm_free( mbedtls_dhm_context *ctx )
455 mbedtls_mpi_free( &ctx->pX );
456 mbedtls_mpi_free( &ctx->Vf );
457 mbedtls_mpi_free( &ctx->Vi );
458 mbedtls_mpi_free( &ctx->RP );
459 mbedtls_mpi_free( &ctx->K );
460 mbedtls_mpi_free( &ctx->GY );
461 mbedtls_mpi_free( &ctx->GX );
462 mbedtls_mpi_free( &ctx->X );
463 mbedtls_mpi_free( &ctx->G );
464 mbedtls_mpi_free( &ctx->P );
466 mbedtls_platform_zeroize( ctx, sizeof( mbedtls_dhm_context ) );
469 #if defined(MBEDTLS_ASN1_PARSE_C)
471 * Parse DHM parameters
473 int mbedtls_dhm_parse_dhm( mbedtls_dhm_context *dhm, const unsigned char *dhmin,
478 unsigned char *p, *end;
479 #if defined(MBEDTLS_PEM_PARSE_C)
480 mbedtls_pem_context pem;
481 #endif /* MBEDTLS_PEM_PARSE_C */
483 DHM_VALIDATE_RET( dhm != NULL );
484 DHM_VALIDATE_RET( dhmin != NULL );
486 #if defined(MBEDTLS_PEM_PARSE_C)
487 mbedtls_pem_init( &pem );
489 /* Avoid calling mbedtls_pem_read_buffer() on non-null-terminated string */
490 if( dhminlen == 0 || dhmin[dhminlen - 1] != '\0' )
491 ret = MBEDTLS_ERR_PEM_NO_HEADER_FOOTER_PRESENT;
493 ret = mbedtls_pem_read_buffer( &pem,
494 "-----BEGIN DH PARAMETERS-----",
495 "-----END DH PARAMETERS-----",
496 dhmin, NULL, 0, &dhminlen );
503 dhminlen = pem.buflen;
505 else if( ret != MBEDTLS_ERR_PEM_NO_HEADER_FOOTER_PRESENT )
508 p = ( ret == 0 ) ? pem.buf : (unsigned char *) dhmin;
510 p = (unsigned char *) dhmin;
511 #endif /* MBEDTLS_PEM_PARSE_C */
515 * DHParams ::= SEQUENCE {
516 * prime INTEGER, -- P
517 * generator INTEGER, -- g
518 * privateValueLength INTEGER OPTIONAL
521 if( ( ret = mbedtls_asn1_get_tag( &p, end, &len,
522 MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) ) != 0 )
524 ret = MBEDTLS_ERR_DHM_INVALID_FORMAT + ret;
530 if( ( ret = mbedtls_asn1_get_mpi( &p, end, &dhm->P ) ) != 0 ||
531 ( ret = mbedtls_asn1_get_mpi( &p, end, &dhm->G ) ) != 0 )
533 ret = MBEDTLS_ERR_DHM_INVALID_FORMAT + ret;
539 /* This might be the optional privateValueLength.
540 * If so, we can cleanly discard it */
542 mbedtls_mpi_init( &rec );
543 ret = mbedtls_asn1_get_mpi( &p, end, &rec );
544 mbedtls_mpi_free( &rec );
547 ret = MBEDTLS_ERR_DHM_INVALID_FORMAT + ret;
552 ret = MBEDTLS_ERR_DHM_INVALID_FORMAT +
553 MBEDTLS_ERR_ASN1_LENGTH_MISMATCH;
560 dhm->len = mbedtls_mpi_size( &dhm->P );
563 #if defined(MBEDTLS_PEM_PARSE_C)
564 mbedtls_pem_free( &pem );
567 mbedtls_dhm_free( dhm );
572 #if defined(MBEDTLS_FS_IO)
574 * Load all data from a file into a given buffer.
576 * The file is expected to contain either PEM or DER encoded data.
577 * A terminating null byte is always appended. It is included in the announced
578 * length only if the data looks like it is PEM encoded.
580 static int load_file( const char *path, unsigned char **buf, size_t *n )
585 if( ( f = fopen( path, "rb" ) ) == NULL )
586 return( MBEDTLS_ERR_DHM_FILE_IO_ERROR );
588 fseek( f, 0, SEEK_END );
589 if( ( size = ftell( f ) ) == -1 )
592 return( MBEDTLS_ERR_DHM_FILE_IO_ERROR );
594 fseek( f, 0, SEEK_SET );
599 ( *buf = mbedtls_calloc( 1, *n + 1 ) ) == NULL )
602 return( MBEDTLS_ERR_DHM_ALLOC_FAILED );
605 if( fread( *buf, 1, *n, f ) != *n )
609 mbedtls_platform_zeroize( *buf, *n + 1 );
610 mbedtls_free( *buf );
612 return( MBEDTLS_ERR_DHM_FILE_IO_ERROR );
619 if( strstr( (const char *) *buf, "-----BEGIN " ) != NULL )
626 * Load and parse DHM parameters
628 int mbedtls_dhm_parse_dhmfile( mbedtls_dhm_context *dhm, const char *path )
633 DHM_VALIDATE_RET( dhm != NULL );
634 DHM_VALIDATE_RET( path != NULL );
636 if( ( ret = load_file( path, &buf, &n ) ) != 0 )
639 ret = mbedtls_dhm_parse_dhm( dhm, buf, n );
641 mbedtls_platform_zeroize( buf, n );
646 #endif /* MBEDTLS_FS_IO */
647 #endif /* MBEDTLS_ASN1_PARSE_C */
648 #endif /* MBEDTLS_DHM_ALT */
650 #if defined(MBEDTLS_SELF_TEST)
652 static const char mbedtls_test_dhm_params[] =
653 "-----BEGIN DH PARAMETERS-----\r\n"
654 "MIGHAoGBAJ419DBEOgmQTzo5qXl5fQcN9TN455wkOL7052HzxxRVMyhYmwQcgJvh\r\n"
655 "1sa18fyfR9OiVEMYglOpkqVoGLN7qd5aQNNi5W7/C+VBdHTBJcGZJyyP5B3qcz32\r\n"
656 "9mLJKudlVudV0Qxk5qUJaPZ/xupz0NyoVpviuiBOI1gNi8ovSXWzAgEC\r\n"
657 "-----END DH PARAMETERS-----\r\n";
659 static const size_t mbedtls_test_dhm_params_len = sizeof( mbedtls_test_dhm_params );
664 int mbedtls_dhm_self_test( int verbose )
667 mbedtls_dhm_context dhm;
669 mbedtls_dhm_init( &dhm );
672 mbedtls_printf( " DHM parameter load: " );
674 if( ( ret = mbedtls_dhm_parse_dhm( &dhm,
675 (const unsigned char *) mbedtls_test_dhm_params,
676 mbedtls_test_dhm_params_len ) ) != 0 )
679 mbedtls_printf( "failed\n" );
686 mbedtls_printf( "passed\n\n" );
689 mbedtls_dhm_free( &dhm );
694 #endif /* MBEDTLS_SELF_TEST */
696 #endif /* MBEDTLS_DHM_C */