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