PolarSSL v1.3.4
dhm.c
Go to the documentation of this file.
1 /*
2  * Diffie-Hellman-Merkle key exchange
3  *
4  * Copyright (C) 2006-2010, Brainspark B.V.
5  *
6  * This file is part of PolarSSL (http://www.polarssl.org)
7  * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
8  *
9  * All rights reserved.
10  *
11  * This program is free software; you can redistribute it and/or modify
12  * it under the terms of the GNU General Public License as published by
13  * the Free Software Foundation; either version 2 of the License, or
14  * (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License along
22  * with this program; if not, write to the Free Software Foundation, Inc.,
23  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
24  */
25 /*
26  * Reference:
27  *
28  * http://www.cacr.math.uwaterloo.ca/hac/ (chapter 12)
29  */
30 
31 #include "polarssl/config.h"
32 
33 #if defined(POLARSSL_DHM_C)
34 
35 #include "polarssl/dhm.h"
36 
37 #if defined(POLARSSL_PEM_PARSE_C)
38 #include "polarssl/pem.h"
39 #endif
40 
41 #if defined(POLARSSL_ASN1_PARSE_C)
42 #include "polarssl/asn1.h"
43 #endif
44 
45 #if defined(POLARSSL_MEMORY_C)
46 #include "polarssl/memory.h"
47 #else
48 #include <stdlib.h>
49 #define polarssl_malloc malloc
50 #define polarssl_free free
51 #endif
52 
53 /*
54  * helper to validate the mpi size and import it
55  */
56 static int dhm_read_bignum( mpi *X,
57  unsigned char **p,
58  const unsigned char *end )
59 {
60  int ret, n;
61 
62  if( end - *p < 2 )
64 
65  n = ( (*p)[0] << 8 ) | (*p)[1];
66  (*p) += 2;
67 
68  if( (int)( end - *p ) < n )
70 
71  if( ( ret = mpi_read_binary( X, *p, n ) ) != 0 )
73 
74  (*p) += n;
75 
76  return( 0 );
77 }
78 
79 /*
80  * Verify sanity of parameter with regards to P
81  *
82  * Parameter should be: 2 <= public_param <= P - 2
83  *
84  * For more information on the attack, see:
85  * http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf
86  * http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2005-2643
87  */
88 static int dhm_check_range( const mpi *param, const mpi *P )
89 {
90  mpi L, U;
92 
93  mpi_init( &L ); mpi_init( &U );
94  mpi_lset( &L, 2 );
95  mpi_sub_int( &U, P, 2 );
96 
97  if( mpi_cmp_mpi( param, &L ) >= 0 &&
98  mpi_cmp_mpi( param, &U ) <= 0 )
99  {
100  ret = 0;
101  }
102 
103  mpi_free( &L ); mpi_free( &U );
104 
105  return( ret );
106 }
107 
108 /*
109  * Parse the ServerKeyExchange parameters
110  */
111 int dhm_read_params( dhm_context *ctx,
112  unsigned char **p,
113  const unsigned char *end )
114 {
115  int ret;
116 
117  dhm_free( ctx );
118 
119  if( ( ret = dhm_read_bignum( &ctx->P, p, end ) ) != 0 ||
120  ( ret = dhm_read_bignum( &ctx->G, p, end ) ) != 0 ||
121  ( ret = dhm_read_bignum( &ctx->GY, p, end ) ) != 0 )
122  return( ret );
123 
124  if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
125  return( ret );
126 
127  ctx->len = mpi_size( &ctx->P );
128 
129  return( 0 );
130 }
131 
132 /*
133  * Setup and write the ServerKeyExchange parameters
134  */
135 int dhm_make_params( dhm_context *ctx, int x_size,
136  unsigned char *output, size_t *olen,
137  int (*f_rng)(void *, unsigned char *, size_t),
138  void *p_rng )
139 {
140  int ret, count = 0;
141  size_t n1, n2, n3;
142  unsigned char *p;
143 
144  if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
146 
147  /*
148  * Generate X as large as possible ( < P )
149  */
150  do
151  {
152  mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
153 
154  while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
155  mpi_shift_r( &ctx->X, 1 );
156 
157  if( count++ > 10 )
159  }
160  while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
161 
162  /*
163  * Calculate GX = G^X mod P
164  */
165  MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
166  &ctx->P , &ctx->RP ) );
167 
168  if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
169  return( ret );
170 
171  /*
172  * export P, G, GX
173  */
174 #define DHM_MPI_EXPORT(X,n) \
175  MPI_CHK( mpi_write_binary( X, p + 2, n ) ); \
176  *p++ = (unsigned char)( n >> 8 ); \
177  *p++ = (unsigned char)( n ); p += n;
178 
179  n1 = mpi_size( &ctx->P );
180  n2 = mpi_size( &ctx->G );
181  n3 = mpi_size( &ctx->GX );
182 
183  p = output;
184  DHM_MPI_EXPORT( &ctx->P , n1 );
185  DHM_MPI_EXPORT( &ctx->G , n2 );
186  DHM_MPI_EXPORT( &ctx->GX, n3 );
187 
188  *olen = p - output;
189 
190  ctx->len = n1;
191 
192 cleanup:
193 
194  if( ret != 0 )
195  return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED + ret );
196 
197  return( 0 );
198 }
199 
200 /*
201  * Import the peer's public value G^Y
202  */
203 int dhm_read_public( dhm_context *ctx,
204  const unsigned char *input, size_t ilen )
205 {
206  int ret;
207 
208  if( ctx == NULL || ilen < 1 || ilen > ctx->len )
210 
211  if( ( ret = mpi_read_binary( &ctx->GY, input, ilen ) ) != 0 )
212  return( POLARSSL_ERR_DHM_READ_PUBLIC_FAILED + ret );
213 
214  return( 0 );
215 }
216 
217 /*
218  * Create own private value X and export G^X
219  */
220 int dhm_make_public( dhm_context *ctx, int x_size,
221  unsigned char *output, size_t olen,
222  int (*f_rng)(void *, unsigned char *, size_t),
223  void *p_rng )
224 {
225  int ret, count = 0;
226 
227  if( ctx == NULL || olen < 1 || olen > ctx->len )
229 
230  if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
232 
233  /*
234  * generate X and calculate GX = G^X mod P
235  */
236  do
237  {
238  mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
239 
240  while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
241  mpi_shift_r( &ctx->X, 1 );
242 
243  if( count++ > 10 )
245  }
246  while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
247 
248  MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
249  &ctx->P , &ctx->RP ) );
250 
251  if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
252  return( ret );
253 
254  MPI_CHK( mpi_write_binary( &ctx->GX, output, olen ) );
255 
256 cleanup:
257 
258  if( ret != 0 )
259  return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED + ret );
260 
261  return( 0 );
262 }
263 
264 /*
265  * Use the blinding method and optimisation suggested in section 10 of:
266  * KOCHER, Paul C. Timing attacks on implementations of Diffie-Hellman, RSA,
267  * DSS, and other systems. In : Advances in Cryptology—CRYPTO’96. Springer
268  * Berlin Heidelberg, 1996. p. 104-113.
269  */
270 static int dhm_update_blinding( dhm_context *ctx,
271  int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
272 {
273  int ret, count;
274 
275  /*
276  * Don't use any blinding the first time a particular X is used,
277  * but remember it to use blinding next time.
278  */
279  if( mpi_cmp_mpi( &ctx->X, &ctx->pX ) != 0 )
280  {
281  MPI_CHK( mpi_copy( &ctx->pX, &ctx->X ) );
282  MPI_CHK( mpi_lset( &ctx->Vi, 1 ) );
283  MPI_CHK( mpi_lset( &ctx->Vf, 1 ) );
284 
285  return( 0 );
286  }
287 
288  /*
289  * Ok, we need blinding. Can we re-use existing values?
290  * If yes, just update them by squaring them.
291  */
292  if( mpi_cmp_int( &ctx->Vi, 1 ) != 0 )
293  {
294  MPI_CHK( mpi_mul_mpi( &ctx->Vi, &ctx->Vi, &ctx->Vi ) );
295  MPI_CHK( mpi_mod_mpi( &ctx->Vi, &ctx->Vi, &ctx->P ) );
296 
297  MPI_CHK( mpi_mul_mpi( &ctx->Vf, &ctx->Vf, &ctx->Vf ) );
298  MPI_CHK( mpi_mod_mpi( &ctx->Vf, &ctx->Vf, &ctx->P ) );
299 
300  return( 0 );
301  }
302 
303  /*
304  * We need to generate blinding values from scratch
305  */
306 
307  /* Vi = random( 2, P-1 ) */
308  count = 0;
309  do
310  {
311  mpi_fill_random( &ctx->Vi, mpi_size( &ctx->P ), f_rng, p_rng );
312 
313  while( mpi_cmp_mpi( &ctx->Vi, &ctx->P ) >= 0 )
314  mpi_shift_r( &ctx->Vi, 1 );
315 
316  if( count++ > 10 )
318  }
319  while( mpi_cmp_int( &ctx->Vi, 1 ) <= 0 );
320 
321  /* Vf = Vi^-X mod P */
322  MPI_CHK( mpi_inv_mod( &ctx->Vf, &ctx->Vi, &ctx->P ) );
323  MPI_CHK( mpi_exp_mod( &ctx->Vf, &ctx->Vf, &ctx->X, &ctx->P, &ctx->RP ) );
324 
325 cleanup:
326  return( ret );
327 }
328 
329 /*
330  * Derive and export the shared secret (G^Y)^X mod P
331  */
332 int dhm_calc_secret( dhm_context *ctx,
333  unsigned char *output, size_t *olen,
334  int (*f_rng)(void *, unsigned char *, size_t),
335  void *p_rng )
336 {
337  int ret;
338  mpi GYb;
339 
340  if( ctx == NULL || *olen < ctx->len )
342 
343  if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
344  return( ret );
345 
346  mpi_init( &GYb );
347 
348  /* Blind peer's value */
349  if( f_rng != NULL )
350  {
351  MPI_CHK( dhm_update_blinding( ctx, f_rng, p_rng ) );
352  MPI_CHK( mpi_mul_mpi( &GYb, &ctx->GY, &ctx->Vi ) );
353  MPI_CHK( mpi_mod_mpi( &GYb, &GYb, &ctx->P ) );
354  }
355  else
356  MPI_CHK( mpi_copy( &GYb, &ctx->GY ) );
357 
358  /* Do modular exponentiation */
359  MPI_CHK( mpi_exp_mod( &ctx->K, &GYb, &ctx->X,
360  &ctx->P, &ctx->RP ) );
361 
362  /* Unblind secret value */
363  if( f_rng != NULL )
364  {
365  MPI_CHK( mpi_mul_mpi( &ctx->K, &ctx->K, &ctx->Vf ) );
366  MPI_CHK( mpi_mod_mpi( &ctx->K, &ctx->K, &ctx->P ) );
367  }
368 
369  *olen = mpi_size( &ctx->K );
370 
371  MPI_CHK( mpi_write_binary( &ctx->K, output, *olen ) );
372 
373 cleanup:
374  mpi_free( &GYb );
375 
376  if( ret != 0 )
377  return( POLARSSL_ERR_DHM_CALC_SECRET_FAILED + ret );
378 
379  return( 0 );
380 }
381 
382 /*
383  * Free the components of a DHM key
384  */
385 void dhm_free( dhm_context *ctx )
386 {
387  mpi_free( &ctx->pX); mpi_free( &ctx->Vf ); mpi_free( &ctx->Vi );
388  mpi_free( &ctx->RP ); mpi_free( &ctx->K ); mpi_free( &ctx->GY );
389  mpi_free( &ctx->GX ); mpi_free( &ctx->X ); mpi_free( &ctx->G );
390  mpi_free( &ctx->P );
391 
392  memset( ctx, 0, sizeof( dhm_context ) );
393 }
394 
395 #if defined(POLARSSL_ASN1_PARSE_C)
396 /*
397  * Parse DHM parameters
398  */
399 int dhm_parse_dhm( dhm_context *dhm, const unsigned char *dhmin, size_t dhminlen )
400 {
401  int ret;
402  size_t len;
403  unsigned char *p, *end;
404 #if defined(POLARSSL_PEM_PARSE_C)
405  pem_context pem;
406 
407  pem_init( &pem );
408  memset( dhm, 0, sizeof( dhm_context ) );
409 
410  ret = pem_read_buffer( &pem,
411  "-----BEGIN DH PARAMETERS-----",
412  "-----END DH PARAMETERS-----",
413  dhmin, NULL, 0, &dhminlen );
414 
415  if( ret == 0 )
416  {
417  /*
418  * Was PEM encoded
419  */
420  dhminlen = pem.buflen;
421  }
423  goto exit;
424 
425  p = ( ret == 0 ) ? pem.buf : (unsigned char *) dhmin;
426 #else
427  p = (unsigned char *) dhmin;
428 #endif
429  end = p + dhminlen;
430 
431  /*
432  * DHParams ::= SEQUENCE {
433  * prime INTEGER, -- P
434  * generator INTEGER, -- g
435  * }
436  */
437  if( ( ret = asn1_get_tag( &p, end, &len,
438  ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 )
439  {
441  goto exit;
442  }
443 
444  end = p + len;
445 
446  if( ( ret = asn1_get_mpi( &p, end, &dhm->P ) ) != 0 ||
447  ( ret = asn1_get_mpi( &p, end, &dhm->G ) ) != 0 )
448  {
450  goto exit;
451  }
452 
453  if( p != end )
454  {
457  goto exit;
458  }
459 
460  ret = 0;
461 
462 exit:
463 #if defined(POLARSSL_PEM_PARSE_C)
464  pem_free( &pem );
465 #endif
466  if( ret != 0 )
467  dhm_free( dhm );
468 
469  return( ret );
470 }
471 
472 #if defined(POLARSSL_FS_IO)
473 /*
474  * Load all data from a file into a given buffer.
475  */
476 static int load_file( const char *path, unsigned char **buf, size_t *n )
477 {
478  FILE *f;
479  long size;
480 
481  if( ( f = fopen( path, "rb" ) ) == NULL )
483 
484  fseek( f, 0, SEEK_END );
485  if( ( size = ftell( f ) ) == -1 )
486  {
487  fclose( f );
489  }
490  fseek( f, 0, SEEK_SET );
491 
492  *n = (size_t) size;
493 
494  if( *n + 1 == 0 ||
495  ( *buf = (unsigned char *) polarssl_malloc( *n + 1 ) ) == NULL )
496  {
497  fclose( f );
499  }
500 
501  if( fread( *buf, 1, *n, f ) != *n )
502  {
503  fclose( f );
504  polarssl_free( *buf );
506  }
507 
508  fclose( f );
509 
510  (*buf)[*n] = '\0';
511 
512  return( 0 );
513 }
514 
515 /*
516  * Load and parse DHM parameters
517  */
518 int dhm_parse_dhmfile( dhm_context *dhm, const char *path )
519 {
520  int ret;
521  size_t n;
522  unsigned char *buf;
523 
524  if ( ( ret = load_file( path, &buf, &n ) ) != 0 )
525  return( ret );
526 
527  ret = dhm_parse_dhm( dhm, buf, n );
528 
529  memset( buf, 0, n + 1 );
530  polarssl_free( buf );
531 
532  return( ret );
533 }
534 #endif /* POLARSSL_FS_IO */
535 #endif /* POLARSSL_ASN1_PARSE_C */
536 
537 #if defined(POLARSSL_SELF_TEST)
538 
539 #include "polarssl/certs.h"
540 
541 /*
542  * Checkup routine
543  */
544 int dhm_self_test( int verbose )
545 {
546 #if defined(POLARSSL_CERTS_C)
547  int ret;
548  dhm_context dhm;
549 
550  if( verbose != 0 )
551  printf( " DHM parameter load: " );
552 
553  if( ( ret = dhm_parse_dhm( &dhm, (const unsigned char *) test_dhm_params,
554  strlen( test_dhm_params ) ) ) != 0 )
555  {
556  if( verbose != 0 )
557  printf( "failed\n" );
558 
559  return( ret );
560  }
561 
562  if( verbose != 0 )
563  printf( "passed\n\n" );
564 
565  dhm_free( &dhm );
566 
567  return( 0 );
568 #else
569  ((void) verbose);
571 #endif
572 }
573 
574 #endif
575 
576 #endif
int mpi_cmp_int(const mpi *X, t_sint z)
Compare signed values.
#define POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED
Making of the public value failed.
Definition: dhm.h:39
mpi P
Definition: dhm.h:146
#define POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED
Making of the DHM parameters failed.
Definition: dhm.h:37
Memory allocation layer.
#define POLARSSL_ERR_DHM_INVALID_FORMAT
The ASN.1 data is not formatted correctly.
Definition: dhm.h:41
void *(* polarssl_malloc)(size_t len)
#define POLARSSL_ERR_ASN1_LENGTH_MISMATCH
Actual length differs from expected length.
Definition: asn1.h:53
DHM context structure.
Definition: dhm.h:143
#define POLARSSL_ERR_DHM_CALC_SECRET_FAILED
Calculation of the DHM secret failed.
Definition: dhm.h:40
int mpi_fill_random(mpi *X, size_t size, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Fill an MPI X with size bytes of random.
#define POLARSSL_ERR_DHM_MALLOC_FAILED
Allocation of memory failed.
Definition: dhm.h:42
int dhm_self_test(int verbose)
Checkup routine.
mpi GX
Definition: dhm.h:149
#define ASN1_SEQUENCE
Definition: asn1.h:78
Configuration options (set of defines)
mpi X
Definition: dhm.h:148
#define ASN1_CONSTRUCTED
Definition: asn1.h:88
int mpi_lset(mpi *X, t_sint z)
Set value from integer.
MPI structure.
Definition: bignum.h:177
void mpi_init(mpi *X)
Initialize one MPI.
int mpi_cmp_mpi(const mpi *X, const mpi *Y)
Compare signed values.
size_t len
Definition: dhm.h:145
int mpi_shift_r(mpi *X, size_t count)
Right-shift: X &gt;&gt;= count.
int dhm_read_params(dhm_context *ctx, unsigned char **p, const unsigned char *end)
Parse the ServerKeyExchange parameters.
Generic ASN.1 parsing.
#define POLARSSL_ERR_DHM_READ_PUBLIC_FAILED
Reading of the public values failed.
Definition: dhm.h:38
Privacy Enhanced Mail (PEM) decoding.
mpi G
Definition: dhm.h:147
#define POLARSSL_ERR_DHM_READ_PARAMS_FAILED
Reading of the DHM parameters failed.
Definition: dhm.h:36
void(* polarssl_free)(void *ptr)
int mpi_inv_mod(mpi *X, const mpi *A, const mpi *N)
Modular inverse: X = A^-1 mod N.
mpi GY
Definition: dhm.h:150
void mpi_free(mpi *X)
Unallocate one MPI.
Diffie-Hellman-Merkle key exchange.
int mpi_exp_mod(mpi *X, const mpi *A, const mpi *E, const mpi *N, mpi *_RR)
Sliding-window exponentiation: X = A^E mod N.
mpi K
Definition: dhm.h:151
mpi RP
Definition: dhm.h:152
int mpi_read_binary(mpi *X, const unsigned char *buf, size_t buflen)
Import X from unsigned binary data, big endian.
mpi Vi
Definition: dhm.h:153
Sample certificates and DHM parameters for testing.
int dhm_make_public(dhm_context *ctx, int x_size, unsigned char *output, size_t olen, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Create own private value X and export G^X.
size_t mpi_size(const mpi *X)
Return the total size in bytes.
#define POLARSSL_ERR_DHM_FILE_IO_ERROR
Read/write of file failed.
Definition: dhm.h:43
int mpi_copy(mpi *X, const mpi *Y)
Copy the contents of Y into X.
#define POLARSSL_ERR_X509_FEATURE_UNAVAILABLE
Unavailable feature, e.g.
Definition: x509.h:48
int mpi_mod_mpi(mpi *R, const mpi *A, const mpi *B)
Modulo: R = A mod B.
int asn1_get_tag(unsigned char **p, const unsigned char *end, size_t *len, int tag)
Get the tag and length of the tag.
int mpi_write_binary(const mpi *X, unsigned char *buf, size_t buflen)
Export X into unsigned binary data, big endian.
int dhm_parse_dhm(dhm_context *dhm, const unsigned char *dhmin, size_t dhminlen)
Parse DHM parameters.
void dhm_free(dhm_context *ctx)
Free the components of a DHM key.
#define POLARSSL_ERR_DHM_BAD_INPUT_DATA
Bad input parameters to function.
Definition: dhm.h:35
#define POLARSSL_ERR_PEM_NO_HEADER_FOOTER_PRESENT
No PEM header or footer found.
Definition: pem.h:38
int mpi_mul_mpi(mpi *X, const mpi *A, const mpi *B)
Baseline multiplication: X = A * B.
mpi pX
Definition: dhm.h:155
int asn1_get_mpi(unsigned char **p, const unsigned char *end, mpi *X)
Retrieve a MPI value from an integer ASN.1 tag.
int mpi_sub_int(mpi *X, const mpi *A, t_sint b)
Signed subtraction: X = A - b.
mpi Vf
Definition: dhm.h:154
int dhm_parse_dhmfile(dhm_context *dhm, const char *path)
Load and parse DHM parameters.
int dhm_make_params(dhm_context *ctx, int x_size, unsigned char *output, size_t *olen, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Setup and write the ServerKeyExchange parameters.
#define POLARSSL_ERR_MPI_NOT_ACCEPTABLE
The input arguments are not acceptable.
Definition: bignum.h:58
int dhm_read_public(dhm_context *ctx, const unsigned char *input, size_t ilen)
Import the peer&#39;s public value G^Y.
#define MPI_CHK(f)
Definition: bignum.h:61
int dhm_calc_secret(dhm_context *ctx, unsigned char *output, size_t *olen, int(*f_rng)(void *, unsigned char *, size_t), void *p_rng)
Derive and export the shared secret (G^Y)^X mod P.