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