1 /* $OpenBSD: ecs_ossl.c,v 1.25 2022/06/30 11:14:47 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/bn.h> 64 #include <openssl/err.h> 65 #include <openssl/objects.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 if (BN_cmp(order, BN_value_one()) <= 0) { 167 ECDSAerror(EC_R_INVALID_GROUP_ORDER); 168 goto err; 169 } 170 171 /* Preallocate space. */ 172 order_bits = BN_num_bits(order); 173 if (!BN_set_bit(k, order_bits) || 174 !BN_set_bit(r, order_bits) || 175 !BN_set_bit(X, order_bits)) 176 goto err; 177 178 do { 179 do { 180 if (!BN_rand_range(k, order)) { 181 ECDSAerror( 182 ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); 183 goto err; 184 } 185 } while (BN_is_zero(k)); 186 187 /* 188 * We do not want timing information to leak the length of k, 189 * so we compute G * k using an equivalent scalar of fixed 190 * bit-length. 191 * 192 * We unconditionally perform both of these additions to prevent 193 * a small timing information leakage. We then choose the sum 194 * that is one bit longer than the order. This guarantees the 195 * code path used in the constant time implementations 196 * elsewhere. 197 * 198 * TODO: revisit the BN_copy aiming for a memory access agnostic 199 * conditional copy. 200 */ 201 if (!BN_add(r, k, order) || 202 !BN_add(X, r, order) || 203 !BN_copy(k, BN_num_bits(r) > order_bits ? r : X)) 204 goto err; 205 206 BN_set_flags(k, BN_FLG_CONSTTIME); 207 208 /* Compute r, the x-coordinate of G * k. */ 209 if (!EC_POINT_mul(group, point, k, NULL, NULL, ctx)) { 210 ECDSAerror(ERR_R_EC_LIB); 211 goto err; 212 } 213 if (!EC_POINT_get_affine_coordinates(group, point, X, NULL, 214 ctx)) { 215 ECDSAerror(ERR_R_EC_LIB); 216 goto err; 217 } 218 if (!BN_nnmod(r, X, order, ctx)) { 219 ECDSAerror(ERR_R_BN_LIB); 220 goto err; 221 } 222 } while (BN_is_zero(r)); 223 224 if (BN_mod_inverse_ct(k, k, order, ctx) == NULL) { 225 ECDSAerror(ERR_R_BN_LIB); 226 goto err; 227 } 228 BN_clear_free(*rp); 229 BN_clear_free(*kinvp); 230 *rp = r; 231 *kinvp = k; 232 ret = 1; 233 234 err: 235 if (ret == 0) { 236 BN_clear_free(k); 237 BN_clear_free(r); 238 } 239 if (ctx_in == NULL) 240 BN_CTX_free(ctx); 241 BN_free(order); 242 EC_POINT_free(point); 243 BN_clear_free(X); 244 return (ret); 245 } 246 247 /* replace w/ ecdsa_sign_setup() when ECDSA_METHOD gets removed */ 248 int 249 ossl_ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) 250 { 251 ECDSA_DATA *ecdsa; 252 253 if ((ecdsa = ecdsa_check(eckey)) == NULL) 254 return 0; 255 return ecdsa->meth->ecdsa_sign_setup(eckey, ctx_in, kinvp, rp); 256 } 257 258 static ECDSA_SIG * 259 ecdsa_do_sign(const unsigned char *dgst, int dgst_len, 260 const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey) 261 { 262 BIGNUM *b = NULL, *binv = NULL, *bm = NULL, *bxr = NULL; 263 BIGNUM *kinv = NULL, *m = NULL, *order = NULL, *range = NULL, *s; 264 const BIGNUM *ckinv, *priv_key; 265 BN_CTX *ctx = NULL; 266 const EC_GROUP *group; 267 ECDSA_SIG *ret; 268 ECDSA_DATA *ecdsa; 269 int ok = 0; 270 271 ecdsa = ecdsa_check(eckey); 272 group = EC_KEY_get0_group(eckey); 273 priv_key = EC_KEY_get0_private_key(eckey); 274 275 if (group == NULL || priv_key == NULL || ecdsa == NULL) { 276 ECDSAerror(ERR_R_PASSED_NULL_PARAMETER); 277 return NULL; 278 } 279 280 if ((ret = ECDSA_SIG_new()) == NULL) { 281 ECDSAerror(ERR_R_MALLOC_FAILURE); 282 return NULL; 283 } 284 s = ret->s; 285 286 if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL || 287 (range = BN_new()) == NULL || (b = BN_new()) == NULL || 288 (binv = BN_new()) == NULL || (bm = BN_new()) == NULL || 289 (bxr = BN_new()) == NULL || (m = BN_new()) == NULL) { 290 ECDSAerror(ERR_R_MALLOC_FAILURE); 291 goto err; 292 } 293 294 if (!EC_GROUP_get_order(group, order, ctx)) { 295 ECDSAerror(ERR_R_EC_LIB); 296 goto err; 297 } 298 299 if (!ecdsa_prepare_digest(dgst, dgst_len, order, m)) 300 goto err; 301 302 do { 303 if (in_kinv == NULL || in_r == NULL) { 304 if (!ECDSA_sign_setup(eckey, ctx, &kinv, &ret->r)) { 305 ECDSAerror(ERR_R_ECDSA_LIB); 306 goto err; 307 } 308 ckinv = kinv; 309 } else { 310 ckinv = in_kinv; 311 if (BN_copy(ret->r, in_r) == NULL) { 312 ECDSAerror(ERR_R_MALLOC_FAILURE); 313 goto err; 314 } 315 } 316 317 /* 318 * Compute: 319 * 320 * s = inv(k)(m + xr) mod order 321 * 322 * In order to reduce the possibility of a side-channel attack, 323 * the following is calculated using a blinding value: 324 * 325 * s = inv(b)(bm + bxr)inv(k) mod order 326 * 327 * where b is a random value in the range [1, order-1]. 328 */ 329 330 /* Generate b in range [1, order-1]. */ 331 if (!BN_sub(range, order, BN_value_one())) { 332 ECDSAerror(ERR_R_BN_LIB); 333 goto err; 334 } 335 if (!BN_rand_range(b, range)) { 336 ECDSAerror(ERR_R_BN_LIB); 337 goto err; 338 } 339 if (!BN_add(b, b, BN_value_one())) { 340 ECDSAerror(ERR_R_BN_LIB); 341 goto err; 342 } 343 344 if (BN_mod_inverse_ct(binv, b, order, ctx) == NULL) { 345 ECDSAerror(ERR_R_BN_LIB); 346 goto err; 347 } 348 349 if (!BN_mod_mul(bxr, b, priv_key, order, ctx)) { /* bx */ 350 ECDSAerror(ERR_R_BN_LIB); 351 goto err; 352 } 353 if (!BN_mod_mul(bxr, bxr, ret->r, order, ctx)) { /* bxr */ 354 ECDSAerror(ERR_R_BN_LIB); 355 goto err; 356 } 357 if (!BN_mod_mul(bm, b, m, order, ctx)) { /* bm */ 358 ECDSAerror(ERR_R_BN_LIB); 359 goto err; 360 } 361 if (!BN_mod_add(s, bm, bxr, order, ctx)) { /* s = bm + bxr */ 362 ECDSAerror(ERR_R_BN_LIB); 363 goto err; 364 } 365 if (!BN_mod_mul(s, s, ckinv, order, ctx)) { /* s = b(m + xr)k^-1 */ 366 ECDSAerror(ERR_R_BN_LIB); 367 goto err; 368 } 369 if (!BN_mod_mul(s, s, binv, order, ctx)) { /* s = (m + xr)k^-1 */ 370 ECDSAerror(ERR_R_BN_LIB); 371 goto err; 372 } 373 374 if (BN_is_zero(s)) { 375 /* 376 * If kinv and r have been supplied by the caller, 377 * don't generate new kinv and r values 378 */ 379 if (in_kinv != NULL && in_r != NULL) { 380 ECDSAerror(ECDSA_R_NEED_NEW_SETUP_VALUES); 381 goto err; 382 } 383 } else 384 /* s != 0 => we have a valid signature */ 385 break; 386 } while (1); 387 388 ok = 1; 389 390 err: 391 if (ok == 0) { 392 ECDSA_SIG_free(ret); 393 ret = NULL; 394 } 395 BN_CTX_free(ctx); 396 BN_clear_free(b); 397 BN_clear_free(binv); 398 BN_clear_free(bm); 399 BN_clear_free(bxr); 400 BN_clear_free(kinv); 401 BN_clear_free(m); 402 BN_free(order); 403 BN_free(range); 404 return ret; 405 } 406 407 /* replace w/ ecdsa_do_sign() when ECDSA_METHOD gets removed */ 408 ECDSA_SIG * 409 ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, 410 const BIGNUM *in_kinv, const BIGNUM *in_r, EC_KEY *eckey) 411 { 412 ECDSA_DATA *ecdsa; 413 414 if ((ecdsa = ecdsa_check(eckey)) == NULL) 415 return NULL; 416 return ecdsa->meth->ecdsa_do_sign(dgst, dgst_len, in_kinv, in_r, eckey); 417 } 418 419 int 420 ossl_ecdsa_verify(int type, const unsigned char *dgst, int dgst_len, 421 const unsigned char *sigbuf, int sig_len, EC_KEY *eckey) 422 { 423 ECDSA_SIG *s; 424 unsigned char *der = NULL; 425 const unsigned char *p = sigbuf; 426 int derlen = -1; 427 int ret = -1; 428 429 if ((s = ECDSA_SIG_new()) == NULL) 430 return (ret); 431 if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL) 432 goto err; 433 /* Ensure signature uses DER and doesn't have trailing garbage */ 434 derlen = i2d_ECDSA_SIG(s, &der); 435 if (derlen != sig_len || memcmp(sigbuf, der, derlen)) 436 goto err; 437 ret = ECDSA_do_verify(dgst, dgst_len, s, eckey); 438 439 err: 440 freezero(der, derlen); 441 ECDSA_SIG_free(s); 442 return (ret); 443 } 444 445 static int 446 ecdsa_do_verify(const unsigned char *dgst, int dgst_len, const ECDSA_SIG *sig, 447 EC_KEY *eckey) 448 { 449 BN_CTX *ctx; 450 BIGNUM *order, *u1, *u2, *m, *X; 451 EC_POINT *point = NULL; 452 const EC_GROUP *group; 453 const EC_POINT *pub_key; 454 int ret = -1; 455 456 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL || 457 (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) { 458 ECDSAerror(ECDSA_R_MISSING_PARAMETERS); 459 return -1; 460 } 461 462 if ((ctx = BN_CTX_new()) == NULL) { 463 ECDSAerror(ERR_R_MALLOC_FAILURE); 464 return -1; 465 } 466 BN_CTX_start(ctx); 467 order = BN_CTX_get(ctx); 468 u1 = BN_CTX_get(ctx); 469 u2 = BN_CTX_get(ctx); 470 m = BN_CTX_get(ctx); 471 X = BN_CTX_get(ctx); 472 if (X == NULL) { 473 ECDSAerror(ERR_R_BN_LIB); 474 goto err; 475 } 476 477 if (!EC_GROUP_get_order(group, order, ctx)) { 478 ECDSAerror(ERR_R_EC_LIB); 479 goto err; 480 } 481 482 /* Verify that r and s are in the range [1, order-1]. */ 483 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 484 BN_ucmp(sig->r, order) >= 0 || 485 BN_is_zero(sig->s) || BN_is_negative(sig->s) || 486 BN_ucmp(sig->s, order) >= 0) { 487 ECDSAerror(ECDSA_R_BAD_SIGNATURE); 488 ret = 0; 489 goto err; 490 } 491 492 if (!ecdsa_prepare_digest(dgst, dgst_len, order, m)) 493 goto err; 494 495 if (BN_mod_inverse_ct(u2, sig->s, order, ctx) == NULL) { /* w = inv(s) */ 496 ECDSAerror(ERR_R_BN_LIB); 497 goto err; 498 } 499 if (!BN_mod_mul(u1, m, u2, order, ctx)) { /* u1 = mw */ 500 ECDSAerror(ERR_R_BN_LIB); 501 goto err; 502 } 503 if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) { /* u2 = rw */ 504 ECDSAerror(ERR_R_BN_LIB); 505 goto err; 506 } 507 508 /* Compute the x-coordinate of G * u1 + pub_key * u2. */ 509 if ((point = EC_POINT_new(group)) == NULL) { 510 ECDSAerror(ERR_R_MALLOC_FAILURE); 511 goto err; 512 } 513 if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) { 514 ECDSAerror(ERR_R_EC_LIB); 515 goto err; 516 } 517 if (!EC_POINT_get_affine_coordinates(group, point, X, NULL, ctx)) { 518 ECDSAerror(ERR_R_EC_LIB); 519 goto err; 520 } 521 if (!BN_nnmod(u1, X, order, ctx)) { 522 ECDSAerror(ERR_R_BN_LIB); 523 goto err; 524 } 525 526 /* If the signature is correct, the x-coordinate is equal to sig->r. */ 527 ret = (BN_ucmp(u1, sig->r) == 0); 528 529 err: 530 BN_CTX_end(ctx); 531 BN_CTX_free(ctx); 532 EC_POINT_free(point); 533 return ret; 534 } 535 536 /* replace w/ ecdsa_do_verify() when ECDSA_METHOD gets removed */ 537 int 538 ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len, 539 const ECDSA_SIG *sig, EC_KEY *eckey) 540 { 541 ECDSA_DATA *ecdsa; 542 543 if ((ecdsa = ecdsa_check(eckey)) == NULL) 544 return 0; 545 return ecdsa->meth->ecdsa_do_verify(dgst, dgst_len, sig, eckey); 546 } 547