1 /* $OpenBSD: dsa_ossl.c,v 1.56 2024/05/11 06:43:50 tb Exp $ */ 2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3 * All rights reserved. 4 * 5 * This package is an SSL implementation written 6 * by Eric Young (eay@cryptsoft.com). 7 * The implementation was written so as to conform with Netscapes SSL. 8 * 9 * This library is free for commercial and non-commercial use as long as 10 * the following conditions are aheared to. The following conditions 11 * apply to all code found in this distribution, be it the RC4, RSA, 12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13 * included with this distribution is covered by the same copyright terms 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15 * 16 * Copyright remains Eric Young's, and as such any Copyright notices in 17 * the code are not to be removed. 18 * If this package is used in a product, Eric Young should be given attribution 19 * as the author of the parts of the library used. 20 * This can be in the form of a textual message at program startup or 21 * in documentation (online or textual) provided with the package. 22 * 23 * Redistribution and use in source and binary forms, with or without 24 * modification, are permitted provided that the following conditions 25 * are met: 26 * 1. Redistributions of source code must retain the copyright 27 * notice, this list of conditions and the following disclaimer. 28 * 2. Redistributions in binary form must reproduce the above copyright 29 * notice, this list of conditions and the following disclaimer in the 30 * documentation and/or other materials provided with the distribution. 31 * 3. All advertising materials mentioning features or use of this software 32 * must display the following acknowledgement: 33 * "This product includes cryptographic software written by 34 * Eric Young (eay@cryptsoft.com)" 35 * The word 'cryptographic' can be left out if the rouines from the library 36 * being used are not cryptographic related :-). 37 * 4. If you include any Windows specific code (or a derivative thereof) from 38 * the apps directory (application code) you must include an acknowledgement: 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 * 53 * The licence and distribution terms for any publically available version or 54 * derivative of this code cannot be changed. i.e. this code cannot simply be 55 * copied and put under another distribution licence 56 * [including the GNU Public Licence.] 57 */ 58 59 /* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */ 60 61 #include <stdio.h> 62 63 #include <openssl/asn1.h> 64 #include <openssl/bn.h> 65 #include <openssl/dsa.h> 66 #include <openssl/err.h> 67 #include <openssl/sha.h> 68 69 #include "bn_local.h" 70 #include "dsa_local.h" 71 72 /* 73 * Since DSA parameters are entirely arbitrary and checking them to be 74 * consistent is very expensive, we cannot do so on every sign operation. 75 * Instead, cap the number of retries so we do not loop indefinitely if 76 * the generator of the multiplicative group happens to be nilpotent. 77 * The probability of needing a retry with valid parameters is negligible, 78 * so trying 32 times is amply enough. 79 */ 80 #define DSA_MAX_SIGN_ITERATIONS 32 81 82 static DSA_SIG * 83 dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa) 84 { 85 BIGNUM *b = NULL, *bm = NULL, *bxr = NULL, *binv = NULL, *m = NULL; 86 BIGNUM *kinv = NULL, *r = NULL, *s = NULL; 87 BN_CTX *ctx = NULL; 88 int reason = ERR_R_BN_LIB; 89 DSA_SIG *ret = NULL; 90 int attempts = 0; 91 int noredo = 0; 92 93 if (!dsa_check_key(dsa)) { 94 reason = DSA_R_INVALID_PARAMETERS; 95 goto err; 96 } 97 98 if ((s = BN_new()) == NULL) 99 goto err; 100 101 if ((ctx = BN_CTX_new()) == NULL) 102 goto err; 103 104 BN_CTX_start(ctx); 105 106 if ((b = BN_CTX_get(ctx)) == NULL) 107 goto err; 108 if ((binv = BN_CTX_get(ctx)) == NULL) 109 goto err; 110 if ((bm = BN_CTX_get(ctx)) == NULL) 111 goto err; 112 if ((bxr = BN_CTX_get(ctx)) == NULL) 113 goto err; 114 if ((m = BN_CTX_get(ctx)) == NULL) 115 goto err; 116 117 /* 118 * If the digest length is greater than N (the bit length of q), the 119 * leftmost N bits of the digest shall be used, see FIPS 186-3, 4.2. 120 * In this case the digest length is given in bytes. 121 */ 122 if (dlen > BN_num_bytes(dsa->q)) 123 dlen = BN_num_bytes(dsa->q); 124 if (BN_bin2bn(dgst, dlen, m) == NULL) 125 goto err; 126 127 redo: 128 if (dsa->kinv == NULL || dsa->r == NULL) { 129 if (!DSA_sign_setup(dsa, ctx, &kinv, &r)) 130 goto err; 131 } else { 132 kinv = dsa->kinv; 133 dsa->kinv = NULL; 134 r = dsa->r; 135 dsa->r = NULL; 136 noredo = 1; 137 } 138 139 /* 140 * Compute: 141 * 142 * s = inv(k)(m + xr) mod q 143 * 144 * In order to reduce the possibility of a side-channel attack, the 145 * following is calculated using a blinding value: 146 * 147 * s = inv(b)(bm + bxr)inv(k) mod q 148 * 149 * Where b is a random value in the range [1, q). 150 */ 151 if (!bn_rand_interval(b, 1, dsa->q)) 152 goto err; 153 if (BN_mod_inverse_ct(binv, b, dsa->q, ctx) == NULL) 154 goto err; 155 156 if (!BN_mod_mul(bxr, b, dsa->priv_key, dsa->q, ctx)) /* bx */ 157 goto err; 158 if (!BN_mod_mul(bxr, bxr, r, dsa->q, ctx)) /* bxr */ 159 goto err; 160 if (!BN_mod_mul(bm, b, m, dsa->q, ctx)) /* bm */ 161 goto err; 162 if (!BN_mod_add(s, bxr, bm, dsa->q, ctx)) /* s = bm + bxr */ 163 goto err; 164 if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) /* s = b(m + xr)k^-1 */ 165 goto err; 166 if (!BN_mod_mul(s, s, binv, dsa->q, ctx)) /* s = (m + xr)k^-1 */ 167 goto err; 168 169 /* 170 * Redo if r or s is zero as required by FIPS 186-3: this is very 171 * unlikely. 172 */ 173 if (BN_is_zero(r) || BN_is_zero(s)) { 174 if (noredo) { 175 reason = DSA_R_NEED_NEW_SETUP_VALUES; 176 goto err; 177 } 178 if (++attempts > DSA_MAX_SIGN_ITERATIONS) { 179 reason = DSA_R_INVALID_PARAMETERS; 180 goto err; 181 } 182 goto redo; 183 } 184 185 if ((ret = DSA_SIG_new()) == NULL) { 186 reason = ERR_R_MALLOC_FAILURE; 187 goto err; 188 } 189 ret->r = r; 190 ret->s = s; 191 192 err: 193 if (!ret) { 194 DSAerror(reason); 195 BN_free(r); 196 BN_free(s); 197 } 198 BN_CTX_end(ctx); 199 BN_CTX_free(ctx); 200 BN_free(kinv); 201 202 return ret; 203 } 204 205 static int 206 dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) 207 { 208 BIGNUM *k = NULL, *l = NULL, *m = NULL, *kinv = NULL, *r = NULL; 209 BN_CTX *ctx = NULL; 210 int q_bits; 211 int ret = 0; 212 213 if (!dsa_check_key(dsa)) 214 goto err; 215 216 if ((r = BN_new()) == NULL) 217 goto err; 218 219 if ((ctx = ctx_in) == NULL) 220 ctx = BN_CTX_new(); 221 if (ctx == NULL) 222 goto err; 223 224 BN_CTX_start(ctx); 225 226 if ((k = BN_CTX_get(ctx)) == NULL) 227 goto err; 228 if ((l = BN_CTX_get(ctx)) == NULL) 229 goto err; 230 if ((m = BN_CTX_get(ctx)) == NULL) 231 goto err; 232 233 /* Preallocate space */ 234 q_bits = BN_num_bits(dsa->q); 235 if (!BN_set_bit(k, q_bits) || 236 !BN_set_bit(l, q_bits) || 237 !BN_set_bit(m, q_bits)) 238 goto err; 239 240 if (!bn_rand_interval(k, 1, dsa->q)) 241 goto err; 242 243 BN_set_flags(k, BN_FLG_CONSTTIME); 244 245 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 246 if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, 247 CRYPTO_LOCK_DSA, dsa->p, ctx)) 248 goto err; 249 } 250 251 /* Compute r = (g^k mod p) mod q */ 252 253 /* 254 * We do not want timing information to leak the length of k, 255 * so we compute G^k using an equivalent exponent of fixed 256 * bit-length. 257 * 258 * We unconditionally perform both of these additions to prevent a 259 * small timing information leakage. We then choose the sum that is 260 * one bit longer than the modulus. 261 * 262 * TODO: revisit the bn_copy aiming for a memory access agnostic 263 * conditional copy. 264 */ 265 266 if (!BN_add(l, k, dsa->q) || 267 !BN_add(m, l, dsa->q) || 268 !bn_copy(k, BN_num_bits(l) > q_bits ? l : m)) 269 goto err; 270 271 if (!BN_mod_exp_mont_ct(r, dsa->g, k, dsa->p, ctx, dsa->method_mont_p)) 272 goto err; 273 274 if (!BN_mod_ct(r, r, dsa->q, ctx)) 275 goto err; 276 277 /* Compute part of 's = inv(k) (m + xr) mod q' */ 278 if ((kinv = BN_mod_inverse_ct(NULL, k, dsa->q, ctx)) == NULL) 279 goto err; 280 281 BN_free(*kinvp); 282 *kinvp = kinv; 283 kinv = NULL; 284 285 BN_free(*rp); 286 *rp = r; 287 288 ret = 1; 289 290 err: 291 if (!ret) { 292 DSAerror(ERR_R_BN_LIB); 293 BN_free(r); 294 } 295 BN_CTX_end(ctx); 296 if (ctx != ctx_in) 297 BN_CTX_free(ctx); 298 299 return ret; 300 } 301 302 static int 303 dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa) 304 { 305 BIGNUM *u1 = NULL, *u2 = NULL, *t1 = NULL; 306 BN_CTX *ctx = NULL; 307 BN_MONT_CTX *mont = NULL; 308 int qbits; 309 int ret = -1; 310 311 if (!dsa_check_key(dsa)) 312 goto err; 313 314 if ((ctx = BN_CTX_new()) == NULL) 315 goto err; 316 317 BN_CTX_start(ctx); 318 319 if ((u1 = BN_CTX_get(ctx)) == NULL) 320 goto err; 321 if ((u2 = BN_CTX_get(ctx)) == NULL) 322 goto err; 323 if ((t1 = BN_CTX_get(ctx)) == NULL) 324 goto err; 325 326 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 327 BN_ucmp(sig->r, dsa->q) >= 0) { 328 ret = 0; 329 goto err; 330 } 331 if (BN_is_zero(sig->s) || BN_is_negative(sig->s) || 332 BN_ucmp(sig->s, dsa->q) >= 0) { 333 ret = 0; 334 goto err; 335 } 336 337 /* Calculate w = inv(s) mod q, saving w in u2. */ 338 if ((BN_mod_inverse_ct(u2, sig->s, dsa->q, ctx)) == NULL) 339 goto err; 340 341 /* 342 * If the digest length is greater than the size of q use the 343 * BN_num_bits(dsa->q) leftmost bits of the digest, see FIPS 186-4, 4.2. 344 */ 345 qbits = BN_num_bits(dsa->q); 346 if (dgst_len > (qbits >> 3)) 347 dgst_len = (qbits >> 3); 348 349 /* Save m in u1. */ 350 if (BN_bin2bn(dgst, dgst_len, u1) == NULL) 351 goto err; 352 353 /* u1 = m * w mod q */ 354 if (!BN_mod_mul(u1, u1, u2, dsa->q, ctx)) 355 goto err; 356 357 /* u2 = r * w mod q */ 358 if (!BN_mod_mul(u2, sig->r, u2, dsa->q, ctx)) 359 goto err; 360 361 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 362 mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p, 363 CRYPTO_LOCK_DSA, dsa->p, ctx); 364 if (!mont) 365 goto err; 366 } 367 368 if (!BN_mod_exp2_mont(t1, dsa->g, u1, dsa->pub_key, u2, dsa->p, 369 ctx, mont)) 370 goto err; 371 372 /* let u1 = u1 mod q */ 373 if (!BN_mod_ct(u1, t1, dsa->q, ctx)) 374 goto err; 375 376 /* v is in u1 - if the signature is correct, it will be equal to r. */ 377 ret = BN_ucmp(u1, sig->r) == 0; 378 379 err: 380 if (ret < 0) 381 DSAerror(ERR_R_BN_LIB); 382 BN_CTX_end(ctx); 383 BN_CTX_free(ctx); 384 385 return ret; 386 } 387 388 static int 389 dsa_init(DSA *dsa) 390 { 391 dsa->flags |= DSA_FLAG_CACHE_MONT_P; 392 return 1; 393 } 394 395 static int 396 dsa_finish(DSA *dsa) 397 { 398 BN_MONT_CTX_free(dsa->method_mont_p); 399 return 1; 400 } 401 402 static const DSA_METHOD openssl_dsa_meth = { 403 .name = "OpenSSL DSA method", 404 .dsa_do_sign = dsa_do_sign, 405 .dsa_sign_setup = dsa_sign_setup, 406 .dsa_do_verify = dsa_do_verify, 407 .init = dsa_init, 408 .finish = dsa_finish, 409 }; 410 411 const DSA_METHOD * 412 DSA_OpenSSL(void) 413 { 414 return &openssl_dsa_meth; 415 } 416 LCRYPTO_ALIAS(DSA_OpenSSL); 417 418 DSA_SIG * 419 DSA_SIG_new(void) 420 { 421 return calloc(1, sizeof(DSA_SIG)); 422 } 423 LCRYPTO_ALIAS(DSA_SIG_new); 424 425 void 426 DSA_SIG_free(DSA_SIG *sig) 427 { 428 if (sig == NULL) 429 return; 430 431 BN_free(sig->r); 432 BN_free(sig->s); 433 free(sig); 434 } 435 LCRYPTO_ALIAS(DSA_SIG_free); 436 437 int 438 DSA_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) 439 { 440 return dsa->meth->dsa_sign_setup(dsa, ctx_in, kinvp, rp); 441 } 442 LCRYPTO_ALIAS(DSA_sign_setup); 443 444 DSA_SIG * 445 DSA_do_sign(const unsigned char *dgst, int dlen, DSA *dsa) 446 { 447 return dsa->meth->dsa_do_sign(dgst, dlen, dsa); 448 } 449 LCRYPTO_ALIAS(DSA_do_sign); 450 451 int 452 DSA_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa) 453 { 454 return dsa->meth->dsa_do_verify(dgst, dgst_len, sig, dsa); 455 } 456 LCRYPTO_ALIAS(DSA_do_verify); 457