1 /* $OpenBSD: dsa_ossl.c,v 1.25 2016/06/06 23:37:37 tedu 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 static DSA_SIG *dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa); 70 static int dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, 71 BIGNUM **rp); 72 static int dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, 73 DSA *dsa); 74 static int dsa_init(DSA *dsa); 75 static int dsa_finish(DSA *dsa); 76 77 static DSA_METHOD openssl_dsa_meth = { 78 .name = "OpenSSL DSA method", 79 .dsa_do_sign = dsa_do_sign, 80 .dsa_sign_setup = dsa_sign_setup, 81 .dsa_do_verify = dsa_do_verify, 82 .init = dsa_init, 83 .finish = dsa_finish 84 }; 85 86 const DSA_METHOD * 87 DSA_OpenSSL(void) 88 { 89 return &openssl_dsa_meth; 90 } 91 92 static DSA_SIG * 93 dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa) 94 { 95 BIGNUM *kinv = NULL, *r = NULL, *s = NULL; 96 BIGNUM m; 97 BIGNUM xr; 98 BN_CTX *ctx = NULL; 99 int reason = ERR_R_BN_LIB; 100 DSA_SIG *ret = NULL; 101 int noredo = 0; 102 103 BN_init(&m); 104 BN_init(&xr); 105 106 if (!dsa->p || !dsa->q || !dsa->g) { 107 reason = DSA_R_MISSING_PARAMETERS; 108 goto err; 109 } 110 111 s = BN_new(); 112 if (s == NULL) 113 goto err; 114 ctx = BN_CTX_new(); 115 if (ctx == NULL) 116 goto err; 117 redo: 118 if (dsa->kinv == NULL || dsa->r == NULL) { 119 if (!DSA_sign_setup(dsa, ctx, &kinv, &r)) 120 goto err; 121 } else { 122 kinv = dsa->kinv; 123 dsa->kinv = NULL; 124 r = dsa->r; 125 dsa->r = NULL; 126 noredo = 1; 127 } 128 129 130 /* 131 * If the digest length is greater than the size of q use the 132 * BN_num_bits(dsa->q) leftmost bits of the digest, see 133 * fips 186-3, 4.2 134 */ 135 if (dlen > BN_num_bytes(dsa->q)) 136 dlen = BN_num_bytes(dsa->q); 137 if (BN_bin2bn(dgst,dlen,&m) == NULL) 138 goto err; 139 140 /* Compute s = inv(k) (m + xr) mod q */ 141 if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx)) /* s = xr */ 142 goto err; 143 if (!BN_add(s, &xr, &m)) /* s = m + xr */ 144 goto err; 145 if (BN_cmp(s, dsa->q) > 0) 146 if (!BN_sub(s, s, dsa->q)) 147 goto err; 148 if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) 149 goto err; 150 151 ret = DSA_SIG_new(); 152 if (ret == NULL) 153 goto err; 154 /* 155 * Redo if r or s is zero as required by FIPS 186-3: this is 156 * very unlikely. 157 */ 158 if (BN_is_zero(r) || BN_is_zero(s)) { 159 if (noredo) { 160 reason = DSA_R_NEED_NEW_SETUP_VALUES; 161 goto err; 162 } 163 goto redo; 164 } 165 ret->r = r; 166 ret->s = s; 167 168 err: 169 if (!ret) { 170 DSAerr(DSA_F_DSA_DO_SIGN, reason); 171 BN_free(r); 172 BN_free(s); 173 } 174 BN_CTX_free(ctx); 175 BN_clear_free(&m); 176 BN_clear_free(&xr); 177 BN_clear_free(kinv); 178 return ret; 179 } 180 181 static int 182 dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) 183 { 184 BN_CTX *ctx; 185 BIGNUM k, *kinv = NULL, *r = NULL; 186 int ret = 0; 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 BN_init(&k); 194 195 if (ctx_in == NULL) { 196 if ((ctx = BN_CTX_new()) == NULL) 197 goto err; 198 } else 199 ctx = ctx_in; 200 201 if ((r = BN_new()) == NULL) 202 goto err; 203 204 /* Get random k */ 205 do { 206 if (!BN_rand_range(&k, dsa->q)) 207 goto err; 208 } while (BN_is_zero(&k)); 209 210 BN_set_flags(&k, BN_FLG_CONSTTIME); 211 212 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 213 if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, 214 CRYPTO_LOCK_DSA, dsa->p, ctx)) 215 goto err; 216 } 217 218 /* Compute r = (g^k mod p) mod q */ 219 220 /* 221 * We do not want timing information to leak the length of k, 222 * so we compute g^k using an equivalent exponent of fixed 223 * length. 224 * 225 * (This is a kludge that we need because the BN_mod_exp_mont() 226 * does not let us specify the desired timing behaviour.) 227 */ 228 229 if (!BN_add(&k, &k, dsa->q)) 230 goto err; 231 if (BN_num_bits(&k) <= BN_num_bits(dsa->q)) { 232 if (!BN_add(&k, &k, dsa->q)) 233 goto err; 234 } 235 236 if (dsa->meth->bn_mod_exp != NULL) { 237 if (!dsa->meth->bn_mod_exp(dsa, r, dsa->g, &k, dsa->p, ctx, 238 dsa->method_mont_p)) 239 goto err; 240 } else { 241 if (!BN_mod_exp_mont(r, dsa->g, &k, dsa->p, ctx, dsa->method_mont_p)) 242 goto err; 243 } 244 245 if (!BN_mod(r,r,dsa->q,ctx)) 246 goto err; 247 248 /* Compute part of 's = inv(k) (m + xr) mod q' */ 249 if ((kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx)) == NULL) 250 goto err; 251 252 BN_clear_free(*kinvp); 253 *kinvp = kinv; 254 kinv = NULL; 255 BN_clear_free(*rp); 256 *rp = r; 257 ret = 1; 258 err: 259 if (!ret) { 260 DSAerr(DSA_F_DSA_SIGN_SETUP, ERR_R_BN_LIB); 261 BN_clear_free(r); 262 } 263 if (ctx_in == NULL) 264 BN_CTX_free(ctx); 265 BN_clear_free(&k); 266 return ret; 267 } 268 269 static int 270 dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa) 271 { 272 BN_CTX *ctx; 273 BIGNUM u1, u2, t1; 274 BN_MONT_CTX *mont = NULL; 275 int ret = -1, i; 276 277 if (!dsa->p || !dsa->q || !dsa->g) { 278 DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MISSING_PARAMETERS); 279 return -1; 280 } 281 282 i = BN_num_bits(dsa->q); 283 /* fips 186-3 allows only different sizes for q */ 284 if (i != 160 && i != 224 && i != 256) { 285 DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_BAD_Q_VALUE); 286 return -1; 287 } 288 289 if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) { 290 DSAerr(DSA_F_DSA_DO_VERIFY, DSA_R_MODULUS_TOO_LARGE); 291 return -1; 292 } 293 BN_init(&u1); 294 BN_init(&u2); 295 BN_init(&t1); 296 297 if ((ctx = BN_CTX_new()) == NULL) 298 goto err; 299 300 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 301 BN_ucmp(sig->r, dsa->q) >= 0) { 302 ret = 0; 303 goto err; 304 } 305 if (BN_is_zero(sig->s) || BN_is_negative(sig->s) || 306 BN_ucmp(sig->s, dsa->q) >= 0) { 307 ret = 0; 308 goto err; 309 } 310 311 /* Calculate W = inv(S) mod Q 312 * save W in u2 */ 313 if ((BN_mod_inverse(&u2, sig->s, dsa->q, ctx)) == NULL) 314 goto err; 315 316 /* save M in u1 */ 317 /* 318 * If the digest length is greater than the size of q use the 319 * BN_num_bits(dsa->q) leftmost bits of the digest, see 320 * fips 186-3, 4.2 321 */ 322 if (dgst_len > (i >> 3)) 323 dgst_len = (i >> 3); 324 if (BN_bin2bn(dgst, dgst_len, &u1) == NULL) 325 goto err; 326 327 /* u1 = M * w mod q */ 328 if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx)) 329 goto err; 330 331 /* u2 = r * w mod q */ 332 if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx)) 333 goto err; 334 335 336 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 337 mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p, 338 CRYPTO_LOCK_DSA, dsa->p, ctx); 339 if (!mont) 340 goto err; 341 } 342 343 if (dsa->meth->dsa_mod_exp != NULL) { 344 if (!dsa->meth->dsa_mod_exp(dsa, &t1, dsa->g, &u1, dsa->pub_key, &u2, 345 dsa->p, ctx, mont)) 346 goto err; 347 } else { 348 if (!BN_mod_exp2_mont(&t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx, 349 mont)) 350 goto err; 351 } 352 353 /* BN_copy(&u1,&t1); */ 354 /* let u1 = u1 mod q */ 355 if (!BN_mod(&u1, &t1, dsa->q, ctx)) 356 goto err; 357 358 /* V is now in u1. If the signature is correct, it will be 359 * equal to R. */ 360 ret = BN_ucmp(&u1, sig->r) == 0; 361 362 err: 363 if (ret < 0) 364 DSAerr(DSA_F_DSA_DO_VERIFY, ERR_R_BN_LIB); 365 BN_CTX_free(ctx); 366 BN_free(&u1); 367 BN_free(&u2); 368 BN_free(&t1); 369 return ret; 370 } 371 372 static int 373 dsa_init(DSA *dsa) 374 { 375 dsa->flags |= DSA_FLAG_CACHE_MONT_P; 376 return 1; 377 } 378 379 static int 380 dsa_finish(DSA *dsa) 381 { 382 BN_MONT_CTX_free(dsa->method_mont_p); 383 return 1; 384 } 385 386