dhm.c

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