reactos/dll/3rdparty/mbedtls/ecdsa.c

   1 /*
   2  *  Elliptic curve DSA
   3  *
   4  *  Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
   5  *  SPDX-License-Identifier: GPL-2.0
   6  *
   7  *  This program is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation; either version 2 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  This program is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License along
  18  *  with this program; if not, write to the Free Software Foundation, Inc.,
  19  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  *  This file is part of mbed TLS (https://tls.mbed.org)
  22  */
  23
  24 /*
  25  * References:
  26  *
  27  * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
  28  */
  29
  30 #if !defined(MBEDTLS_CONFIG_FILE)
  31 #include "mbedtls/config.h"
  32 #else
  33 #include MBEDTLS_CONFIG_FILE
  34 #endif
  35
  36 #if defined(MBEDTLS_ECDSA_C)
  37
  38 #include "mbedtls/ecdsa.h"
  39 #include "mbedtls/asn1write.h"
  40
  41 #include <string.h>
  42
  43 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
  44 #include "mbedtls/hmac_drbg.h"
  45 #endif
  46
  47 /*
  48  * Derive a suitable integer for group grp from a buffer of length len
  49  * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
  50  */
  51 static int derive_mpi( const mbedtls_ecp_group *grp, mbedtls_mpi *x,
  52                        const unsigned char *buf, size_t blen )
  53 {
  54     int ret;
  55     size_t n_size = ( grp->nbits + 7 ) / 8;
  56     size_t use_size = blen > n_size ? n_size : blen;
  57
  58     MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( x, buf, use_size ) );
  59     if( use_size * 8 > grp->nbits )
  60         MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( x, use_size * 8 - grp->nbits ) );
  61
  62     /* While at it, reduce modulo N */
  63     if( mbedtls_mpi_cmp_mpi( x, &grp->N ) >= 0 )
  64         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( x, x, &grp->N ) );
  65
  66 cleanup:
  67     return( ret );
  68 }
  69
  70 /*
  71  * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
  72  * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
  73  */
  74 int mbedtls_ecdsa_sign( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
  75                 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
  76                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
  77 {
  78     int ret, key_tries, sign_tries, blind_tries;
  79     mbedtls_ecp_point R;
  80     mbedtls_mpi k, e, t;
  81
  82     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
  83     if( grp->N.p == NULL )
  84         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
  85
  86     mbedtls_ecp_point_init( &R );
  87     mbedtls_mpi_init( &k ); mbedtls_mpi_init( &e ); mbedtls_mpi_init( &t );
  88
  89     sign_tries = 0;
  90     do
  91     {
  92         /*
  93          * Steps 1-3: generate a suitable ephemeral keypair
  94          * and set r = xR mod n
  95          */
  96         key_tries = 0;
  97         do
  98         {
  99             MBEDTLS_MPI_CHK( mbedtls_ecp_gen_keypair( grp, &k, &R, f_rng, p_rng ) );
 100             MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( r, &R.X, &grp->N ) );
 101
 102             if( key_tries++ > 10 )
 103             {
 104                 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
 105                 goto cleanup;
 106             }
 107         }
 108         while( mbedtls_mpi_cmp_int( r, 0 ) == 0 );
 109
 110         /*
 111          * Step 5: derive MPI from hashed message
 112          */
 113         MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
 114
 115         /*
 116          * Generate a random value to blind inv_mod in next step,
 117          * avoiding a potential timing leak.
 118          */
 119         blind_tries = 0;
 120         do
 121         {
 122             size_t n_size = ( grp->nbits + 7 ) / 8;
 123             MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &t, n_size, f_rng, p_rng ) );
 124             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &t, 8 * n_size - grp->nbits ) );
 125
 126             /* See mbedtls_ecp_gen_keypair() */
 127             if( ++blind_tries > 30 )
 128                 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
 129         }
 130         while( mbedtls_mpi_cmp_int( &t, 1 ) < 0 ||
 131                mbedtls_mpi_cmp_mpi( &t, &grp->N ) >= 0 );
 132
 133         /*
 134          * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
 135          */
 136         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, r, d ) );
 137         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &e, &e, s ) );
 138         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &e, &e, &t ) );
 139         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &k, &k, &t ) );
 140         MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( s, &k, &grp->N ) );
 141         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, s, &e ) );
 142         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( s, s, &grp->N ) );
 143
 144         if( sign_tries++ > 10 )
 145         {
 146             ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
 147             goto cleanup;
 148         }
 149     }
 150     while( mbedtls_mpi_cmp_int( s, 0 ) == 0 );
 151
 152 cleanup:
 153     mbedtls_ecp_point_free( &R );
 154     mbedtls_mpi_free( &k ); mbedtls_mpi_free( &e ); mbedtls_mpi_free( &t );
 155
 156     return( ret );
 157 }
 158
 159 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
 160 /*
 161  * Deterministic signature wrapper
 162  */
 163 int mbedtls_ecdsa_sign_det( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
 164                     const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
 165                     mbedtls_md_type_t md_alg )
 166 {
 167     int ret;
 168     mbedtls_hmac_drbg_context rng_ctx;
 169     unsigned char data[2 * MBEDTLS_ECP_MAX_BYTES];
 170     size_t grp_len = ( grp->nbits + 7 ) / 8;
 171     const mbedtls_md_info_t *md_info;
 172     mbedtls_mpi h;
 173
 174     if( ( md_info = mbedtls_md_info_from_type( md_alg ) ) == NULL )
 175         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
 176
 177     mbedtls_mpi_init( &h );
 178     mbedtls_hmac_drbg_init( &rng_ctx );
 179
 180     /* Use private key and message hash (reduced) to initialize HMAC_DRBG */
 181     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( d, data, grp_len ) );
 182     MBEDTLS_MPI_CHK( derive_mpi( grp, &h, buf, blen ) );
 183     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &h, data + grp_len, grp_len ) );
 184     mbedtls_hmac_drbg_seed_buf( &rng_ctx, md_info, data, 2 * grp_len );
 185
 186     ret = mbedtls_ecdsa_sign( grp, r, s, d, buf, blen,
 187                       mbedtls_hmac_drbg_random, &rng_ctx );
 188
 189 cleanup:
 190     mbedtls_hmac_drbg_free( &rng_ctx );
 191     mbedtls_mpi_free( &h );
 192
 193     return( ret );
 194 }
 195 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
 196
 197 /*
 198  * Verify ECDSA signature of hashed message (SEC1 4.1.4)
 199  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
 200  */
 201 int mbedtls_ecdsa_verify( mbedtls_ecp_group *grp,
 202                   const unsigned char *buf, size_t blen,
 203                   const mbedtls_ecp_point *Q, const mbedtls_mpi *r, const mbedtls_mpi *s)
 204 {
 205     int ret;
 206     mbedtls_mpi e, s_inv, u1, u2;
 207     mbedtls_ecp_point R;
 208
 209     mbedtls_ecp_point_init( &R );
 210     mbedtls_mpi_init( &e ); mbedtls_mpi_init( &s_inv ); mbedtls_mpi_init( &u1 ); mbedtls_mpi_init( &u2 );
 211
 212     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
 213     if( grp->N.p == NULL )
 214         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
 215
 216     /*
 217      * Step 1: make sure r and s are in range 1..n-1
 218      */
 219     if( mbedtls_mpi_cmp_int( r, 1 ) < 0 || mbedtls_mpi_cmp_mpi( r, &grp->N ) >= 0 ||
 220         mbedtls_mpi_cmp_int( s, 1 ) < 0 || mbedtls_mpi_cmp_mpi( s, &grp->N ) >= 0 )
 221     {
 222         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
 223         goto cleanup;
 224     }
 225
 226     /*
 227      * Additional precaution: make sure Q is valid
 228      */
 229     MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, Q ) );
 230
 231     /*
 232      * Step 3: derive MPI from hashed message
 233      */
 234     MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
 235
 236     /*
 237      * Step 4: u1 = e / s mod n, u2 = r / s mod n
 238      */
 239     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &s_inv, s, &grp->N ) );
 240
 241     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u1, &e, &s_inv ) );
 242     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &u1, &u1, &grp->N ) );
 243
 244     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u2, r, &s_inv ) );
 245     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &u2, &u2, &grp->N ) );
 246
 247     /*
 248      * Step 5: R = u1 G + u2 Q
 249      *
 250      * Since we're not using any secret data, no need to pass a RNG to
 251      * mbedtls_ecp_mul() for countermesures.
 252      */
 253     MBEDTLS_MPI_CHK( mbedtls_ecp_muladd( grp, &R, &u1, &grp->G, &u2, Q ) );
 254
 255     if( mbedtls_ecp_is_zero( &R ) )
 256     {
 257         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
 258         goto cleanup;
 259     }
 260
 261     /*
 262      * Step 6: convert xR to an integer (no-op)
 263      * Step 7: reduce xR mod n (gives v)
 264      */
 265     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &R.X, &R.X, &grp->N ) );
 266
 267     /*
 268      * Step 8: check if v (that is, R.X) is equal to r
 269      */
 270     if( mbedtls_mpi_cmp_mpi( &R.X, r ) != 0 )
 271     {
 272         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
 273         goto cleanup;
 274     }
 275
 276 cleanup:
 277     mbedtls_ecp_point_free( &R );
 278     mbedtls_mpi_free( &e ); mbedtls_mpi_free( &s_inv ); mbedtls_mpi_free( &u1 ); mbedtls_mpi_free( &u2 );
 279
 280     return( ret );
 281 }
 282
 283 /*
 284  * Convert a signature (given by context) to ASN.1
 285  */
 286 static int ecdsa_signature_to_asn1( const mbedtls_mpi *r, const mbedtls_mpi *s,
 287                                     unsigned char *sig, size_t *slen )
 288 {
 289     int ret;
 290     unsigned char buf[MBEDTLS_ECDSA_MAX_LEN];
 291     unsigned char *p = buf + sizeof( buf );
 292     size_t len = 0;
 293
 294     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, s ) );
 295     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, r ) );
 296
 297     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_len( &p, buf, len ) );
 298     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_tag( &p, buf,
 299                                        MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) );
 300
 301     memcpy( sig, p, len );
 302     *slen = len;
 303
 304     return( 0 );
 305 }
 306
 307 /*
 308  * Compute and write signature
 309  */
 310 int mbedtls_ecdsa_write_signature( mbedtls_ecdsa_context *ctx, mbedtls_md_type_t md_alg,
 311                            const unsigned char *hash, size_t hlen,
 312                            unsigned char *sig, size_t *slen,
 313                            int (*f_rng)(void *, unsigned char *, size_t),
 314                            void *p_rng )
 315 {
 316     int ret;
 317     mbedtls_mpi r, s;
 318
 319     mbedtls_mpi_init( &r );
 320     mbedtls_mpi_init( &s );
 321
 322 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
 323     (void) f_rng;
 324     (void) p_rng;
 325
 326     MBEDTLS_MPI_CHK( mbedtls_ecdsa_sign_det( &ctx->grp, &r, &s, &ctx->d,
 327                              hash, hlen, md_alg ) );
 328 #else
 329     (void) md_alg;
 330
 331     MBEDTLS_MPI_CHK( mbedtls_ecdsa_sign( &ctx->grp, &r, &s, &ctx->d,
 332                          hash, hlen, f_rng, p_rng ) );
 333 #endif
 334
 335     MBEDTLS_MPI_CHK( ecdsa_signature_to_asn1( &r, &s, sig, slen ) );
 336
 337 cleanup:
 338     mbedtls_mpi_free( &r );
 339     mbedtls_mpi_free( &s );
 340
 341     return( ret );
 342 }
 343
 344 #if ! defined(MBEDTLS_DEPRECATED_REMOVED) && \
 345     defined(MBEDTLS_ECDSA_DETERMINISTIC)
 346 int mbedtls_ecdsa_write_signature_det( mbedtls_ecdsa_context *ctx,
 347                                const unsigned char *hash, size_t hlen,
 348                                unsigned char *sig, size_t *slen,
 349                                mbedtls_md_type_t md_alg )
 350 {
 351     return( mbedtls_ecdsa_write_signature( ctx, md_alg, hash, hlen, sig, slen,
 352                                    NULL, NULL ) );
 353 }
 354 #endif
 355
 356 /*
 357  * Read and check signature
 358  */
 359 int mbedtls_ecdsa_read_signature( mbedtls_ecdsa_context *ctx,
 360                           const unsigned char *hash, size_t hlen,
 361                           const unsigned char *sig, size_t slen )
 362 {
 363     int ret;
 364     unsigned char *p = (unsigned char *) sig;
 365     const unsigned char *end = sig + slen;
 366     size_t len;
 367     mbedtls_mpi r, s;
 368
 369     mbedtls_mpi_init( &r );
 370     mbedtls_mpi_init( &s );
 371
 372     if( ( ret = mbedtls_asn1_get_tag( &p, end, &len,
 373                     MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) ) != 0 )
 374     {
 375         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
 376         goto cleanup;
 377     }
 378
 379     if( p + len != end )
 380     {
 381         ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA +
 382               MBEDTLS_ERR_ASN1_LENGTH_MISMATCH;
 383         goto cleanup;
 384     }
 385
 386     if( ( ret = mbedtls_asn1_get_mpi( &p, end, &r ) ) != 0 ||
 387         ( ret = mbedtls_asn1_get_mpi( &p, end, &s ) ) != 0 )
 388     {
 389         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
 390         goto cleanup;
 391     }
 392
 393     if( ( ret = mbedtls_ecdsa_verify( &ctx->grp, hash, hlen,
 394                               &ctx->Q, &r, &s ) ) != 0 )
 395         goto cleanup;
 396
 397     if( p != end )
 398         ret = MBEDTLS_ERR_ECP_SIG_LEN_MISMATCH;
 399
 400 cleanup:
 401     mbedtls_mpi_free( &r );
 402     mbedtls_mpi_free( &s );
 403
 404     return( ret );
 405 }
 406
 407 /*
 408  * Generate key pair
 409  */
 410 int mbedtls_ecdsa_genkey( mbedtls_ecdsa_context *ctx, mbedtls_ecp_group_id gid,
 411                   int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
 412 {
 413     return( mbedtls_ecp_group_load( &ctx->grp, gid ) ||
 414             mbedtls_ecp_gen_keypair( &ctx->grp, &ctx->d, &ctx->Q, f_rng, p_rng ) );
 415 }
 416
 417 /*
 418  * Set context from an mbedtls_ecp_keypair
 419  */
 420 int mbedtls_ecdsa_from_keypair( mbedtls_ecdsa_context *ctx, const mbedtls_ecp_keypair *key )
 421 {
 422     int ret;
 423
 424     if( ( ret = mbedtls_ecp_group_copy( &ctx->grp, &key->grp ) ) != 0 ||
 425         ( ret = mbedtls_mpi_copy( &ctx->d, &key->d ) ) != 0 ||
 426         ( ret = mbedtls_ecp_copy( &ctx->Q, &key->Q ) ) != 0 )
 427     {
 428         mbedtls_ecdsa_free( ctx );
 429     }
 430
 431     return( ret );
 432 }
 433
 434 /*
 435  * Initialize context
 436  */
 437 void mbedtls_ecdsa_init( mbedtls_ecdsa_context *ctx )
 438 {
 439     mbedtls_ecp_keypair_init( ctx );
 440 }
 441
 442 /*
 443  * Free context
 444  */
 445 void mbedtls_ecdsa_free( mbedtls_ecdsa_context *ctx )
 446 {
 447     mbedtls_ecp_keypair_free( ctx );
 448 }
 449
 450 #endif /* MBEDTLS_ECDSA_C */