dhm.c

00001 /*
00002  *  Diffie-Hellman-Merkle key exchange
00003  *
00004  *  Copyright (C) 2006-2014, 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 #if !defined(POLARSSL_CONFIG_FILE)
00032 #include "polarssl/config.h"
00033 #else
00034 #include POLARSSL_CONFIG_FILE
00035 #endif
00036 
00037 #if defined(POLARSSL_DHM_C)
00038 
00039 #include "polarssl/dhm.h"
00040 
00041 #if defined(POLARSSL_PEM_PARSE_C)
00042 #include "polarssl/pem.h"
00043 #endif
00044 
00045 #if defined(POLARSSL_ASN1_PARSE_C)
00046 #include "polarssl/asn1.h"
00047 #endif
00048 
00049 #if defined(POLARSSL_PLATFORM_C)
00050 #include "polarssl/platform.h"
00051 #else
00052 #include <stdlib.h>
00053 #define polarssl_printf     printf
00054 #define polarssl_malloc     malloc
00055 #define polarssl_free       free
00056 #endif
00057 
00058 /*
00059  * helper to validate the mpi size and import it
00060  */
00061 static int dhm_read_bignum( mpi *X,
00062                             unsigned char **p,
00063                             const unsigned char *end )
00064 {
00065     int ret, n;
00066 
00067     if( end - *p < 2 )
00068         return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
00069 
00070     n = ( (*p)[0] << 8 ) | (*p)[1];
00071     (*p) += 2;
00072 
00073     if( (int)( end - *p ) < n )
00074         return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
00075 
00076     if( ( ret = mpi_read_binary( X, *p, n ) ) != 0 )
00077         return( POLARSSL_ERR_DHM_READ_PARAMS_FAILED + ret );
00078 
00079     (*p) += n;
00080 
00081     return( 0 );
00082 }
00083 
00084 /*
00085  * Verify sanity of parameter with regards to P
00086  *
00087  * Parameter should be: 2 <= public_param <= P - 2
00088  *
00089  * For more information on the attack, see:
00090  *  http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf
00091  *  http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2005-2643
00092  */
00093 static int dhm_check_range( const mpi *param, const mpi *P )
00094 {
00095     mpi L, U;
00096     int ret = POLARSSL_ERR_DHM_BAD_INPUT_DATA;
00097 
00098     mpi_init( &L ); mpi_init( &U );
00099 
00100     MPI_CHK( mpi_lset( &L, 2 ) );
00101     MPI_CHK( mpi_sub_int( &U, P, 2 ) );
00102 
00103     if( mpi_cmp_mpi( param, &L ) >= 0 &&
00104         mpi_cmp_mpi( param, &U ) <= 0 )
00105     {
00106         ret = 0;
00107     }
00108 
00109 cleanup:
00110     mpi_free( &L ); mpi_free( &U );
00111     return( ret );
00112 }
00113 
00114 /*
00115  * Parse the ServerKeyExchange parameters
00116  */
00117 int dhm_read_params( dhm_context *ctx,
00118                      unsigned char **p,
00119                      const unsigned char *end )
00120 {
00121     int ret;
00122 
00123     dhm_free( ctx );
00124 
00125     if( ( ret = dhm_read_bignum( &ctx->P ,  p, end ) ) != 0 ||
00126         ( ret = dhm_read_bignum( &ctx->G ,  p, end ) ) != 0 ||
00127         ( ret = dhm_read_bignum( &ctx->GY , p, end ) ) != 0 )
00128         return( ret );
00129 
00130     if( ( ret = dhm_check_range( &ctx->GY , &ctx->P  ) ) != 0 )
00131         return( ret );
00132 
00133     ctx->len  = mpi_size( &ctx->P  );
00134 
00135     return( 0 );
00136 }
00137 
00138 /*
00139  * Setup and write the ServerKeyExchange parameters
00140  */
00141 int dhm_make_params( dhm_context *ctx, int x_size,
00142                      unsigned char *output, size_t *olen,
00143                      int (*f_rng)(void *, unsigned char *, size_t),
00144                      void *p_rng )
00145 {
00146     int ret, count = 0;
00147     size_t n1, n2, n3;
00148     unsigned char *p;
00149 
00150     if( mpi_cmp_int( &ctx->P , 0 ) == 0 )
00151         return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
00152 
00153     /*
00154      * Generate X as large as possible ( < P )
00155      */
00156     do
00157     {
00158         mpi_fill_random( &ctx->X , x_size, f_rng, p_rng );
00159 
00160         while( mpi_cmp_mpi( &ctx->X , &ctx->P  ) >= 0 )
00161             MPI_CHK( mpi_shift_r( &ctx->X , 1 ) );
00162 
00163         if( count++ > 10 )
00164             return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED );
00165     }
00166     while( dhm_check_range( &ctx->X , &ctx->P  ) != 0 );
00167 
00168     /*
00169      * Calculate GX = G^X mod P
00170      */
00171     MPI_CHK( mpi_exp_mod( &ctx->GX , &ctx->G , &ctx->X ,
00172                           &ctx->P  , &ctx->RP  ) );
00173 
00174     if( ( ret = dhm_check_range( &ctx->GX , &ctx->P  ) ) != 0 )
00175         return( ret );
00176 
00177     /*
00178      * export P, G, GX
00179      */
00180 #define DHM_MPI_EXPORT(X,n)                     \
00181     MPI_CHK( mpi_write_binary( X, p + 2, n ) ); \
00182     *p++ = (unsigned char)( n >> 8 );           \
00183     *p++ = (unsigned char)( n      ); p += n;
00184 
00185     n1 = mpi_size( &ctx->P   );
00186     n2 = mpi_size( &ctx->G   );
00187     n3 = mpi_size( &ctx->GX  );
00188 
00189     p = output;
00190     DHM_MPI_EXPORT( &ctx->P  , n1 );
00191     DHM_MPI_EXPORT( &ctx->G  , n2 );
00192     DHM_MPI_EXPORT( &ctx->GX , n3 );
00193 
00194     *olen  = p - output;
00195 
00196     ctx->len  = n1;
00197 
00198 cleanup:
00199 
00200     if( ret != 0 )
00201         return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED + ret );
00202 
00203     return( 0 );
00204 }
00205 
00206 /*
00207  * Import the peer's public value G^Y
00208  */
00209 int dhm_read_public( dhm_context *ctx,
00210                      const unsigned char *input, size_t ilen )
00211 {
00212     int ret;
00213 
00214     if( ctx == NULL || ilen < 1 || ilen > ctx->len  )
00215         return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
00216 
00217     if( ( ret = mpi_read_binary( &ctx->GY , input, ilen ) ) != 0 )
00218         return( POLARSSL_ERR_DHM_READ_PUBLIC_FAILED + ret );
00219 
00220     return( 0 );
00221 }
00222 
00223 /*
00224  * Create own private value X and export G^X
00225  */
00226 int dhm_make_public( dhm_context *ctx, int x_size,
00227                      unsigned char *output, size_t olen,
00228                      int (*f_rng)(void *, unsigned char *, size_t),
00229                      void *p_rng )
00230 {
00231     int ret, count = 0;
00232 
00233     if( ctx == NULL || olen < 1 || olen > ctx->len  )
00234         return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
00235 
00236     if( mpi_cmp_int( &ctx->P , 0 ) == 0 )
00237         return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
00238 
00239     /*
00240      * generate X and calculate GX = G^X mod P
00241      */
00242     do
00243     {
00244         mpi_fill_random( &ctx->X , x_size, f_rng, p_rng );
00245 
00246         while( mpi_cmp_mpi( &ctx->X , &ctx->P  ) >= 0 )
00247             MPI_CHK( mpi_shift_r( &ctx->X , 1 ) );
00248 
00249         if( count++ > 10 )
00250             return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED );
00251     }
00252     while( dhm_check_range( &ctx->X , &ctx->P  ) != 0 );
00253 
00254     MPI_CHK( mpi_exp_mod( &ctx->GX , &ctx->G , &ctx->X ,
00255                           &ctx->P  , &ctx->RP  ) );
00256 
00257     if( ( ret = dhm_check_range( &ctx->GX , &ctx->P  ) ) != 0 )
00258         return( ret );
00259 
00260     MPI_CHK( mpi_write_binary( &ctx->GX , output, olen ) );
00261 
00262 cleanup:
00263 
00264     if( ret != 0 )
00265         return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED + ret );
00266 
00267     return( 0 );
00268 }
00269 
00270 /*
00271  * Use the blinding method and optimisation suggested in section 10 of:
00272  *  KOCHER, Paul C. Timing attacks on implementations of Diffie-Hellman, RSA,
00273  *  DSS, and other systems. In : Advances in Cryptology—CRYPTO’96. Springer
00274  *  Berlin Heidelberg, 1996. p. 104-113.
00275  */
00276 static int dhm_update_blinding( dhm_context *ctx,
00277                     int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
00278 {
00279     int ret, count;
00280 
00281     /*
00282      * Don't use any blinding the first time a particular X is used,
00283      * but remember it to use blinding next time.
00284      */
00285     if( mpi_cmp_mpi( &ctx->X , &ctx->pX  ) != 0 )
00286     {
00287         MPI_CHK( mpi_copy( &ctx->pX , &ctx->X  ) );
00288         MPI_CHK( mpi_lset( &ctx->Vi , 1 ) );
00289         MPI_CHK( mpi_lset( &ctx->Vf , 1 ) );
00290 
00291         return( 0 );
00292     }
00293 
00294     /*
00295      * Ok, we need blinding. Can we re-use existing values?
00296      * If yes, just update them by squaring them.
00297      */
00298     if( mpi_cmp_int( &ctx->Vi , 1 ) != 0 )
00299     {
00300         MPI_CHK( mpi_mul_mpi( &ctx->Vi , &ctx->Vi , &ctx->Vi  ) );
00301         MPI_CHK( mpi_mod_mpi( &ctx->Vi , &ctx->Vi , &ctx->P  ) );
00302 
00303         MPI_CHK( mpi_mul_mpi( &ctx->Vf , &ctx->Vf , &ctx->Vf  ) );
00304         MPI_CHK( mpi_mod_mpi( &ctx->Vf , &ctx->Vf , &ctx->P  ) );
00305 
00306         return( 0 );
00307     }
00308 
00309     /*
00310      * We need to generate blinding values from scratch
00311      */
00312 
00313     /* Vi = random( 2, P-1 ) */
00314     count = 0;
00315     do
00316     {
00317         mpi_fill_random( &ctx->Vi , mpi_size( &ctx->P  ), f_rng, p_rng );
00318 
00319         while( mpi_cmp_mpi( &ctx->Vi , &ctx->P  ) >= 0 )
00320             MPI_CHK( mpi_shift_r( &ctx->Vi , 1 ) );
00321 
00322         if( count++ > 10 )
00323             return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
00324     }
00325     while( mpi_cmp_int( &ctx->Vi , 1 ) <= 0 );
00326 
00327     /* Vf = Vi^-X mod P */
00328     MPI_CHK( mpi_inv_mod( &ctx->Vf , &ctx->Vi , &ctx->P  ) );
00329     MPI_CHK( mpi_exp_mod( &ctx->Vf , &ctx->Vf , &ctx->X , &ctx->P , &ctx->RP  ) );
00330 
00331 cleanup:
00332     return( ret );
00333 }
00334 
00335 /*
00336  * Derive and export the shared secret (G^Y)^X mod P
00337  */
00338 int dhm_calc_secret( dhm_context *ctx,
00339                      unsigned char *output, size_t *olen,
00340                      int (*f_rng)(void *, unsigned char *, size_t),
00341                      void *p_rng )
00342 {
00343     int ret;
00344     mpi GYb;
00345 
00346     if( ctx == NULL || *olen < ctx->len )
00347         return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
00348 
00349     if( ( ret = dhm_check_range( &ctx->GY , &ctx->P  ) ) != 0 )
00350         return( ret );
00351 
00352     mpi_init( &GYb );
00353 
00354     /* Blind peer's value */
00355     if( f_rng != NULL )
00356     {
00357         MPI_CHK( dhm_update_blinding( ctx, f_rng, p_rng ) );
00358         MPI_CHK( mpi_mul_mpi( &GYb, &ctx->GY , &ctx->Vi  ) );
00359         MPI_CHK( mpi_mod_mpi( &GYb, &GYb, &ctx->P  ) );
00360     }
00361     else
00362         MPI_CHK( mpi_copy( &GYb, &ctx->GY  ) );
00363 
00364     /* Do modular exponentiation */
00365     MPI_CHK( mpi_exp_mod( &ctx->K , &GYb, &ctx->X ,
00366                           &ctx->P , &ctx->RP  ) );
00367 
00368     /* Unblind secret value */
00369     if( f_rng != NULL )
00370     {
00371         MPI_CHK( mpi_mul_mpi( &ctx->K , &ctx->K , &ctx->Vf  ) );
00372         MPI_CHK( mpi_mod_mpi( &ctx->K , &ctx->K , &ctx->P  ) );
00373     }
00374 
00375     *olen = mpi_size( &ctx->K  );
00376 
00377     MPI_CHK( mpi_write_binary( &ctx->K , output, *olen ) );
00378 
00379 cleanup:
00380     mpi_free( &GYb );
00381 
00382     if( ret != 0 )
00383         return( POLARSSL_ERR_DHM_CALC_SECRET_FAILED + ret );
00384 
00385     return( 0 );
00386 }
00387 
00388 /*
00389  * Free the components of a DHM key
00390  */
00391 void dhm_free( dhm_context *ctx )
00392 {
00393     mpi_free( &ctx->pX ); mpi_free( &ctx->Vf  ); mpi_free( &ctx->Vi  );
00394     mpi_free( &ctx->RP  ); mpi_free( &ctx->K  ); mpi_free( &ctx->GY  );
00395     mpi_free( &ctx->GX  ); mpi_free( &ctx->X  ); mpi_free( &ctx->G  );
00396     mpi_free( &ctx->P  );
00397 
00398     memset( ctx, 0, sizeof( dhm_context ) );
00399 }
00400 
00401 #if defined(POLARSSL_ASN1_PARSE_C)
00402 /*
00403  * Parse DHM parameters
00404  */
00405 int dhm_parse_dhm( dhm_context *dhm, const unsigned char *dhmin,
00406                    size_t dhminlen )
00407 {
00408     int ret;
00409     size_t len;
00410     unsigned char *p, *end;
00411 #if defined(POLARSSL_PEM_PARSE_C)
00412     pem_context pem;
00413 
00414     pem_init( &pem );
00415     memset( dhm, 0, sizeof( dhm_context ) );
00416 
00417     ret = pem_read_buffer( &pem,
00418                            "-----BEGIN DH PARAMETERS-----",
00419                            "-----END DH PARAMETERS-----",
00420                            dhmin, NULL, 0, &dhminlen );
00421 
00422     if( ret == 0 )
00423     {
00424         /*
00425          * Was PEM encoded
00426          */
00427         dhminlen = pem.buflen ;
00428     }
00429     else if( ret != POLARSSL_ERR_PEM_NO_HEADER_FOOTER_PRESENT )
00430         goto exit;
00431 
00432     p = ( ret == 0 ) ? pem.buf  : (unsigned char *) dhmin;
00433 #else
00434     p = (unsigned char *) dhmin;
00435 #endif /* POLARSSL_PEM_PARSE_C */
00436     end = p + dhminlen;
00437 
00438     /*
00439      *  DHParams ::= SEQUENCE {
00440      *      prime            INTEGER,  -- P
00441      *      generator        INTEGER,  -- g
00442      *  }
00443      */
00444     if( ( ret = asn1_get_tag( &p, end, &len,
00445             ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 )
00446     {
00447         ret = POLARSSL_ERR_DHM_INVALID_FORMAT + ret;
00448         goto exit;
00449     }
00450 
00451     end = p + len;
00452 
00453     if( ( ret = asn1_get_mpi( &p, end, &dhm->P   ) ) != 0 ||
00454         ( ret = asn1_get_mpi( &p, end, &dhm->G  ) ) != 0 )
00455     {
00456         ret = POLARSSL_ERR_DHM_INVALID_FORMAT + ret;
00457         goto exit;
00458     }
00459 
00460     if( p != end )
00461     {
00462         ret = POLARSSL_ERR_DHM_INVALID_FORMAT +
00463               POLARSSL_ERR_ASN1_LENGTH_MISMATCH;
00464         goto exit;
00465     }
00466 
00467     ret = 0;
00468 
00469     dhm->len  = mpi_size( &dhm->P  );
00470 
00471 exit:
00472 #if defined(POLARSSL_PEM_PARSE_C)
00473     pem_free( &pem );
00474 #endif
00475     if( ret != 0 )
00476         dhm_free( dhm );
00477 
00478     return( ret );
00479 }
00480 
00481 #if defined(POLARSSL_FS_IO)
00482 /*
00483  * Load all data from a file into a given buffer.
00484  */
00485 static int load_file( const char *path, unsigned char **buf, size_t *n )
00486 {
00487     FILE *f;
00488     long size;
00489 
00490     if( ( f = fopen( path, "rb" ) ) == NULL )
00491         return( POLARSSL_ERR_DHM_FILE_IO_ERROR );
00492 
00493     fseek( f, 0, SEEK_END );
00494     if( ( size = ftell( f ) ) == -1 )
00495     {
00496         fclose( f );
00497         return( POLARSSL_ERR_DHM_FILE_IO_ERROR );
00498     }
00499     fseek( f, 0, SEEK_SET );
00500 
00501     *n = (size_t) size;
00502 
00503     if( *n + 1 == 0 ||
00504         ( *buf = (unsigned char *) polarssl_malloc( *n + 1 ) ) == NULL )
00505     {
00506         fclose( f );
00507         return( POLARSSL_ERR_DHM_MALLOC_FAILED );
00508     }
00509 
00510     if( fread( *buf, 1, *n, f ) != *n )
00511     {
00512         fclose( f );
00513         polarssl_free( *buf );
00514         return( POLARSSL_ERR_DHM_FILE_IO_ERROR );
00515     }
00516 
00517     fclose( f );
00518 
00519     (*buf)[*n] = '\0';
00520 
00521     return( 0 );
00522 }
00523 
00524 /*
00525  * Load and parse DHM parameters
00526  */
00527 int dhm_parse_dhmfile( dhm_context *dhm, const char *path )
00528 {
00529     int ret;
00530     size_t n;
00531     unsigned char *buf;
00532 
00533     if ( ( ret = load_file( path, &buf, &n ) ) != 0 )
00534         return( ret );
00535 
00536     ret = dhm_parse_dhm( dhm, buf, n );
00537 
00538     memset( buf, 0, n + 1 );
00539     polarssl_free( buf );
00540 
00541     return( ret );
00542 }
00543 #endif /* POLARSSL_FS_IO */
00544 #endif /* POLARSSL_ASN1_PARSE_C */
00545 
00546 #if defined(POLARSSL_SELF_TEST)
00547 
00548 #include "polarssl/certs.h"
00549 
00550 /*
00551  * Checkup routine
00552  */
00553 int dhm_self_test( int verbose )
00554 {
00555 #if defined(POLARSSL_CERTS_C)
00556     int ret;
00557     dhm_context dhm;
00558 
00559     if( verbose != 0 )
00560         polarssl_printf( "  DHM parameter load: " );
00561 
00562     if( ( ret = dhm_parse_dhm( &dhm, (const unsigned char *) test_dhm_params,
00563                                strlen( test_dhm_params ) ) ) != 0 )
00564     {
00565         if( verbose != 0 )
00566             polarssl_printf( "failed\n" );
00567 
00568         return( ret );
00569     }
00570 
00571     if( verbose != 0 )
00572         polarssl_printf( "passed\n\n" );
00573 
00574     dhm_free( &dhm );
00575 
00576     return( 0 );
00577 #else
00578     if( verbose != 0 )
00579         polarssl_printf( "  DHM parameter load: skipped\n" );
00580 
00581     return( 0 );
00582 #endif /* POLARSSL_CERTS_C */
00583 }
00584 
00585 #endif /* POLARSSL_SELF_TEST */
00586 
00587 #endif /* POLARSSL_DHM_C */
00588 
00589