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"
42 #if defined(MBEDTLS_PEM_PARSE_C)
43 #include "mbedtls/pem.h"
46 #if defined(MBEDTLS_ASN1_PARSE_C)
47 #include "mbedtls/asn1.h"
50 #if defined(MBEDTLS_PLATFORM_C)
51 #include "mbedtls/platform.h"
55 #define mbedtls_printf printf
56 #define mbedtls_calloc calloc
57 #define mbedtls_free free
60 /* Implementation that should never be optimized out by the compiler */
61 static void mbedtls_zeroize( void *v
, size_t n
) {
62 volatile unsigned char *p
= v
; while( n
-- ) *p
++ = 0;
66 * helper to validate the mbedtls_mpi size and import it
68 static int dhm_read_bignum( mbedtls_mpi
*X
,
70 const unsigned char *end
)
75 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA
);
77 n
= ( (*p
)[0] << 8 ) | (*p
)[1];
80 if( (int)( end
- *p
) < n
)
81 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA
);
83 if( ( ret
= mbedtls_mpi_read_binary( X
, *p
, n
) ) != 0 )
84 return( MBEDTLS_ERR_DHM_READ_PARAMS_FAILED
+ ret
);
92 * Verify sanity of parameter with regards to P
94 * Parameter should be: 2 <= public_param <= P - 2
96 * For more information on the attack, see:
97 * http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf
98 * http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2005-2643
100 static int dhm_check_range( const mbedtls_mpi
*param
, const mbedtls_mpi
*P
)
103 int ret
= MBEDTLS_ERR_DHM_BAD_INPUT_DATA
;
105 mbedtls_mpi_init( &L
); mbedtls_mpi_init( &U
);
107 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &L
, 2 ) );
108 MBEDTLS_MPI_CHK( mbedtls_mpi_sub_int( &U
, P
, 2 ) );
110 if( mbedtls_mpi_cmp_mpi( param
, &L
) >= 0 &&
111 mbedtls_mpi_cmp_mpi( param
, &U
) <= 0 )
117 mbedtls_mpi_free( &L
); mbedtls_mpi_free( &U
);
121 void mbedtls_dhm_init( mbedtls_dhm_context
*ctx
)
123 memset( ctx
, 0, sizeof( mbedtls_dhm_context
) );
127 * Parse the ServerKeyExchange parameters
129 int mbedtls_dhm_read_params( mbedtls_dhm_context
*ctx
,
131 const unsigned char *end
)
135 if( ( ret
= dhm_read_bignum( &ctx
->P
, p
, end
) ) != 0 ||
136 ( ret
= dhm_read_bignum( &ctx
->G
, p
, end
) ) != 0 ||
137 ( ret
= dhm_read_bignum( &ctx
->GY
, p
, end
) ) != 0 )
140 if( ( ret
= dhm_check_range( &ctx
->GY
, &ctx
->P
) ) != 0 )
143 ctx
->len
= mbedtls_mpi_size( &ctx
->P
);
149 * Setup and write the ServerKeyExchange parameters
151 int mbedtls_dhm_make_params( mbedtls_dhm_context
*ctx
, int x_size
,
152 unsigned char *output
, size_t *olen
,
153 int (*f_rng
)(void *, unsigned char *, size_t),
160 if( mbedtls_mpi_cmp_int( &ctx
->P
, 0 ) == 0 )
161 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA
);
164 * Generate X as large as possible ( < P )
168 mbedtls_mpi_fill_random( &ctx
->X
, x_size
, f_rng
, p_rng
);
170 while( mbedtls_mpi_cmp_mpi( &ctx
->X
, &ctx
->P
) >= 0 )
171 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &ctx
->X
, 1 ) );
174 return( MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED
);
176 while( dhm_check_range( &ctx
->X
, &ctx
->P
) != 0 );
179 * Calculate GX = G^X mod P
181 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx
->GX
, &ctx
->G
, &ctx
->X
,
182 &ctx
->P
, &ctx
->RP
) );
184 if( ( ret
= dhm_check_range( &ctx
->GX
, &ctx
->P
) ) != 0 )
190 #define DHM_MPI_EXPORT(X,n) \
191 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( X, p + 2, n ) ); \
192 *p++ = (unsigned char)( n >> 8 ); \
193 *p++ = (unsigned char)( n ); p += n;
195 n1
= mbedtls_mpi_size( &ctx
->P
);
196 n2
= mbedtls_mpi_size( &ctx
->G
);
197 n3
= mbedtls_mpi_size( &ctx
->GX
);
200 DHM_MPI_EXPORT( &ctx
->P
, n1
);
201 DHM_MPI_EXPORT( &ctx
->G
, n2
);
202 DHM_MPI_EXPORT( &ctx
->GX
, n3
);
211 return( MBEDTLS_ERR_DHM_MAKE_PARAMS_FAILED
+ ret
);
217 * Import the peer's public value G^Y
219 int mbedtls_dhm_read_public( mbedtls_dhm_context
*ctx
,
220 const unsigned char *input
, size_t ilen
)
224 if( ctx
== NULL
|| ilen
< 1 || ilen
> ctx
->len
)
225 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA
);
227 if( ( ret
= mbedtls_mpi_read_binary( &ctx
->GY
, input
, ilen
) ) != 0 )
228 return( MBEDTLS_ERR_DHM_READ_PUBLIC_FAILED
+ ret
);
234 * Create own private value X and export G^X
236 int mbedtls_dhm_make_public( mbedtls_dhm_context
*ctx
, int x_size
,
237 unsigned char *output
, size_t olen
,
238 int (*f_rng
)(void *, unsigned char *, size_t),
243 if( ctx
== NULL
|| olen
< 1 || olen
> ctx
->len
)
244 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA
);
246 if( mbedtls_mpi_cmp_int( &ctx
->P
, 0 ) == 0 )
247 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA
);
250 * generate X and calculate GX = G^X mod P
254 mbedtls_mpi_fill_random( &ctx
->X
, x_size
, f_rng
, p_rng
);
256 while( mbedtls_mpi_cmp_mpi( &ctx
->X
, &ctx
->P
) >= 0 )
257 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &ctx
->X
, 1 ) );
260 return( MBEDTLS_ERR_DHM_MAKE_PUBLIC_FAILED
);
262 while( dhm_check_range( &ctx
->X
, &ctx
->P
) != 0 );
264 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx
->GX
, &ctx
->G
, &ctx
->X
,
265 &ctx
->P
, &ctx
->RP
) );
267 if( ( ret
= dhm_check_range( &ctx
->GX
, &ctx
->P
) ) != 0 )
270 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &ctx
->GX
, output
, olen
) );
275 return( MBEDTLS_ERR_DHM_MAKE_PUBLIC_FAILED
+ ret
);
281 * Use the blinding method and optimisation suggested in section 10 of:
282 * KOCHER, Paul C. Timing attacks on implementations of Diffie-Hellman, RSA,
283 * DSS, and other systems. In : Advances in Cryptology-CRYPTO'96. Springer
284 * Berlin Heidelberg, 1996. p. 104-113.
286 static int dhm_update_blinding( mbedtls_dhm_context
*ctx
,
287 int (*f_rng
)(void *, unsigned char *, size_t), void *p_rng
)
292 * Don't use any blinding the first time a particular X is used,
293 * but remember it to use blinding next time.
295 if( mbedtls_mpi_cmp_mpi( &ctx
->X
, &ctx
->pX
) != 0 )
297 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &ctx
->pX
, &ctx
->X
) );
298 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &ctx
->Vi
, 1 ) );
299 MBEDTLS_MPI_CHK( mbedtls_mpi_lset( &ctx
->Vf
, 1 ) );
305 * Ok, we need blinding. Can we re-use existing values?
306 * If yes, just update them by squaring them.
308 if( mbedtls_mpi_cmp_int( &ctx
->Vi
, 1 ) != 0 )
310 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx
->Vi
, &ctx
->Vi
, &ctx
->Vi
) );
311 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx
->Vi
, &ctx
->Vi
, &ctx
->P
) );
313 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx
->Vf
, &ctx
->Vf
, &ctx
->Vf
) );
314 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx
->Vf
, &ctx
->Vf
, &ctx
->P
) );
320 * We need to generate blinding values from scratch
323 /* Vi = random( 2, P-1 ) */
327 mbedtls_mpi_fill_random( &ctx
->Vi
, mbedtls_mpi_size( &ctx
->P
), f_rng
, p_rng
);
329 while( mbedtls_mpi_cmp_mpi( &ctx
->Vi
, &ctx
->P
) >= 0 )
330 MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &ctx
->Vi
, 1 ) );
333 return( MBEDTLS_ERR_MPI_NOT_ACCEPTABLE
);
335 while( mbedtls_mpi_cmp_int( &ctx
->Vi
, 1 ) <= 0 );
337 /* Vf = Vi^-X mod P */
338 MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &ctx
->Vf
, &ctx
->Vi
, &ctx
->P
) );
339 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx
->Vf
, &ctx
->Vf
, &ctx
->X
, &ctx
->P
, &ctx
->RP
) );
346 * Derive and export the shared secret (G^Y)^X mod P
348 int mbedtls_dhm_calc_secret( mbedtls_dhm_context
*ctx
,
349 unsigned char *output
, size_t output_size
, size_t *olen
,
350 int (*f_rng
)(void *, unsigned char *, size_t),
356 if( ctx
== NULL
|| output_size
< ctx
->len
)
357 return( MBEDTLS_ERR_DHM_BAD_INPUT_DATA
);
359 if( ( ret
= dhm_check_range( &ctx
->GY
, &ctx
->P
) ) != 0 )
362 mbedtls_mpi_init( &GYb
);
364 /* Blind peer's value */
367 MBEDTLS_MPI_CHK( dhm_update_blinding( ctx
, f_rng
, p_rng
) );
368 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &GYb
, &ctx
->GY
, &ctx
->Vi
) );
369 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &GYb
, &GYb
, &ctx
->P
) );
372 MBEDTLS_MPI_CHK( mbedtls_mpi_copy( &GYb
, &ctx
->GY
) );
374 /* Do modular exponentiation */
375 MBEDTLS_MPI_CHK( mbedtls_mpi_exp_mod( &ctx
->K
, &GYb
, &ctx
->X
,
376 &ctx
->P
, &ctx
->RP
) );
378 /* Unblind secret value */
381 MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &ctx
->K
, &ctx
->K
, &ctx
->Vf
) );
382 MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &ctx
->K
, &ctx
->K
, &ctx
->P
) );
385 *olen
= mbedtls_mpi_size( &ctx
->K
);
387 MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &ctx
->K
, output
, *olen
) );
390 mbedtls_mpi_free( &GYb
);
393 return( MBEDTLS_ERR_DHM_CALC_SECRET_FAILED
+ ret
);
399 * Free the components of a DHM key
401 void mbedtls_dhm_free( mbedtls_dhm_context
*ctx
)
403 mbedtls_mpi_free( &ctx
->pX
); mbedtls_mpi_free( &ctx
->Vf
); mbedtls_mpi_free( &ctx
->Vi
);
404 mbedtls_mpi_free( &ctx
->RP
); mbedtls_mpi_free( &ctx
->K
); mbedtls_mpi_free( &ctx
->GY
);
405 mbedtls_mpi_free( &ctx
->GX
); mbedtls_mpi_free( &ctx
->X
); mbedtls_mpi_free( &ctx
->G
);
406 mbedtls_mpi_free( &ctx
->P
);
408 mbedtls_zeroize( ctx
, sizeof( mbedtls_dhm_context
) );
411 #if defined(MBEDTLS_ASN1_PARSE_C)
413 * Parse DHM parameters
415 int mbedtls_dhm_parse_dhm( mbedtls_dhm_context
*dhm
, const unsigned char *dhmin
,
420 unsigned char *p
, *end
;
421 #if defined(MBEDTLS_PEM_PARSE_C)
422 mbedtls_pem_context pem
;
424 mbedtls_pem_init( &pem
);
426 /* Avoid calling mbedtls_pem_read_buffer() on non-null-terminated string */
427 if( dhminlen
== 0 || dhmin
[dhminlen
- 1] != '\0' )
428 ret
= MBEDTLS_ERR_PEM_NO_HEADER_FOOTER_PRESENT
;
430 ret
= mbedtls_pem_read_buffer( &pem
,
431 "-----BEGIN DH PARAMETERS-----",
432 "-----END DH PARAMETERS-----",
433 dhmin
, NULL
, 0, &dhminlen
);
440 dhminlen
= pem
.buflen
;
442 else if( ret
!= MBEDTLS_ERR_PEM_NO_HEADER_FOOTER_PRESENT
)
445 p
= ( ret
== 0 ) ? pem
.buf
: (unsigned char *) dhmin
;
447 p
= (unsigned char *) dhmin
;
448 #endif /* MBEDTLS_PEM_PARSE_C */
452 * DHParams ::= SEQUENCE {
453 * prime INTEGER, -- P
454 * generator INTEGER, -- g
455 * privateValueLength INTEGER OPTIONAL
458 if( ( ret
= mbedtls_asn1_get_tag( &p
, end
, &len
,
459 MBEDTLS_ASN1_CONSTRUCTED
| MBEDTLS_ASN1_SEQUENCE
) ) != 0 )
461 ret
= MBEDTLS_ERR_DHM_INVALID_FORMAT
+ ret
;
467 if( ( ret
= mbedtls_asn1_get_mpi( &p
, end
, &dhm
->P
) ) != 0 ||
468 ( ret
= mbedtls_asn1_get_mpi( &p
, end
, &dhm
->G
) ) != 0 )
470 ret
= MBEDTLS_ERR_DHM_INVALID_FORMAT
+ ret
;
476 /* This might be the optional privateValueLength.
477 * If so, we can cleanly discard it */
479 mbedtls_mpi_init( &rec
);
480 ret
= mbedtls_asn1_get_mpi( &p
, end
, &rec
);
481 mbedtls_mpi_free( &rec
);
484 ret
= MBEDTLS_ERR_DHM_INVALID_FORMAT
+ ret
;
489 ret
= MBEDTLS_ERR_DHM_INVALID_FORMAT
+
490 MBEDTLS_ERR_ASN1_LENGTH_MISMATCH
;
497 dhm
->len
= mbedtls_mpi_size( &dhm
->P
);
500 #if defined(MBEDTLS_PEM_PARSE_C)
501 mbedtls_pem_free( &pem
);
504 mbedtls_dhm_free( dhm
);
509 #if defined(MBEDTLS_FS_IO)
511 * Load all data from a file into a given buffer.
513 * The file is expected to contain either PEM or DER encoded data.
514 * A terminating null byte is always appended. It is included in the announced
515 * length only if the data looks like it is PEM encoded.
517 static int load_file( const char *path
, unsigned char **buf
, size_t *n
)
522 if( ( f
= fopen( path
, "rb" ) ) == NULL
)
523 return( MBEDTLS_ERR_DHM_FILE_IO_ERROR
);
525 fseek( f
, 0, SEEK_END
);
526 if( ( size
= ftell( f
) ) == -1 )
529 return( MBEDTLS_ERR_DHM_FILE_IO_ERROR
);
531 fseek( f
, 0, SEEK_SET
);
536 ( *buf
= mbedtls_calloc( 1, *n
+ 1 ) ) == NULL
)
539 return( MBEDTLS_ERR_DHM_ALLOC_FAILED
);
542 if( fread( *buf
, 1, *n
, f
) != *n
)
545 mbedtls_free( *buf
);
546 return( MBEDTLS_ERR_DHM_FILE_IO_ERROR
);
553 if( strstr( (const char *) *buf
, "-----BEGIN " ) != NULL
)
560 * Load and parse DHM parameters
562 int mbedtls_dhm_parse_dhmfile( mbedtls_dhm_context
*dhm
, const char *path
)
568 if( ( ret
= load_file( path
, &buf
, &n
) ) != 0 )
571 ret
= mbedtls_dhm_parse_dhm( dhm
, buf
, n
);
573 mbedtls_zeroize( buf
, n
);
578 #endif /* MBEDTLS_FS_IO */
579 #endif /* MBEDTLS_ASN1_PARSE_C */
581 #if defined(MBEDTLS_SELF_TEST)
583 static const char mbedtls_test_dhm_params
[] =
584 "-----BEGIN DH PARAMETERS-----\r\n"
585 "MIGHAoGBAJ419DBEOgmQTzo5qXl5fQcN9TN455wkOL7052HzxxRVMyhYmwQcgJvh\r\n"
586 "1sa18fyfR9OiVEMYglOpkqVoGLN7qd5aQNNi5W7/C+VBdHTBJcGZJyyP5B3qcz32\r\n"
587 "9mLJKudlVudV0Qxk5qUJaPZ/xupz0NyoVpviuiBOI1gNi8ovSXWzAgEC\r\n"
588 "-----END DH PARAMETERS-----\r\n";
590 static const size_t mbedtls_test_dhm_params_len
= sizeof( mbedtls_test_dhm_params
);
595 int mbedtls_dhm_self_test( int verbose
)
598 mbedtls_dhm_context dhm
;
600 mbedtls_dhm_init( &dhm
);
603 mbedtls_printf( " DHM parameter load: " );
605 if( ( ret
= mbedtls_dhm_parse_dhm( &dhm
,
606 (const unsigned char *) mbedtls_test_dhm_params
,
607 mbedtls_test_dhm_params_len
) ) != 0 )
610 mbedtls_printf( "failed\n" );
617 mbedtls_printf( "passed\n\n" );
620 mbedtls_dhm_free( &dhm
);
625 #endif /* MBEDTLS_SELF_TEST */
627 #endif /* MBEDTLS_DHM_C */