1 /* 2 * Copyright 2002-2024 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the Apache License 2.0 (the "License"). You may not use 5 * this file except in compliance with the License. You can obtain a copy 6 * in the file LICENSE in the source distribution or at 7 * https://www.openssl.org/source/license.html 8 */ 9 10 /* 11 * ECDSA low level APIs are deprecated for public use, but still ok for 12 * internal use. 13 */ 14 #include "internal/deprecated.h" 15 16 #include <string.h> 17 #include <openssl/err.h> 18 #include <openssl/obj_mac.h> 19 #include <openssl/rand.h> 20 #include "crypto/bn.h" 21 #include "ec_local.h" 22 23 #define MIN_ECDSA_SIGN_ORDERBITS 64 24 /* 25 * It is highly unlikely that a retry will happen, 26 * Multiple retries would indicate that something is wrong 27 * with the group parameters (which would normally only happen 28 * with a bad custom group). 29 */ 30 #define MAX_ECDSA_SIGN_RETRIES 8 31 32 int ossl_ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 33 BIGNUM **rp) 34 { 35 if (eckey->group->meth->ecdsa_sign_setup == NULL) { 36 ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_ECDSA); 37 return 0; 38 } 39 40 return eckey->group->meth->ecdsa_sign_setup(eckey, ctx_in, kinvp, rp); 41 } 42 43 ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len, 44 const BIGNUM *in_kinv, const BIGNUM *in_r, 45 EC_KEY *eckey) 46 { 47 if (eckey->group->meth->ecdsa_sign_sig == NULL) { 48 ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_ECDSA); 49 return NULL; 50 } 51 52 return eckey->group->meth->ecdsa_sign_sig(dgst, dgst_len, 53 in_kinv, in_r, eckey); 54 } 55 56 int ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len, 57 const ECDSA_SIG *sig, EC_KEY *eckey) 58 { 59 if (eckey->group->meth->ecdsa_verify_sig == NULL) { 60 ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_ECDSA); 61 return 0; 62 } 63 64 return eckey->group->meth->ecdsa_verify_sig(dgst, dgst_len, sig, eckey); 65 } 66 67 int ossl_ecdsa_sign(int type, const unsigned char *dgst, int dlen, 68 unsigned char *sig, unsigned int *siglen, 69 const BIGNUM *kinv, const BIGNUM *r, EC_KEY *eckey) 70 { 71 ECDSA_SIG *s; 72 73 if (sig == NULL && (kinv == NULL || r == NULL)) { 74 *siglen = ECDSA_size(eckey); 75 return 1; 76 } 77 78 s = ECDSA_do_sign_ex(dgst, dlen, kinv, r, eckey); 79 if (s == NULL) { 80 *siglen = 0; 81 return 0; 82 } 83 *siglen = i2d_ECDSA_SIG(s, sig != NULL ? &sig : NULL); 84 ECDSA_SIG_free(s); 85 return 1; 86 } 87 88 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, 89 BIGNUM **kinvp, BIGNUM **rp, 90 const unsigned char *dgst, int dlen) 91 { 92 BN_CTX *ctx = NULL; 93 BIGNUM *k = NULL, *r = NULL, *X = NULL; 94 const BIGNUM *order; 95 EC_POINT *tmp_point = NULL; 96 const EC_GROUP *group; 97 int ret = 0; 98 int order_bits; 99 const BIGNUM *priv_key; 100 101 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) { 102 ERR_raise(ERR_LIB_EC, ERR_R_PASSED_NULL_PARAMETER); 103 return 0; 104 } 105 if ((priv_key = EC_KEY_get0_private_key(eckey)) == NULL) { 106 ERR_raise(ERR_LIB_EC, EC_R_MISSING_PRIVATE_KEY); 107 return 0; 108 } 109 110 if (!EC_KEY_can_sign(eckey)) { 111 ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING); 112 return 0; 113 } 114 115 if ((ctx = ctx_in) == NULL) { 116 if ((ctx = BN_CTX_new_ex(eckey->libctx)) == NULL) { 117 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 118 return 0; 119 } 120 } 121 122 k = BN_secure_new(); /* this value is later returned in *kinvp */ 123 r = BN_new(); /* this value is later returned in *rp */ 124 X = BN_new(); 125 if (k == NULL || r == NULL || X == NULL) { 126 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 127 goto err; 128 } 129 if ((tmp_point = EC_POINT_new(group)) == NULL) { 130 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 131 goto err; 132 } 133 134 if ((order = EC_GROUP_get0_order(group)) == NULL) { 135 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 136 goto err; 137 } 138 139 /* Preallocate space */ 140 order_bits = BN_num_bits(order); 141 /* Check the number of bits here so that an infinite loop is not possible */ 142 if (order_bits < MIN_ECDSA_SIGN_ORDERBITS 143 || !BN_set_bit(k, order_bits) 144 || !BN_set_bit(r, order_bits) 145 || !BN_set_bit(X, order_bits)) 146 goto err; 147 148 do { 149 /* get random k */ 150 do { 151 if (dgst != NULL) { 152 if (!ossl_bn_gen_dsa_nonce_fixed_top(k, order, priv_key, 153 dgst, dlen, ctx)) { 154 ERR_raise(ERR_LIB_EC, EC_R_RANDOM_NUMBER_GENERATION_FAILED); 155 goto err; 156 } 157 } else { 158 if (!ossl_bn_priv_rand_range_fixed_top(k, order, 0, ctx)) { 159 ERR_raise(ERR_LIB_EC, EC_R_RANDOM_NUMBER_GENERATION_FAILED); 160 goto err; 161 } 162 } 163 } while (ossl_bn_is_word_fixed_top(k, 0)); 164 165 /* compute r the x-coordinate of generator * k */ 166 if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) { 167 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 168 goto err; 169 } 170 171 if (!EC_POINT_get_affine_coordinates(group, tmp_point, X, NULL, ctx)) { 172 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 173 goto err; 174 } 175 176 if (!BN_nnmod(r, X, order, ctx)) { 177 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 178 goto err; 179 } 180 } while (BN_is_zero(r)); 181 182 /* compute the inverse of k */ 183 if (!ossl_ec_group_do_inverse_ord(group, k, k, ctx)) { 184 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 185 goto err; 186 } 187 188 /* clear old values if necessary */ 189 BN_clear_free(*rp); 190 BN_clear_free(*kinvp); 191 /* save the pre-computed values */ 192 *rp = r; 193 *kinvp = k; 194 ret = 1; 195 err: 196 if (!ret) { 197 BN_clear_free(k); 198 BN_clear_free(r); 199 } 200 if (ctx != ctx_in) 201 BN_CTX_free(ctx); 202 EC_POINT_free(tmp_point); 203 BN_clear_free(X); 204 return ret; 205 } 206 207 int ossl_ecdsa_simple_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, 208 BIGNUM **rp) 209 { 210 return ecdsa_sign_setup(eckey, ctx_in, kinvp, rp, NULL, 0); 211 } 212 213 ECDSA_SIG *ossl_ecdsa_simple_sign_sig(const unsigned char *dgst, int dgst_len, 214 const BIGNUM *in_kinv, const BIGNUM *in_r, 215 EC_KEY *eckey) 216 { 217 int ok = 0, i; 218 int retries = 0; 219 BIGNUM *kinv = NULL, *s, *m = NULL; 220 const BIGNUM *order, *ckinv; 221 BN_CTX *ctx = NULL; 222 const EC_GROUP *group; 223 ECDSA_SIG *ret; 224 const BIGNUM *priv_key; 225 226 group = EC_KEY_get0_group(eckey); 227 priv_key = EC_KEY_get0_private_key(eckey); 228 229 if (group == NULL) { 230 ERR_raise(ERR_LIB_EC, ERR_R_PASSED_NULL_PARAMETER); 231 return NULL; 232 } 233 if (priv_key == NULL) { 234 ERR_raise(ERR_LIB_EC, EC_R_MISSING_PRIVATE_KEY); 235 return NULL; 236 } 237 238 if (!EC_KEY_can_sign(eckey)) { 239 ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING); 240 return NULL; 241 } 242 243 ret = ECDSA_SIG_new(); 244 if (ret == NULL) { 245 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 246 return NULL; 247 } 248 ret->r = BN_new(); 249 ret->s = BN_new(); 250 if (ret->r == NULL || ret->s == NULL) { 251 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 252 goto err; 253 } 254 s = ret->s; 255 256 if ((ctx = BN_CTX_new_ex(eckey->libctx)) == NULL 257 || (m = BN_new()) == NULL) { 258 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 259 goto err; 260 } 261 262 if ((order = EC_GROUP_get0_order(group)) == NULL) { 263 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 264 goto err; 265 } 266 267 i = BN_num_bits(order); 268 /* 269 * Need to truncate digest if it is too long: first truncate whole bytes. 270 */ 271 if (8 * dgst_len > i) 272 dgst_len = (i + 7) / 8; 273 if (!BN_bin2bn(dgst, dgst_len, m)) { 274 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 275 goto err; 276 } 277 /* If still too long, truncate remaining bits with a shift */ 278 if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) { 279 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 280 goto err; 281 } 282 do { 283 if (in_kinv == NULL || in_r == NULL) { 284 if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, dgst, dgst_len)) { 285 ERR_raise(ERR_LIB_EC, ERR_R_ECDSA_LIB); 286 goto err; 287 } 288 ckinv = kinv; 289 } else { 290 ckinv = in_kinv; 291 if (BN_copy(ret->r, in_r) == NULL) { 292 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 293 goto err; 294 } 295 } 296 297 /* 298 * With only one multiplicant being in Montgomery domain 299 * multiplication yields real result without post-conversion. 300 * Also note that all operations but last are performed with 301 * zero-padded vectors. Last operation, BN_mod_mul_montgomery 302 * below, returns user-visible value with removed zero padding. 303 */ 304 if (!bn_to_mont_fixed_top(s, ret->r, group->mont_data, ctx) 305 || !bn_mul_mont_fixed_top(s, s, priv_key, group->mont_data, ctx)) { 306 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 307 goto err; 308 } 309 if (!bn_mod_add_fixed_top(s, s, m, order)) { 310 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 311 goto err; 312 } 313 /* 314 * |s| can still be larger than modulus, because |m| can be. In 315 * such case we count on Montgomery reduction to tie it up. 316 */ 317 if (!bn_to_mont_fixed_top(s, s, group->mont_data, ctx) 318 || !BN_mod_mul_montgomery(s, s, ckinv, group->mont_data, ctx)) { 319 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 320 goto err; 321 } 322 323 if (BN_is_zero(s)) { 324 /* 325 * if kinv and r have been supplied by the caller, don't 326 * generate new kinv and r values 327 */ 328 if (in_kinv != NULL && in_r != NULL) { 329 ERR_raise(ERR_LIB_EC, EC_R_NEED_NEW_SETUP_VALUES); 330 goto err; 331 } 332 /* Avoid infinite loops cause by invalid group parameters */ 333 if (retries++ > MAX_ECDSA_SIGN_RETRIES) { 334 ERR_raise(ERR_LIB_EC, EC_R_TOO_MANY_RETRIES); 335 goto err; 336 } 337 } else { 338 /* s != 0 => we have a valid signature */ 339 break; 340 } 341 } while (1); 342 343 ok = 1; 344 err: 345 if (!ok) { 346 ECDSA_SIG_free(ret); 347 ret = NULL; 348 } 349 BN_CTX_free(ctx); 350 BN_clear_free(m); 351 BN_clear_free(kinv); 352 return ret; 353 } 354 355 /*- 356 * returns 357 * 1: correct signature 358 * 0: incorrect signature 359 * -1: error 360 */ 361 int ossl_ecdsa_verify(int type, const unsigned char *dgst, int dgst_len, 362 const unsigned char *sigbuf, int sig_len, EC_KEY *eckey) 363 { 364 ECDSA_SIG *s; 365 const unsigned char *p = sigbuf; 366 unsigned char *der = NULL; 367 int derlen = -1; 368 int ret = -1; 369 370 s = ECDSA_SIG_new(); 371 if (s == NULL) 372 return ret; 373 if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL) 374 goto err; 375 /* Ensure signature uses DER and doesn't have trailing garbage */ 376 derlen = i2d_ECDSA_SIG(s, &der); 377 if (derlen != sig_len || memcmp(sigbuf, der, derlen) != 0) 378 goto err; 379 ret = ECDSA_do_verify(dgst, dgst_len, s, eckey); 380 err: 381 OPENSSL_free(der); 382 ECDSA_SIG_free(s); 383 return ret; 384 } 385 386 int ossl_ecdsa_simple_verify_sig(const unsigned char *dgst, int dgst_len, 387 const ECDSA_SIG *sig, EC_KEY *eckey) 388 { 389 int ret = -1, i; 390 BN_CTX *ctx; 391 const BIGNUM *order; 392 BIGNUM *u1, *u2, *m, *X; 393 EC_POINT *point = NULL; 394 const EC_GROUP *group; 395 const EC_POINT *pub_key; 396 397 /* check input values */ 398 if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL || 399 (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) { 400 ERR_raise(ERR_LIB_EC, EC_R_MISSING_PARAMETERS); 401 return -1; 402 } 403 404 if (!EC_KEY_can_sign(eckey)) { 405 ERR_raise(ERR_LIB_EC, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING); 406 return -1; 407 } 408 409 ctx = BN_CTX_new_ex(eckey->libctx); 410 if (ctx == NULL) { 411 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 412 return -1; 413 } 414 BN_CTX_start(ctx); 415 u1 = BN_CTX_get(ctx); 416 u2 = BN_CTX_get(ctx); 417 m = BN_CTX_get(ctx); 418 X = BN_CTX_get(ctx); 419 if (X == NULL) { 420 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 421 goto err; 422 } 423 424 order = EC_GROUP_get0_order(group); 425 if (order == NULL) { 426 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 427 goto err; 428 } 429 430 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 431 BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) || 432 BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) { 433 ERR_raise(ERR_LIB_EC, EC_R_BAD_SIGNATURE); 434 ret = 0; /* signature is invalid */ 435 goto err; 436 } 437 /* calculate tmp1 = inv(S) mod order */ 438 if (!ossl_ec_group_do_inverse_ord(group, u2, sig->s, ctx)) { 439 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 440 goto err; 441 } 442 /* digest -> m */ 443 i = BN_num_bits(order); 444 /* 445 * Need to truncate digest if it is too long: first truncate whole bytes. 446 */ 447 if (8 * dgst_len > i) 448 dgst_len = (i + 7) / 8; 449 if (!BN_bin2bn(dgst, dgst_len, m)) { 450 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 451 goto err; 452 } 453 /* If still too long truncate remaining bits with a shift */ 454 if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) { 455 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 456 goto err; 457 } 458 /* u1 = m * tmp mod order */ 459 if (!BN_mod_mul(u1, m, u2, order, ctx)) { 460 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 461 goto err; 462 } 463 /* u2 = r * w mod q */ 464 if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) { 465 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 466 goto err; 467 } 468 469 if ((point = EC_POINT_new(group)) == NULL) { 470 ERR_raise(ERR_LIB_EC, ERR_R_MALLOC_FAILURE); 471 goto err; 472 } 473 if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) { 474 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 475 goto err; 476 } 477 478 if (!EC_POINT_get_affine_coordinates(group, point, X, NULL, ctx)) { 479 ERR_raise(ERR_LIB_EC, ERR_R_EC_LIB); 480 goto err; 481 } 482 483 if (!BN_nnmod(u1, X, order, ctx)) { 484 ERR_raise(ERR_LIB_EC, ERR_R_BN_LIB); 485 goto err; 486 } 487 /* if the signature is correct u1 is equal to sig->r */ 488 ret = (BN_ucmp(u1, sig->r) == 0); 489 err: 490 BN_CTX_end(ctx); 491 BN_CTX_free(ctx); 492 EC_POINT_free(point); 493 return ret; 494 } 495