ecdsa.c

00001 /*
00002  *  Elliptic curve DSA
00003  *
00004  *  Copyright (C) 2006-2015, ARM Limited, All Rights Reserved
00005  *  SPDX-License-Identifier: Apache-2.0
00006  *
00007  *  Licensed under the Apache License, Version 2.0 (the "License"); you may
00008  *  not use this file except in compliance with the License.
00009  *  You may obtain a copy of the License at
00010  *
00011  *  http://www.apache.org/licenses/LICENSE-2.0
00012  *
00013  *  Unless required by applicable law or agreed to in writing, software
00014  *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
00015  *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00016  *  See the License for the specific language governing permissions and
00017  *  limitations under the License.
00018  *
00019  *  This file is part of mbed TLS (https://tls.mbed.org)
00020  */
00021 
00022 /*
00023  * References:
00024  *
00025  * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
00026  */
00027 
00028 #if !defined(MBEDTLS_CONFIG_FILE)
00029 #include "mbedtls/config.h"
00030 #else
00031 #include MBEDTLS_CONFIG_FILE
00032 #endif
00033 
00034 #if defined(MBEDTLS_ECDSA_C)
00035 
00036 #include "mbedtls/ecdsa.h"
00037 #include "mbedtls/asn1write.h"
00038 
00039 #include <string.h>
00040 
00041 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00042 #include "mbedtls/hmac_drbg.h"
00043 #endif
00044 
00045 /*
00046  * Derive a suitable integer for group grp from a buffer of length len
00047  * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
00048  */
00049 static int derive_mpi( const mbedtls_ecp_group *grp, mbedtls_mpi *x,
00050                        const unsigned char *buf, size_t blen )
00051 {
00052     int ret;
00053     size_t n_size = ( grp->nbits  + 7 ) / 8;
00054     size_t use_size = blen > n_size ? n_size : blen;
00055 
00056     MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( x, buf, use_size ) );
00057     if( use_size * 8 > grp->nbits  )
00058         MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( x, use_size * 8 - grp->nbits  ) );
00059 
00060     /* While at it, reduce modulo N */
00061     if( mbedtls_mpi_cmp_mpi( x, &grp->N  ) >= 0 )
00062         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( x, x, &grp->N  ) );
00063 
00064 cleanup:
00065     return( ret );
00066 }
00067 
00068 #if !defined(MBEDTLS_ECDSA_SIGN_ALT)
00069 /*
00070  * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
00071  * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
00072  */
00073 int mbedtls_ecdsa_sign( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
00074                 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
00075                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
00076 {
00077     int ret, key_tries, sign_tries, blind_tries;
00078     mbedtls_ecp_point R;
00079     mbedtls_mpi k, e, t;
00080 
00081     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
00082     if( grp->N .p  == NULL )
00083         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00084 
00085     /* Make sure d is in range 1..n-1 */
00086     if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || mbedtls_mpi_cmp_mpi( d, &grp->N  ) >= 0 )
00087         return( MBEDTLS_ERR_ECP_INVALID_KEY );
00088 
00089     mbedtls_ecp_point_init( &R );
00090     mbedtls_mpi_init( &k ); mbedtls_mpi_init( &e ); mbedtls_mpi_init( &t );
00091 
00092     sign_tries = 0;
00093     do
00094     {
00095         /*
00096          * Steps 1-3: generate a suitable ephemeral keypair
00097          * and set r = xR mod n
00098          */
00099         key_tries = 0;
00100         do
00101         {
00102             MBEDTLS_MPI_CHK( mbedtls_ecp_gen_keypair( grp, &k, &R, f_rng, p_rng ) );
00103             MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( r, &R.X , &grp->N  ) );
00104 
00105             if( key_tries++ > 10 )
00106             {
00107                 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
00108                 goto cleanup;
00109             }
00110         }
00111         while( mbedtls_mpi_cmp_int( r, 0 ) == 0 );
00112 
00113         /*
00114          * Step 5: derive MPI from hashed message
00115          */
00116         MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
00117 
00118         /*
00119          * Generate a random value to blind inv_mod in next step,
00120          * avoiding a potential timing leak.
00121          */
00122         blind_tries = 0;
00123         do
00124         {
00125             size_t n_size = ( grp->nbits  + 7 ) / 8;
00126             MBEDTLS_MPI_CHK( mbedtls_mpi_fill_random( &t, n_size, f_rng, p_rng ) );
00127             MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( &t, 8 * n_size - grp->nbits  ) );
00128 
00129             /* See mbedtls_ecp_gen_keypair() */
00130             if( ++blind_tries > 30 )
00131                 return( MBEDTLS_ERR_ECP_RANDOM_FAILED );
00132         }
00133         while( mbedtls_mpi_cmp_int( &t, 1 ) < 0 ||
00134                mbedtls_mpi_cmp_mpi( &t, &grp->N  ) >= 0 );
00135 
00136         /*
00137          * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
00138          */
00139         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, r, d ) );
00140         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &e, &e, s ) );
00141         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &e, &e, &t ) );
00142         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &k, &k, &t ) );
00143         MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( s, &k, &grp->N  ) );
00144         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, s, &e ) );
00145         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( s, s, &grp->N  ) );
00146 
00147         if( sign_tries++ > 10 )
00148         {
00149             ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
00150             goto cleanup;
00151         }
00152     }
00153     while( mbedtls_mpi_cmp_int( s, 0 ) == 0 );
00154 
00155 cleanup:
00156     mbedtls_ecp_point_free( &R );
00157     mbedtls_mpi_free( &k ); mbedtls_mpi_free( &e ); mbedtls_mpi_free( &t );
00158 
00159     return( ret );
00160 }
00161 #endif /* MBEDTLS_ECDSA_SIGN_ALT */
00162 
00163 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00164 /*
00165  * Deterministic signature wrapper
00166  */
00167 int mbedtls_ecdsa_sign_det( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
00168                     const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
00169                     mbedtls_md_type_t md_alg )
00170 {
00171     int ret;
00172     mbedtls_hmac_drbg_context rng_ctx;
00173     unsigned char data[2 * MBEDTLS_ECP_MAX_BYTES];
00174     size_t grp_len = ( grp->nbits  + 7 ) / 8;
00175     const mbedtls_md_info_t *md_info;
00176     mbedtls_mpi h;
00177 
00178     if( ( md_info = mbedtls_md_info_from_type( md_alg ) ) == NULL )
00179         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00180 
00181     mbedtls_mpi_init( &h );
00182     mbedtls_hmac_drbg_init( &rng_ctx );
00183 
00184     /* Use private key and message hash (reduced) to initialize HMAC_DRBG */
00185     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( d, data, grp_len ) );
00186     MBEDTLS_MPI_CHK( derive_mpi( grp, &h, buf, blen ) );
00187     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &h, data + grp_len, grp_len ) );
00188     mbedtls_hmac_drbg_seed_buf( &rng_ctx, md_info, data, 2 * grp_len );
00189 
00190     ret = mbedtls_ecdsa_sign( grp, r, s, d, buf, blen,
00191                       mbedtls_hmac_drbg_random, &rng_ctx );
00192 
00193 cleanup:
00194     mbedtls_hmac_drbg_free( &rng_ctx );
00195     mbedtls_mpi_free( &h );
00196 
00197     return( ret );
00198 }
00199 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
00200 
00201 #if !defined(MBEDTLS_ECDSA_VERIFY_ALT)
00202 /*
00203  * Verify ECDSA signature of hashed message (SEC1 4.1.4)
00204  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
00205  */
00206 int mbedtls_ecdsa_verify( mbedtls_ecp_group *grp,
00207                   const unsigned char *buf, size_t blen,
00208                   const mbedtls_ecp_point *Q, const mbedtls_mpi *r, const mbedtls_mpi *s)
00209 {
00210     int ret;
00211     mbedtls_mpi e, s_inv, u1, u2;
00212     mbedtls_ecp_point R;
00213 
00214     mbedtls_ecp_point_init( &R );
00215     mbedtls_mpi_init( &e ); mbedtls_mpi_init( &s_inv ); mbedtls_mpi_init( &u1 ); mbedtls_mpi_init( &u2 );
00216 
00217     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
00218     if( grp->N .p  == NULL )
00219         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00220 
00221     /*
00222      * Step 1: make sure r and s are in range 1..n-1
00223      */
00224     if( mbedtls_mpi_cmp_int( r, 1 ) < 0 || mbedtls_mpi_cmp_mpi( r, &grp->N  ) >= 0 ||
00225         mbedtls_mpi_cmp_int( s, 1 ) < 0 || mbedtls_mpi_cmp_mpi( s, &grp->N  ) >= 0 )
00226     {
00227         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
00228         goto cleanup;
00229     }
00230 
00231     /*
00232      * Additional precaution: make sure Q is valid
00233      */
00234     MBEDTLS_MPI_CHK( mbedtls_ecp_check_pubkey( grp, Q ) );
00235 
00236     /*
00237      * Step 3: derive MPI from hashed message
00238      */
00239     MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
00240 
00241     /*
00242      * Step 4: u1 = e / s mod n, u2 = r / s mod n
00243      */
00244     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &s_inv, s, &grp->N  ) );
00245 
00246     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u1, &e, &s_inv ) );
00247     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &u1, &u1, &grp->N  ) );
00248 
00249     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &u2, r, &s_inv ) );
00250     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &u2, &u2, &grp->N  ) );
00251 
00252     /*
00253      * Step 5: R = u1 G + u2 Q
00254      *
00255      * Since we're not using any secret data, no need to pass a RNG to
00256      * mbedtls_ecp_mul() for countermesures.
00257      */
00258     MBEDTLS_MPI_CHK( mbedtls_ecp_muladd( grp, &R, &u1, &grp->G , &u2, Q ) );
00259 
00260     if( mbedtls_ecp_is_zero( &R ) )
00261     {
00262         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
00263         goto cleanup;
00264     }
00265 
00266     /*
00267      * Step 6: convert xR to an integer (no-op)
00268      * Step 7: reduce xR mod n (gives v)
00269      */
00270     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &R.X , &R.X , &grp->N  ) );
00271 
00272     /*
00273      * Step 8: check if v (that is, R.X) is equal to r
00274      */
00275     if( mbedtls_mpi_cmp_mpi( &R.X , r ) != 0 )
00276     {
00277         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
00278         goto cleanup;
00279     }
00280 
00281 cleanup:
00282     mbedtls_ecp_point_free( &R );
00283     mbedtls_mpi_free( &e ); mbedtls_mpi_free( &s_inv ); mbedtls_mpi_free( &u1 ); mbedtls_mpi_free( &u2 );
00284 
00285     return( ret );
00286 }
00287 #endif /* MBEDTLS_ECDSA_VERIFY_ALT */
00288 
00289 /*
00290  * Convert a signature (given by context) to ASN.1
00291  */
00292 static int ecdsa_signature_to_asn1( const mbedtls_mpi *r, const mbedtls_mpi *s,
00293                                     unsigned char *sig, size_t *slen )
00294 {
00295     int ret;
00296     unsigned char buf[MBEDTLS_ECDSA_MAX_LEN];
00297     unsigned char *p = buf + sizeof( buf );
00298     size_t len = 0;
00299 
00300     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, s ) );
00301     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, r ) );
00302 
00303     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_len( &p, buf, len ) );
00304     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_tag( &p, buf,
00305                                        MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) );
00306 
00307     memcpy( sig, p, len );
00308     *slen = len;
00309 
00310     return( 0 );
00311 }
00312 
00313 /*
00314  * Compute and write signature
00315  */
00316 int mbedtls_ecdsa_write_signature( mbedtls_ecdsa_context *ctx, mbedtls_md_type_t md_alg,
00317                            const unsigned char *hash, size_t hlen,
00318                            unsigned char *sig, size_t *slen,
00319                            int (*f_rng)(void *, unsigned char *, size_t),
00320                            void *p_rng )
00321 {
00322     int ret;
00323     mbedtls_mpi r, s;
00324 
00325     mbedtls_mpi_init( &r );
00326     mbedtls_mpi_init( &s );
00327 
00328 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00329     (void) f_rng;
00330     (void) p_rng;
00331 
00332     MBEDTLS_MPI_CHK( mbedtls_ecdsa_sign_det( &ctx->grp , &r, &s, &ctx->d ,
00333                              hash, hlen, md_alg ) );
00334 #else
00335     (void) md_alg;
00336 
00337     MBEDTLS_MPI_CHK( mbedtls_ecdsa_sign( &ctx->grp , &r, &s, &ctx->d ,
00338                          hash, hlen, f_rng, p_rng ) );
00339 #endif
00340 
00341     MBEDTLS_MPI_CHK( ecdsa_signature_to_asn1( &r, &s, sig, slen ) );
00342 
00343 cleanup:
00344     mbedtls_mpi_free( &r );
00345     mbedtls_mpi_free( &s );
00346 
00347     return( ret );
00348 }
00349 
00350 #if ! defined(MBEDTLS_DEPRECATED_REMOVED) && \
00351     defined(MBEDTLS_ECDSA_DETERMINISTIC)
00352 int mbedtls_ecdsa_write_signature_det( mbedtls_ecdsa_context *ctx,
00353                                const unsigned char *hash, size_t hlen,
00354                                unsigned char *sig, size_t *slen,
00355                                mbedtls_md_type_t md_alg )
00356 {
00357     return( mbedtls_ecdsa_write_signature( ctx, md_alg, hash, hlen, sig, slen,
00358                                    NULL, NULL ) );
00359 }
00360 #endif
00361 
00362 /*
00363  * Read and check signature
00364  */
00365 int mbedtls_ecdsa_read_signature( mbedtls_ecdsa_context *ctx,
00366                           const unsigned char *hash, size_t hlen,
00367                           const unsigned char *sig, size_t slen )
00368 {
00369     int ret;
00370     unsigned char *p = (unsigned char *) sig;
00371     const unsigned char *end = sig + slen;
00372     size_t len;
00373     mbedtls_mpi r, s;
00374 
00375     mbedtls_mpi_init( &r );
00376     mbedtls_mpi_init( &s );
00377 
00378     if( ( ret = mbedtls_asn1_get_tag( &p, end, &len,
00379                     MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) ) != 0 )
00380     {
00381         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
00382         goto cleanup;
00383     }
00384 
00385     if( p + len != end )
00386     {
00387         ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA +
00388               MBEDTLS_ERR_ASN1_LENGTH_MISMATCH;
00389         goto cleanup;
00390     }
00391 
00392     if( ( ret = mbedtls_asn1_get_mpi( &p, end, &r ) ) != 0 ||
00393         ( ret = mbedtls_asn1_get_mpi( &p, end, &s ) ) != 0 )
00394     {
00395         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
00396         goto cleanup;
00397     }
00398 
00399     if( ( ret = mbedtls_ecdsa_verify( &ctx->grp , hash, hlen,
00400                               &ctx->Q , &r, &s ) ) != 0 )
00401         goto cleanup;
00402 
00403     /* At this point we know that the buffer starts with a valid signature.
00404      * Return 0 if the buffer just contains the signature, and a specific
00405      * error code if the valid signature is followed by more data. */
00406     if( p != end )
00407         ret = MBEDTLS_ERR_ECP_SIG_LEN_MISMATCH;
00408 
00409 cleanup:
00410     mbedtls_mpi_free( &r );
00411     mbedtls_mpi_free( &s );
00412 
00413     return( ret );
00414 }
00415 
00416 #if !defined(MBEDTLS_ECDSA_GENKEY_ALT)
00417 /*
00418  * Generate key pair
00419  */
00420 int mbedtls_ecdsa_genkey( mbedtls_ecdsa_context *ctx, mbedtls_ecp_group_id gid,
00421                   int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
00422 {
00423     return( mbedtls_ecp_group_load( &ctx->grp , gid ) ||
00424             mbedtls_ecp_gen_keypair( &ctx->grp , &ctx->d , &ctx->Q , f_rng, p_rng ) );
00425 }
00426 #endif /* MBEDTLS_ECDSA_GENKEY_ALT */
00427 
00428 /*
00429  * Set context from an mbedtls_ecp_keypair
00430  */
00431 int mbedtls_ecdsa_from_keypair( mbedtls_ecdsa_context *ctx, const mbedtls_ecp_keypair *key )
00432 {
00433     int ret;
00434 
00435     if( ( ret = mbedtls_ecp_group_copy( &ctx->grp , &key->grp  ) ) != 0 ||
00436         ( ret = mbedtls_mpi_copy( &ctx->d , &key->d  ) ) != 0 ||
00437         ( ret = mbedtls_ecp_copy( &ctx->Q , &key->Q  ) ) != 0 )
00438     {
00439         mbedtls_ecdsa_free( ctx );
00440     }
00441 
00442     return( ret );
00443 }
00444 
00445 /*
00446  * Initialize context
00447  */
00448 void mbedtls_ecdsa_init( mbedtls_ecdsa_context *ctx )
00449 {
00450     mbedtls_ecp_keypair_init( ctx );
00451 }
00452 
00453 /*
00454  * Free context
00455  */
00456 void mbedtls_ecdsa_free( mbedtls_ecdsa_context *ctx )
00457 {
00458     mbedtls_ecp_keypair_free( ctx );
00459 }
00460 
00461 #endif /* MBEDTLS_ECDSA_C */