PolarSSL v1.2.11
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 /* Implementation that should never be optimized out by the compiler */
38 static void polarssl_zeroize( void *v, size_t n ) {
39  volatile unsigned char *p = v; while( n-- ) *p++ = 0;
40 }
41 
42 /*
43  * helper to validate the mpi size and import it
44  */
45 static int dhm_read_bignum( mpi *X,
46  unsigned char **p,
47  const unsigned char *end )
48 {
49  int ret, n;
50 
51  if( end - *p < 2 )
53 
54  n = ( (*p)[0] << 8 ) | (*p)[1];
55  (*p) += 2;
56 
57  if( (int)( end - *p ) < n )
59 
60  if( ( ret = mpi_read_binary( X, *p, n ) ) != 0 )
62 
63  (*p) += n;
64 
65  return( 0 );
66 }
67 
68 /*
69  * Verify sanity of parameter with regards to P
70  *
71  * Parameter should be: 2 <= public_param <= P - 2
72  *
73  * For more information on the attack, see:
74  * http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf
75  * http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2005-2643
76  */
77 static int dhm_check_range( const mpi *param, const mpi *P )
78 {
79  mpi L, U;
81 
82  mpi_init( &L ); mpi_init( &U );
83 
84  MPI_CHK( mpi_lset( &L, 2 ) );
85  MPI_CHK( mpi_sub_int( &U, P, 2 ) );
86 
87  if( mpi_cmp_mpi( param, &L ) >= 0 &&
88  mpi_cmp_mpi( param, &U ) <= 0 )
89  {
90  ret = 0;
91  }
92 
93 cleanup:
94  mpi_free( &L ); mpi_free( &U );
95  return( ret );
96 }
97 
98 /*
99  * Parse the ServerKeyExchange parameters
100  */
101 int dhm_read_params( dhm_context *ctx,
102  unsigned char **p,
103  const unsigned char *end )
104 {
105  int ret;
106 
107  memset( ctx, 0, sizeof( dhm_context ) );
108 
109  if( ( ret = dhm_read_bignum( &ctx->P, p, end ) ) != 0 ||
110  ( ret = dhm_read_bignum( &ctx->G, p, end ) ) != 0 ||
111  ( ret = dhm_read_bignum( &ctx->GY, p, end ) ) != 0 )
112  return( ret );
113 
114  if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
115  return( ret );
116 
117  ctx->len = mpi_size( &ctx->P );
118 
119  if( end - *p < 2 )
121 
122  return( 0 );
123 }
124 
125 /*
126  * Setup and write the ServerKeyExchange parameters
127  */
128 int dhm_make_params( dhm_context *ctx, int x_size,
129  unsigned char *output, size_t *olen,
130  int (*f_rng)(void *, unsigned char *, size_t),
131  void *p_rng )
132 {
133  int ret, count = 0;
134  size_t n1, n2, n3;
135  unsigned char *p;
136 
137  if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
139 
140  /*
141  * Generate X as large as possible ( < P )
142  */
143  do
144  {
145  mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
146 
147  while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
148  MPI_CHK( mpi_shift_r( &ctx->X, 1 ) );
149 
150  if( count++ > 10 )
152  }
153  while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
154 
155  /*
156  * Calculate GX = G^X mod P
157  */
158  MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
159  &ctx->P , &ctx->RP ) );
160 
161  if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
162  return( ret );
163 
164  /*
165  * export P, G, GX
166  */
167 #define DHM_MPI_EXPORT(X,n) \
168  MPI_CHK( mpi_write_binary( X, p + 2, n ) ); \
169  *p++ = (unsigned char)( n >> 8 ); \
170  *p++ = (unsigned char)( n ); p += n;
171 
172  n1 = mpi_size( &ctx->P );
173  n2 = mpi_size( &ctx->G );
174  n3 = mpi_size( &ctx->GX );
175 
176  p = output;
177  DHM_MPI_EXPORT( &ctx->P , n1 );
178  DHM_MPI_EXPORT( &ctx->G , n2 );
179  DHM_MPI_EXPORT( &ctx->GX, n3 );
180 
181  *olen = p - output;
182 
183  ctx->len = n1;
184 
185 cleanup:
186 
187  if( ret != 0 )
188  return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED + ret );
189 
190  return( 0 );
191 }
192 
193 /*
194  * Import the peer's public value G^Y
195  */
196 int dhm_read_public( dhm_context *ctx,
197  const unsigned char *input, size_t ilen )
198 {
199  int ret;
200 
201  if( ctx == NULL || ilen < 1 || ilen > ctx->len )
203 
204  if( ( ret = mpi_read_binary( &ctx->GY, input, ilen ) ) != 0 )
205  return( POLARSSL_ERR_DHM_READ_PUBLIC_FAILED + ret );
206 
207  return( 0 );
208 }
209 
210 /*
211  * Create own private value X and export G^X
212  */
213 int dhm_make_public( dhm_context *ctx, int x_size,
214  unsigned char *output, size_t olen,
215  int (*f_rng)(void *, unsigned char *, size_t),
216  void *p_rng )
217 {
218  int ret, count = 0;
219 
220  if( ctx == NULL || olen < 1 || olen > ctx->len )
222 
223  if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
225 
226  /*
227  * generate X and calculate GX = G^X mod P
228  */
229  do
230  {
231  mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
232 
233  while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
234  MPI_CHK( mpi_shift_r( &ctx->X, 1 ) );
235 
236  if( count++ > 10 )
238  }
239  while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
240 
241  MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
242  &ctx->P , &ctx->RP ) );
243 
244  if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
245  return( ret );
246 
247  MPI_CHK( mpi_write_binary( &ctx->GX, output, olen ) );
248 
249 cleanup:
250 
251  if( ret != 0 )
252  return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED + ret );
253 
254  return( 0 );
255 }
256 
257 /*
258  * Derive and export the shared secret (G^Y)^X mod P
259  */
260 int dhm_calc_secret( dhm_context *ctx,
261  unsigned char *output, size_t *olen )
262 {
263  int ret;
264 
265  if( ctx == NULL || *olen < ctx->len )
267 
268  MPI_CHK( mpi_exp_mod( &ctx->K, &ctx->GY, &ctx->X,
269  &ctx->P, &ctx->RP ) );
270 
271  if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
272  return( ret );
273 
274  *olen = mpi_size( &ctx->K );
275 
276  MPI_CHK( mpi_write_binary( &ctx->K, output, *olen ) );
277 
278 cleanup:
279 
280  if( ret != 0 )
281  return( POLARSSL_ERR_DHM_CALC_SECRET_FAILED + ret );
282 
283  return( 0 );
284 }
285 
286 /*
287  * Free the components of a DHM key
288  */
289 void dhm_free( dhm_context *ctx )
290 {
291  mpi_free( &ctx->RP ); mpi_free( &ctx->K ); mpi_free( &ctx->GY );
292  mpi_free( &ctx->GX ); mpi_free( &ctx->X ); mpi_free( &ctx->G );
293  mpi_free( &ctx->P );
294 
295  polarssl_zeroize( ctx, sizeof( dhm_context ) );
296 }
297 
298 #if defined(POLARSSL_SELF_TEST)
299 
300 /*
301  * Checkup routine
302  */
303 int dhm_self_test( int verbose )
304 {
305  return( verbose++ );
306 }
307 
308 #endif
309 
310 #endif