PolarSSL v1.1.4
|
00001 /* 00002 * Diffie-Hellman-Merkle key exchange 00003 * 00004 * Copyright (C) 2006-2010, Brainspark B.V. 00005 * 00006 * This file is part of PolarSSL (http://www.polarssl.org) 00007 * Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org> 00008 * 00009 * All rights reserved. 00010 * 00011 * This program is free software; you can redistribute it and/or modify 00012 * it under the terms of the GNU General Public License as published by 00013 * the Free Software Foundation; either version 2 of the License, or 00014 * (at your option) any later version. 00015 * 00016 * This program is distributed in the hope that it will be useful, 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00019 * GNU General Public License for more details. 00020 * 00021 * You should have received a copy of the GNU General Public License along 00022 * with this program; if not, write to the Free Software Foundation, Inc., 00023 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. 00024 */ 00025 /* 00026 * Reference: 00027 * 00028 * http://www.cacr.math.uwaterloo.ca/hac/ (chapter 12) 00029 */ 00030 00031 #include "polarssl/config.h" 00032 00033 #if defined(POLARSSL_DHM_C) 00034 00035 #include "polarssl/dhm.h" 00036 00037 /* 00038 * helper to validate the mpi size and import it 00039 */ 00040 static int dhm_read_bignum( mpi *X, 00041 unsigned char **p, 00042 const unsigned char *end ) 00043 { 00044 int ret, n; 00045 00046 if( end - *p < 2 ) 00047 return( POLARSSL_ERR_DHM_BAD_INPUT_DATA ); 00048 00049 n = ( (*p)[0] << 8 ) | (*p)[1]; 00050 (*p) += 2; 00051 00052 if( (int)( end - *p ) < n ) 00053 return( POLARSSL_ERR_DHM_BAD_INPUT_DATA ); 00054 00055 if( ( ret = mpi_read_binary( X, *p, n ) ) != 0 ) 00056 return( POLARSSL_ERR_DHM_READ_PARAMS_FAILED + ret ); 00057 00058 (*p) += n; 00059 00060 return( 0 ); 00061 } 00062 00063 /* 00064 * Verify sanity of parameter with regards to P 00065 * 00066 * Parameter should be: 2 <= public_param <= P - 2 00067 * 00068 * For more information on the attack, see: 00069 * http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf 00070 * http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2005-2643 00071 */ 00072 static int dhm_check_range( const mpi *param, const mpi *P ) 00073 { 00074 mpi L, U; 00075 int ret = POLARSSL_ERR_DHM_BAD_INPUT_DATA; 00076 00077 mpi_init( &L ); mpi_init( &U ); 00078 mpi_lset( &L, 2 ); 00079 mpi_sub_int( &U, P, 2 ); 00080 00081 if( mpi_cmp_mpi( param, &L ) >= 0 && 00082 mpi_cmp_mpi( param, &U ) <= 0 ) 00083 { 00084 ret = 0; 00085 } 00086 00087 mpi_free( &L ); mpi_free( &U ); 00088 00089 return( ret ); 00090 } 00091 00092 /* 00093 * Parse the ServerKeyExchange parameters 00094 */ 00095 int dhm_read_params( dhm_context *ctx, 00096 unsigned char **p, 00097 const unsigned char *end ) 00098 { 00099 int ret, n; 00100 00101 memset( ctx, 0, sizeof( dhm_context ) ); 00102 00103 if( ( ret = dhm_read_bignum( &ctx->P, p, end ) ) != 0 || 00104 ( ret = dhm_read_bignum( &ctx->G, p, end ) ) != 0 || 00105 ( ret = dhm_read_bignum( &ctx->GY, p, end ) ) != 0 ) 00106 return( ret ); 00107 00108 if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 ) 00109 return( ret ); 00110 00111 ctx->len = mpi_size( &ctx->P ); 00112 00113 if( end - *p < 2 ) 00114 return( POLARSSL_ERR_DHM_BAD_INPUT_DATA ); 00115 00116 n = ( (*p)[0] << 8 ) | (*p)[1]; 00117 (*p) += 2; 00118 00119 if( end != *p + n ) 00120 return( POLARSSL_ERR_DHM_BAD_INPUT_DATA ); 00121 00122 return( 0 ); 00123 } 00124 00125 /* 00126 * Setup and write the ServerKeyExchange parameters 00127 */ 00128 int dhm_make_params( dhm_context *ctx, int x_size, 00129 unsigned char *output, size_t *olen, 00130 int (*f_rng)(void *, unsigned char *, size_t), 00131 void *p_rng ) 00132 { 00133 int ret, count = 0; 00134 size_t n1, n2, n3; 00135 unsigned char *p; 00136 00137 /* 00138 * Generate X as large as possible ( < P ) 00139 */ 00140 do 00141 { 00142 mpi_fill_random( &ctx->X, x_size, f_rng, p_rng ); 00143 00144 while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 ) 00145 mpi_shift_r( &ctx->X, 1 ); 00146 00147 if( count++ > 10 ) 00148 return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED ); 00149 } 00150 while( dhm_check_range( &ctx->X, &ctx->P ) != 0 ); 00151 00152 /* 00153 * Calculate GX = G^X mod P 00154 */ 00155 MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X, 00156 &ctx->P , &ctx->RP ) ); 00157 00158 if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 ) 00159 return( ret ); 00160 00161 /* 00162 * export P, G, GX 00163 */ 00164 #define DHM_MPI_EXPORT(X,n) \ 00165 MPI_CHK( mpi_write_binary( X, p + 2, n ) ); \ 00166 *p++ = (unsigned char)( n >> 8 ); \ 00167 *p++ = (unsigned char)( n ); p += n; 00168 00169 n1 = mpi_size( &ctx->P ); 00170 n2 = mpi_size( &ctx->G ); 00171 n3 = mpi_size( &ctx->GX ); 00172 00173 p = output; 00174 DHM_MPI_EXPORT( &ctx->P , n1 ); 00175 DHM_MPI_EXPORT( &ctx->G , n2 ); 00176 DHM_MPI_EXPORT( &ctx->GX, n3 ); 00177 00178 *olen = p - output; 00179 00180 ctx->len = n1; 00181 00182 cleanup: 00183 00184 if( ret != 0 ) 00185 return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED + ret ); 00186 00187 return( 0 ); 00188 } 00189 00190 /* 00191 * Import the peer's public value G^Y 00192 */ 00193 int dhm_read_public( dhm_context *ctx, 00194 const unsigned char *input, size_t ilen ) 00195 { 00196 int ret; 00197 00198 if( ctx == NULL || ilen < 1 || ilen > ctx->len ) 00199 return( POLARSSL_ERR_DHM_BAD_INPUT_DATA ); 00200 00201 if( ( ret = mpi_read_binary( &ctx->GY, input, ilen ) ) != 0 ) 00202 return( POLARSSL_ERR_DHM_READ_PUBLIC_FAILED + ret ); 00203 00204 return( 0 ); 00205 } 00206 00207 /* 00208 * Create own private value X and export G^X 00209 */ 00210 int dhm_make_public( dhm_context *ctx, int x_size, 00211 unsigned char *output, size_t olen, 00212 int (*f_rng)(void *, unsigned char *, size_t), 00213 void *p_rng ) 00214 { 00215 int ret, count = 0; 00216 00217 if( ctx == NULL || olen < 1 || olen > ctx->len ) 00218 return( POLARSSL_ERR_DHM_BAD_INPUT_DATA ); 00219 00220 /* 00221 * generate X and calculate GX = G^X mod P 00222 */ 00223 do 00224 { 00225 mpi_fill_random( &ctx->X, x_size, f_rng, p_rng ); 00226 00227 while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 ) 00228 mpi_shift_r( &ctx->X, 1 ); 00229 00230 if( count++ > 10 ) 00231 return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED ); 00232 } 00233 while( dhm_check_range( &ctx->X, &ctx->P ) != 0 ); 00234 00235 MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X, 00236 &ctx->P , &ctx->RP ) ); 00237 00238 if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 ) 00239 return( ret ); 00240 00241 MPI_CHK( mpi_write_binary( &ctx->GX, output, olen ) ); 00242 00243 cleanup: 00244 00245 if( ret != 0 ) 00246 return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED + ret ); 00247 00248 return( 0 ); 00249 } 00250 00251 /* 00252 * Derive and export the shared secret (G^Y)^X mod P 00253 */ 00254 int dhm_calc_secret( dhm_context *ctx, 00255 unsigned char *output, size_t *olen ) 00256 { 00257 int ret; 00258 00259 if( ctx == NULL || *olen < ctx->len ) 00260 return( POLARSSL_ERR_DHM_BAD_INPUT_DATA ); 00261 00262 MPI_CHK( mpi_exp_mod( &ctx->K, &ctx->GY, &ctx->X, 00263 &ctx->P, &ctx->RP ) ); 00264 00265 if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 ) 00266 return( ret ); 00267 00268 *olen = mpi_size( &ctx->K ); 00269 00270 MPI_CHK( mpi_write_binary( &ctx->K, output, *olen ) ); 00271 00272 cleanup: 00273 00274 if( ret != 0 ) 00275 return( POLARSSL_ERR_DHM_CALC_SECRET_FAILED + ret ); 00276 00277 return( 0 ); 00278 } 00279 00280 /* 00281 * Free the components of a DHM key 00282 */ 00283 void dhm_free( dhm_context *ctx ) 00284 { 00285 mpi_free( &ctx->RP ); mpi_free( &ctx->K ); mpi_free( &ctx->GY ); 00286 mpi_free( &ctx->GX ); mpi_free( &ctx->X ); mpi_free( &ctx->G ); 00287 mpi_free( &ctx->P ); 00288 } 00289 00290 #if defined(POLARSSL_SELF_TEST) 00291 00292 /* 00293 * Checkup routine 00294 */ 00295 int dhm_self_test( int verbose ) 00296 { 00297 return( verbose++ ); 00298 } 00299 00300 #endif 00301 00302 #endif