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