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