1 /* 2 * Copyright 1995-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 * 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 (!BN_generate_dsa_nonce(k, dsa->params.q, dsa->priv_key, dgst, 266 dlen, ctx)) 267 goto err; 268 } else if (!BN_priv_rand_range_ex(k, dsa->params.q, 0, ctx)) 269 goto err; 270 } while (BN_is_zero(k)); 271 272 BN_set_flags(k, BN_FLG_CONSTTIME); 273 BN_set_flags(l, BN_FLG_CONSTTIME); 274 275 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 276 if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, 277 dsa->lock, dsa->params.p, ctx)) 278 goto err; 279 } 280 281 /* Compute r = (g^k mod p) mod q */ 282 283 /* 284 * We do not want timing information to leak the length of k, so we 285 * compute G^k using an equivalent scalar of fixed bit-length. 286 * 287 * We unconditionally perform both of these additions to prevent a 288 * small timing information leakage. We then choose the sum that is 289 * one bit longer than the modulus. 290 * 291 * There are some concerns about the efficacy of doing this. More 292 * specifically refer to the discussion starting with: 293 * https://github.com/openssl/openssl/pull/7486#discussion_r228323705 294 * The fix is to rework BN so these gymnastics aren't required. 295 */ 296 if (!BN_add(l, k, dsa->params.q) 297 || !BN_add(k, l, dsa->params.q)) 298 goto err; 299 300 BN_consttime_swap(BN_is_bit_set(l, q_bits), k, l, q_words + 2); 301 302 if ((dsa)->meth->bn_mod_exp != NULL) { 303 if (!dsa->meth->bn_mod_exp(dsa, r, dsa->params.g, k, dsa->params.p, 304 ctx, dsa->method_mont_p)) 305 goto err; 306 } else { 307 if (!BN_mod_exp_mont(r, dsa->params.g, k, dsa->params.p, ctx, 308 dsa->method_mont_p)) 309 goto err; 310 } 311 312 if (!BN_mod(r, r, dsa->params.q, ctx)) 313 goto err; 314 315 /* Compute part of 's = inv(k) (m + xr) mod q' */ 316 if ((kinv = dsa_mod_inverse_fermat(k, dsa->params.q, ctx)) == NULL) 317 goto err; 318 319 BN_clear_free(*kinvp); 320 *kinvp = kinv; 321 kinv = NULL; 322 ret = 1; 323 err: 324 if (!ret) 325 ERR_raise(ERR_LIB_DSA, ERR_R_BN_LIB); 326 if (ctx != ctx_in) 327 BN_CTX_free(ctx); 328 BN_clear_free(k); 329 BN_clear_free(l); 330 return ret; 331 } 332 333 static int dsa_do_verify(const unsigned char *dgst, int dgst_len, 334 DSA_SIG *sig, DSA *dsa) 335 { 336 BN_CTX *ctx; 337 BIGNUM *u1, *u2, *t1; 338 BN_MONT_CTX *mont = NULL; 339 const BIGNUM *r, *s; 340 int ret = -1, i; 341 342 if (dsa->params.p == NULL 343 || dsa->params.q == NULL 344 || dsa->params.g == NULL) { 345 ERR_raise(ERR_LIB_DSA, DSA_R_MISSING_PARAMETERS); 346 return -1; 347 } 348 349 i = BN_num_bits(dsa->params.q); 350 /* fips 186-3 allows only different sizes for q */ 351 if (i != 160 && i != 224 && i != 256) { 352 ERR_raise(ERR_LIB_DSA, DSA_R_BAD_Q_VALUE); 353 return -1; 354 } 355 356 if (BN_num_bits(dsa->params.p) > OPENSSL_DSA_MAX_MODULUS_BITS) { 357 ERR_raise(ERR_LIB_DSA, DSA_R_MODULUS_TOO_LARGE); 358 return -1; 359 } 360 u1 = BN_new(); 361 u2 = BN_new(); 362 t1 = BN_new(); 363 ctx = BN_CTX_new_ex(NULL); /* verify does not need a libctx */ 364 if (u1 == NULL || u2 == NULL || t1 == NULL || ctx == NULL) 365 goto err; 366 367 DSA_SIG_get0(sig, &r, &s); 368 369 if (BN_is_zero(r) || BN_is_negative(r) || 370 BN_ucmp(r, dsa->params.q) >= 0) { 371 ret = 0; 372 goto err; 373 } 374 if (BN_is_zero(s) || BN_is_negative(s) || 375 BN_ucmp(s, dsa->params.q) >= 0) { 376 ret = 0; 377 goto err; 378 } 379 380 /* 381 * Calculate W = inv(S) mod Q save W in u2 382 */ 383 if ((BN_mod_inverse(u2, s, dsa->params.q, ctx)) == NULL) 384 goto err; 385 386 /* save M in u1 */ 387 if (dgst_len > (i >> 3)) 388 /* 389 * if the digest length is greater than the size of q use the 390 * BN_num_bits(dsa->q) leftmost bits of the digest, see fips 186-3, 391 * 4.2 392 */ 393 dgst_len = (i >> 3); 394 if (BN_bin2bn(dgst, dgst_len, u1) == NULL) 395 goto err; 396 397 /* u1 = M * w mod q */ 398 if (!BN_mod_mul(u1, u1, u2, dsa->params.q, ctx)) 399 goto err; 400 401 /* u2 = r * w mod q */ 402 if (!BN_mod_mul(u2, r, u2, dsa->params.q, ctx)) 403 goto err; 404 405 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 406 mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p, 407 dsa->lock, dsa->params.p, ctx); 408 if (!mont) 409 goto err; 410 } 411 412 if (dsa->meth->dsa_mod_exp != NULL) { 413 if (!dsa->meth->dsa_mod_exp(dsa, t1, dsa->params.g, u1, dsa->pub_key, u2, 414 dsa->params.p, ctx, mont)) 415 goto err; 416 } else { 417 if (!BN_mod_exp2_mont(t1, dsa->params.g, u1, dsa->pub_key, u2, 418 dsa->params.p, ctx, mont)) 419 goto err; 420 } 421 422 /* let u1 = u1 mod q */ 423 if (!BN_mod(u1, t1, dsa->params.q, ctx)) 424 goto err; 425 426 /* 427 * V is now in u1. If the signature is correct, it will be equal to R. 428 */ 429 ret = (BN_ucmp(u1, r) == 0); 430 431 err: 432 if (ret < 0) 433 ERR_raise(ERR_LIB_DSA, ERR_R_BN_LIB); 434 BN_CTX_free(ctx); 435 BN_free(u1); 436 BN_free(u2); 437 BN_free(t1); 438 return ret; 439 } 440 441 static int dsa_init(DSA *dsa) 442 { 443 dsa->flags |= DSA_FLAG_CACHE_MONT_P; 444 ossl_ffc_params_init(&dsa->params); 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