dhm.c 7.1 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 42 43

#include <string.h>

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

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

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

    if( (int)( end - *p ) < n )
55
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
56 57

    if( ( ret = mpi_read_binary( X, *p, n ) ) != 0 )
58
        return( POLARSSL_ERR_DHM_READ_PARAMS_FAILED | ret );
59 60 61 62 63 64

    (*p) += n;

    return( 0 );
}

Paul Bakker's avatar
Paul Bakker committed
65
/*
66 67 68 69 70 71 72
 * Verify sanity of public parameter with regards to P
 *
 * Public parameter should be: 2 <= public_param <= P - 2
 *
 * 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
73
 */
74
static int dhm_check_range( const mpi *public_param, const mpi *P )
Paul Bakker's avatar
Paul Bakker committed
75
{
76 77
    mpi L, U;
    int ret = POLARSSL_ERR_DHM_BAD_INPUT_DATA;
Paul Bakker's avatar
Paul Bakker committed
78

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

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

89
    mpi_free( &L, &U, NULL );
Paul Bakker's avatar
Paul Bakker committed
90

91
    return( ret );
Paul Bakker's avatar
Paul Bakker committed
92 93
}

94 95 96 97 98
/*
 * Parse the ServerKeyExchange parameters
 */
int dhm_read_params( dhm_context *ctx,
                     unsigned char **p,
99
                     const unsigned char *end )
100 101 102 103 104 105 106 107 108 109
{
    int ret, n;

    memset( ctx, 0, sizeof( dhm_context ) );

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

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

113 114 115
    ctx->len = mpi_size( &ctx->P );

    if( end - *p < 2 )
116
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
117 118 119 120 121

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

    if( end != *p + n )
122
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
123 124 125 126 127 128 129 130 131 132 133 134 135 136 137

    return( 0 );
}

/*
 * Setup and write the ServerKeyExchange parameters
 */
int dhm_make_params( dhm_context *ctx, int x_size,
                     unsigned char *output, int *olen,
                     int (*f_rng)(void *), void *p_rng )
{
    int i, ret, n, n1, n2, n3;
    unsigned char *p;

    /*
138
     * Generate X as large as possible ( < P )
139
     */
Paul Bakker's avatar
Paul Bakker committed
140
    n = x_size / sizeof( t_int ) + 1;
141 142 143 144
    MPI_CHK( mpi_grow( &ctx->X, n ) );
    MPI_CHK( mpi_lset( &ctx->X, 0 ) );

    p = (unsigned char *) ctx->X.p;
Paul Bakker's avatar
Paul Bakker committed
145
    for( i = 0; i < x_size; i++ )
146 147 148 149 150
        *p++ = (unsigned char) f_rng( p_rng );

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

151 152 153
    /*
     * Calculate GX = G^X mod P
     */
154 155 156
    MPI_CHK( mpi_exp_mod( &ctx->GX, &ctx->G, &ctx->X,
                          &ctx->P , &ctx->RP ) );

157
    if( ( ret = dhm_check_range( &ctx->GX, &ctx->P ) ) != 0 )
Paul Bakker's avatar
Paul Bakker committed
158 159
        return( ret );

160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183
    /*
     * 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 )
184
        return( ret | POLARSSL_ERR_DHM_MAKE_PARAMS_FAILED );
185 186 187 188 189 190 191 192

    return( 0 );
}

/*
 * Import the peer's public value G^Y
 */
int dhm_read_public( dhm_context *ctx,
193
                     const unsigned char *input, int ilen )
194 195 196 197
{
    int ret;

    if( ctx == NULL || ilen < 1 || ilen > ctx->len )
198
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
199 200

    if( ( ret = mpi_read_binary( &ctx->GY, input, ilen ) ) != 0 )
201
        return( POLARSSL_ERR_DHM_READ_PUBLIC_FAILED | ret );
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216

    return( 0 );
}

/*
 * Create own private value X and export G^X
 */
int dhm_make_public( dhm_context *ctx, int x_size,
                     unsigned char *output, int olen,
                     int (*f_rng)(void *), void *p_rng )
{
    int ret, i, n;
    unsigned char *p;

    if( ctx == NULL || olen < 1 || olen > ctx->len )
217
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
218 219 220 221

    /*
     * generate X and calculate GX = G^X mod P
     */
Paul Bakker's avatar
Paul Bakker committed
222
    n = x_size / sizeof( t_int ) + 1;
223 224 225 226
    MPI_CHK( mpi_grow( &ctx->X, n ) );
    MPI_CHK( mpi_lset( &ctx->X, 0 ) );

    p = (unsigned char *) ctx->X.p;
Paul Bakker's avatar
Paul Bakker committed
227
    for( i = 0; i < x_size; i++ )
228 229 230 231 232 233 234 235
        *p++ = (unsigned char) f_rng( p_rng );

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

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

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

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

cleanup:

    if( ret != 0 )
244
        return( POLARSSL_ERR_DHM_MAKE_PUBLIC_FAILED | ret );
245 246 247 248 249 250 251 252 253 254 255 256 257

    return( 0 );
}

/*
 * Derive and export the shared secret (G^Y)^X mod P
 */
int dhm_calc_secret( dhm_context *ctx,
                     unsigned char *output, int *olen )
{
    int ret;

    if( ctx == NULL || *olen < ctx->len )
258
        return( POLARSSL_ERR_DHM_BAD_INPUT_DATA );
259 260 261 262

    MPI_CHK( mpi_exp_mod( &ctx->K, &ctx->GY, &ctx->X,
                          &ctx->P, &ctx->RP ) );

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

266 267 268 269 270 271 272
    *olen = mpi_size( &ctx->K );

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

cleanup:

    if( ret != 0 )
273
        return( POLARSSL_ERR_DHM_CALC_SECRET_FAILED | ret );
274 275 276 277 278 279 280 281 282 283 284 285 286 287

    return( 0 );
}

/*
 * Free the components of a DHM key
 */
void dhm_free( dhm_context *ctx )
{
    mpi_free( &ctx->RP, &ctx->K, &ctx->GY,
              &ctx->GX, &ctx->X, &ctx->G,
              &ctx->P, NULL );    
}

288
#if defined(POLARSSL_SELF_TEST)
289 290 291 292 293 294 295 296 297 298 299 300

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

#endif

#endif