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