PolarSSL v1.1.4
dhm.c
Go to the documentation of this file.
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