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 #if defined(MBEDTLS_PLATFORM_C)
00046 #include "mbedtls/platform.h"
00047 #else
00048 #include <stdlib.h>
00049 #define mbedtls_calloc    calloc
00050 #define mbedtls_free       free
00051 #endif
00052 
00053 #include "mbedtls/platform_util.h"
00054 
00055 /* Parameter validation macros based on platform_util.h */
00056 #define ECDSA_VALIDATE_RET( cond )    \
00057     MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_ECP_BAD_INPUT_DATA )
00058 #define ECDSA_VALIDATE( cond )        \
00059     MBEDTLS_INTERNAL_VALIDATE( cond )
00060 
00061 #if defined(MBEDTLS_ECP_RESTARTABLE)
00062 
00063 /*
00064  * Sub-context for ecdsa_verify()
00065  */
00066 struct mbedtls_ecdsa_restart_ver
00067 {
00068     mbedtls_mpi u1, u2;     /* intermediate values  */
00069     enum {                  /* what to do next?     */
00070         ecdsa_ver_init = 0, /* getting started      */
00071         ecdsa_ver_muladd,   /* muladd step          */
00072     } state;
00073 };
00074 
00075 /*
00076  * Init verify restart sub-context
00077  */
00078 static void ecdsa_restart_ver_init( mbedtls_ecdsa_restart_ver_ctx *ctx )
00079 {
00080     mbedtls_mpi_init( &ctx->u1 );
00081     mbedtls_mpi_init( &ctx->u2 );
00082     ctx->state = ecdsa_ver_init;
00083 }
00084 
00085 /*
00086  * Free the components of a verify restart sub-context
00087  */
00088 static void ecdsa_restart_ver_free( mbedtls_ecdsa_restart_ver_ctx *ctx )
00089 {
00090     if( ctx == NULL )
00091         return;
00092 
00093     mbedtls_mpi_free( &ctx->u1 );
00094     mbedtls_mpi_free( &ctx->u2 );
00095 
00096     ecdsa_restart_ver_init( ctx );
00097 }
00098 
00099 /*
00100  * Sub-context for ecdsa_sign()
00101  */
00102 struct mbedtls_ecdsa_restart_sig
00103 {
00104     int sign_tries;
00105     int key_tries;
00106     mbedtls_mpi k;          /* per-signature random */
00107     mbedtls_mpi r;          /* r value              */
00108     enum {                  /* what to do next?     */
00109         ecdsa_sig_init = 0, /* getting started      */
00110         ecdsa_sig_mul,      /* doing ecp_mul()      */
00111         ecdsa_sig_modn,     /* mod N computations   */
00112     } state;
00113 };
00114 
00115 /*
00116  * Init verify sign sub-context
00117  */
00118 static void ecdsa_restart_sig_init( mbedtls_ecdsa_restart_sig_ctx *ctx )
00119 {
00120     ctx->sign_tries = 0;
00121     ctx->key_tries = 0;
00122     mbedtls_mpi_init( &ctx->k );
00123     mbedtls_mpi_init( &ctx->r );
00124     ctx->state = ecdsa_sig_init;
00125 }
00126 
00127 /*
00128  * Free the components of a sign restart sub-context
00129  */
00130 static void ecdsa_restart_sig_free( mbedtls_ecdsa_restart_sig_ctx *ctx )
00131 {
00132     if( ctx == NULL )
00133         return;
00134 
00135     mbedtls_mpi_free( &ctx->k );
00136     mbedtls_mpi_free( &ctx->r );
00137 }
00138 
00139 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00140 /*
00141  * Sub-context for ecdsa_sign_det()
00142  */
00143 struct mbedtls_ecdsa_restart_det
00144 {
00145     mbedtls_hmac_drbg_context rng_ctx;  /* DRBG state   */
00146     enum {                      /* what to do next?     */
00147         ecdsa_det_init = 0,     /* getting started      */
00148         ecdsa_det_sign,         /* make signature       */
00149     } state;
00150 };
00151 
00152 /*
00153  * Init verify sign_det sub-context
00154  */
00155 static void ecdsa_restart_det_init( mbedtls_ecdsa_restart_det_ctx *ctx )
00156 {
00157     mbedtls_hmac_drbg_init( &ctx->rng_ctx );
00158     ctx->state = ecdsa_det_init;
00159 }
00160 
00161 /*
00162  * Free the components of a sign_det restart sub-context
00163  */
00164 static void ecdsa_restart_det_free( mbedtls_ecdsa_restart_det_ctx *ctx )
00165 {
00166     if( ctx == NULL )
00167         return;
00168 
00169     mbedtls_hmac_drbg_free( &ctx->rng_ctx );
00170 
00171     ecdsa_restart_det_init( ctx );
00172 }
00173 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
00174 
00175 #define ECDSA_RS_ECP    ( rs_ctx == NULL ? NULL : &rs_ctx->ecp )
00176 
00177 /* Utility macro for checking and updating ops budget */
00178 #define ECDSA_BUDGET( ops )   \
00179     MBEDTLS_MPI_CHK( mbedtls_ecp_check_budget( grp, ECDSA_RS_ECP, ops ) );
00180 
00181 /* Call this when entering a function that needs its own sub-context */
00182 #define ECDSA_RS_ENTER( SUB )   do {                                 \
00183     /* reset ops count for this call if top-level */                 \
00184     if( rs_ctx != NULL && rs_ctx->ecp.depth++ == 0 )                 \
00185         rs_ctx->ecp.ops_done = 0;                                    \
00186                                                                      \
00187     /* set up our own sub-context if needed */                       \
00188     if( mbedtls_ecp_restart_is_enabled() &&                          \
00189         rs_ctx != NULL && rs_ctx->SUB == NULL )                      \
00190     {                                                                \
00191         rs_ctx->SUB = mbedtls_calloc( 1, sizeof( *rs_ctx->SUB ) );   \
00192         if( rs_ctx->SUB == NULL )                                    \
00193             return( MBEDTLS_ERR_ECP_ALLOC_FAILED );                  \
00194                                                                      \
00195         ecdsa_restart_## SUB ##_init( rs_ctx->SUB );                 \
00196     }                                                                \
00197 } while( 0 )
00198 
00199 /* Call this when leaving a function that needs its own sub-context */
00200 #define ECDSA_RS_LEAVE( SUB )   do {                                 \
00201     /* clear our sub-context when not in progress (done or error) */ \
00202     if( rs_ctx != NULL && rs_ctx->SUB != NULL &&                     \
00203         ret != MBEDTLS_ERR_ECP_IN_PROGRESS )                         \
00204     {                                                                \
00205         ecdsa_restart_## SUB ##_free( rs_ctx->SUB );                 \
00206         mbedtls_free( rs_ctx->SUB );                                 \
00207         rs_ctx->SUB = NULL;                                          \
00208     }                                                                \
00209                                                                      \
00210     if( rs_ctx != NULL )                                             \
00211         rs_ctx->ecp.depth--;                                         \
00212 } while( 0 )
00213 
00214 #else /* MBEDTLS_ECP_RESTARTABLE */
00215 
00216 #define ECDSA_RS_ECP    NULL
00217 
00218 #define ECDSA_BUDGET( ops )   /* no-op; for compatibility */
00219 
00220 #define ECDSA_RS_ENTER( SUB )   (void) rs_ctx
00221 #define ECDSA_RS_LEAVE( SUB )   (void) rs_ctx
00222 
00223 #endif /* MBEDTLS_ECP_RESTARTABLE */
00224 
00225 /*
00226  * Derive a suitable integer for group grp from a buffer of length len
00227  * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
00228  */
00229 static int derive_mpi( const mbedtls_ecp_group *grp, mbedtls_mpi *x,
00230                        const unsigned char *buf, size_t blen )
00231 {
00232     int ret;
00233     size_t n_size = ( grp->nbits  + 7 ) / 8;
00234     size_t use_size = blen > n_size ? n_size : blen;
00235 
00236     MBEDTLS_MPI_CHK( mbedtls_mpi_read_binary( x, buf, use_size ) );
00237     if( use_size * 8 > grp->nbits  )
00238         MBEDTLS_MPI_CHK( mbedtls_mpi_shift_r( x, use_size * 8 - grp->nbits  ) );
00239 
00240     /* While at it, reduce modulo N */
00241     if( mbedtls_mpi_cmp_mpi( x, &grp->N  ) >= 0 )
00242         MBEDTLS_MPI_CHK( mbedtls_mpi_sub_mpi( x, x, &grp->N  ) );
00243 
00244 cleanup:
00245     return( ret );
00246 }
00247 
00248 #if !defined(MBEDTLS_ECDSA_SIGN_ALT)
00249 /*
00250  * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
00251  * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
00252  */
00253 static int ecdsa_sign_restartable( mbedtls_ecp_group *grp,
00254                 mbedtls_mpi *r, mbedtls_mpi *s,
00255                 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
00256                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
00257                 int (*f_rng_blind)(void *, unsigned char *, size_t),
00258                 void *p_rng_blind,
00259                 mbedtls_ecdsa_restart_ctx *rs_ctx )
00260 {
00261     int ret, key_tries, sign_tries;
00262     int *p_sign_tries = &sign_tries, *p_key_tries = &key_tries;
00263     mbedtls_ecp_point R;
00264     mbedtls_mpi k, e, t;
00265     mbedtls_mpi *pk = &k, *pr = r;
00266 
00267     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
00268     if( ! mbedtls_ecdsa_can_do( grp->id  ) || grp->N .p  == NULL )
00269         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00270 
00271     /* Make sure d is in range 1..n-1 */
00272     if( mbedtls_mpi_cmp_int( d, 1 ) < 0 || mbedtls_mpi_cmp_mpi( d, &grp->N  ) >= 0 )
00273         return( MBEDTLS_ERR_ECP_INVALID_KEY );
00274 
00275     mbedtls_ecp_point_init( &R );
00276     mbedtls_mpi_init( &k ); mbedtls_mpi_init( &e ); mbedtls_mpi_init( &t );
00277 
00278     ECDSA_RS_ENTER( sig );
00279 
00280 #if defined(MBEDTLS_ECP_RESTARTABLE)
00281     if( rs_ctx != NULL && rs_ctx->sig  != NULL )
00282     {
00283         /* redirect to our context */
00284         p_sign_tries = &rs_ctx->sig ->sign_tries;
00285         p_key_tries = &rs_ctx->sig ->key_tries;
00286         pk = &rs_ctx->sig ->k;
00287         pr = &rs_ctx->sig ->r;
00288 
00289         /* jump to current step */
00290         if( rs_ctx->sig ->state == ecdsa_sig_mul )
00291             goto mul;
00292         if( rs_ctx->sig ->state == ecdsa_sig_modn )
00293             goto modn;
00294     }
00295 #endif /* MBEDTLS_ECP_RESTARTABLE */
00296 
00297     *p_sign_tries = 0;
00298     do
00299     {
00300         if( *p_sign_tries++ > 10 )
00301         {
00302             ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
00303             goto cleanup;
00304         }
00305 
00306         /*
00307          * Steps 1-3: generate a suitable ephemeral keypair
00308          * and set r = xR mod n
00309          */
00310         *p_key_tries = 0;
00311         do
00312         {
00313             if( *p_key_tries++ > 10 )
00314             {
00315                 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
00316                 goto cleanup;
00317             }
00318 
00319             MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, pk, f_rng, p_rng ) );
00320 
00321 #if defined(MBEDTLS_ECP_RESTARTABLE)
00322             if( rs_ctx != NULL && rs_ctx->sig  != NULL )
00323                 rs_ctx->sig ->state = ecdsa_sig_mul;
00324 
00325 mul:
00326 #endif
00327             MBEDTLS_MPI_CHK( mbedtls_ecp_mul_restartable( grp, &R, pk, &grp->G ,
00328                                                           f_rng_blind,
00329                                                           p_rng_blind,
00330                                                           ECDSA_RS_ECP ) );
00331             MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pr, &R.X , &grp->N  ) );
00332         }
00333         while( mbedtls_mpi_cmp_int( pr, 0 ) == 0 );
00334 
00335 #if defined(MBEDTLS_ECP_RESTARTABLE)
00336         if( rs_ctx != NULL && rs_ctx->sig  != NULL )
00337             rs_ctx->sig ->state = ecdsa_sig_modn;
00338 
00339 modn:
00340 #endif
00341         /*
00342          * Accounting for everything up to the end of the loop
00343          * (step 6, but checking now avoids saving e and t)
00344          */
00345         ECDSA_BUDGET( MBEDTLS_ECP_OPS_INV + 4 );
00346 
00347         /*
00348          * Step 5: derive MPI from hashed message
00349          */
00350         MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
00351 
00352         /*
00353          * Generate a random value to blind inv_mod in next step,
00354          * avoiding a potential timing leak.
00355          */
00356         MBEDTLS_MPI_CHK( mbedtls_ecp_gen_privkey( grp, &t, f_rng_blind,
00357                                                   p_rng_blind ) );
00358 
00359         /*
00360          * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
00361          */
00362         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, pr, d ) );
00363         MBEDTLS_MPI_CHK( mbedtls_mpi_add_mpi( &e, &e, s ) );
00364         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( &e, &e, &t ) );
00365         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pk, pk, &t ) );
00366         MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( s, pk, &grp->N  ) );
00367         MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( s, s, &e ) );
00368         MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( s, s, &grp->N  ) );
00369     }
00370     while( mbedtls_mpi_cmp_int( s, 0 ) == 0 );
00371 
00372 #if defined(MBEDTLS_ECP_RESTARTABLE)
00373     if( rs_ctx != NULL && rs_ctx->sig  != NULL )
00374         mbedtls_mpi_copy( r, pr );
00375 #endif
00376 
00377 cleanup:
00378     mbedtls_ecp_point_free( &R );
00379     mbedtls_mpi_free( &k ); mbedtls_mpi_free( &e ); mbedtls_mpi_free( &t );
00380 
00381     ECDSA_RS_LEAVE( sig );
00382 
00383     return( ret );
00384 }
00385 
00386 int mbedtls_ecdsa_can_do( mbedtls_ecp_group_id gid )
00387 {
00388     switch( gid )
00389     {
00390 #ifdef MBEDTLS_ECP_DP_CURVE25519_ENABLED
00391         case MBEDTLS_ECP_DP_CURVE25519: return 0;
00392 #endif
00393 #ifdef MBEDTLS_ECP_DP_CURVE448_ENABLED
00394         case MBEDTLS_ECP_DP_CURVE448: return 0;
00395 #endif
00396     default: return 1;
00397     }
00398 }
00399 
00400 /*
00401  * Compute ECDSA signature of a hashed message
00402  */
00403 int mbedtls_ecdsa_sign( mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
00404                 const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
00405                 int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
00406 {
00407     ECDSA_VALIDATE_RET( grp   != NULL );
00408     ECDSA_VALIDATE_RET( r     != NULL );
00409     ECDSA_VALIDATE_RET( s     != NULL );
00410     ECDSA_VALIDATE_RET( d     != NULL );
00411     ECDSA_VALIDATE_RET( f_rng != NULL );
00412     ECDSA_VALIDATE_RET( buf   != NULL || blen == 0 );
00413 
00414     /* Use the same RNG for both blinding and ephemeral key generation */
00415     return( ecdsa_sign_restartable( grp, r, s, d, buf, blen,
00416                                     f_rng, p_rng, f_rng, p_rng, NULL ) );
00417 }
00418 #endif /* !MBEDTLS_ECDSA_SIGN_ALT */
00419 
00420 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00421 /*
00422  * Deterministic signature wrapper
00423  */
00424 static int ecdsa_sign_det_restartable( mbedtls_ecp_group *grp,
00425                     mbedtls_mpi *r, mbedtls_mpi *s,
00426                     const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
00427                     mbedtls_md_type_t md_alg,
00428                     int (*f_rng_blind)(void *, unsigned char *, size_t),
00429                     void *p_rng_blind,
00430                     mbedtls_ecdsa_restart_ctx *rs_ctx )
00431 {
00432     int ret;
00433     mbedtls_hmac_drbg_context rng_ctx;
00434     mbedtls_hmac_drbg_context *p_rng = &rng_ctx;
00435     unsigned char data[2 * MBEDTLS_ECP_MAX_BYTES];
00436     size_t grp_len = ( grp->nbits  + 7 ) / 8;
00437     const mbedtls_md_info_t *md_info;
00438     mbedtls_mpi h;
00439 
00440     if( ( md_info = mbedtls_md_info_from_type( md_alg ) ) == NULL )
00441         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00442 
00443     mbedtls_mpi_init( &h );
00444     mbedtls_hmac_drbg_init( &rng_ctx );
00445 
00446     ECDSA_RS_ENTER( det );
00447 
00448 #if defined(MBEDTLS_ECP_RESTARTABLE)
00449     if( rs_ctx != NULL && rs_ctx->det  != NULL )
00450     {
00451         /* redirect to our context */
00452         p_rng = &rs_ctx->det ->rng_ctx;
00453 
00454         /* jump to current step */
00455         if( rs_ctx->det ->state == ecdsa_det_sign )
00456             goto sign;
00457     }
00458 #endif /* MBEDTLS_ECP_RESTARTABLE */
00459 
00460     /* Use private key and message hash (reduced) to initialize HMAC_DRBG */
00461     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( d, data, grp_len ) );
00462     MBEDTLS_MPI_CHK( derive_mpi( grp, &h, buf, blen ) );
00463     MBEDTLS_MPI_CHK( mbedtls_mpi_write_binary( &h, data + grp_len, grp_len ) );
00464     mbedtls_hmac_drbg_seed_buf( p_rng, md_info, data, 2 * grp_len );
00465 
00466 #if defined(MBEDTLS_ECP_RESTARTABLE)
00467     if( rs_ctx != NULL && rs_ctx->det  != NULL )
00468         rs_ctx->det ->state = ecdsa_det_sign;
00469 
00470 sign:
00471 #endif
00472 #if defined(MBEDTLS_ECDSA_SIGN_ALT)
00473     ret = mbedtls_ecdsa_sign( grp, r, s, d, buf, blen,
00474                               mbedtls_hmac_drbg_random, p_rng );
00475 #else
00476     if( f_rng_blind != NULL )
00477         ret = ecdsa_sign_restartable( grp, r, s, d, buf, blen,
00478                                       mbedtls_hmac_drbg_random, p_rng,
00479                                       f_rng_blind, p_rng_blind, rs_ctx );
00480     else
00481     {
00482         mbedtls_hmac_drbg_context *p_rng_blind_det;
00483 
00484 #if !defined(MBEDTLS_ECP_RESTARTABLE)
00485         /*
00486          * To avoid reusing rng_ctx and risking incorrect behavior we seed a
00487          * second HMAC-DRBG with the same seed. We also apply a label to avoid
00488          * reusing the bits of the ephemeral key for blinding and eliminate the
00489          * risk that they leak this way.
00490          */
00491         const char* blind_label = "BLINDING CONTEXT";
00492         mbedtls_hmac_drbg_context rng_ctx_blind;
00493 
00494         mbedtls_hmac_drbg_init( &rng_ctx_blind );
00495         p_rng_blind_det = &rng_ctx_blind;
00496         mbedtls_hmac_drbg_seed_buf( p_rng_blind_det, md_info,
00497                                     data, 2 * grp_len );
00498         ret = mbedtls_hmac_drbg_update_ret( p_rng_blind_det,
00499                                             (const unsigned char*) blind_label,
00500                                             strlen( blind_label ) );
00501         if( ret != 0 )
00502         {
00503             mbedtls_hmac_drbg_free( &rng_ctx_blind );
00504             goto cleanup;
00505         }
00506 #else
00507         /*
00508          * In the case of restartable computations we would either need to store
00509          * the second RNG in the restart context too or set it up at every
00510          * restart. The first option would penalize the correct application of
00511          * the function and the second would defeat the purpose of the
00512          * restartable feature.
00513          *
00514          * Therefore in this case we reuse the original RNG. This comes with the
00515          * price that the resulting signature might not be a valid deterministic
00516          * ECDSA signature with a very low probability (same magnitude as
00517          * successfully guessing the private key). However even then it is still
00518          * a valid ECDSA signature.
00519          */
00520         p_rng_blind_det = p_rng;
00521 #endif /* MBEDTLS_ECP_RESTARTABLE */
00522 
00523         /*
00524          * Since the output of the RNGs is always the same for the same key and
00525          * message, this limits the efficiency of blinding and leaks information
00526          * through side channels. After mbedtls_ecdsa_sign_det() is removed NULL
00527          * won't be a valid value for f_rng_blind anymore. Therefore it should
00528          * be checked by the caller and this branch and check can be removed.
00529          */
00530         ret = ecdsa_sign_restartable( grp, r, s, d, buf, blen,
00531                                       mbedtls_hmac_drbg_random, p_rng,
00532                                       mbedtls_hmac_drbg_random, p_rng_blind_det,
00533                                       rs_ctx );
00534 
00535 #if !defined(MBEDTLS_ECP_RESTARTABLE)
00536         mbedtls_hmac_drbg_free( &rng_ctx_blind );
00537 #endif
00538     }
00539 #endif /* MBEDTLS_ECDSA_SIGN_ALT */
00540 
00541 cleanup:
00542     mbedtls_hmac_drbg_free( &rng_ctx );
00543     mbedtls_mpi_free( &h );
00544 
00545     ECDSA_RS_LEAVE( det );
00546 
00547     return( ret );
00548 }
00549 
00550 /*
00551  * Deterministic signature wrappers
00552  */
00553 
00554 #if !defined(MBEDTLS_DEPRECATED_REMOVED)
00555 int mbedtls_ecdsa_sign_det( mbedtls_ecp_group *grp, mbedtls_mpi *r,
00556                             mbedtls_mpi *s, const mbedtls_mpi *d,
00557                             const unsigned char *buf, size_t blen,
00558                             mbedtls_md_type_t md_alg )
00559 {
00560     ECDSA_VALIDATE_RET( grp   != NULL );
00561     ECDSA_VALIDATE_RET( r     != NULL );
00562     ECDSA_VALIDATE_RET( s     != NULL );
00563     ECDSA_VALIDATE_RET( d     != NULL );
00564     ECDSA_VALIDATE_RET( buf   != NULL || blen == 0 );
00565 
00566     return( ecdsa_sign_det_restartable( grp, r, s, d, buf, blen, md_alg,
00567                                         NULL, NULL, NULL ) );
00568 }
00569 #endif /* MBEDTLS_DEPRECATED_REMOVED */
00570 
00571 int mbedtls_ecdsa_sign_det_ext( mbedtls_ecp_group *grp, mbedtls_mpi *r,
00572                                 mbedtls_mpi *s, const mbedtls_mpi *d,
00573                                 const unsigned char *buf, size_t blen,
00574                                 mbedtls_md_type_t md_alg,
00575                                 int (*f_rng_blind)(void *, unsigned char *,
00576                                                    size_t),
00577                                 void *p_rng_blind )
00578 {
00579     ECDSA_VALIDATE_RET( grp   != NULL );
00580     ECDSA_VALIDATE_RET( r     != NULL );
00581     ECDSA_VALIDATE_RET( s     != NULL );
00582     ECDSA_VALIDATE_RET( d     != NULL );
00583     ECDSA_VALIDATE_RET( buf   != NULL || blen == 0 );
00584     ECDSA_VALIDATE_RET( f_rng_blind != NULL );
00585 
00586     return( ecdsa_sign_det_restartable( grp, r, s, d, buf, blen, md_alg,
00587                                         f_rng_blind, p_rng_blind, NULL ) );
00588 }
00589 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
00590 
00591 #if !defined(MBEDTLS_ECDSA_VERIFY_ALT)
00592 /*
00593  * Verify ECDSA signature of hashed message (SEC1 4.1.4)
00594  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
00595  */
00596 static int ecdsa_verify_restartable( mbedtls_ecp_group *grp,
00597                                      const unsigned char *buf, size_t blen,
00598                                      const mbedtls_ecp_point *Q,
00599                                      const mbedtls_mpi *r, const mbedtls_mpi *s,
00600                                      mbedtls_ecdsa_restart_ctx *rs_ctx )
00601 {
00602     int ret;
00603     mbedtls_mpi e, s_inv, u1, u2;
00604     mbedtls_ecp_point R;
00605     mbedtls_mpi *pu1 = &u1, *pu2 = &u2;
00606 
00607     mbedtls_ecp_point_init( &R );
00608     mbedtls_mpi_init( &e ); mbedtls_mpi_init( &s_inv );
00609     mbedtls_mpi_init( &u1 ); mbedtls_mpi_init( &u2 );
00610 
00611     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
00612     if( ! mbedtls_ecdsa_can_do( grp->id  ) || grp->N .p  == NULL )
00613         return( MBEDTLS_ERR_ECP_BAD_INPUT_DATA );
00614 
00615     ECDSA_RS_ENTER( ver );
00616 
00617 #if defined(MBEDTLS_ECP_RESTARTABLE)
00618     if( rs_ctx != NULL && rs_ctx->ver  != NULL )
00619     {
00620         /* redirect to our context */
00621         pu1 = &rs_ctx->ver ->u1;
00622         pu2 = &rs_ctx->ver ->u2;
00623 
00624         /* jump to current step */
00625         if( rs_ctx->ver ->state == ecdsa_ver_muladd )
00626             goto muladd;
00627     }
00628 #endif /* MBEDTLS_ECP_RESTARTABLE */
00629 
00630     /*
00631      * Step 1: make sure r and s are in range 1..n-1
00632      */
00633     if( mbedtls_mpi_cmp_int( r, 1 ) < 0 || mbedtls_mpi_cmp_mpi( r, &grp->N  ) >= 0 ||
00634         mbedtls_mpi_cmp_int( s, 1 ) < 0 || mbedtls_mpi_cmp_mpi( s, &grp->N  ) >= 0 )
00635     {
00636         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
00637         goto cleanup;
00638     }
00639 
00640     /*
00641      * Step 3: derive MPI from hashed message
00642      */
00643     MBEDTLS_MPI_CHK( derive_mpi( grp, &e, buf, blen ) );
00644 
00645     /*
00646      * Step 4: u1 = e / s mod n, u2 = r / s mod n
00647      */
00648     ECDSA_BUDGET( MBEDTLS_ECP_OPS_CHK + MBEDTLS_ECP_OPS_INV + 2 );
00649 
00650     MBEDTLS_MPI_CHK( mbedtls_mpi_inv_mod( &s_inv, s, &grp->N  ) );
00651 
00652     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pu1, &e, &s_inv ) );
00653     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pu1, pu1, &grp->N  ) );
00654 
00655     MBEDTLS_MPI_CHK( mbedtls_mpi_mul_mpi( pu2, r, &s_inv ) );
00656     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( pu2, pu2, &grp->N  ) );
00657 
00658 #if defined(MBEDTLS_ECP_RESTARTABLE)
00659     if( rs_ctx != NULL && rs_ctx->ver  != NULL )
00660         rs_ctx->ver ->state = ecdsa_ver_muladd;
00661 
00662 muladd:
00663 #endif
00664     /*
00665      * Step 5: R = u1 G + u2 Q
00666      */
00667     MBEDTLS_MPI_CHK( mbedtls_ecp_muladd_restartable( grp,
00668                      &R, pu1, &grp->G , pu2, Q, ECDSA_RS_ECP ) );
00669 
00670     if( mbedtls_ecp_is_zero( &R ) )
00671     {
00672         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
00673         goto cleanup;
00674     }
00675 
00676     /*
00677      * Step 6: convert xR to an integer (no-op)
00678      * Step 7: reduce xR mod n (gives v)
00679      */
00680     MBEDTLS_MPI_CHK( mbedtls_mpi_mod_mpi( &R.X , &R.X , &grp->N  ) );
00681 
00682     /*
00683      * Step 8: check if v (that is, R.X) is equal to r
00684      */
00685     if( mbedtls_mpi_cmp_mpi( &R.X , r ) != 0 )
00686     {
00687         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
00688         goto cleanup;
00689     }
00690 
00691 cleanup:
00692     mbedtls_ecp_point_free( &R );
00693     mbedtls_mpi_free( &e ); mbedtls_mpi_free( &s_inv );
00694     mbedtls_mpi_free( &u1 ); mbedtls_mpi_free( &u2 );
00695 
00696     ECDSA_RS_LEAVE( ver );
00697 
00698     return( ret );
00699 }
00700 
00701 /*
00702  * Verify ECDSA signature of hashed message
00703  */
00704 int mbedtls_ecdsa_verify( mbedtls_ecp_group *grp,
00705                           const unsigned char *buf, size_t blen,
00706                           const mbedtls_ecp_point *Q,
00707                           const mbedtls_mpi *r,
00708                           const mbedtls_mpi *s)
00709 {
00710     ECDSA_VALIDATE_RET( grp != NULL );
00711     ECDSA_VALIDATE_RET( Q   != NULL );
00712     ECDSA_VALIDATE_RET( r   != NULL );
00713     ECDSA_VALIDATE_RET( s   != NULL );
00714     ECDSA_VALIDATE_RET( buf != NULL || blen == 0 );
00715 
00716     return( ecdsa_verify_restartable( grp, buf, blen, Q, r, s, NULL ) );
00717 }
00718 #endif /* !MBEDTLS_ECDSA_VERIFY_ALT */
00719 
00720 /*
00721  * Convert a signature (given by context) to ASN.1
00722  */
00723 static int ecdsa_signature_to_asn1( const mbedtls_mpi *r, const mbedtls_mpi *s,
00724                                     unsigned char *sig, size_t *slen )
00725 {
00726     int ret;
00727     unsigned char buf[MBEDTLS_ECDSA_MAX_LEN];
00728     unsigned char *p = buf + sizeof( buf );
00729     size_t len = 0;
00730 
00731     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, s ) );
00732     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_mpi( &p, buf, r ) );
00733 
00734     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_len( &p, buf, len ) );
00735     MBEDTLS_ASN1_CHK_ADD( len, mbedtls_asn1_write_tag( &p, buf,
00736                                        MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) );
00737 
00738     memcpy( sig, p, len );
00739     *slen = len;
00740 
00741     return( 0 );
00742 }
00743 
00744 /*
00745  * Compute and write signature
00746  */
00747 int mbedtls_ecdsa_write_signature_restartable( mbedtls_ecdsa_context *ctx,
00748                            mbedtls_md_type_t md_alg,
00749                            const unsigned char *hash, size_t hlen,
00750                            unsigned char *sig, size_t *slen,
00751                            int (*f_rng)(void *, unsigned char *, size_t),
00752                            void *p_rng,
00753                            mbedtls_ecdsa_restart_ctx *rs_ctx )
00754 {
00755     int ret;
00756     mbedtls_mpi r, s;
00757     ECDSA_VALIDATE_RET( ctx  != NULL );
00758     ECDSA_VALIDATE_RET( hash != NULL );
00759     ECDSA_VALIDATE_RET( sig  != NULL );
00760     ECDSA_VALIDATE_RET( slen != NULL );
00761 
00762     mbedtls_mpi_init( &r );
00763     mbedtls_mpi_init( &s );
00764 
00765 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00766     MBEDTLS_MPI_CHK( ecdsa_sign_det_restartable( &ctx->grp , &r, &s, &ctx->d ,
00767                                                  hash, hlen, md_alg, f_rng,
00768                                                  p_rng, rs_ctx ) );
00769 #else
00770     (void) md_alg;
00771 
00772 #if defined(MBEDTLS_ECDSA_SIGN_ALT)
00773     MBEDTLS_MPI_CHK( mbedtls_ecdsa_sign( &ctx->grp , &r, &s, &ctx->d ,
00774                          hash, hlen, f_rng, p_rng ) );
00775 #else
00776     /* Use the same RNG for both blinding and ephemeral key generation */
00777     MBEDTLS_MPI_CHK( ecdsa_sign_restartable( &ctx->grp , &r, &s, &ctx->d ,
00778                                              hash, hlen, f_rng, p_rng, f_rng,
00779                                              p_rng, rs_ctx ) );
00780 #endif /* MBEDTLS_ECDSA_SIGN_ALT */
00781 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
00782 
00783     MBEDTLS_MPI_CHK( ecdsa_signature_to_asn1( &r, &s, sig, slen ) );
00784 
00785 cleanup:
00786     mbedtls_mpi_free( &r );
00787     mbedtls_mpi_free( &s );
00788 
00789     return( ret );
00790 }
00791 
00792 /*
00793  * Compute and write signature
00794  */
00795 int mbedtls_ecdsa_write_signature( mbedtls_ecdsa_context *ctx,
00796                                  mbedtls_md_type_t md_alg,
00797                                  const unsigned char *hash, size_t hlen,
00798                                  unsigned char *sig, size_t *slen,
00799                                  int (*f_rng)(void *, unsigned char *, size_t),
00800                                  void *p_rng )
00801 {
00802     ECDSA_VALIDATE_RET( ctx  != NULL );
00803     ECDSA_VALIDATE_RET( hash != NULL );
00804     ECDSA_VALIDATE_RET( sig  != NULL );
00805     ECDSA_VALIDATE_RET( slen != NULL );
00806     return( mbedtls_ecdsa_write_signature_restartable(
00807                 ctx, md_alg, hash, hlen, sig, slen, f_rng, p_rng, NULL ) );
00808 }
00809 
00810 #if !defined(MBEDTLS_DEPRECATED_REMOVED) && \
00811     defined(MBEDTLS_ECDSA_DETERMINISTIC)
00812 int mbedtls_ecdsa_write_signature_det( mbedtls_ecdsa_context *ctx,
00813                                const unsigned char *hash, size_t hlen,
00814                                unsigned char *sig, size_t *slen,
00815                                mbedtls_md_type_t md_alg )
00816 {
00817     ECDSA_VALIDATE_RET( ctx  != NULL );
00818     ECDSA_VALIDATE_RET( hash != NULL );
00819     ECDSA_VALIDATE_RET( sig  != NULL );
00820     ECDSA_VALIDATE_RET( slen != NULL );
00821     return( mbedtls_ecdsa_write_signature( ctx, md_alg, hash, hlen, sig, slen,
00822                                    NULL, NULL ) );
00823 }
00824 #endif
00825 
00826 /*
00827  * Read and check signature
00828  */
00829 int mbedtls_ecdsa_read_signature( mbedtls_ecdsa_context *ctx,
00830                           const unsigned char *hash, size_t hlen,
00831                           const unsigned char *sig, size_t slen )
00832 {
00833     ECDSA_VALIDATE_RET( ctx  != NULL );
00834     ECDSA_VALIDATE_RET( hash != NULL );
00835     ECDSA_VALIDATE_RET( sig  != NULL );
00836     return( mbedtls_ecdsa_read_signature_restartable(
00837                 ctx, hash, hlen, sig, slen, NULL ) );
00838 }
00839 
00840 /*
00841  * Restartable read and check signature
00842  */
00843 int mbedtls_ecdsa_read_signature_restartable( mbedtls_ecdsa_context *ctx,
00844                           const unsigned char *hash, size_t hlen,
00845                           const unsigned char *sig, size_t slen,
00846                           mbedtls_ecdsa_restart_ctx *rs_ctx )
00847 {
00848     int ret;
00849     unsigned char *p = (unsigned char *) sig;
00850     const unsigned char *end = sig + slen;
00851     size_t len;
00852     mbedtls_mpi r, s;
00853     ECDSA_VALIDATE_RET( ctx  != NULL );
00854     ECDSA_VALIDATE_RET( hash != NULL );
00855     ECDSA_VALIDATE_RET( sig  != NULL );
00856 
00857     mbedtls_mpi_init( &r );
00858     mbedtls_mpi_init( &s );
00859 
00860     if( ( ret = mbedtls_asn1_get_tag( &p, end, &len,
00861                     MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE ) ) != 0 )
00862     {
00863         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
00864         goto cleanup;
00865     }
00866 
00867     if( p + len != end )
00868     {
00869         ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA +
00870               MBEDTLS_ERR_ASN1_LENGTH_MISMATCH;
00871         goto cleanup;
00872     }
00873 
00874     if( ( ret = mbedtls_asn1_get_mpi( &p, end, &r ) ) != 0 ||
00875         ( ret = mbedtls_asn1_get_mpi( &p, end, &s ) ) != 0 )
00876     {
00877         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
00878         goto cleanup;
00879     }
00880 #if defined(MBEDTLS_ECDSA_VERIFY_ALT)
00881     if( ( ret = mbedtls_ecdsa_verify( &ctx->grp , hash, hlen,
00882                                       &ctx->Q , &r, &s ) ) != 0 )
00883         goto cleanup;
00884 #else
00885     if( ( ret = ecdsa_verify_restartable( &ctx->grp , hash, hlen,
00886                               &ctx->Q , &r, &s, rs_ctx ) ) != 0 )
00887         goto cleanup;
00888 #endif /* MBEDTLS_ECDSA_VERIFY_ALT */
00889 
00890     /* At this point we know that the buffer starts with a valid signature.
00891      * Return 0 if the buffer just contains the signature, and a specific
00892      * error code if the valid signature is followed by more data. */
00893     if( p != end )
00894         ret = MBEDTLS_ERR_ECP_SIG_LEN_MISMATCH;
00895 
00896 cleanup:
00897     mbedtls_mpi_free( &r );
00898     mbedtls_mpi_free( &s );
00899 
00900     return( ret );
00901 }
00902 
00903 #if !defined(MBEDTLS_ECDSA_GENKEY_ALT)
00904 /*
00905  * Generate key pair
00906  */
00907 int mbedtls_ecdsa_genkey( mbedtls_ecdsa_context *ctx, mbedtls_ecp_group_id gid,
00908                   int (*f_rng)(void *, unsigned char *, size_t), void *p_rng )
00909 {
00910     int ret = 0;
00911     ECDSA_VALIDATE_RET( ctx   != NULL );
00912     ECDSA_VALIDATE_RET( f_rng != NULL );
00913 
00914     ret = mbedtls_ecp_group_load( &ctx->grp , gid );
00915     if( ret != 0 )
00916         return( ret );
00917 
00918    return( mbedtls_ecp_gen_keypair( &ctx->grp , &ctx->d ,
00919                                     &ctx->Q , f_rng, p_rng ) );
00920 }
00921 #endif /* !MBEDTLS_ECDSA_GENKEY_ALT */
00922 
00923 /*
00924  * Set context from an mbedtls_ecp_keypair
00925  */
00926 int mbedtls_ecdsa_from_keypair( mbedtls_ecdsa_context *ctx, const mbedtls_ecp_keypair *key )
00927 {
00928     int ret;
00929     ECDSA_VALIDATE_RET( ctx != NULL );
00930     ECDSA_VALIDATE_RET( key != NULL );
00931 
00932     if( ( ret = mbedtls_ecp_group_copy( &ctx->grp , &key->grp  ) ) != 0 ||
00933         ( ret = mbedtls_mpi_copy( &ctx->d , &key->d  ) ) != 0 ||
00934         ( ret = mbedtls_ecp_copy( &ctx->Q , &key->Q  ) ) != 0 )
00935     {
00936         mbedtls_ecdsa_free( ctx );
00937     }
00938 
00939     return( ret );
00940 }
00941 
00942 /*
00943  * Initialize context
00944  */
00945 void mbedtls_ecdsa_init( mbedtls_ecdsa_context *ctx )
00946 {
00947     ECDSA_VALIDATE( ctx != NULL );
00948 
00949     mbedtls_ecp_keypair_init( ctx );
00950 }
00951 
00952 /*
00953  * Free context
00954  */
00955 void mbedtls_ecdsa_free( mbedtls_ecdsa_context *ctx )
00956 {
00957     if( ctx == NULL )
00958         return;
00959 
00960     mbedtls_ecp_keypair_free( ctx );
00961 }
00962 
00963 #if defined(MBEDTLS_ECP_RESTARTABLE)
00964 /*
00965  * Initialize a restart context
00966  */
00967 void mbedtls_ecdsa_restart_init( mbedtls_ecdsa_restart_ctx *ctx )
00968 {
00969     ECDSA_VALIDATE( ctx != NULL );
00970 
00971     mbedtls_ecp_restart_init( &ctx->ecp  );
00972 
00973     ctx->ver  = NULL;
00974     ctx->sig  = NULL;
00975 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00976     ctx->det  = NULL;
00977 #endif
00978 }
00979 
00980 /*
00981  * Free the components of a restart context
00982  */
00983 void mbedtls_ecdsa_restart_free( mbedtls_ecdsa_restart_ctx *ctx )
00984 {
00985     if( ctx == NULL )
00986         return;
00987 
00988     mbedtls_ecp_restart_free( &ctx->ecp  );
00989 
00990     ecdsa_restart_ver_free( ctx->ver  );
00991     mbedtls_free( ctx->ver  );
00992     ctx->ver  = NULL;
00993 
00994     ecdsa_restart_sig_free( ctx->sig  );
00995     mbedtls_free( ctx->sig  );
00996     ctx->sig  = NULL;
00997 
00998 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
00999     ecdsa_restart_det_free( ctx->det  );
01000     mbedtls_free( ctx->det  );
01001     ctx->det  = NULL;
01002 #endif
01003 }
01004 #endif /* MBEDTLS_ECP_RESTARTABLE */
01005 
01006 #endif /* MBEDTLS_ECDSA_C */