dhm.c 14.1 KB
Newer Older
1 2 3
/*
 *  Diffie-Hellman-Merkle key exchange
 *
Manuel Pégourié-Gonnard's avatar
Manuel Pégourié-Gonnard committed
4
 *  Copyright (C) 2006-2014, ARM Limited, All Rights Reserved
Paul Bakker's avatar
Paul Bakker committed
5
 *
6
 *  This file is part of mbed TLS (https://www.polarssl.org)
Paul Bakker's avatar
Paul Bakker committed
7
 *
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
 *  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)
 */

28
#if !defined(POLARSSL_CONFIG_FILE)
29
#include "polarssl/config.h"
30 31 32
#else
#include POLARSSL_CONFIG_FILE
#endif
33

34
#if defined(POLARSSL_DHM_C)
35

36
#include "polarssl/dhm.h"
37

38
#if defined(POLARSSL_PEM_PARSE_C)
39 40 41 42 43 44 45
#include "polarssl/pem.h"
#endif

#if defined(POLARSSL_ASN1_PARSE_C)
#include "polarssl/asn1.h"
#endif

46 47
#if defined(POLARSSL_PLATFORM_C)
#include "polarssl/platform.h"
48 49
#else
#include <stdlib.h>
50
#define polarssl_printf     printf
51 52 53 54
#define polarssl_malloc     malloc
#define polarssl_free       free
#endif

55 56 57 58 59
/* Implementation that should never be optimized out by the compiler */
static void polarssl_zeroize( void *v, size_t n ) {
    volatile unsigned char *p = v; while( n-- ) *p++ = 0;
}

60 61 62 63 64
/*
 * helper to validate the mpi size and import it
 */
static int dhm_read_bignum( mpi *X,
                            unsigned char **p,
65
                            const unsigned char *end )
66 67 68 69
{
    int ret, n;

    if( end - *p < 2 )
70
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
71 72 73 74 75

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

    if( (int)( end - *p ) < n )
76
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
77 78

    if( ( ret = mpi_read_binary( X, *p, n ) ) != 0 )
79
        return( POLARSSL_ERR_DHM_READ_PARAMS_FAILED + ret );
80 81 82 83 84 85

    (*p) += n;

    return( 0 );
}

Paul Bakker's avatar
Paul Bakker committed
86
/*
87
 * Verify sanity of parameter with regards to P
88
 *
89
 * Parameter should be: 2 <= public_param <= P - 2
90 91 92 93
 *
 * 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
94
 */
95
static int dhm_check_range( const mpi *param, const mpi *P )
Paul Bakker's avatar
Paul Bakker committed
96
{
97 98
    mpi L, U;
    int ret = POLARSSL_ERR_DHM_BAD_INPUT_DATA;
Paul Bakker's avatar
Paul Bakker committed
99

100
    mpi_init( &L ); mpi_init( &U );
101 102 103

    MPI_CHK( mpi_lset( &L, 2 ) );
    MPI_CHK( mpi_sub_int( &U, P, 2 ) );
Paul Bakker's avatar
Paul Bakker committed
104

105 106
    if( mpi_cmp_mpi( param, &L ) >= 0 &&
        mpi_cmp_mpi( param, &U ) <= 0 )
Paul Bakker's avatar
Paul Bakker committed
107
    {
108
        ret = 0;
Paul Bakker's avatar
Paul Bakker committed
109 110
    }

111
cleanup:
112
    mpi_free( &L ); mpi_free( &U );
113
    return( ret );
Paul Bakker's avatar
Paul Bakker committed
114 115
}

Paul Bakker's avatar
Paul Bakker committed
116 117 118 119 120
void dhm_init( dhm_context *ctx )
{
    memset( ctx, 0, sizeof( dhm_context ) );
}

121 122 123 124 125
/*
 * Parse the ServerKeyExchange parameters
 */
int dhm_read_params( dhm_context *ctx,
                     unsigned char **p,
126
                     const unsigned char *end )
127
{
Paul Bakker's avatar
Paul Bakker committed
128
    int ret;
129 130 131 132 133 134

    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 );

135 136 137
    if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
        return( ret );

138 139 140 141 142 143 144 145 146
    ctx->len = mpi_size( &ctx->P );

    return( 0 );
}

/*
 * Setup and write the ServerKeyExchange parameters
 */
int dhm_make_params( dhm_context *ctx, int x_size,
147
                     unsigned char *output, size_t *olen,
148 149
                     int (*f_rng)(void *, unsigned char *, size_t),
                     void *p_rng )
150
{
151
    int ret, count = 0;
152
    size_t n1, n2, n3;
153 154
    unsigned char *p;

155 156 157
    if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );

158
    /*
159
     * Generate X as large as possible ( < P )
160
     */
161 162 163
    do
    {
        mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
164

165
        while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
166
            MPI_CHK( mpi_shift_r( &ctx->X, 1 ) );
167 168 169 170 171

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

173 174 175
    /*
     * Calculate GX = G^X mod P
     */
176 177 178
    MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
                          &ctx->P , &ctx->RP ) );

179
    if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
Paul Bakker's avatar
Paul Bakker committed
180 181
        return( ret );

182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205
    /*
     * 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 )
206
        return( POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED + ret );
207 208 209 210 211 212 213 214

    return( 0 );
}

/*
 * Import the peer's public value G^Y
 */
int dhm_read_public( dhm_context *ctx,
215
                     const unsigned char *input, size_t ilen )
216 217 218 219
{
    int ret;

    if( ctx == NULL || ilen < 1 || ilen > ctx->len )
220
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
221 222

    if( ( ret = mpi_read_binary( &ctx->GY, input, ilen ) ) != 0 )
223
        return( POLARSSL_ERR_DHM_READ_PUBLIC_FAILED + ret );
224 225 226 227 228 229 230 231

    return( 0 );
}

/*
 * Create own private value X and export G^X
 */
int dhm_make_public( dhm_context *ctx, int x_size,
232
                     unsigned char *output, size_t olen,
233 234
                     int (*f_rng)(void *, unsigned char *, size_t),
                     void *p_rng )
235
{
236
    int ret, count = 0;
237 238

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

241 242 243
    if( mpi_cmp_int( &ctx->P, 0 ) == 0 )
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );

244 245 246
    /*
     * generate X and calculate GX = G^X mod P
     */
247 248 249
    do
    {
        mpi_fill_random( &ctx->X, x_size, f_rng, p_rng );
250

251
        while( mpi_cmp_mpi( &ctx->X, &ctx->P ) >= 0 )
252
            MPI_CHK( mpi_shift_r( &ctx->X, 1 ) );
253 254 255 256 257

        if( count++ > 10 )
            return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED );
    }
    while( dhm_check_range( &ctx->X, &ctx->P ) != 0 );
258 259 260 261

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

262 263
    if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
        return( ret );
Paul Bakker's avatar
Paul Bakker committed
264

265 266 267 268 269
    MPI_CHK( mpi_write_binary( &ctx->GX, output, olen ) );

cleanup:

    if( ret != 0 )
270
        return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED + ret );
271 272 273 274

    return( 0 );
}

275 276 277 278 279 280 281 282 283 284 285 286
/*
 * 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;

    /*
287 288
     * Don't use any blinding the first time a particular X is used,
     * but remember it to use blinding next time.
289
     */
290
    if( mpi_cmp_mpi( &ctx->X, &ctx->pX ) != 0 )
291
    {
292
        MPI_CHK( mpi_copy( &ctx->pX, &ctx->X ) );
293 294 295 296
        MPI_CHK( mpi_lset( &ctx->Vi, 1 ) );
        MPI_CHK( mpi_lset( &ctx->Vf, 1 ) );

        return( 0 );
297 298 299
    }

    /*
300 301
     * Ok, we need blinding. Can we re-use existing values?
     * If yes, just update them by squaring them.
302
     */
303
    if( mpi_cmp_int( &ctx->Vi, 1 ) != 0 )
304
    {
305 306 307
        MPI_CHK( mpi_mul_mpi( &ctx->Vi, &ctx->Vi, &ctx->Vi ) );
        MPI_CHK( mpi_mod_mpi( &ctx->Vi, &ctx->Vi, &ctx->P ) );

308 309
        MPI_CHK( mpi_mul_mpi( &ctx->Vf, &ctx->Vf, &ctx->Vf ) );
        MPI_CHK( mpi_mod_mpi( &ctx->Vf, &ctx->Vf, &ctx->P ) );
310

311
        return( 0 );
312
    }
313 314

    /*
315
     * We need to generate blinding values from scratch
316
     */
317

318 319 320 321 322 323 324
    /* 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 )
325
            MPI_CHK( mpi_shift_r( &ctx->Vi, 1 ) );
326 327 328 329 330 331

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

332 333 334 335 336 337 338 339
    /* 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 ) );

cleanup:
    return( ret );
}

340 341 342 343
/*
 * Derive and export the shared secret (G^Y)^X mod P
 */
int dhm_calc_secret( dhm_context *ctx,
344 345 346
                     unsigned char *output, size_t *olen,
                     int (*f_rng)(void *, unsigned char *, size_t),
                     void *p_rng )
347 348
{
    int ret;
349
    mpi GYb;
350

351
    if( ctx == NULL || *olen < ctx->len )
352
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
353

354
    if( ( ret = dhm_check_range( &ctx->GY, &ctx->P ) ) != 0 )
Paul Bakker's avatar
Paul Bakker committed
355 356
        return( ret );

357 358 359
    mpi_init( &GYb );

    /* Blind peer's value */
360
    if( f_rng != NULL )
361 362 363 364 365 366 367 368 369 370 371 372 373
    {
        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 */
374
    if( f_rng != NULL )
375 376 377 378 379
    {
        MPI_CHK( mpi_mul_mpi( &ctx->K, &ctx->K, &ctx->Vf ) );
        MPI_CHK( mpi_mod_mpi( &ctx->K, &ctx->K, &ctx->P ) );
    }

380 381 382 383 384
    *olen = mpi_size( &ctx->K );

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

cleanup:
385
    mpi_free( &GYb );
386 387

    if( ret != 0 )
388
        return( POLARSSL_ERR_DHM_CALC_SECRET_FAILED + ret );
389 390 391 392 393 394 395 396 397

    return( 0 );
}

/*
 * Free the components of a DHM key
 */
void dhm_free( dhm_context *ctx )
{
398
    mpi_free( &ctx->pX); mpi_free( &ctx->Vf ); mpi_free( &ctx->Vi );
399 400 401
    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 );
402

403
    polarssl_zeroize( ctx, sizeof( dhm_context ) );
404 405
}

406 407 408 409
#if defined(POLARSSL_ASN1_PARSE_C)
/*
 * Parse DHM parameters
 */
410 411
int dhm_parse_dhm( dhm_context *dhm, const unsigned char *dhmin,
                   size_t dhminlen )
412 413 414 415
{
    int ret;
    size_t len;
    unsigned char *p, *end;
416
#if defined(POLARSSL_PEM_PARSE_C)
417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438
    pem_context pem;

    pem_init( &pem );

    ret = pem_read_buffer( &pem,
                           "-----BEGIN DH PARAMETERS-----",
                           "-----END DH PARAMETERS-----",
                           dhmin, NULL, 0, &dhminlen );

    if( ret == 0 )
    {
        /*
         * Was PEM encoded
         */
        dhminlen = pem.buflen;
    }
    else if( ret != POLARSSL_ERR_PEM_NO_HEADER_FOOTER_PRESENT )
        goto exit;

    p = ( ret == 0 ) ? pem.buf : (unsigned char *) dhmin;
#else
    p = (unsigned char *) dhmin;
439
#endif /* POLARSSL_PEM_PARSE_C */
440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472
    end = p + dhminlen;

    /*
     *  DHParams ::= SEQUENCE {
     *      prime            INTEGER,  -- P
     *      generator        INTEGER,  -- g
     *  }
     */
    if( ( ret = asn1_get_tag( &p, end, &len,
            ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 )
    {
        ret = POLARSSL_ERR_DHM_INVALID_FORMAT + ret;
        goto exit;
    }

    end = p + len;

    if( ( ret = asn1_get_mpi( &p, end, &dhm->P  ) ) != 0 ||
        ( ret = asn1_get_mpi( &p, end, &dhm->G ) ) != 0 )
    {
        ret = POLARSSL_ERR_DHM_INVALID_FORMAT + ret;
        goto exit;
    }

    if( p != end )
    {
        ret = POLARSSL_ERR_DHM_INVALID_FORMAT +
              POLARSSL_ERR_ASN1_LENGTH_MISMATCH;
        goto exit;
    }

    ret = 0;

473 474
    dhm->len = mpi_size( &dhm->P );

475
exit:
476
#if defined(POLARSSL_PEM_PARSE_C)
477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536
    pem_free( &pem );
#endif
    if( ret != 0 )
        dhm_free( dhm );

    return( ret );
}

#if defined(POLARSSL_FS_IO)
/*
 * Load all data from a file into a given buffer.
 */
static int load_file( const char *path, unsigned char **buf, size_t *n )
{
    FILE *f;
    long size;

    if( ( f = fopen( path, "rb" ) ) == NULL )
        return( POLARSSL_ERR_DHM_FILE_IO_ERROR );

    fseek( f, 0, SEEK_END );
    if( ( size = ftell( f ) ) == -1 )
    {
        fclose( f );
        return( POLARSSL_ERR_DHM_FILE_IO_ERROR );
    }
    fseek( f, 0, SEEK_SET );

    *n = (size_t) size;

    if( *n + 1 == 0 ||
        ( *buf = (unsigned char *) polarssl_malloc( *n + 1 ) ) == NULL )
    {
        fclose( f );
        return( POLARSSL_ERR_DHM_MALLOC_FAILED );
    }

    if( fread( *buf, 1, *n, f ) != *n )
    {
        fclose( f );
        polarssl_free( *buf );
        return( POLARSSL_ERR_DHM_FILE_IO_ERROR );
    }

    fclose( f );

    (*buf)[*n] = '\0';

    return( 0 );
}

/*
 * Load and parse DHM parameters
 */
int dhm_parse_dhmfile( dhm_context *dhm, const char *path )
{
    int ret;
    size_t n;
    unsigned char *buf;

537
    if( ( ret = load_file( path, &buf, &n ) ) != 0 )
538 539 540 541
        return( ret );

    ret = dhm_parse_dhm( dhm, buf, n );

542
    polarssl_zeroize( buf, n + 1 );
543 544 545 546 547 548 549
    polarssl_free( buf );

    return( ret );
}
#endif /* POLARSSL_FS_IO */
#endif /* POLARSSL_ASN1_PARSE_C */

550
#if defined(POLARSSL_SELF_TEST)
551

552 553
#include "polarssl/certs.h"

554 555 556 557 558
/*
 * Checkup routine
 */
int dhm_self_test( int verbose )
{
559 560 561 562
#if defined(POLARSSL_CERTS_C)
    int ret;
    dhm_context dhm;

Paul Bakker's avatar
Paul Bakker committed
563 564
    dhm_init( &dhm );

565
    if( verbose != 0 )
566
        polarssl_printf( "  DHM parameter load: " );
567 568 569 570 571

    if( ( ret = dhm_parse_dhm( &dhm, (const unsigned char *) test_dhm_params,
                               strlen( test_dhm_params ) ) ) != 0 )
    {
        if( verbose != 0 )
572
            polarssl_printf( "failed\n" );
573

574
        ret = 1;
Paul Bakker's avatar
Paul Bakker committed
575
        goto exit;
576 577 578
    }

    if( verbose != 0 )
579
        polarssl_printf( "passed\n\n" );
580

Paul Bakker's avatar
Paul Bakker committed
581
exit:
582 583
    dhm_free( &dhm );

Paul Bakker's avatar
Paul Bakker committed
584
    return( ret );
585
#else
586 587 588 589
    if( verbose != 0 )
        polarssl_printf( "  DHM parameter load: skipped\n" );

    return( 0 );
590
#endif /* POLARSSL_CERTS_C */
591 592
}

593
#endif /* POLARSSL_SELF_TEST */
594

595
#endif /* POLARSSL_DHM_C */