1 /* 2 * Copyright 1995-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 * DSA low level APIs are deprecated for public use, but still ok for 12 * internal use. 13 */ 14 #include "internal/deprecated.h" 15 16 #include <stdio.h> 17 #include "internal/cryptlib.h" 18 #include "crypto/bn.h" 19 #include <openssl/bn.h> 20 #include <openssl/sha.h> 21 #include "dsa_local.h" 22 #include <openssl/asn1.h> 23 24 #define MIN_DSA_SIGN_QBITS 128 25 #define MAX_DSA_SIGN_RETRIES 8 26 27 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa); 28 static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, 29 BIGNUM **rp); 30 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, 31 BIGNUM **rp, const unsigned char *dgst, int dlen); 32 static int dsa_do_verify(const unsigned char *dgst, int dgst_len, 33 DSA_SIG *sig, DSA *dsa); 34 static int dsa_init(DSA *dsa); 35 static int dsa_finish(DSA *dsa); 36 static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q, 37 BN_CTX *ctx); 38 39 static DSA_METHOD openssl_dsa_meth = { 40 "OpenSSL DSA method", 41 dsa_do_sign, 42 dsa_sign_setup_no_digest, 43 dsa_do_verify, 44 NULL, /* dsa_mod_exp, */ 45 NULL, /* dsa_bn_mod_exp, */ 46 dsa_init, 47 dsa_finish, 48 DSA_FLAG_FIPS_METHOD, 49 NULL, 50 NULL, 51 NULL 52 }; 53 54 static const DSA_METHOD *default_DSA_method = &openssl_dsa_meth; 55 56 #ifndef FIPS_MODULE 57 void DSA_set_default_method(const DSA_METHOD *meth) 58 { 59 default_DSA_method = meth; 60 } 61 #endif /* FIPS_MODULE */ 62 63 const DSA_METHOD *DSA_get_default_method(void) 64 { 65 return default_DSA_method; 66 } 67 68 const DSA_METHOD *DSA_OpenSSL(void) 69 { 70 return &openssl_dsa_meth; 71 } 72 73 DSA_SIG *ossl_dsa_do_sign_int(const unsigned char *dgst, int dlen, DSA *dsa) 74 { 75 BIGNUM *kinv = NULL; 76 BIGNUM *m, *blind, *blindm, *tmp; 77 BN_CTX *ctx = NULL; 78 int reason = ERR_R_BN_LIB; 79 DSA_SIG *ret = NULL; 80 int rv = 0; 81 int retries = 0; 82 83 if (dsa->params.p == NULL 84 || dsa->params.q == NULL 85 || dsa->params.g == NULL) { 86 reason = DSA_R_MISSING_PARAMETERS; 87 goto err; 88 } 89 if (dsa->priv_key == NULL) { 90 reason = DSA_R_MISSING_PRIVATE_KEY; 91 goto err; 92 } 93 94 ret = DSA_SIG_new(); 95 if (ret == NULL) 96 goto err; 97 ret->r = BN_new(); 98 ret->s = BN_new(); 99 if (ret->r == NULL || ret->s == NULL) 100 goto err; 101 102 ctx = BN_CTX_new_ex(dsa->libctx); 103 if (ctx == NULL) 104 goto err; 105 m = BN_CTX_get(ctx); 106 blind = BN_CTX_get(ctx); 107 blindm = BN_CTX_get(ctx); 108 tmp = BN_CTX_get(ctx); 109 if (tmp == NULL) 110 goto err; 111 112 redo: 113 if (!dsa_sign_setup(dsa, ctx, &kinv, &ret->r, dgst, dlen)) 114 goto err; 115 116 if (dlen > BN_num_bytes(dsa->params.q)) 117 /* 118 * if the digest length is greater than the size of q use the 119 * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3, 120 * 4.2 121 */ 122 dlen = BN_num_bytes(dsa->params.q); 123 if (BN_bin2bn(dgst, dlen, m) == NULL) 124 goto err; 125 126 /* 127 * The normal signature calculation is: 128 * 129 * s := k^-1 * (m + r * priv_key) mod q 130 * 131 * We will blind this to protect against side channel attacks 132 * 133 * s := blind^-1 * k^-1 * (blind * m + blind * r * priv_key) mod q 134 */ 135 136 /* 137 * Generate a blinding value 138 * The size of q is tested in dsa_sign_setup() so there should not be an infinite loop here. 139 */ 140 do { 141 if (!BN_priv_rand_ex(blind, BN_num_bits(dsa->params.q) - 1, 142 BN_RAND_TOP_ANY, BN_RAND_BOTTOM_ANY, 0, ctx)) 143 goto err; 144 } while (BN_is_zero(blind)); 145 BN_set_flags(blind, BN_FLG_CONSTTIME); 146 BN_set_flags(blindm, BN_FLG_CONSTTIME); 147 BN_set_flags(tmp, BN_FLG_CONSTTIME); 148 149 /* tmp := blind * priv_key * r mod q */ 150 if (!BN_mod_mul(tmp, blind, dsa->priv_key, dsa->params.q, ctx)) 151 goto err; 152 if (!BN_mod_mul(tmp, tmp, ret->r, dsa->params.q, ctx)) 153 goto err; 154 155 /* blindm := blind * m mod q */ 156 if (!BN_mod_mul(blindm, blind, m, dsa->params.q, ctx)) 157 goto err; 158 159 /* s : = (blind * priv_key * r) + (blind * m) mod q */ 160 if (!BN_mod_add_quick(ret->s, tmp, blindm, dsa->params.q)) 161 goto err; 162 163 /* s := s * k^-1 mod q */ 164 if (!BN_mod_mul(ret->s, ret->s, kinv, dsa->params.q, ctx)) 165 goto err; 166 167 /* s:= s * blind^-1 mod q */ 168 if (BN_mod_inverse(blind, blind, dsa->params.q, ctx) == NULL) 169 goto err; 170 if (!BN_mod_mul(ret->s, ret->s, blind, dsa->params.q, ctx)) 171 goto err; 172 173 /* 174 * Redo if r or s is zero as required by FIPS 186-4: Section 4.6 175 * This is very unlikely. 176 * Limit the retries so there is no possibility of an infinite 177 * loop for bad domain parameter values. 178 */ 179 if (BN_is_zero(ret->r) || BN_is_zero(ret->s)) { 180 if (retries++ > MAX_DSA_SIGN_RETRIES) { 181 reason = DSA_R_TOO_MANY_RETRIES; 182 goto err; 183 } 184 goto redo; 185 } 186 rv = 1; 187 err: 188 if (rv == 0) { 189 ERR_raise(ERR_LIB_DSA, reason); 190 DSA_SIG_free(ret); 191 ret = NULL; 192 } 193 BN_CTX_free(ctx); 194 BN_clear_free(kinv); 195 return ret; 196 } 197 198 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa) 199 { 200 return ossl_dsa_do_sign_int(dgst, dlen, dsa); 201 } 202 203 static int dsa_sign_setup_no_digest(DSA *dsa, BN_CTX *ctx_in, 204 BIGNUM **kinvp, BIGNUM **rp) 205 { 206 return dsa_sign_setup(dsa, ctx_in, kinvp, rp, NULL, 0); 207 } 208 209 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, 210 BIGNUM **kinvp, BIGNUM **rp, 211 const unsigned char *dgst, int dlen) 212 { 213 BN_CTX *ctx = NULL; 214 BIGNUM *k, *kinv = NULL, *r = *rp; 215 BIGNUM *l; 216 int ret = 0; 217 int q_bits, q_words; 218 219 if (!dsa->params.p || !dsa->params.q || !dsa->params.g) { 220 ERR_raise(ERR_LIB_DSA, DSA_R_MISSING_PARAMETERS); 221 return 0; 222 } 223 224 /* Reject obviously invalid parameters */ 225 if (BN_is_zero(dsa->params.p) 226 || BN_is_zero(dsa->params.q) 227 || BN_is_zero(dsa->params.g) 228 || BN_is_negative(dsa->params.p) 229 || BN_is_negative(dsa->params.q) 230 || BN_is_negative(dsa->params.g)) { 231 ERR_raise(ERR_LIB_DSA, DSA_R_INVALID_PARAMETERS); 232 return 0; 233 } 234 if (dsa->priv_key == NULL) { 235 ERR_raise(ERR_LIB_DSA, DSA_R_MISSING_PRIVATE_KEY); 236 return 0; 237 } 238 k = BN_new(); 239 l = BN_new(); 240 if (k == NULL || l == NULL) 241 goto err; 242 243 if (ctx_in == NULL) { 244 /* if you don't pass in ctx_in you get a default libctx */ 245 if ((ctx = BN_CTX_new_ex(NULL)) == NULL) 246 goto err; 247 } else 248 ctx = ctx_in; 249 250 /* Preallocate space */ 251 q_bits = BN_num_bits(dsa->params.q); 252 q_words = bn_get_top(dsa->params.q); 253 if (q_bits < MIN_DSA_SIGN_QBITS 254 || !bn_wexpand(k, q_words + 2) 255 || !bn_wexpand(l, q_words + 2)) 256 goto err; 257 258 /* Get random k */ 259 do { 260 if (dgst != NULL) { 261 /* 262 * We calculate k from SHA512(private_key + H(message) + random). 263 * This protects the private key from a weak PRNG. 264 */ 265 if (!ossl_bn_gen_dsa_nonce_fixed_top(k, dsa->params.q, 266 dsa->priv_key, dgst, 267 dlen, ctx)) 268 goto err; 269 } else if (!ossl_bn_priv_rand_range_fixed_top(k, dsa->params.q, 0, ctx)) 270 goto err; 271 } while (ossl_bn_is_word_fixed_top(k, 0)); 272 273 BN_set_flags(k, BN_FLG_CONSTTIME); 274 BN_set_flags(l, BN_FLG_CONSTTIME); 275 276 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 277 if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, 278 dsa->lock, dsa->params.p, ctx)) 279 goto err; 280 } 281 282 /* Compute r = (g^k mod p) mod q */ 283 284 /* 285 * We do not want timing information to leak the length of k, so we 286 * compute G^k using an equivalent scalar of fixed bit-length. 287 * 288 * We unconditionally perform both of these additions to prevent a 289 * small timing information leakage. We then choose the sum that is 290 * one bit longer than the modulus. 291 * 292 * There are some concerns about the efficacy of doing this. More 293 * specifically refer to the discussion starting with: 294 * https://github.com/openssl/openssl/pull/7486#discussion_r228323705 295 * The fix is to rework BN so these gymnastics aren't required. 296 */ 297 if (!BN_add(l, k, dsa->params.q) 298 || !BN_add(k, l, dsa->params.q)) 299 goto err; 300 301 BN_consttime_swap(BN_is_bit_set(l, q_bits), k, l, q_words + 2); 302 303 if ((dsa)->meth->bn_mod_exp != NULL) { 304 if (!dsa->meth->bn_mod_exp(dsa, r, dsa->params.g, k, dsa->params.p, 305 ctx, dsa->method_mont_p)) 306 goto err; 307 } else { 308 if (!BN_mod_exp_mont(r, dsa->params.g, k, dsa->params.p, ctx, 309 dsa->method_mont_p)) 310 goto err; 311 } 312 313 if (!BN_mod(r, r, dsa->params.q, ctx)) 314 goto err; 315 316 /* Compute part of 's = inv(k) (m + xr) mod q' */ 317 if ((kinv = dsa_mod_inverse_fermat(k, dsa->params.q, ctx)) == NULL) 318 goto err; 319 320 BN_clear_free(*kinvp); 321 *kinvp = kinv; 322 kinv = NULL; 323 ret = 1; 324 err: 325 if (!ret) 326 ERR_raise(ERR_LIB_DSA, ERR_R_BN_LIB); 327 if (ctx != ctx_in) 328 BN_CTX_free(ctx); 329 BN_clear_free(k); 330 BN_clear_free(l); 331 return ret; 332 } 333 334 static int dsa_do_verify(const unsigned char *dgst, int dgst_len, 335 DSA_SIG *sig, DSA *dsa) 336 { 337 BN_CTX *ctx; 338 BIGNUM *u1, *u2, *t1; 339 BN_MONT_CTX *mont = NULL; 340 const BIGNUM *r, *s; 341 int ret = -1, i; 342 343 if (dsa->params.p == NULL 344 || dsa->params.q == NULL 345 || dsa->params.g == NULL) { 346 ERR_raise(ERR_LIB_DSA, DSA_R_MISSING_PARAMETERS); 347 return -1; 348 } 349 350 i = BN_num_bits(dsa->params.q); 351 /* fips 186-3 allows only different sizes for q */ 352 if (i != 160 && i != 224 && i != 256) { 353 ERR_raise(ERR_LIB_DSA, DSA_R_BAD_Q_VALUE); 354 return -1; 355 } 356 357 if (BN_num_bits(dsa->params.p) > OPENSSL_DSA_MAX_MODULUS_BITS) { 358 ERR_raise(ERR_LIB_DSA, DSA_R_MODULUS_TOO_LARGE); 359 return -1; 360 } 361 u1 = BN_new(); 362 u2 = BN_new(); 363 t1 = BN_new(); 364 ctx = BN_CTX_new_ex(NULL); /* verify does not need a libctx */ 365 if (u1 == NULL || u2 == NULL || t1 == NULL || ctx == NULL) 366 goto err; 367 368 DSA_SIG_get0(sig, &r, &s); 369 370 if (BN_is_zero(r) || BN_is_negative(r) || 371 BN_ucmp(r, dsa->params.q) >= 0) { 372 ret = 0; 373 goto err; 374 } 375 if (BN_is_zero(s) || BN_is_negative(s) || 376 BN_ucmp(s, dsa->params.q) >= 0) { 377 ret = 0; 378 goto err; 379 } 380 381 /* 382 * Calculate W = inv(S) mod Q save W in u2 383 */ 384 if ((BN_mod_inverse(u2, s, dsa->params.q, ctx)) == NULL) 385 goto err; 386 387 /* save M in u1 */ 388 if (dgst_len > (i >> 3)) 389 /* 390 * if the digest length is greater than the size of q use the 391 * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3, 392 * 4.2 393 */ 394 dgst_len = (i >> 3); 395 if (BN_bin2bn(dgst, dgst_len, u1) == NULL) 396 goto err; 397 398 /* u1 = M * w mod q */ 399 if (!BN_mod_mul(u1, u1, u2, dsa->params.q, ctx)) 400 goto err; 401 402 /* u2 = r * w mod q */ 403 if (!BN_mod_mul(u2, r, u2, dsa->params.q, ctx)) 404 goto err; 405 406 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 407 mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p, 408 dsa->lock, dsa->params.p, ctx); 409 if (!mont) 410 goto err; 411 } 412 413 if (dsa->meth->dsa_mod_exp != NULL) { 414 if (!dsa->meth->dsa_mod_exp(dsa, t1, dsa->params.g, u1, dsa->pub_key, u2, 415 dsa->params.p, ctx, mont)) 416 goto err; 417 } else { 418 if (!BN_mod_exp2_mont(t1, dsa->params.g, u1, dsa->pub_key, u2, 419 dsa->params.p, ctx, mont)) 420 goto err; 421 } 422 423 /* let u1 = u1 mod q */ 424 if (!BN_mod(u1, t1, dsa->params.q, ctx)) 425 goto err; 426 427 /* 428 * V is now in u1. If the signature is correct, it will be equal to R. 429 */ 430 ret = (BN_ucmp(u1, r) == 0); 431 432 err: 433 if (ret < 0) 434 ERR_raise(ERR_LIB_DSA, ERR_R_BN_LIB); 435 BN_CTX_free(ctx); 436 BN_free(u1); 437 BN_free(u2); 438 BN_free(t1); 439 return ret; 440 } 441 442 static int dsa_init(DSA *dsa) 443 { 444 dsa->flags |= DSA_FLAG_CACHE_MONT_P; 445 dsa->dirty_cnt++; 446 return 1; 447 } 448 449 static int dsa_finish(DSA *dsa) 450 { 451 BN_MONT_CTX_free(dsa->method_mont_p); 452 return 1; 453 } 454 455 /* 456 * Compute the inverse of k modulo q. 457 * Since q is prime, Fermat's Little Theorem applies, which reduces this to 458 * mod-exp operation. Both the exponent and modulus are public information 459 * so a mod-exp that doesn't leak the base is sufficient. A newly allocated 460 * BIGNUM is returned which the caller must free. 461 */ 462 static BIGNUM *dsa_mod_inverse_fermat(const BIGNUM *k, const BIGNUM *q, 463 BN_CTX *ctx) 464 { 465 BIGNUM *res = NULL; 466 BIGNUM *r, *e; 467 468 if ((r = BN_new()) == NULL) 469 return NULL; 470 471 BN_CTX_start(ctx); 472 if ((e = BN_CTX_get(ctx)) != NULL 473 && BN_set_word(r, 2) 474 && BN_sub(e, q, r) 475 && BN_mod_exp_mont(r, k, e, q, ctx, NULL)) 476 res = r; 477 else 478 BN_free(r); 479 BN_CTX_end(ctx); 480 return res; 481 } 482