ecdsa.c

00001 /*
00002  *  Elliptic curve DSA
00003  *
00004  *  Copyright (C) 2006-2014, ARM Limited, All Rights Reserved
00005  *
00006  *  This file is part of mbed TLS (https://tls.mbed.org)
00007  *
00008  *  This program is free software; you can redistribute it and/or modify
00009  *  it under the terms of the GNU General Public License as published by
00010  *  the Free Software Foundation; either version 2 of the License, or
00011  *  (at your option) any later version.
00012  *
00013  *  This program is distributed in the hope that it will be useful,
00014  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00015  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016  *  GNU General Public License for more details.
00017  *
00018  *  You should have received a copy of the GNU General Public License along
00019  *  with this program; if not, write to the Free Software Foundation, Inc.,
00020  *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
00021  */
00022 
00023 /*
00024  * References:
00025  *
00026  * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
00027  */
00028 
00029 #if !defined(POLARSSL_CONFIG_FILE)
00030 #include "polarssl/config.h"
00031 #else
00032 #include POLARSSL_CONFIG_FILE
00033 #endif
00034 
00035 #if defined(POLARSSL_ECDSA_C)
00036 
00037 #include "polarssl/ecdsa.h"
00038 #include "polarssl/asn1write.h"
00039 
00040 #include <string.h>
00041 
00042 #if defined(POLARSSL_ECDSA_DETERMINISTIC)
00043 #include "polarssl/hmac_drbg.h"
00044 #endif
00045 
00046 #if defined(POLARSSL_ECDSA_DETERMINISTIC)
00047 /*
00048  * This a hopefully temporary compatibility function.
00049  *
00050  * Since we can't ensure the caller will pass a valid md_alg before the next
00051  * interface change, try to pick up a decent md by size.
00052  *
00053  * Argument is the minimum size in bytes of the MD output.
00054  */
00055 static const md_info_t *md_info_by_size( size_t min_size )
00056 {
00057     const md_info_t *md_cur, *md_picked = NULL;
00058     const int *md_alg;
00059 
00060     for( md_alg = md_list(); *md_alg != 0; md_alg++ )
00061     {
00062         if( ( md_cur = md_info_from_type( (md_type_t) *md_alg ) ) == NULL ||
00063             (size_t) md_cur->size < min_size ||
00064             ( md_picked != NULL && md_cur->size > md_picked->size ) )
00065             continue;
00066 
00067         md_picked = md_cur;
00068     }
00069 
00070     return( md_picked );
00071 }
00072 #endif /* POLARSSL_ECDSA_DETERMINISTIC */
00073 
00074 /*
00075  * Derive a suitable integer for group grp from a buffer of length len
00076  * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
00077  */
00078 static int derive_mpi( const ecp_group *grp, mpi *x,
00079                        const unsigned char *buf, size_t blen )
00080 {
00081     int ret;
00082     size_t n_size = ( grp->nbits  + 7 ) / 8;
00083     size_t use_size = blen > n_size ? n_size : blen;
00084 
00085     MPI_CHK( mpi_read_binary( x, buf, use_size ) );
00086     if( use_size * 8 > grp->nbits  )
00087         MPI_CHK( mpi_shift_r( x, use_size * 8 - grp->nbits  ) );
00088 
00089     /* While at it, reduce modulo N */
00090     if( mpi_cmp_mpi( x, &grp->N  ) >= 0 )
00091         MPI_CHK( mpi_sub_mpi( x, x, &grp->N  ) );
00092 
00093 cleanup:
00094     return( ret );
00095 }
00096 
00097 /*
00098  * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
00099  * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
00100  */
00101 int ecdsa_sign( ecp_group *grp, mpi *r, mpi *s,
00102                 const mpi *d, const unsigned char *buf, size_t blen,
00103                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
00104 {
00105     int ret, key_tries, sign_tries, blind_tries;
00106     ecp_point R;
00107     mpi k, e, t;
00108 
00109     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
00110     if( grp->N .p  == NULL )
00111         return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
00112 
00113     ecp_point_init( &R );
00114     mpi_init( &k ); mpi_init( &e ); mpi_init( &t );
00115 
00116     sign_tries = 0;
00117     do
00118     {
00119         /*
00120          * Steps 1-3: generate a suitable ephemeral keypair
00121          * and set r = xR mod n
00122          */
00123         key_tries = 0;
00124         do
00125         {
00126             MPI_CHK( ecp_gen_keypair( grp, &k, &R, f_rng, p_rng ) );
00127             MPI_CHK( mpi_mod_mpi( r, &R.X , &grp->N  ) );
00128 
00129             if( key_tries++ > 10 )
00130             {
00131                 ret = POLARSSL_ERR_ECP_RANDOM_FAILED;
00132                 goto cleanup;
00133             }
00134         }
00135         while( mpi_cmp_int( r, 0 ) == 0 );
00136 
00137         /*
00138          * Step 5: derive MPI from hashed message
00139          */
00140         MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
00141 
00142         /*
00143          * Generate a random value to blind inv_mod in next step,
00144          * avoiding a potential timing leak.
00145          */
00146         blind_tries = 0;
00147         do
00148         {
00149             size_t n_size = ( grp->nbits  + 7 ) / 8;
00150             MPI_CHK( mpi_fill_random( &t, n_size, f_rng, p_rng ) );
00151             MPI_CHK( mpi_shift_r( &t, 8 * n_size - grp->nbits  ) );
00152 
00153             /* See ecp_gen_keypair() */
00154             if( ++blind_tries > 30 )
00155                 return( POLARSSL_ERR_ECP_RANDOM_FAILED );
00156         }
00157         while( mpi_cmp_int( &t, 1 ) < 0 ||
00158                mpi_cmp_mpi( &t, &grp->N  ) >= 0 );
00159 
00160         /*
00161          * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
00162          */
00163         MPI_CHK( mpi_mul_mpi( s, r, d ) );
00164         MPI_CHK( mpi_add_mpi( &e, &e, s ) );
00165         MPI_CHK( mpi_mul_mpi( &e, &e, &t ) );
00166         MPI_CHK( mpi_mul_mpi( &k, &k, &t ) );
00167         MPI_CHK( mpi_inv_mod( s, &k, &grp->N  ) );
00168         MPI_CHK( mpi_mul_mpi( s, s, &e ) );
00169         MPI_CHK( mpi_mod_mpi( s, s, &grp->N  ) );
00170 
00171         if( sign_tries++ > 10 )
00172         {
00173             ret = POLARSSL_ERR_ECP_RANDOM_FAILED;
00174             goto cleanup;
00175         }
00176     }
00177     while( mpi_cmp_int( s, 0 ) == 0 );
00178 
00179 cleanup:
00180     ecp_point_free( &R );
00181     mpi_free( &k ); mpi_free( &e ); mpi_free( &t );
00182 
00183     return( ret );
00184 }
00185 
00186 #if defined(POLARSSL_ECDSA_DETERMINISTIC)
00187 /*
00188  * Deterministic signature wrapper
00189  */
00190 int ecdsa_sign_det( ecp_group *grp, mpi *r, mpi *s,
00191                     const mpi *d, const unsigned char *buf, size_t blen,
00192                     md_type_t md_alg )
00193 {
00194     int ret;
00195     hmac_drbg_context rng_ctx;
00196     unsigned char data[2 * POLARSSL_ECP_MAX_BYTES];
00197     size_t grp_len = ( grp->nbits  + 7 ) / 8;
00198     const md_info_t *md_info;
00199     mpi h;
00200 
00201     /* Temporary fallback */
00202     if( md_alg == POLARSSL_MD_NONE )
00203         md_info = md_info_by_size( blen );
00204     else
00205         md_info = md_info_from_type( md_alg );
00206 
00207     if( md_info == NULL )
00208         return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
00209 
00210     mpi_init( &h );
00211     memset( &rng_ctx, 0, sizeof( hmac_drbg_context ) );
00212 
00213     /* Use private key and message hash (reduced) to initialize HMAC_DRBG */
00214     MPI_CHK( mpi_write_binary( d, data, grp_len ) );
00215     MPI_CHK( derive_mpi( grp, &h, buf, blen ) );
00216     MPI_CHK( mpi_write_binary( &h, data + grp_len, grp_len ) );
00217     hmac_drbg_init_buf( &rng_ctx, md_info, data, 2 * grp_len );
00218 
00219     ret = ecdsa_sign( grp, r, s, d, buf, blen,
00220                       hmac_drbg_random, &rng_ctx );
00221 
00222 cleanup:
00223     hmac_drbg_free( &rng_ctx );
00224     mpi_free( &h );
00225 
00226     return( ret );
00227 }
00228 #endif /* POLARSSL_ECDSA_DETERMINISTIC */
00229 
00230 /*
00231  * Verify ECDSA signature of hashed message (SEC1 4.1.4)
00232  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
00233  */
00234 int ecdsa_verify( ecp_group *grp,
00235                   const unsigned char *buf, size_t blen,
00236                   const ecp_point *Q, const mpi *r, const mpi *s)
00237 {
00238     int ret;
00239     mpi e, s_inv, u1, u2;
00240     ecp_point R, P;
00241 
00242     ecp_point_init( &R ); ecp_point_init( &P );
00243     mpi_init( &e ); mpi_init( &s_inv ); mpi_init( &u1 ); mpi_init( &u2 );
00244 
00245     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
00246     if( grp->N .p  == NULL )
00247         return( POLARSSL_ERR_ECP_BAD_INPUT_DATA );
00248 
00249     /*
00250      * Step 1: make sure r and s are in range 1..n-1
00251      */
00252     if( mpi_cmp_int( r, 1 ) < 0 || mpi_cmp_mpi( r, &grp->N  ) >= 0 ||
00253         mpi_cmp_int( s, 1 ) < 0 || mpi_cmp_mpi( s, &grp->N  ) >= 0 )
00254     {
00255         ret = POLARSSL_ERR_ECP_VERIFY_FAILED;
00256         goto cleanup;
00257     }
00258 
00259     /*
00260      * Additional precaution: make sure Q is valid
00261      */
00262     MPI_CHK( ecp_check_pubkey( grp, Q ) );
00263 
00264     /*
00265      * Step 3: derive MPI from hashed message
00266      */
00267     MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
00268 
00269     /*
00270      * Step 4: u1 = e / s mod n, u2 = r / s mod n
00271      */
00272     MPI_CHK( mpi_inv_mod( &s_inv, s, &grp->N  ) );
00273 
00274     MPI_CHK( mpi_mul_mpi( &u1, &e, &s_inv ) );
00275     MPI_CHK( mpi_mod_mpi( &u1, &u1, &grp->N  ) );
00276 
00277     MPI_CHK( mpi_mul_mpi( &u2, r, &s_inv ) );
00278     MPI_CHK( mpi_mod_mpi( &u2, &u2, &grp->N  ) );
00279 
00280     /*
00281      * Step 5: R = u1 G + u2 Q
00282      *
00283      * Since we're not using any secret data, no need to pass a RNG to
00284      * ecp_mul() for countermesures.
00285      */
00286     MPI_CHK( ecp_mul( grp, &R, &u1, &grp->G , NULL, NULL ) );
00287     MPI_CHK( ecp_mul( grp, &P, &u2, Q, NULL, NULL ) );
00288     MPI_CHK( ecp_add( grp, &R, &R, &P ) );
00289 
00290     if( ecp_is_zero( &R ) )
00291     {
00292         ret = POLARSSL_ERR_ECP_VERIFY_FAILED;
00293         goto cleanup;
00294     }
00295 
00296     /*
00297      * Step 6: convert xR to an integer (no-op)
00298      * Step 7: reduce xR mod n (gives v)
00299      */
00300     MPI_CHK( mpi_mod_mpi( &R.X , &R.X , &grp->N  ) );
00301 
00302     /*
00303      * Step 8: check if v (that is, R.X) is equal to r
00304      */
00305     if( mpi_cmp_mpi( &R.X , r ) != 0 )
00306     {
00307         ret = POLARSSL_ERR_ECP_VERIFY_FAILED;
00308         goto cleanup;
00309     }
00310 
00311 cleanup:
00312     ecp_point_free( &R ); ecp_point_free( &P );
00313     mpi_free( &e ); mpi_free( &s_inv ); mpi_free( &u1 ); mpi_free( &u2 );
00314 
00315     return( ret );
00316 }
00317 
00318 /*
00319  * RFC 4492 page 20:
00320  *
00321  *     Ecdsa-Sig-Value ::= SEQUENCE {
00322  *         r       INTEGER,
00323  *         s       INTEGER
00324  *     }
00325  *
00326  * Size is at most
00327  *    1 (tag) + 1 (len) + 1 (initial 0) + ECP_MAX_BYTES for each of r and s,
00328  *    twice that + 1 (tag) + 2 (len) for the sequence
00329  * (assuming ECP_MAX_BYTES is less than 126 for r and s,
00330  * and less than 124 (total len <= 255) for the sequence)
00331  */
00332 #if POLARSSL_ECP_MAX_BYTES > 124
00333 #error "POLARSSL_ECP_MAX_BYTES bigger than expected, please fix MAX_SIG_LEN"
00334 #endif
00335 #define MAX_SIG_LEN ( 3 + 2 * ( 3 + POLARSSL_ECP_MAX_BYTES ) )
00336 
00337 /*
00338  * Convert a signature (given by context) to ASN.1
00339  */
00340 static int ecdsa_signature_to_asn1( ecdsa_context *ctx,
00341                                     unsigned char *sig, size_t *slen )
00342 {
00343     int ret;
00344     unsigned char buf[MAX_SIG_LEN];
00345     unsigned char *p = buf + sizeof( buf );
00346     size_t len = 0;
00347 
00348     ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->s  ) );
00349     ASN1_CHK_ADD( len, asn1_write_mpi( &p, buf, &ctx->r  ) );
00350 
00351     ASN1_CHK_ADD( len, asn1_write_len( &p, buf, len ) );
00352     ASN1_CHK_ADD( len, asn1_write_tag( &p, buf,
00353                                        ASN1_CONSTRUCTED | ASN1_SEQUENCE ) );
00354 
00355     memcpy( sig, p, len );
00356     *slen = len;
00357 
00358     return( 0 );
00359 }
00360 
00361 /*
00362  * Compute and write signature
00363  */
00364 int ecdsa_write_signature( ecdsa_context *ctx,
00365                            const unsigned char *hash, size_t hlen,
00366                            unsigned char *sig, size_t *slen,
00367                            int (*f_rng)(void *, unsigned char *, size_t),
00368                            void *p_rng )
00369 {
00370     int ret;
00371 
00372     if( ( ret = ecdsa_sign( &ctx->grp , &ctx->r , &ctx->s , &ctx->d ,
00373                             hash, hlen, f_rng, p_rng ) ) != 0 )
00374     {
00375         return( ret );
00376     }
00377 
00378     return( ecdsa_signature_to_asn1( ctx, sig, slen ) );
00379 }
00380 
00381 #if defined(POLARSSL_ECDSA_DETERMINISTIC)
00382 /*
00383  * Compute and write signature deterministically
00384  */
00385 int ecdsa_write_signature_det( ecdsa_context *ctx,
00386                                const unsigned char *hash, size_t hlen,
00387                                unsigned char *sig, size_t *slen,
00388                                md_type_t md_alg )
00389 {
00390     int ret;
00391 
00392     if( ( ret = ecdsa_sign_det( &ctx->grp , &ctx->r , &ctx->s , &ctx->d ,
00393                                 hash, hlen, md_alg ) ) != 0 )
00394     {
00395         return( ret );
00396     }
00397 
00398     return( ecdsa_signature_to_asn1( ctx, sig, slen ) );
00399 }
00400 #endif /* POLARSSL_ECDSA_DETERMINISTIC */
00401 
00402 /*
00403  * Read and check signature
00404  */
00405 int ecdsa_read_signature( ecdsa_context *ctx,
00406                           const unsigned char *hash, size_t hlen,
00407                           const unsigned char *sig, size_t slen )
00408 {
00409     int ret;
00410     unsigned char *p = (unsigned char *) sig;
00411     const unsigned char *end = sig + slen;
00412     size_t len;
00413 
00414     if( ( ret = asn1_get_tag( &p, end, &len,
00415                     ASN1_CONSTRUCTED | ASN1_SEQUENCE ) ) != 0 )
00416     {
00417         return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret );
00418     }
00419 
00420     if( p + len != end )
00421         return( POLARSSL_ERR_ECP_BAD_INPUT_DATA +
00422                 POLARSSL_ERR_ASN1_LENGTH_MISMATCH );
00423 
00424     if( ( ret = asn1_get_mpi( &p, end, &ctx->r  ) ) != 0 ||
00425         ( ret = asn1_get_mpi( &p, end, &ctx->s  ) ) != 0 )
00426         return( POLARSSL_ERR_ECP_BAD_INPUT_DATA + ret );
00427 
00428     if( ( ret = ecdsa_verify( &ctx->grp , hash, hlen,
00429                               &ctx->Q , &ctx->r , &ctx->s  ) ) != 0 )
00430         return( ret );
00431 
00432     if( p != end )
00433         return( POLARSSL_ERR_ECP_SIG_LEN_MISMATCH );
00434 
00435     return( 0 );
00436 }
00437 
00438 /*
00439  * Generate key pair
00440  */
00441 int ecdsa_genkey( ecdsa_context *ctx, ecp_group_id gid,
00442                   int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
00443 {
00444     return( ecp_use_known_dp( &ctx->grp , gid ) ||
00445             ecp_gen_keypair( &ctx->grp , &ctx->d , &ctx->Q , f_rng, p_rng ) );
00446 }
00447 
00448 /*
00449  * Set context from an ecp_keypair
00450  */
00451 int ecdsa_from_keypair( ecdsa_context *ctx, const ecp_keypair *key )
00452 {
00453     int ret;
00454 
00455     if( ( ret = ecp_group_copy( &ctx->grp , &key->grp  ) ) != 0 ||
00456         ( ret = mpi_copy( &ctx->d , &key->d  ) ) != 0 ||
00457         ( ret = ecp_copy( &ctx->Q , &key->Q  ) ) != 0 )
00458     {
00459         ecdsa_free( ctx );
00460     }
00461 
00462     return( ret );
00463 }
00464 
00465 /*
00466  * Initialize context
00467  */
00468 void ecdsa_init( ecdsa_context *ctx )
00469 {
00470     ecp_group_init( &ctx->grp  );
00471     mpi_init( &ctx->d  );
00472     ecp_point_init( &ctx->Q  );
00473     mpi_init( &ctx->r  );
00474     mpi_init( &ctx->s  );
00475 }
00476 
00477 /*
00478  * Free context
00479  */
00480 void ecdsa_free( ecdsa_context *ctx )
00481 {
00482     ecp_group_free( &ctx->grp  );
00483     mpi_free( &ctx->d  );
00484     ecp_point_free( &ctx->Q  );
00485     mpi_free( &ctx->r  );
00486     mpi_free( &ctx->s  );
00487 }
00488 
00489 #if defined(POLARSSL_SELF_TEST)
00490 
00491 /*
00492  * Checkup routine
00493  */
00494 int ecdsa_self_test( int verbose )
00495 {
00496     ((void) verbose );
00497     return( 0 );
00498 }
00499 
00500 #endif /* POLARSSL_SELF_TEST */
00501 
00502 #endif /* POLARSSL_ECDSA_C */
00503