1 /* $OpenBSD: ecs_ossl.c,v 1.18 2019/01/19 01:12:48 tb Exp $ */ 2 /* 3 * Written by Nils Larsch for the OpenSSL project 4 */ 5 /* ==================================================================== 6 * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in 17 * the documentation and/or other materials provided with the 18 * distribution. 19 * 20 * 3. All advertising materials mentioning features or use of this 21 * software must display the following acknowledgment: 22 * "This product includes software developed by the OpenSSL Project 23 * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 24 * 25 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26 * endorse or promote products derived from this software without 27 * prior written permission. For written permission, please contact 28 * openssl-core@OpenSSL.org. 29 * 30 * 5. Products derived from this software may not be called "OpenSSL" 31 * nor may "OpenSSL" appear in their names without prior written 32 * permission of the OpenSSL Project. 33 * 34 * 6. Redistributions of any form whatsoever must retain the following 35 * acknowledgment: 36 * "This product includes software developed by the OpenSSL Project 37 * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 38 * 39 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50 * OF THE POSSIBILITY OF SUCH DAMAGE. 51 * ==================================================================== 52 * 53 * This product includes cryptographic software written by Eric Young 54 * (eay@cryptsoft.com). This product includes software written by Tim 55 * Hudson (tjh@cryptsoft.com). 56 * 57 */ 58 59 #include <string.h> 60 61 #include <openssl/opensslconf.h> 62 63 #include <openssl/err.h> 64 #include <openssl/obj_mac.h> 65 #include <openssl/bn.h> 66 67 #include "bn_lcl.h" 68 #include "ecs_locl.h" 69 70 static int ecdsa_prepare_digest(const unsigned char *dgst, int dgst_len, 71 BIGNUM *order, BIGNUM *ret); 72 static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, 73 const BIGNUM *, const BIGNUM *, EC_KEY *eckey); 74 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 75 BIGNUM **rp); 76 static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, 77 const ECDSA_SIG *sig, EC_KEY *eckey); 78 79 static ECDSA_METHOD openssl_ecdsa_meth = { 80 .name = "OpenSSL ECDSA method", 81 .ecdsa_do_sign = ecdsa_do_sign, 82 .ecdsa_sign_setup = ecdsa_sign_setup, 83 .ecdsa_do_verify = ecdsa_do_verify 84 }; 85 86 const ECDSA_METHOD * 87 ECDSA_OpenSSL(void) 88 { 89 return &openssl_ecdsa_meth; 90 } 91 92 static int 93 ecdsa_prepare_digest(const unsigned char *dgst, int dgst_len, BIGNUM *order, 94 BIGNUM *ret) 95 { 96 int dgst_bits, order_bits; 97 98 if (!BN_bin2bn(dgst, dgst_len, ret)) { 99 ECDSAerror(ERR_R_BN_LIB); 100 return 0; 101 } 102 103 /* FIPS 186-3 6.4: Use order_bits leftmost bits if digest is too long */ 104 dgst_bits = 8 * dgst_len; 105 order_bits = BN_num_bits(order); 106 if (dgst_bits > order_bits) { 107 if (!BN_rshift(ret, ret, dgst_bits - order_bits)) { 108 ECDSAerror(ERR_R_BN_LIB); 109 return 0; 110 } 111 } 112 113 return 1; 114 } 115 116 int 117 ossl_ecdsa_sign(int type, const unsigned char *dgst, int dlen, unsigned char *sig, 118 unsigned int *siglen, const BIGNUM *kinv, const BIGNUM *r, EC_KEY *eckey) 119 { 120 ECDSA_SIG *s; 121 122 if ((s = ECDSA_do_sign_ex(dgst, dlen, kinv, r, eckey)) == NULL) { 123 *siglen = 0; 124 return 0; 125 } 126 *siglen = i2d_ECDSA_SIG(s, &sig); 127 ECDSA_SIG_free(s); 128 return 1; 129 } 130 131 static int 132 ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) 133 { 134 BN_CTX *ctx = ctx_in; 135 BIGNUM *k = NULL, *r = NULL, *order = NULL, *X = NULL; 136 EC_POINT *point = NULL; 137 const EC_GROUP *group; 138 int order_bits, ret = 0; 139 140 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) { 141 ECDSAerror(ERR_R_PASSED_NULL_PARAMETER); 142 return 0; 143 } 144 145 if (ctx == NULL) { 146 if ((ctx = BN_CTX_new()) == NULL) { 147 ECDSAerror(ERR_R_MALLOC_FAILURE); 148 return 0; 149 } 150 } 151 152 if ((k = BN_new()) == NULL || (r = BN_new()) == NULL || 153 (order = BN_new()) == NULL || (X = BN_new()) == NULL) { 154 ECDSAerror(ERR_R_MALLOC_FAILURE); 155 goto err; 156 } 157 if ((point = EC_POINT_new(group)) == NULL) { 158 ECDSAerror(ERR_R_EC_LIB); 159 goto err; 160 } 161 if (!EC_GROUP_get_order(group, order, ctx)) { 162 ECDSAerror(ERR_R_EC_LIB); 163 goto err; 164 } 165 166 /* Preallocate space. */ 167 order_bits = BN_num_bits(order); 168 if (!BN_set_bit(k, order_bits) || 169 !BN_set_bit(r, order_bits) || 170 !BN_set_bit(X, order_bits)) 171 goto err; 172 173 do { 174 do { 175 if (!BN_rand_range(k, order)) { 176 ECDSAerror( 177 ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); 178 goto err; 179 } 180 } while (BN_is_zero(k)); 181 182 /* 183 * We do not want timing information to leak the length of k, 184 * so we compute G * k using an equivalent scalar of fixed 185 * bit-length. 186 * 187 * We unconditionally perform both of these additions to prevent 188 * a small timing information leakage. We then choose the sum 189 * that is one bit longer than the order. This guarantees the 190 * code path used in the constant time implementations 191 * elsewhere. 192 * 193 * TODO: revisit the BN_copy aiming for a memory access agnostic 194 * conditional copy. 195 */ 196 if (!BN_add(r, k, order) || 197 !BN_add(X, r, order) || 198 !BN_copy(k, BN_num_bits(r) > order_bits ? r : X)) 199 goto err; 200 201 BN_set_flags(k, BN_FLG_CONSTTIME); 202 203 /* Compute r, the x-coordinate of G * k. */ 204 if (!EC_POINT_mul(group, point, k, NULL, NULL, ctx)) { 205 ECDSAerror(ERR_R_EC_LIB); 206 goto err; 207 } 208 if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == 209 NID_X9_62_prime_field) { 210 if (!EC_POINT_get_affine_coordinates_GFp(group, point, 211 X, NULL, ctx)) { 212 ECDSAerror(ERR_R_EC_LIB); 213 goto err; 214 } 215 } 216 #ifndef OPENSSL_NO_EC2M 217 else { /* NID_X9_62_characteristic_two_field */ 218 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, 219 X, NULL, ctx)) { 220 ECDSAerror(ERR_R_EC_LIB); 221 goto err; 222 } 223 } 224 #endif 225 if (!BN_nnmod(r, X, order, ctx)) { 226 ECDSAerror(ERR_R_BN_LIB); 227 goto err; 228 } 229 } while (BN_is_zero(r)); 230 231 if (!BN_mod_inverse_ct(k, k, order, ctx)) { 232 ECDSAerror(ERR_R_BN_LIB); 233 goto err; 234 } 235 BN_clear_free(*rp); 236 BN_clear_free(*kinvp); 237 *rp = r; 238 *kinvp = k; 239 ret = 1; 240 241 err: 242 if (ret == 0) { 243 BN_clear_free(k); 244 BN_clear_free(r); 245 } 246 if (ctx_in == NULL) 247 BN_CTX_free(ctx); 248 BN_free(order); 249 EC_POINT_free(point); 250 BN_clear_free(X); 251 return (ret); 252 } 253 254 /* replace w/ ecdsa_sign_setup() when ECDSA_METHOD gets removed */ 255 int 256 ossl_ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) 257 { 258 ECDSA_DATA *ecdsa; 259 260 if ((ecdsa = ecdsa_check(eckey)) == NULL) 261 return 0; 262 return ecdsa->meth->ecdsa_sign_setup(eckey, ctx_in, kinvp, rp); 263 } 264 265 static ECDSA_SIG * 266 ecdsa_do_sign(const unsigned char *dgst, int dgst_len, 267 const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey) 268 { 269 BIGNUM *b = NULL, *binv = NULL, *bm = NULL, *bxr = NULL; 270 BIGNUM *kinv = NULL, *m = NULL, *order = NULL, *range = NULL, *s; 271 const BIGNUM *ckinv, *priv_key; 272 BN_CTX *ctx = NULL; 273 const EC_GROUP *group; 274 ECDSA_SIG *ret; 275 ECDSA_DATA *ecdsa; 276 int ok = 0; 277 278 ecdsa = ecdsa_check(eckey); 279 group = EC_KEY_get0_group(eckey); 280 priv_key = EC_KEY_get0_private_key(eckey); 281 282 if (group == NULL || priv_key == NULL || ecdsa == NULL) { 283 ECDSAerror(ERR_R_PASSED_NULL_PARAMETER); 284 return NULL; 285 } 286 287 if ((ret = ECDSA_SIG_new()) == NULL) { 288 ECDSAerror(ERR_R_MALLOC_FAILURE); 289 return NULL; 290 } 291 s = ret->s; 292 293 if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL || 294 (range = BN_new()) == NULL || (b = BN_new()) == NULL || 295 (binv = BN_new()) == NULL || (bm = BN_new()) == NULL || 296 (bxr = BN_new()) == NULL || (m = BN_new()) == NULL) { 297 ECDSAerror(ERR_R_MALLOC_FAILURE); 298 goto err; 299 } 300 301 if (!EC_GROUP_get_order(group, order, ctx)) { 302 ECDSAerror(ERR_R_EC_LIB); 303 goto err; 304 } 305 306 if (!ecdsa_prepare_digest(dgst, dgst_len, order, m)) 307 goto err; 308 309 do { 310 if (in_kinv == NULL || in_r == NULL) { 311 if (!ECDSA_sign_setup(eckey, ctx, &kinv, &ret->r)) { 312 ECDSAerror(ERR_R_ECDSA_LIB); 313 goto err; 314 } 315 ckinv = kinv; 316 } else { 317 ckinv = in_kinv; 318 if (BN_copy(ret->r, in_r) == NULL) { 319 ECDSAerror(ERR_R_MALLOC_FAILURE); 320 goto err; 321 } 322 } 323 324 /* 325 * Compute: 326 * 327 * s = inv(k)(m + xr) mod order 328 * 329 * In order to reduce the possibility of a side-channel attack, 330 * the following is calculated using a blinding value: 331 * 332 * s = inv(k)inv(b)(bm + bxr) mod order 333 * 334 * where b is a random value in the range [1, order-1]. 335 */ 336 337 /* Generate b in range [1, order-1]. */ 338 if (!BN_sub(range, order, BN_value_one())) { 339 ECDSAerror(ERR_R_BN_LIB); 340 goto err; 341 } 342 if (!BN_rand_range(b, range)) { 343 ECDSAerror(ERR_R_BN_LIB); 344 goto err; 345 } 346 if (!BN_add(b, b, BN_value_one())) { 347 ECDSAerror(ERR_R_BN_LIB); 348 goto err; 349 } 350 351 if (BN_mod_inverse_ct(binv, b, order, ctx) == NULL) { 352 ECDSAerror(ERR_R_BN_LIB); 353 goto err; 354 } 355 356 if (!BN_mod_mul(bxr, b, priv_key, order, ctx)) { /* bx */ 357 ECDSAerror(ERR_R_BN_LIB); 358 goto err; 359 } 360 if (!BN_mod_mul(bxr, bxr, ret->r, order, ctx)) { /* bxr */ 361 ECDSAerror(ERR_R_BN_LIB); 362 goto err; 363 } 364 if (!BN_mod_mul(bm, b, m, order, ctx)) { /* bm */ 365 ECDSAerror(ERR_R_BN_LIB); 366 goto err; 367 } 368 if (!BN_mod_add(s, bm, bxr, order, ctx)) { /* s = bm + bxr */ 369 ECDSAerror(ERR_R_BN_LIB); 370 goto err; 371 } 372 if (!BN_mod_mul(s, s, binv, order, ctx)) { /* s = m + xr */ 373 ECDSAerror(ERR_R_BN_LIB); 374 goto err; 375 } 376 if (!BN_mod_mul(s, s, ckinv, order, ctx)) { 377 ECDSAerror(ERR_R_BN_LIB); 378 goto err; 379 } 380 381 if (BN_is_zero(s)) { 382 /* 383 * If kinv and r have been supplied by the caller, 384 * don't generate new kinv and r values 385 */ 386 if (in_kinv != NULL && in_r != NULL) { 387 ECDSAerror(ECDSA_R_NEED_NEW_SETUP_VALUES); 388 goto err; 389 } 390 } else 391 /* s != 0 => we have a valid signature */ 392 break; 393 } while (1); 394 395 ok = 1; 396 397 err: 398 if (ok == 0) { 399 ECDSA_SIG_free(ret); 400 ret = NULL; 401 } 402 BN_CTX_free(ctx); 403 BN_clear_free(b); 404 BN_clear_free(binv); 405 BN_clear_free(bm); 406 BN_clear_free(bxr); 407 BN_clear_free(kinv); 408 BN_clear_free(m); 409 BN_free(order); 410 BN_free(range); 411 return ret; 412 } 413 414 /* replace w/ ecdsa_do_sign() when ECDSA_METHOD gets removed */ 415 ECDSA_SIG * 416 ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, 417 const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey) 418 { 419 ECDSA_DATA *ecdsa; 420 421 if ((ecdsa = ecdsa_check(eckey)) == NULL) 422 return NULL; 423 return ecdsa->meth->ecdsa_do_sign(dgst, dgst_len, in_kinv, in_r, eckey); 424 } 425 426 int 427 ossl_ecdsa_verify(int type, const unsigned char *dgst, int dgst_len, 428 const unsigned char *sigbuf, int sig_len, EC_KEY *eckey) 429 { 430 ECDSA_SIG *s; 431 unsigned char *der = NULL; 432 const unsigned char *p = sigbuf; 433 int derlen = -1; 434 int ret = -1; 435 436 if ((s = ECDSA_SIG_new()) == NULL) 437 return (ret); 438 if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL) 439 goto err; 440 /* Ensure signature uses DER and doesn't have trailing garbage */ 441 derlen = i2d_ECDSA_SIG(s, &der); 442 if (derlen != sig_len || memcmp(sigbuf, der, derlen)) 443 goto err; 444 ret = ECDSA_do_verify(dgst, dgst_len, s, eckey); 445 446 err: 447 freezero(der, derlen); 448 ECDSA_SIG_free(s); 449 return (ret); 450 } 451 452 static int 453 ecdsa_do_verify(const unsigned char *dgst, int dgst_len, const ECDSA_SIG *sig, 454 EC_KEY *eckey) 455 { 456 BN_CTX *ctx; 457 BIGNUM *order, *u1, *u2, *m, *X; 458 EC_POINT *point = NULL; 459 const EC_GROUP *group; 460 const EC_POINT *pub_key; 461 int ret = -1; 462 463 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL || 464 (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) { 465 ECDSAerror(ECDSA_R_MISSING_PARAMETERS); 466 return -1; 467 } 468 469 if ((ctx = BN_CTX_new()) == NULL) { 470 ECDSAerror(ERR_R_MALLOC_FAILURE); 471 return -1; 472 } 473 BN_CTX_start(ctx); 474 order = BN_CTX_get(ctx); 475 u1 = BN_CTX_get(ctx); 476 u2 = BN_CTX_get(ctx); 477 m = BN_CTX_get(ctx); 478 X = BN_CTX_get(ctx); 479 if (X == NULL) { 480 ECDSAerror(ERR_R_BN_LIB); 481 goto err; 482 } 483 484 if (!EC_GROUP_get_order(group, order, ctx)) { 485 ECDSAerror(ERR_R_EC_LIB); 486 goto err; 487 } 488 489 /* Verify that r and s are in the range [1, order-1]. */ 490 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 491 BN_ucmp(sig->r, order) >= 0 || 492 BN_is_zero(sig->s) || BN_is_negative(sig->s) || 493 BN_ucmp(sig->s, order) >= 0) { 494 ECDSAerror(ECDSA_R_BAD_SIGNATURE); 495 ret = 0; 496 goto err; 497 } 498 499 if (!ecdsa_prepare_digest(dgst, dgst_len, order, m)) 500 goto err; 501 502 if (!BN_mod_inverse_ct(u2, sig->s, order, ctx)) { /* w = inv(s) */ 503 ECDSAerror(ERR_R_BN_LIB); 504 goto err; 505 } 506 if (!BN_mod_mul(u1, m, u2, order, ctx)) { /* u1 = mw */ 507 ECDSAerror(ERR_R_BN_LIB); 508 goto err; 509 } 510 if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) { /* u2 = rw */ 511 ECDSAerror(ERR_R_BN_LIB); 512 goto err; 513 } 514 515 /* Compute the x-coordinate of G * u1 + pub_key * u2. */ 516 if ((point = EC_POINT_new(group)) == NULL) { 517 ECDSAerror(ERR_R_MALLOC_FAILURE); 518 goto err; 519 } 520 if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) { 521 ECDSAerror(ERR_R_EC_LIB); 522 goto err; 523 } 524 if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == 525 NID_X9_62_prime_field) { 526 if (!EC_POINT_get_affine_coordinates_GFp(group, point, X, NULL, 527 ctx)) { 528 ECDSAerror(ERR_R_EC_LIB); 529 goto err; 530 } 531 } 532 #ifndef OPENSSL_NO_EC2M 533 else { /* NID_X9_62_characteristic_two_field */ 534 if (!EC_POINT_get_affine_coordinates_GF2m(group, point, X, NULL, 535 ctx)) { 536 ECDSAerror(ERR_R_EC_LIB); 537 goto err; 538 } 539 } 540 #endif 541 if (!BN_nnmod(u1, X, order, ctx)) { 542 ECDSAerror(ERR_R_BN_LIB); 543 goto err; 544 } 545 546 /* If the signature is correct, the x-coordinate is equal to sig->r. */ 547 ret = (BN_ucmp(u1, sig->r) == 0); 548 549 err: 550 BN_CTX_end(ctx); 551 BN_CTX_free(ctx); 552 EC_POINT_free(point); 553 return ret; 554 } 555 556 /* replace w/ ecdsa_do_verify() when ECDSA_METHOD gets removed */ 557 int 558 ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len, 559 const ECDSA_SIG *sig, EC_KEY *eckey) 560 { 561 ECDSA_DATA *ecdsa; 562 563 if ((ecdsa = ecdsa_check(eckey)) == NULL) 564 return 0; 565 return ecdsa->meth->ecdsa_do_verify(dgst, dgst_len, sig, eckey); 566 } 567