common/mbedtls/ecdsa.c

   1 /*
   2  *  Elliptic curve DSA
   3  *
   4  *  Copyright The Mbed TLS Contributors
   5  *  SPDX-License-Identifier: Apache-2.0
   6  *
   7  *  Licensed under the Apache License, Version 2.0 (the "License"); you may
   8  *  not use this file except in compliance with the License.
   9  *  You may obtain a copy of the License at
  10  *
  11  *  http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  *  Unless required by applicable law or agreed to in writing, software
  14  *  distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  15  *  WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  *  See the License for the specific language governing permissions and
  17  *  limitations under the License.
  18  */
  19
  20 /*
  21  * References:
  22  *
  23  * SEC1 http://www.secg.org/index.php?action=secg,docs_secg
  24  */
  25
  26 #include "common.h"
  27
  28 #if defined(MBEDTLS_ECDSA_C)
  29
  30 #include "mbedtls/ecdsa.h"
  31 #include "mbedtls/asn1write.h"
  32
  33 #include <string.h>
  34
  35 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
  36 #include "mbedtls/hmac_drbg.h"
  37 #endif
  38
  39 #if defined(MBEDTLS_PLATFORM_C)
  40 #include "mbedtls/platform.h"
  41 #else
  42 #include <stdlib.h>
  43 #define mbedtls_calloc    calloc
  44 #define mbedtls_free       free
  45 #endif
  46
  47 #include "mbedtls/platform_util.h"
  48 #include "mbedtls/error.h"
  49
  50 /* Parameter validation macros based on platform_util.h */
  51 #define ECDSA_VALIDATE_RET( cond )    \
  52     MBEDTLS_INTERNAL_VALIDATE_RET( cond, MBEDTLS_ERR_ECP_BAD_INPUT_DATA )
  53 #define ECDSA_VALIDATE( cond )        \
  54     MBEDTLS_INTERNAL_VALIDATE( cond )
  55
  56 #if defined(MBEDTLS_ECP_RESTARTABLE)
  57
  58 /*
  59  * Sub-context for ecdsa_verify()
  60  */
  61 struct mbedtls_ecdsa_restart_ver {
  62     mbedtls_mpi u1, u2;     /* intermediate values  */
  63     enum {                  /* what to do next?     */
  64         ecdsa_ver_init = 0, /* getting started      */
  65         ecdsa_ver_muladd,   /* muladd step          */
  66     } state;
  67 };
  68
  69 /*
  70  * Init verify restart sub-context
  71  */
  72 static void ecdsa_restart_ver_init(mbedtls_ecdsa_restart_ver_ctx *ctx) {
  73     mbedtls_mpi_init(&ctx->u1);
  74     mbedtls_mpi_init(&ctx->u2);
  75     ctx->state = ecdsa_ver_init;
  76 }
  77
  78 /*
  79  * Free the components of a verify restart sub-context
  80  */
  81 static void ecdsa_restart_ver_free(mbedtls_ecdsa_restart_ver_ctx *ctx) {
  82     if (ctx == NULL)
  83         return;
  84
  85     mbedtls_mpi_free(&ctx->u1);
  86     mbedtls_mpi_free(&ctx->u2);
  87
  88     ecdsa_restart_ver_init(ctx);
  89 }
  90
  91 /*
  92  * Sub-context for ecdsa_sign()
  93  */
  94 struct mbedtls_ecdsa_restart_sig {
  95     int sign_tries;
  96     int key_tries;
  97     mbedtls_mpi k;          /* per-signature random */
  98     mbedtls_mpi r;          /* r value              */
  99     enum {                  /* what to do next?     */
 100         ecdsa_sig_init = 0, /* getting started      */
 101         ecdsa_sig_mul,      /* doing ecp_mul()      */
 102         ecdsa_sig_modn,     /* mod N computations   */
 103     } state;
 104 };
 105
 106 /*
 107  * Init verify sign sub-context
 108  */
 109 static void ecdsa_restart_sig_init(mbedtls_ecdsa_restart_sig_ctx *ctx) {
 110     ctx->sign_tries = 0;
 111     ctx->key_tries = 0;
 112     mbedtls_mpi_init(&ctx->k);
 113     mbedtls_mpi_init(&ctx->r);
 114     ctx->state = ecdsa_sig_init;
 115 }
 116
 117 /*
 118  * Free the components of a sign restart sub-context
 119  */
 120 static void ecdsa_restart_sig_free(mbedtls_ecdsa_restart_sig_ctx *ctx) {
 121     if (ctx == NULL)
 122         return;
 123
 124     mbedtls_mpi_free(&ctx->k);
 125     mbedtls_mpi_free(&ctx->r);
 126 }
 127
 128 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
 129 /*
 130  * Sub-context for ecdsa_sign_det()
 131  */
 132 struct mbedtls_ecdsa_restart_det {
 133     mbedtls_hmac_drbg_context rng_ctx;  /* DRBG state   */
 134     enum {                      /* what to do next?     */
 135         ecdsa_det_init = 0,     /* getting started      */
 136         ecdsa_det_sign,         /* make signature       */
 137     } state;
 138 };
 139
 140 /*
 141  * Init verify sign_det sub-context
 142  */
 143 static void ecdsa_restart_det_init(mbedtls_ecdsa_restart_det_ctx *ctx) {
 144     mbedtls_hmac_drbg_init(&ctx->rng_ctx);
 145     ctx->state = ecdsa_det_init;
 146 }
 147
 148 /*
 149  * Free the components of a sign_det restart sub-context
 150  */
 151 static void ecdsa_restart_det_free(mbedtls_ecdsa_restart_det_ctx *ctx) {
 152     if (ctx == NULL)
 153         return;
 154
 155     mbedtls_hmac_drbg_free(&ctx->rng_ctx);
 156
 157     ecdsa_restart_det_init(ctx);
 158 }
 159 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
 160
 161 #define ECDSA_RS_ECP    ( rs_ctx == NULL ? NULL : &rs_ctx->ecp )
 162
 163 /* Utility macro for checking and updating ops budget */
 164 #define ECDSA_BUDGET( ops )   \
 165     MBEDTLS_MPI_CHK( mbedtls_ecp_check_budget( grp, ECDSA_RS_ECP, ops ) );
 166
 167 /* Call this when entering a function that needs its own sub-context */
 168 #define ECDSA_RS_ENTER( SUB )   do {                                 \
 169     /* reset ops count for this call if top-level */                 \
 170     if( rs_ctx != NULL && rs_ctx->ecp.depth++ == 0 )                 \
 171         rs_ctx->ecp.ops_done = 0;                                    \
 172                                                                      \
 173     /* set up our own sub-context if needed */                       \
 174     if( mbedtls_ecp_restart_is_enabled() &&                          \
 175         rs_ctx != NULL && rs_ctx->SUB == NULL )                      \
 176     {                                                                \
 177         rs_ctx->SUB = mbedtls_calloc( 1, sizeof( *rs_ctx->SUB ) );   \
 178         if( rs_ctx->SUB == NULL )                                    \
 179             return( MBEDTLS_ERR_ECP_ALLOC_FAILED );                  \
 180                                                                      \
 181         ecdsa_restart_## SUB ##_init( rs_ctx->SUB );                 \
 182     }                                                                \
 183 } while( 0 )
 184
 185 /* Call this when leaving a function that needs its own sub-context */
 186 #define ECDSA_RS_LEAVE( SUB )   do {                                 \
 187     /* clear our sub-context when not in progress (done or error) */ \
 188     if( rs_ctx != NULL && rs_ctx->SUB != NULL &&                     \
 189         ret != MBEDTLS_ERR_ECP_IN_PROGRESS )                         \
 190     {                                                                \
 191         ecdsa_restart_## SUB ##_free( rs_ctx->SUB );                 \
 192         mbedtls_free( rs_ctx->SUB );                                 \
 193         rs_ctx->SUB = NULL;                                          \
 194     }                                                                \
 195                                                                      \
 196     if( rs_ctx != NULL )                                             \
 197         rs_ctx->ecp.depth--;                                         \
 198 } while( 0 )
 199
 200 #else /* MBEDTLS_ECP_RESTARTABLE */
 201
 202 #define ECDSA_RS_ECP    NULL
 203
 204 #define ECDSA_BUDGET( ops )   /* no-op; for compatibility */
 205
 206 #define ECDSA_RS_ENTER( SUB )   (void) rs_ctx
 207 #define ECDSA_RS_LEAVE( SUB )   (void) rs_ctx
 208
 209 #endif /* MBEDTLS_ECP_RESTARTABLE */
 210
 211 #if defined(MBEDTLS_ECDSA_DETERMINISTIC) || \
 212     !defined(MBEDTLS_ECDSA_SIGN_ALT)     || \
 213     !defined(MBEDTLS_ECDSA_VERIFY_ALT)
 214 /*
 215  * Derive a suitable integer for group grp from a buffer of length len
 216  * SEC1 4.1.3 step 5 aka SEC1 4.1.4 step 3
 217  */
 218 static int derive_mpi(const mbedtls_ecp_group *grp, mbedtls_mpi *x,
 219                       const unsigned char *buf, size_t blen) {
 220     int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
 221     size_t n_size = (grp->nbits + 7) / 8;
 222     size_t use_size = blen > n_size ? n_size : blen;
 223
 224     MBEDTLS_MPI_CHK(mbedtls_mpi_read_binary(x, buf, use_size));
 225     if (use_size * 8 > grp->nbits)
 226         MBEDTLS_MPI_CHK(mbedtls_mpi_shift_r(x, use_size * 8 - grp->nbits));
 227
 228     /* While at it, reduce modulo N */
 229     if (mbedtls_mpi_cmp_mpi(x, &grp->N) >= 0)
 230         MBEDTLS_MPI_CHK(mbedtls_mpi_sub_mpi(x, x, &grp->N));
 231
 232 cleanup:
 233     return (ret);
 234 }
 235 #endif /* ECDSA_DETERMINISTIC || !ECDSA_SIGN_ALT || !ECDSA_VERIFY_ALT */
 236
 237 #if !defined(MBEDTLS_ECDSA_SIGN_ALT)
 238 /*
 239  * Compute ECDSA signature of a hashed message (SEC1 4.1.3)
 240  * Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message)
 241  */
 242 static int ecdsa_sign_restartable(mbedtls_ecp_group *grp,
 243                                   mbedtls_mpi *r, mbedtls_mpi *s,
 244                                   const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
 245                                   int (*f_rng)(void *, unsigned char *, size_t), void *p_rng,
 246                                   int (*f_rng_blind)(void *, unsigned char *, size_t),
 247                                   void *p_rng_blind,
 248                                   mbedtls_ecdsa_restart_ctx *rs_ctx) {
 249     int ret, key_tries, sign_tries;
 250     int *p_sign_tries = &sign_tries, *p_key_tries = &key_tries;
 251     mbedtls_ecp_point R;
 252     mbedtls_mpi k, e, t;
 253     mbedtls_mpi *pk = &k, *pr = r;
 254
 255     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
 256     if (! mbedtls_ecdsa_can_do(grp->id) || grp->N.p == NULL)
 257         return (MBEDTLS_ERR_ECP_BAD_INPUT_DATA);
 258
 259     /* Make sure d is in range 1..n-1 */
 260     if (mbedtls_mpi_cmp_int(d, 1) < 0 || mbedtls_mpi_cmp_mpi(d, &grp->N) >= 0)
 261         return (MBEDTLS_ERR_ECP_INVALID_KEY);
 262
 263     mbedtls_ecp_point_init(&R);
 264     mbedtls_mpi_init(&k);
 265     mbedtls_mpi_init(&e);
 266     mbedtls_mpi_init(&t);
 267
 268     ECDSA_RS_ENTER(sig);
 269
 270 #if defined(MBEDTLS_ECP_RESTARTABLE)
 271     if (rs_ctx != NULL && rs_ctx->sig != NULL) {
 272         /* redirect to our context */
 273         p_sign_tries = &rs_ctx->sig->sign_tries;
 274         p_key_tries = &rs_ctx->sig->key_tries;
 275         pk = &rs_ctx->sig->k;
 276         pr = &rs_ctx->sig->r;
 277
 278         /* jump to current step */
 279         if (rs_ctx->sig->state == ecdsa_sig_mul)
 280             goto mul;
 281         if (rs_ctx->sig->state == ecdsa_sig_modn)
 282             goto modn;
 283     }
 284 #endif /* MBEDTLS_ECP_RESTARTABLE */
 285
 286     *p_sign_tries = 0;
 287     do {
 288         if ((*p_sign_tries)++ > 10) {
 289             ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
 290             goto cleanup;
 291         }
 292
 293         /*
 294          * Steps 1-3: generate a suitable ephemeral keypair
 295          * and set r = xR mod n
 296          */
 297         *p_key_tries = 0;
 298         do {
 299             if ((*p_key_tries)++ > 10) {
 300                 ret = MBEDTLS_ERR_ECP_RANDOM_FAILED;
 301                 goto cleanup;
 302             }
 303
 304             MBEDTLS_MPI_CHK(mbedtls_ecp_gen_privkey(grp, pk, f_rng, p_rng));
 305
 306 #if defined(MBEDTLS_ECP_RESTARTABLE)
 307             if (rs_ctx != NULL && rs_ctx->sig != NULL)
 308                 rs_ctx->sig->state = ecdsa_sig_mul;
 309
 310 mul:
 311 #endif
 312             MBEDTLS_MPI_CHK(mbedtls_ecp_mul_restartable(grp, &R, pk, &grp->G,
 313                                                         f_rng_blind,
 314                                                         p_rng_blind,
 315                                                         ECDSA_RS_ECP));
 316             MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(pr, &R.X, &grp->N));
 317         } while (mbedtls_mpi_cmp_int(pr, 0) == 0);
 318
 319 #if defined(MBEDTLS_ECP_RESTARTABLE)
 320         if (rs_ctx != NULL && rs_ctx->sig != NULL)
 321             rs_ctx->sig->state = ecdsa_sig_modn;
 322
 323 modn:
 324 #endif
 325         /*
 326          * Accounting for everything up to the end of the loop
 327          * (step 6, but checking now avoids saving e and t)
 328          */
 329         ECDSA_BUDGET(MBEDTLS_ECP_OPS_INV + 4);
 330
 331         /*
 332          * Step 5: derive MPI from hashed message
 333          */
 334         MBEDTLS_MPI_CHK(derive_mpi(grp, &e, buf, blen));
 335
 336         /*
 337          * Generate a random value to blind inv_mod in next step,
 338          * avoiding a potential timing leak.
 339          */
 340         MBEDTLS_MPI_CHK(mbedtls_ecp_gen_privkey(grp, &t, f_rng_blind,
 341                                                 p_rng_blind));
 342
 343         /*
 344          * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
 345          */
 346         MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(s, pr, d));
 347         MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&e, &e, s));
 348         MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&e, &e, &t));
 349         MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(pk, pk, &t));
 350         MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(pk, pk, &grp->N));
 351         MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(s, pk, &grp->N));
 352         MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(s, s, &e));
 353         MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(s, s, &grp->N));
 354     } while (mbedtls_mpi_cmp_int(s, 0) == 0);
 355
 356 #if defined(MBEDTLS_ECP_RESTARTABLE)
 357     if (rs_ctx != NULL && rs_ctx->sig != NULL)
 358         mbedtls_mpi_copy(r, pr);
 359 #endif
 360
 361 cleanup:
 362     mbedtls_ecp_point_free(&R);
 363     mbedtls_mpi_free(&k);
 364     mbedtls_mpi_free(&e);
 365     mbedtls_mpi_free(&t);
 366
 367     ECDSA_RS_LEAVE(sig);
 368
 369     return (ret);
 370 }
 371
 372 int mbedtls_ecdsa_can_do(mbedtls_ecp_group_id gid) {
 373     switch (gid) {
 374 #ifdef MBEDTLS_ECP_DP_CURVE25519_ENABLED
 375         case MBEDTLS_ECP_DP_CURVE25519:
 376             return 0;
 377 #endif
 378 #ifdef MBEDTLS_ECP_DP_CURVE448_ENABLED
 379         case MBEDTLS_ECP_DP_CURVE448:
 380             return 0;
 381 #endif
 382         default:
 383             return 1;
 384     }
 385 }
 386
 387 /*
 388  * Compute ECDSA signature of a hashed message
 389  */
 390 int mbedtls_ecdsa_sign(mbedtls_ecp_group *grp, mbedtls_mpi *r, mbedtls_mpi *s,
 391                        const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
 392                        int (*f_rng)(void *, unsigned char *, size_t), void *p_rng) {
 393     ECDSA_VALIDATE_RET(grp   != NULL);
 394     ECDSA_VALIDATE_RET(r     != NULL);
 395     ECDSA_VALIDATE_RET(s     != NULL);
 396     ECDSA_VALIDATE_RET(d     != NULL);
 397     ECDSA_VALIDATE_RET(f_rng != NULL);
 398     ECDSA_VALIDATE_RET(buf   != NULL || blen == 0);
 399
 400     /* Use the same RNG for both blinding and ephemeral key generation */
 401     return (ecdsa_sign_restartable(grp, r, s, d, buf, blen,
 402                                    f_rng, p_rng, f_rng, p_rng, NULL));
 403 }
 404 #endif /* !MBEDTLS_ECDSA_SIGN_ALT */
 405
 406 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
 407 /*
 408  * Deterministic signature wrapper
 409  */
 410 static int ecdsa_sign_det_restartable(mbedtls_ecp_group *grp,
 411                                       mbedtls_mpi *r, mbedtls_mpi *s,
 412                                       const mbedtls_mpi *d, const unsigned char *buf, size_t blen,
 413                                       mbedtls_md_type_t md_alg,
 414                                       int (*f_rng_blind)(void *, unsigned char *, size_t),
 415                                       void *p_rng_blind,
 416                                       mbedtls_ecdsa_restart_ctx *rs_ctx) {
 417     int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
 418     mbedtls_hmac_drbg_context rng_ctx;
 419     mbedtls_hmac_drbg_context *p_rng = &rng_ctx;
 420     unsigned char data[2 * MBEDTLS_ECP_MAX_BYTES];
 421     size_t grp_len = (grp->nbits + 7) / 8;
 422     const mbedtls_md_info_t *md_info;
 423     mbedtls_mpi h;
 424
 425     if ((md_info = mbedtls_md_info_from_type(md_alg)) == NULL)
 426         return (MBEDTLS_ERR_ECP_BAD_INPUT_DATA);
 427
 428     mbedtls_mpi_init(&h);
 429     mbedtls_hmac_drbg_init(&rng_ctx);
 430
 431     ECDSA_RS_ENTER(det);
 432
 433 #if defined(MBEDTLS_ECP_RESTARTABLE)
 434     if (rs_ctx != NULL && rs_ctx->det != NULL) {
 435         /* redirect to our context */
 436         p_rng = &rs_ctx->det->rng_ctx;
 437
 438         /* jump to current step */
 439         if (rs_ctx->det->state == ecdsa_det_sign)
 440             goto sign;
 441     }
 442 #endif /* MBEDTLS_ECP_RESTARTABLE */
 443
 444     /* Use private key and message hash (reduced) to initialize HMAC_DRBG */
 445     MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(d, data, grp_len));
 446     MBEDTLS_MPI_CHK(derive_mpi(grp, &h, buf, blen));
 447     MBEDTLS_MPI_CHK(mbedtls_mpi_write_binary(&h, data + grp_len, grp_len));
 448     mbedtls_hmac_drbg_seed_buf(p_rng, md_info, data, 2 * grp_len);
 449
 450 #if defined(MBEDTLS_ECP_RESTARTABLE)
 451     if (rs_ctx != NULL && rs_ctx->det != NULL)
 452         rs_ctx->det->state = ecdsa_det_sign;
 453
 454 sign:
 455 #endif
 456 #if defined(MBEDTLS_ECDSA_SIGN_ALT)
 457     (void) f_rng_blind;
 458     (void) p_rng_blind;
 459     ret = mbedtls_ecdsa_sign(grp, r, s, d, buf, blen,
 460                              mbedtls_hmac_drbg_random, p_rng);
 461 #else
 462     if (f_rng_blind != NULL)
 463         ret = ecdsa_sign_restartable(grp, r, s, d, buf, blen,
 464                                      mbedtls_hmac_drbg_random, p_rng,
 465                                      f_rng_blind, p_rng_blind, rs_ctx);
 466     else {
 467         mbedtls_hmac_drbg_context *p_rng_blind_det;
 468
 469 #if !defined(MBEDTLS_ECP_RESTARTABLE)
 470         /*
 471          * To avoid reusing rng_ctx and risking incorrect behavior we seed a
 472          * second HMAC-DRBG with the same seed. We also apply a label to avoid
 473          * reusing the bits of the ephemeral key for blinding and eliminate the
 474          * risk that they leak this way.
 475          */
 476         const char *blind_label = "BLINDING CONTEXT";
 477         mbedtls_hmac_drbg_context rng_ctx_blind;
 478
 479         mbedtls_hmac_drbg_init(&rng_ctx_blind);
 480         p_rng_blind_det = &rng_ctx_blind;
 481         mbedtls_hmac_drbg_seed_buf(p_rng_blind_det, md_info,
 482                                    data, 2 * grp_len);
 483         ret = mbedtls_hmac_drbg_update_ret(p_rng_blind_det,
 484                                            (const unsigned char *) blind_label,
 485                                            strlen(blind_label));
 486         if (ret != 0) {
 487             mbedtls_hmac_drbg_free(&rng_ctx_blind);
 488             goto cleanup;
 489         }
 490 #else
 491         /*
 492          * In the case of restartable computations we would either need to store
 493          * the second RNG in the restart context too or set it up at every
 494          * restart. The first option would penalize the correct application of
 495          * the function and the second would defeat the purpose of the
 496          * restartable feature.
 497          *
 498          * Therefore in this case we reuse the original RNG. This comes with the
 499          * price that the resulting signature might not be a valid deterministic
 500          * ECDSA signature with a very low probability (same magnitude as
 501          * successfully guessing the private key). However even then it is still
 502          * a valid ECDSA signature.
 503          */
 504         p_rng_blind_det = p_rng;
 505 #endif /* MBEDTLS_ECP_RESTARTABLE */
 506
 507         /*
 508          * Since the output of the RNGs is always the same for the same key and
 509          * message, this limits the efficiency of blinding and leaks information
 510          * through side channels. After mbedtls_ecdsa_sign_det() is removed NULL
 511          * won't be a valid value for f_rng_blind anymore. Therefore it should
 512          * be checked by the caller and this branch and check can be removed.
 513          */
 514         ret = ecdsa_sign_restartable(grp, r, s, d, buf, blen,
 515                                      mbedtls_hmac_drbg_random, p_rng,
 516                                      mbedtls_hmac_drbg_random, p_rng_blind_det,
 517                                      rs_ctx);
 518
 519 #if !defined(MBEDTLS_ECP_RESTARTABLE)
 520         mbedtls_hmac_drbg_free(&rng_ctx_blind);
 521 #endif
 522     }
 523 #endif /* MBEDTLS_ECDSA_SIGN_ALT */
 524
 525 cleanup:
 526     mbedtls_hmac_drbg_free(&rng_ctx);
 527     mbedtls_mpi_free(&h);
 528
 529     ECDSA_RS_LEAVE(det);
 530
 531     return (ret);
 532 }
 533
 534 /*
 535  * Deterministic signature wrappers
 536  */
 537
 538 #if !defined(MBEDTLS_DEPRECATED_REMOVED)
 539 int mbedtls_ecdsa_sign_det(mbedtls_ecp_group *grp, mbedtls_mpi *r,
 540                            mbedtls_mpi *s, const mbedtls_mpi *d,
 541                            const unsigned char *buf, size_t blen,
 542                            mbedtls_md_type_t md_alg) {
 543     ECDSA_VALIDATE_RET(grp   != NULL);
 544     ECDSA_VALIDATE_RET(r     != NULL);
 545     ECDSA_VALIDATE_RET(s     != NULL);
 546     ECDSA_VALIDATE_RET(d     != NULL);
 547     ECDSA_VALIDATE_RET(buf   != NULL || blen == 0);
 548
 549     return (ecdsa_sign_det_restartable(grp, r, s, d, buf, blen, md_alg,
 550                                        NULL, NULL, NULL));
 551 }
 552 #endif /* MBEDTLS_DEPRECATED_REMOVED */
 553
 554 int mbedtls_ecdsa_sign_det_ext(mbedtls_ecp_group *grp, mbedtls_mpi *r,
 555                                mbedtls_mpi *s, const mbedtls_mpi *d,
 556                                const unsigned char *buf, size_t blen,
 557                                mbedtls_md_type_t md_alg,
 558                                int (*f_rng_blind)(void *, unsigned char *,
 559                                                   size_t),
 560                                void *p_rng_blind) {
 561     ECDSA_VALIDATE_RET(grp   != NULL);
 562     ECDSA_VALIDATE_RET(r     != NULL);
 563     ECDSA_VALIDATE_RET(s     != NULL);
 564     ECDSA_VALIDATE_RET(d     != NULL);
 565     ECDSA_VALIDATE_RET(buf   != NULL || blen == 0);
 566     ECDSA_VALIDATE_RET(f_rng_blind != NULL);
 567
 568     return (ecdsa_sign_det_restartable(grp, r, s, d, buf, blen, md_alg,
 569                                        f_rng_blind, p_rng_blind, NULL));
 570 }
 571 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
 572
 573 #if !defined(MBEDTLS_ECDSA_VERIFY_ALT)
 574 /*
 575  * Verify ECDSA signature of hashed message (SEC1 4.1.4)
 576  * Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message)
 577  */
 578 static int ecdsa_verify_restartable(mbedtls_ecp_group *grp,
 579                                     const unsigned char *buf, size_t blen,
 580                                     const mbedtls_ecp_point *Q,
 581                                     const mbedtls_mpi *r, const mbedtls_mpi *s,
 582                                     mbedtls_ecdsa_restart_ctx *rs_ctx) {
 583     int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
 584     mbedtls_mpi e, s_inv, u1, u2;
 585     mbedtls_ecp_point R;
 586     mbedtls_mpi *pu1 = &u1, *pu2 = &u2;
 587
 588     mbedtls_ecp_point_init(&R);
 589     mbedtls_mpi_init(&e);
 590     mbedtls_mpi_init(&s_inv);
 591     mbedtls_mpi_init(&u1);
 592     mbedtls_mpi_init(&u2);
 593
 594     /* Fail cleanly on curves such as Curve25519 that can't be used for ECDSA */
 595     if (! mbedtls_ecdsa_can_do(grp->id) || grp->N.p == NULL)
 596         return (MBEDTLS_ERR_ECP_BAD_INPUT_DATA);
 597
 598     ECDSA_RS_ENTER(ver);
 599
 600 #if defined(MBEDTLS_ECP_RESTARTABLE)
 601     if (rs_ctx != NULL && rs_ctx->ver != NULL) {
 602         /* redirect to our context */
 603         pu1 = &rs_ctx->ver->u1;
 604         pu2 = &rs_ctx->ver->u2;
 605
 606         /* jump to current step */
 607         if (rs_ctx->ver->state == ecdsa_ver_muladd)
 608             goto muladd;
 609     }
 610 #endif /* MBEDTLS_ECP_RESTARTABLE */
 611
 612     /*
 613      * Step 1: make sure r and s are in range 1..n-1
 614      */
 615     if (mbedtls_mpi_cmp_int(r, 1) < 0 || mbedtls_mpi_cmp_mpi(r, &grp->N) >= 0 ||
 616             mbedtls_mpi_cmp_int(s, 1) < 0 || mbedtls_mpi_cmp_mpi(s, &grp->N) >= 0) {
 617         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
 618         goto cleanup;
 619     }
 620
 621     /*
 622      * Step 3: derive MPI from hashed message
 623      */
 624     MBEDTLS_MPI_CHK(derive_mpi(grp, &e, buf, blen));
 625
 626     /*
 627      * Step 4: u1 = e / s mod n, u2 = r / s mod n
 628      */
 629     ECDSA_BUDGET(MBEDTLS_ECP_OPS_CHK + MBEDTLS_ECP_OPS_INV + 2);
 630
 631     MBEDTLS_MPI_CHK(mbedtls_mpi_inv_mod(&s_inv, s, &grp->N));
 632
 633     MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(pu1, &e, &s_inv));
 634     MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(pu1, pu1, &grp->N));
 635
 636     MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(pu2, r, &s_inv));
 637     MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(pu2, pu2, &grp->N));
 638
 639 #if defined(MBEDTLS_ECP_RESTARTABLE)
 640     if (rs_ctx != NULL && rs_ctx->ver != NULL)
 641         rs_ctx->ver->state = ecdsa_ver_muladd;
 642
 643 muladd:
 644 #endif
 645     /*
 646      * Step 5: R = u1 G + u2 Q
 647      */
 648     MBEDTLS_MPI_CHK(mbedtls_ecp_muladd_restartable(grp,
 649                                                    &R, pu1, &grp->G, pu2, Q, ECDSA_RS_ECP));
 650
 651     if (mbedtls_ecp_is_zero(&R)) {
 652         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
 653         goto cleanup;
 654     }
 655
 656     /*
 657      * Step 6: convert xR to an integer (no-op)
 658      * Step 7: reduce xR mod n (gives v)
 659      */
 660     MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&R.X, &R.X, &grp->N));
 661
 662     /*
 663      * Step 8: check if v (that is, R.X) is equal to r
 664      */
 665     if (mbedtls_mpi_cmp_mpi(&R.X, r) != 0) {
 666         ret = MBEDTLS_ERR_ECP_VERIFY_FAILED;
 667         goto cleanup;
 668     }
 669
 670 cleanup:
 671     mbedtls_ecp_point_free(&R);
 672     mbedtls_mpi_free(&e);
 673     mbedtls_mpi_free(&s_inv);
 674     mbedtls_mpi_free(&u1);
 675     mbedtls_mpi_free(&u2);
 676
 677     ECDSA_RS_LEAVE(ver);
 678
 679     return (ret);
 680 }
 681
 682 /*
 683  * Verify ECDSA signature of hashed message
 684  */
 685 int mbedtls_ecdsa_verify(mbedtls_ecp_group *grp,
 686                          const unsigned char *buf, size_t blen,
 687                          const mbedtls_ecp_point *Q,
 688                          const mbedtls_mpi *r,
 689                          const mbedtls_mpi *s) {
 690     ECDSA_VALIDATE_RET(grp != NULL);
 691     ECDSA_VALIDATE_RET(Q   != NULL);
 692     ECDSA_VALIDATE_RET(r   != NULL);
 693     ECDSA_VALIDATE_RET(s   != NULL);
 694     ECDSA_VALIDATE_RET(buf != NULL || blen == 0);
 695
 696     return (ecdsa_verify_restartable(grp, buf, blen, Q, r, s, NULL));
 697 }
 698 #endif /* !MBEDTLS_ECDSA_VERIFY_ALT */
 699
 700 /*
 701  * Convert a signature (given by context) to ASN.1
 702  */
 703 int ecdsa_signature_to_asn1(const mbedtls_mpi *r, const mbedtls_mpi *s,
 704                             unsigned char *sig, size_t *slen) {
 705     int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
 706
 707     unsigned char buf[MBEDTLS_ECDSA_MAX_LEN] = {0};
 708     unsigned char *p = buf + sizeof(buf) - 1;
 709     size_t len = 0;
 710
 711     MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_mpi(&p, buf, s));
 712     MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_mpi(&p, buf, r));
 713
 714     MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_len(&p, buf, len));
 715     MBEDTLS_ASN1_CHK_ADD(len, mbedtls_asn1_write_tag(&p, buf,
 716                                                      MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE));
 717
 718     memcpy(sig, p, len);
 719     *slen = len;
 720
 721     return (0);
 722 }
 723
 724 /*
 725  * Compute and write signature
 726  */
 727 int mbedtls_ecdsa_write_signature_restartable(mbedtls_ecdsa_context *ctx,
 728                                               mbedtls_md_type_t md_alg,
 729                                               const unsigned char *hash, size_t hlen,
 730                                               unsigned char *sig, size_t *slen,
 731                                               int (*f_rng)(void *, unsigned char *, size_t),
 732                                               void *p_rng,
 733                                               mbedtls_ecdsa_restart_ctx *rs_ctx) {
 734     int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
 735     mbedtls_mpi r, s;
 736     ECDSA_VALIDATE_RET(ctx  != NULL);
 737     ECDSA_VALIDATE_RET(hash != NULL);
 738     ECDSA_VALIDATE_RET(sig  != NULL);
 739     ECDSA_VALIDATE_RET(slen != NULL);
 740
 741     mbedtls_mpi_init(&r);
 742     mbedtls_mpi_init(&s);
 743
 744 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
 745     MBEDTLS_MPI_CHK(ecdsa_sign_det_restartable(&ctx->grp, &r, &s, &ctx->d,
 746                                                hash, hlen, md_alg, f_rng,
 747                                                p_rng, rs_ctx));
 748 #else
 749     (void) md_alg;
 750
 751 #if defined(MBEDTLS_ECDSA_SIGN_ALT)
 752     (void) rs_ctx;
 753
 754     MBEDTLS_MPI_CHK(mbedtls_ecdsa_sign(&ctx->grp, &r, &s, &ctx->d,
 755                                        hash, hlen, f_rng, p_rng));
 756 #else
 757     /* Use the same RNG for both blinding and ephemeral key generation */
 758     MBEDTLS_MPI_CHK(ecdsa_sign_restartable(&ctx->grp, &r, &s, &ctx->d,
 759                                            hash, hlen, f_rng, p_rng, f_rng,
 760                                            p_rng, rs_ctx));
 761 #endif /* MBEDTLS_ECDSA_SIGN_ALT */
 762 #endif /* MBEDTLS_ECDSA_DETERMINISTIC */
 763
 764     MBEDTLS_MPI_CHK(ecdsa_signature_to_asn1(&r, &s, sig, slen));
 765
 766 cleanup:
 767     mbedtls_mpi_free(&r);
 768     mbedtls_mpi_free(&s);
 769
 770     return (ret);
 771 }
 772
 773 /*
 774  * Compute and write signature
 775  */
 776 int mbedtls_ecdsa_write_signature(mbedtls_ecdsa_context *ctx,
 777                                   mbedtls_md_type_t md_alg,
 778                                   const unsigned char *hash, size_t hlen,
 779                                   unsigned char *sig, size_t *slen,
 780                                   int (*f_rng)(void *, unsigned char *, size_t),
 781                                   void *p_rng) {
 782     ECDSA_VALIDATE_RET(ctx  != NULL);
 783     ECDSA_VALIDATE_RET(hash != NULL);
 784     ECDSA_VALIDATE_RET(sig  != NULL);
 785     ECDSA_VALIDATE_RET(slen != NULL);
 786     return (mbedtls_ecdsa_write_signature_restartable(
 787                 ctx, md_alg, hash, hlen, sig, slen, f_rng, p_rng, NULL));
 788 }
 789
 790 #if !defined(MBEDTLS_DEPRECATED_REMOVED) && \
 791     defined(MBEDTLS_ECDSA_DETERMINISTIC)
 792 int mbedtls_ecdsa_write_signature_det(mbedtls_ecdsa_context *ctx,
 793                                       const unsigned char *hash, size_t hlen,
 794                                       unsigned char *sig, size_t *slen,
 795                                       mbedtls_md_type_t md_alg) {
 796     ECDSA_VALIDATE_RET(ctx  != NULL);
 797     ECDSA_VALIDATE_RET(hash != NULL);
 798     ECDSA_VALIDATE_RET(sig  != NULL);
 799     ECDSA_VALIDATE_RET(slen != NULL);
 800     return (mbedtls_ecdsa_write_signature(ctx, md_alg, hash, hlen, sig, slen,
 801                                           NULL, NULL));
 802 }
 803 #endif
 804
 805 /*
 806  * Read and check signature
 807  */
 808 int mbedtls_ecdsa_read_signature(mbedtls_ecdsa_context *ctx,
 809                                  const unsigned char *hash, size_t hlen,
 810                                  const unsigned char *sig, size_t slen) {
 811     ECDSA_VALIDATE_RET(ctx  != NULL);
 812     ECDSA_VALIDATE_RET(hash != NULL);
 813     ECDSA_VALIDATE_RET(sig  != NULL);
 814     return (mbedtls_ecdsa_read_signature_restartable(
 815                 ctx, hash, hlen, sig, slen, NULL));
 816 }
 817
 818 /*
 819  * Restartable read and check signature
 820  */
 821 int mbedtls_ecdsa_read_signature_restartable(mbedtls_ecdsa_context *ctx,
 822                                              const unsigned char *hash, size_t hlen,
 823                                              const unsigned char *sig, size_t slen,
 824                                              mbedtls_ecdsa_restart_ctx *rs_ctx) {
 825     int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
 826     unsigned char *p = (unsigned char *) sig;
 827     const unsigned char *end = sig + slen;
 828     size_t len;
 829     mbedtls_mpi r, s;
 830     ECDSA_VALIDATE_RET(ctx  != NULL);
 831     ECDSA_VALIDATE_RET(hash != NULL);
 832     ECDSA_VALIDATE_RET(sig  != NULL);
 833
 834     mbedtls_mpi_init(&r);
 835     mbedtls_mpi_init(&s);
 836
 837     if ((ret = mbedtls_asn1_get_tag(&p, end, &len,
 838                                     MBEDTLS_ASN1_CONSTRUCTED | MBEDTLS_ASN1_SEQUENCE)) != 0) {
 839         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
 840         goto cleanup;
 841     }
 842
 843     if (p + len != end) {
 844         ret = MBEDTLS_ERR_ECP_BAD_INPUT_DATA +
 845               MBEDTLS_ERR_ASN1_LENGTH_MISMATCH;
 846         goto cleanup;
 847     }
 848
 849     if ((ret = mbedtls_asn1_get_mpi(&p, end, &r)) != 0 ||
 850             (ret = mbedtls_asn1_get_mpi(&p, end, &s)) != 0) {
 851         ret += MBEDTLS_ERR_ECP_BAD_INPUT_DATA;
 852         goto cleanup;
 853     }
 854 #if defined(MBEDTLS_ECDSA_VERIFY_ALT)
 855     (void) rs_ctx;
 856
 857     if ((ret = mbedtls_ecdsa_verify(&ctx->grp, hash, hlen,
 858                                     &ctx->Q, &r, &s)) != 0)
 859         goto cleanup;
 860 #else
 861     if ((ret = ecdsa_verify_restartable(&ctx->grp, hash, hlen,
 862                                         &ctx->Q, &r, &s, rs_ctx)) != 0)
 863         goto cleanup;
 864 #endif /* MBEDTLS_ECDSA_VERIFY_ALT */
 865
 866     /* At this point we know that the buffer starts with a valid signature.
 867      * Return 0 if the buffer just contains the signature, and a specific
 868      * error code if the valid signature is followed by more data. */
 869     if (p != end)
 870         ret = MBEDTLS_ERR_ECP_SIG_LEN_MISMATCH;
 871
 872 cleanup:
 873     mbedtls_mpi_free(&r);
 874     mbedtls_mpi_free(&s);
 875
 876     return (ret);
 877 }
 878
 879 #if !defined(MBEDTLS_ECDSA_GENKEY_ALT)
 880 /*
 881  * Generate key pair
 882  */
 883 int mbedtls_ecdsa_genkey(mbedtls_ecdsa_context *ctx, mbedtls_ecp_group_id gid,
 884                          int (*f_rng)(void *, unsigned char *, size_t), void *p_rng) {
 885     int ret = 0;
 886     ECDSA_VALIDATE_RET(ctx   != NULL);
 887     ECDSA_VALIDATE_RET(f_rng != NULL);
 888
 889     ret = mbedtls_ecp_group_load(&ctx->grp, gid);
 890     if (ret != 0)
 891         return (ret);
 892
 893     return (mbedtls_ecp_gen_keypair(&ctx->grp, &ctx->d,
 894                                     &ctx->Q, f_rng, p_rng));
 895 }
 896 #endif /* !MBEDTLS_ECDSA_GENKEY_ALT */
 897
 898 /*
 899  * Set context from an mbedtls_ecp_keypair
 900  */
 901 int mbedtls_ecdsa_from_keypair(mbedtls_ecdsa_context *ctx, const mbedtls_ecp_keypair *key) {
 902     int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
 903     ECDSA_VALIDATE_RET(ctx != NULL);
 904     ECDSA_VALIDATE_RET(key != NULL);
 905
 906     if ((ret = mbedtls_ecp_group_copy(&ctx->grp, &key->grp)) != 0 ||
 907             (ret = mbedtls_mpi_copy(&ctx->d, &key->d)) != 0 ||
 908             (ret = mbedtls_ecp_copy(&ctx->Q, &key->Q)) != 0) {
 909         mbedtls_ecdsa_free(ctx);
 910     }
 911
 912     return (ret);
 913 }
 914
 915 /*
 916  * Initialize context
 917  */
 918 void mbedtls_ecdsa_init(mbedtls_ecdsa_context *ctx) {
 919     ECDSA_VALIDATE(ctx != NULL);
 920
 921     mbedtls_ecp_keypair_init(ctx);
 922 }
 923
 924 /*
 925  * Free context
 926  */
 927 void mbedtls_ecdsa_free(mbedtls_ecdsa_context *ctx) {
 928     if (ctx == NULL)
 929         return;
 930
 931     mbedtls_ecp_keypair_free(ctx);
 932 }
 933
 934 #if defined(MBEDTLS_ECP_RESTARTABLE)
 935 /*
 936  * Initialize a restart context
 937  */
 938 void mbedtls_ecdsa_restart_init(mbedtls_ecdsa_restart_ctx *ctx) {
 939     ECDSA_VALIDATE(ctx != NULL);
 940
 941     mbedtls_ecp_restart_init(&ctx->ecp);
 942
 943     ctx->ver = NULL;
 944     ctx->sig = NULL;
 945 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
 946     ctx->det = NULL;
 947 #endif
 948 }
 949
 950 /*
 951  * Free the components of a restart context
 952  */
 953 void mbedtls_ecdsa_restart_free(mbedtls_ecdsa_restart_ctx *ctx) {
 954     if (ctx == NULL)
 955         return;
 956
 957     mbedtls_ecp_restart_free(&ctx->ecp);
 958
 959     ecdsa_restart_ver_free(ctx->ver);
 960     mbedtls_free(ctx->ver);
 961     ctx->ver = NULL;
 962
 963     ecdsa_restart_sig_free(ctx->sig);
 964     mbedtls_free(ctx->sig);
 965     ctx->sig = NULL;
 966
 967 #if defined(MBEDTLS_ECDSA_DETERMINISTIC)
 968     ecdsa_restart_det_free(ctx->det);
 969     mbedtls_free(ctx->det);
 970     ctx->det = NULL;
 971 #endif
 972 }
 973 #endif /* MBEDTLS_ECP_RESTARTABLE */
 974
 975 #endif /* MBEDTLS_ECDSA_C */