dhm.c 9.6 KB
Newer Older
1 2 3
/*
 *  Diffie-Hellman-Merkle key exchange
 *
4
 *  Copyright (C) 2006-2010, Brainspark B.V.
Paul Bakker's avatar
Paul Bakker committed
5 6
 *
 *  This file is part of PolarSSL (http://www.polarssl.org)
7
 *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
Paul Bakker's avatar
Paul Bakker committed
8
 *
9
 *  All rights reserved.
Paul Bakker's avatar
Paul Bakker committed
10
 *
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
/*
 *  Reference:
 *
 *  http://www.cacr.math.uwaterloo.ca/hac/ (chapter 12)
 */

31
#include "polarssl/config.h"
32

33
#if defined(POLARSSL_DHM_C)
34

35
#include "polarssl/dhm.h"
36 37 38 39 40 41

/*
 * helper to validate the mpi size and import it
 */
static int dhm_read_bignum( mpi *X,
                            unsigned char **p,
42
                            const unsigned char *end )
43 44 45 46
{
    int ret, n;

    if( end - *p < 2 )
47
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
48 49 50 51 52

    n = ( (*p)[0] << 8 ) | (*p)[1];
    (*p) += 2;

    if( (int)( end - *p ) < n )
53
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
54 55

    if( ( ret = mpi_read_binary( X, *p, n ) ) != 0 )
56
        return( POLARSSL_ERR_DHM_READ_PARAMS_FAILED + ret );
57 58 59 60 61 62

    (*p) += n;

    return( 0 );
}

Paul Bakker's avatar
Paul Bakker committed
63
/*
64
 * Verify sanity of parameter with regards to P
65
 *
66
 * Parameter should be: 2 <= public_param <= P - 2
67 68 69 70
 *
 * For more information on the attack, see:
 *  http://www.cl.cam.ac.uk/~rja14/Papers/psandqs.pdf
 *  http://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2005-2643
Paul Bakker's avatar
Paul Bakker committed
71
 */
72
static int dhm_check_range( const mpi *param, const mpi *P )
Paul Bakker's avatar
Paul Bakker committed
73
{
74 75
    mpi L, U;
    int ret = POLARSSL_ERR_DHM_BAD_INPUT_DATA;
Paul Bakker's avatar
Paul Bakker committed
76

77
    mpi_init( &L ); mpi_init( &U );
78 79
    mpi_lset( &L, 2 );
    mpi_sub_int( &U, P, 2 );
Paul Bakker's avatar
Paul Bakker committed
80

81 82
    if( mpi_cmp_mpi( param, &L ) >= 0 &&
        mpi_cmp_mpi( param, &U ) <= 0 )
Paul Bakker's avatar
Paul Bakker committed
83
    {
84
        ret = 0;
Paul Bakker's avatar
Paul Bakker committed
85 86
    }

87
    mpi_free( &L ); mpi_free( &U );
Paul Bakker's avatar
Paul Bakker committed
88

89
    return( ret );
Paul Bakker's avatar
Paul Bakker committed
90 91
}

92 93 94 95 96
/*
 * Parse the ServerKeyExchange parameters
 */
int dhm_read_params( dhm_context *ctx,
                     unsigned char **p,
97
                     const unsigned char *end )
98
{
Paul Bakker's avatar
Paul Bakker committed
99
    int ret;
100

101
    dhm_free( ctx );
102 103 104 105 106 107

    if( ( ret = dhm_read_bignum( &ctx->P,  p, end ) ) != 0 ||
        ( ret = dhm_read_bignum( &ctx->G,  p, end ) ) != 0 ||
        ( ret = dhm_read_bignum( &ctx->GY, p, end ) ) != 0 )
        return( ret );

108 109 110
    if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
        return( ret );

111 112 113 114 115 116 117 118 119
    ctx->len = mpi_size( &ctx->P );

    return( 0 );
}

/*
 * Setup and write the ServerKeyExchange parameters
 */
int dhm_make_params( dhm_context *ctx, int x_size,
120
                     unsigned char *output, size_t *olen,
121 122
                     int (*f_rng)(void *, unsigned char *, size_t),
                     void *p_rng )
123
{
124
    int ret, count = 0;
125
    size_t n1, n2, n3;
126 127
    unsigned char *p;

128 129 130
    if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );

131
    /*
132
     * Generate X as large as possible ( < P )
133
     */
134 135 136
    do
    {
        mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
137

138 139 140 141 142 143 144
        while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
            mpi_shift_r( &ctx->X, 1 );

        if( count++ > 10 )
            return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED );
    }
    while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
145

146 147 148
    /*
     * Calculate GX = G^X mod P
     */
149 150 151
    MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
                          &ctx->P , &ctx->RP ) );

152
    if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
Paul Bakker's avatar
Paul Bakker committed
153 154
        return( ret );

155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
    /*
     * export P, G, GX
     */
#define DHM_MPI_EXPORT(X,n)                     \
    MPI_CHK( mpi_write_binary( X, p + 2, n ) ); \
    *p++ = (unsigned char)( n >> 8 );           \
    *p++ = (unsigned char)( n      ); p += n;

    n1 = mpi_size( &ctx->P  );
    n2 = mpi_size( &ctx->G  );
    n3 = mpi_size( &ctx->GX );

    p = output;
    DHM_MPI_EXPORT( &ctx->P , n1 );
    DHM_MPI_EXPORT( &ctx->G , n2 );
    DHM_MPI_EXPORT( &ctx->GX, n3 );

    *olen  = p - output;

    ctx->len = n1;

cleanup:

    if( ret != 0 )
179
        return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED + ret );
180 181 182 183 184 185 186 187

    return( 0 );
}

/*
 * Import the peer's public value G^Y
 */
int dhm_read_public( dhm_context *ctx,
188
                     const unsigned char *input, size_t ilen )
189 190 191 192
{
    int ret;

    if( ctx == NULL || ilen < 1 || ilen > ctx->len )
193
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
194 195

    if( ( ret = mpi_read_binary( &ctx->GY, input, ilen ) ) != 0 )
196
        return( POLARSSL_ERR_DHM_READ_PUBLIC_FAILED + ret );
197 198 199 200 201 202 203 204

    return( 0 );
}

/*
 * Create own private value X and export G^X
 */
int dhm_make_public( dhm_context *ctx, int x_size,
205
                     unsigned char *output, size_t olen,
206 207
                     int (*f_rng)(void *, unsigned char *, size_t),
                     void *p_rng )
208
{
209
    int ret, count = 0;
210 211

    if( ctx == NULL || olen < 1 || olen > ctx->len )
212
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
213

214 215 216
    if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );

217 218 219
    /*
     * generate X and calculate GX = G^X mod P
     */
220 221 222
    do
    {
        mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
223

224 225 226 227 228 229 230
        while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
            mpi_shift_r( &ctx->X, 1 );

        if( count++ > 10 )
            return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED );
    }
    while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
231 232 233 234

    MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
                          &ctx->P , &ctx->RP ) );

235 236
    if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
        return( ret );
Paul Bakker's avatar
Paul Bakker committed
237

238 239 240 241 242
    MPI_CHK( mpi_write_binary( &ctx->GX, output, olen ) );

cleanup:

    if( ret != 0 )
243
        return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED + ret );
244 245 246 247

    return( 0 );
}

248 249 250 251 252 253 254 255 256 257 258 259
/*
 * Use the blinding method and optimisation suggested in section 10 of:
 *  KOCHER, Paul C. Timing attacks on implementations of Diffie-Hellman, RSA,
 *  DSS, and other systems. In : Advances in Cryptology—CRYPTO’96. Springer
 *  Berlin Heidelberg, 1996. p. 104-113.
 */
static int dhm_update_blinding( dhm_context *ctx,
                    int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
{
    int ret, count;

    /*
260
     * If Vi is initialized, update it by squaring it
261
     */
262
    if( ctx->Vi.p != NULL )
263 264
    {
        MPI_CHK( mpi_mul_mpi( &ctx->Vi, &ctx->Vi, &ctx->Vi ) );
265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281
        MPI_CHK( mpi_mod_mpi( &ctx->Vi, &ctx->Vi, &ctx->P ) );
    }
    else
    {
        /* Vi = random( 2, P-1 ) */
        count = 0;
        do
        {
            mpi_fill_random( &ctx->Vi, mpi_size( &ctx->P ), f_rng, p_rng );

            while( mpi_cmp_mpi( &ctx->Vi, &ctx->P ) >= 0 )
                mpi_shift_r( &ctx->Vi, 1 );

            if( count++ > 10 )
                return( POLARSSL_ERR_MPI_NOT_ACCEPTABLE );
        }
        while( mpi_cmp_int( &ctx->Vi, 1 ) <= 0 );
282 283 284
    }

    /*
285
     * If X did not change, update Vf by squaring it too
286
     */
287
    if( mpi_cmp_mpi( &ctx->X, &ctx->_X ) == 0 )
288
    {
289 290 291
        MPI_CHK( mpi_mul_mpi( &ctx->Vf, &ctx->Vf, &ctx->Vf ) );
        MPI_CHK( mpi_mod_mpi( &ctx->Vf, &ctx->Vf, &ctx->P ) );
        return( 0 );
292
    }
293 294 295 296

    /*
     * Otherwise, compute Vf from scratch
     */
297 298 299 300 301 302 303 304 305 306 307 308

    /* Vf = Vi^-X mod P */
    MPI_CHK( mpi_inv_mod( &ctx->Vf, &ctx->Vi, &ctx->P ) );
    MPI_CHK( mpi_exp_mod( &ctx->Vf, &ctx->Vf, &ctx->X, &ctx->P, &ctx->RP ) );

    /* Remember secret associated with Vi and Vf */
    MPI_CHK( mpi_copy( &ctx->_X, &ctx->X ) );;

cleanup:
    return( ret );
}

309 310 311 312
/*
 * Derive and export the shared secret (G^Y)^X mod P
 */
int dhm_calc_secret( dhm_context *ctx,
313 314 315
                     unsigned char *output, size_t *olen,
                     int (*f_rng)(void *, unsigned char *, size_t),
                     void *p_rng )
316 317
{
    int ret;
318
    mpi GYb;
319

320
    if( ctx == NULL || *olen < ctx->len )
321
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
322

323
    if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
Paul Bakker's avatar
Paul Bakker committed
324 325
        return( ret );

326 327 328
    mpi_init( &GYb );

    /* Blind peer's value */
329
    if( f_rng != NULL )
330 331 332 333 334 335 336 337 338 339 340 341 342
    {
        MPI_CHK( dhm_update_blinding( ctx, f_rng, p_rng ) );
        MPI_CHK( mpi_mul_mpi( &GYb, &ctx->GY, &ctx->Vi ) );
        MPI_CHK( mpi_mod_mpi( &GYb, &GYb, &ctx->P ) );
    }
    else
        MPI_CHK( mpi_copy( &GYb, &ctx->GY ) );

    /* Do modular exponentiation */
    MPI_CHK( mpi_exp_mod( &ctx->K, &GYb, &ctx->X,
                          &ctx->P, &ctx->RP ) );

    /* Unblind secret value */
343
    if( f_rng != NULL )
344 345 346 347 348
    {
        MPI_CHK( mpi_mul_mpi( &ctx->K, &ctx->K, &ctx->Vf ) );
        MPI_CHK( mpi_mod_mpi( &ctx->K, &ctx->K, &ctx->P ) );
    }

349 350 351 352 353
    *olen = mpi_size( &ctx->K );

    MPI_CHK( mpi_write_binary( &ctx->K, output, *olen ) );

cleanup:
354
    mpi_free( &GYb );
355 356

    if( ret != 0 )
357
        return( POLARSSL_ERR_DHM_CALC_SECRET_FAILED + ret );
358 359 360 361 362 363 364 365 366

    return( 0 );
}

/*
 * Free the components of a DHM key
 */
void dhm_free( dhm_context *ctx )
{
367
    mpi_free( &ctx->_X); mpi_free( &ctx->Vf ); mpi_free( &ctx->Vi );
368 369 370
    mpi_free( &ctx->RP ); mpi_free( &ctx->K ); mpi_free( &ctx->GY );
    mpi_free( &ctx->GX ); mpi_free( &ctx->X ); mpi_free( &ctx->G );
    mpi_free( &ctx->P );
371 372

    memset( ctx, 0, sizeof( dhm_context ) );
373 374
}

375
#if defined(POLARSSL_SELF_TEST)
376 377 378 379 380 381 382 383 384 385 386 387

/*
 * Checkup routine
 */
int dhm_self_test( int verbose )
{
    return( verbose++ );
}

#endif

#endif