1/* 2 * Copyright (c) 2011-12 Apple Inc. All Rights Reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * This file contains Original Code and/or Modifications of Original Code 7 * as defined in and that are subject to the Apple Public Source License 8 * Version 2.0 (the 'License'). You may not use this file except in 9 * compliance with the License. Please obtain a copy of the License at 10 * http://www.opensource.apple.com/apsl/ and read it before using this 11 * file. 12 * 13 * The Original Code and all software distributed under the License are 14 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 15 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 16 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 17 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 18 * Please see the License for the specific language governing rights and 19 * limitations under the License. 20 * 21 * @APPLE_LICENSE_HEADER_END@ 22 */ 23 24/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 25 * All rights reserved. 26 * 27 * This package is an SSL implementation written 28 * by Eric Young (eay@cryptsoft.com). 29 * The implementation was written so as to conform with Netscapes SSL. 30 * 31 * This library is free for commercial and non-commercial use as long as 32 * the following conditions are aheared to. The following conditions 33 * apply to all code found in this distribution, be it the RC4, RSA, 34 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 35 * included with this distribution is covered by the same copyright terms 36 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 37 * 38 * Copyright remains Eric Young's, and as such any Copyright notices in 39 * the code are not to be removed. 40 * If this package is used in a product, Eric Young should be given attribution 41 * as the author of the parts of the library used. 42 * This can be in the form of a textual message at program startup or 43 * in documentation (online or textual) provided with the package. 44 * 45 * Redistribution and use in source and binary forms, with or without 46 * modification, are permitted provided that the following conditions 47 * are met: 48 * 1. Redistributions of source code must retain the copyright 49 * notice, this list of conditions and the following disclaimer. 50 * 2. Redistributions in binary form must reproduce the above copyright 51 * notice, this list of conditions and the following disclaimer in the 52 * documentation and/or other materials provided with the distribution. 53 * 3. All advertising materials mentioning features or use of this software 54 * must display the following acknowledgement: 55 * "This product includes cryptographic software written by 56 * Eric Young (eay@cryptsoft.com)" 57 * The word 'cryptographic' can be left out if the rouines from the library 58 * being used are not cryptographic related :-). 59 * 4. If you include any Windows specific code (or a derivative thereof) from 60 * the apps directory (application code) you must include an acknowledgement: 61 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 62 * 63 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 64 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 65 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 66 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 67 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 68 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 69 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 70 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 71 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 72 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 73 * SUCH DAMAGE. 74 * 75 * The licence and distribution terms for any publically available version or 76 * derivative of this code cannot be changed. i.e. this code cannot simply be 77 * copied and put under another distribution licence 78 * [including the GNU Public Licence.] 79 */ 80 81/* Original version from Steven Schoch <schoch@sheba.arc.nasa.gov> */ 82 83#include "ossl-config.h" 84 85#include <stdio.h> 86#include <stdlib.h> 87#include <string.h> 88 89#include "ossl-bn.h" 90#include "ossl-dsa.h" 91#include "ossl-rand.h" 92 93#if !defined(PR_10488503_FIXED) 94 95#define DSA_MAX_MODULUS_BITS 10000 96 97static DSA_SIG *eay_dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa); 98static int eay_dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp); 99static int eay_dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, 100 DSA *dsa); 101static int eay_dsa_init(DSA *dsa); 102static int eay_dsa_finish(DSA *dsa); 103 104/* These macro wrappers replace attempts to use the dsa_mod_exp() and 105 * bn_mod_exp() handlers in the DSA_METHOD structure. We avoid the problem of 106 * having a the macro work as an expression by bundling an "err_instr". So; 107 * 108 * if (!dsa->meth->bn_mod_exp(dsa, r,dsa->g,&k,dsa->p,ctx, 109 * dsa->method_mont_p)) goto err; 110 * 111 * can be replaced by; 112 * 113 * DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, &k, dsa->p, ctx, 114 * dsa->method_mont_p); 115 */ 116#define DSA_MOD_EXP(err_instr, dsa, rr, a1, p1, a2, p2, m, ctx, in_mont) \ 117 do { \ 118 int _tmp_res53; \ 119 if ((dsa)->meth->dsa_mod_exp) { \ 120 _tmp_res53 = (dsa)->meth->dsa_mod_exp((dsa), (rr), (a1), (p1), \ 121 (a2), (p2), (m), (ctx), (in_mont)); } \ 122 else{ \ 123 _tmp_res53 = BN_mod_exp2_mont((rr), (a1), (p1), (a2), (p2), \ 124 (m), (ctx), (in_mont)); } \ 125 if (!_tmp_res53) { err_instr; } \ 126 } \ 127 while (0) 128#define DSA_BN_MOD_EXP(err_instr, dsa, r, a, p, m, ctx, m_ctx) \ 129 do { \ 130 int _tmp_res53; \ 131 if ((dsa)->meth->bn_mod_exp) { \ 132 _tmp_res53 = (dsa)->meth->bn_mod_exp((dsa), (r), (a), (p), \ 133 (m), (ctx), (m_ctx)); } \ 134 else{ \ 135 _tmp_res53 = BN_mod_exp_mont((r), (a), (p), (m), (ctx), (m_ctx)); } \ 136 if (!_tmp_res53) { err_instr; } \ 137 } \ 138 while (0) 139 140static DSA_SIG * 141eay_dsa_do_sign(const unsigned char *dgst, int dlen, DSA *dsa) 142{ 143 BIGNUM *kinv = NULL, *r = NULL, *s = NULL; 144 BIGNUM m; 145 BIGNUM xr; 146 BN_CTX *ctx = NULL; 147 int i /* , reason = ERR_R_BN_LIB */; 148 DSA_SIG *ret = NULL; 149 150 BN_init(&m); 151 BN_init(&xr); 152 153 if (!dsa->p || !dsa->q || !dsa->g) { 154 /* reason = DSA_R_MISSING_PARAMETERS; */ 155 goto err; 156 } 157 158 s = BN_new(); 159 if (s == NULL) { 160 goto err; 161 } 162 163 i = BN_num_bytes(dsa->q); /* should be 20 */ 164 if ((dlen > i) || (dlen > 50)) { 165 /* reason=DSA_R_DATA_TOO_LARGE_FOR_KEY_SIZE; */ 166 goto err; 167 } 168 169 ctx = BN_CTX_new(); 170 if (ctx == NULL) { 171 goto err; 172 } 173 174 if ((dsa->kinv == NULL) || (dsa->r == NULL)) { 175 if (!DSA_sign_setup(dsa, ctx, &kinv, &r)) { 176 goto err; 177 } 178 } else { 179 kinv = dsa->kinv; 180 dsa->kinv = NULL; 181 r = dsa->r; 182 dsa->r = NULL; 183 } 184 185 if (BN_bin2bn(dgst, dlen, &m) == NULL) { 186 goto err; 187 } 188 189 /* Compute s = inv(k) (m + xr) mod q */ 190 if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx)) { 191 goto err; /* s = xr */ 192 } 193 if (!BN_add(s, &xr, &m)) { 194 goto err; /* s = m + xr */ 195 } 196 if (BN_cmp(s, dsa->q) > 0) { 197 if (!BN_sub(s, s, dsa->q)) { 198 goto err; 199 } 200 } 201 if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) { 202 goto err; 203 } 204 205 ret = DSA_SIG_new(); 206 if (ret == NULL) { 207 goto err; 208 } 209 ret->r = r; 210 ret->s = s; 211 212err: 213 if (!ret) { 214 /* DSAerr(DSA_F_DSA_DO_SIGN,reason); */ 215 BN_free(r); 216 BN_free(s); 217 } 218 if (ctx != NULL) { 219 BN_CTX_free(ctx); 220 } 221 BN_clear_free(&m); 222 BN_clear_free(&xr); 223 if (kinv != NULL) { /* dsa->kinv is NULL now if we used it */ 224 BN_clear_free(kinv); 225 } 226 return (ret); 227} 228 229 230static int 231eay_dsa_sign_setup(DSA *dsa, BN_CTX *ctx_in, BIGNUM **kinvp, BIGNUM **rp) 232{ 233 BN_CTX *ctx; 234 BIGNUM k, kq, *K, *kinv = NULL, *r = NULL; 235 int ret = 0; 236 237 if (!dsa->p || !dsa->q || !dsa->g) { 238 /* DSAerr(DSA_F_DSA_SIGN_SETUP,DSA_R_MISSING_PARAMETERS); */ 239 return (0); 240 } 241 242 BN_init(&k); 243 BN_init(&kq); 244 245 if (ctx_in == NULL) { 246 if ((ctx = BN_CTX_new()) == NULL) { 247 goto err; 248 } 249 } else{ 250 ctx = ctx_in; 251 } 252 253 if ((r = BN_new()) == NULL) { 254 goto err; 255 } 256 257 /* Get random k */ 258 do { 259 if (!BN_rand_range(&k, dsa->q)) { 260 goto err; 261 } 262 } while (BN_is_zero(&k)); 263 if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) { 264 BN_set_flags(&k, BN_FLG_CONSTTIME); 265 } 266 267#if 0 268 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 269 if (!BN_MONT_CTX_set_locked(&dsa->method_mont_p, 270 CRYPTO_LOCK_DSA, 271 dsa->p, ctx)) { 272 goto err; 273 } 274 } 275#endif 276 277 /* Compute r = (g^k mod p) mod q */ 278 279 if ((dsa->flags & DSA_FLAG_NO_EXP_CONSTTIME) == 0) { 280 if (!BN_copy(&kq, &k)) { 281 goto err; 282 } 283 284 /* We do not want timing information to leak the length of k, 285 * so we compute g^k using an equivalent exponent of fixed length. 286 * 287 * (This is a kludge that we need because the BN_mod_exp_mont() 288 * does not let us specify the desired timing behaviour.) */ 289 290 if (!BN_add(&kq, &kq, dsa->q)) { 291 goto err; 292 } 293 if (BN_num_bits(&kq) <= BN_num_bits(dsa->q)) { 294 if (!BN_add(&kq, &kq, dsa->q)) { 295 goto err; 296 } 297 } 298 299 K = &kq; 300 } else { 301 K = &k; 302 } 303#if 1 304 DSA_BN_MOD_EXP(goto err, dsa, r, dsa->g, K, dsa->p, ctx, 305 dsa->method_mont_p); 306#else 307 if (!BN_mod_exp(r, dsa->g, K, dsa->p, ctx)) { 308 goto err; 309 } 310#endif 311 if (!BN_mod(r, r, dsa->q, ctx)) { 312 goto err; 313 } 314 315 /* Compute part of 's = inv(k) (m + xr) mod q' */ 316 if ((kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx)) == NULL) { 317 goto err; 318 } 319 320 if (*kinvp != NULL) { 321 BN_clear_free(*kinvp); 322 } 323 *kinvp = kinv; 324 kinv = NULL; 325 if (*rp != NULL) { 326 BN_clear_free(*rp); 327 } 328 *rp = r; 329 ret = 1; 330err: 331 if (!ret) { 332 /* DSAerr(DSA_F_DSA_SIGN_SETUP,ERR_R_BN_LIB); */ 333 if (kinv != NULL) { 334 BN_clear_free(kinv); 335 } 336 if (r != NULL) { 337 BN_clear_free(r); 338 } 339 } 340 if (ctx_in == NULL) { 341 BN_CTX_free(ctx); 342 } 343 if (kinv != NULL) { 344 BN_clear_free(kinv); 345 } 346 BN_clear_free(&k); 347 BN_clear_free(&kq); 348 349 return (ret); 350} 351 352 353static int 354eay_dsa_do_verify(const unsigned char *dgst, int dgst_len, DSA_SIG *sig, DSA *dsa) 355{ 356 BN_CTX *ctx; 357 BIGNUM u1, u2, t1; 358 BN_MONT_CTX *mont = NULL; 359 int ret = -1; 360 361 if (!dsa->p || !dsa->q || !dsa->g) { 362 /* DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_MISSING_PARAMETERS); */ 363 return (-1); 364 } 365 366 if (BN_num_bits(dsa->q) != 160) { 367 /* DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_BAD_Q_VALUE); */ 368 return (-1); 369 } 370 371 if (BN_num_bits(dsa->p) > DSA_MAX_MODULUS_BITS) { 372 /* DSAerr(DSA_F_DSA_DO_VERIFY,DSA_R_MODULUS_TOO_LARGE); */ 373 return (-1); 374 } 375 376 BN_init(&u1); 377 BN_init(&u2); 378 BN_init(&t1); 379 380 if ((ctx = BN_CTX_new()) == NULL) { 381 goto err; 382 } 383 384 if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || 385 (BN_ucmp(sig->r, dsa->q) >= 0)) { 386 ret = 0; 387 goto err; 388 } 389 if (BN_is_zero(sig->s) || BN_is_negative(sig->s) || 390 (BN_ucmp(sig->s, dsa->q) >= 0)) { 391 ret = 0; 392 goto err; 393 } 394 395 /* Calculate W = inv(S) mod Q 396 * save W in u2 */ 397 if ((BN_mod_inverse(&u2, sig->s, dsa->q, ctx)) == NULL) { 398 goto err; 399 } 400 401 /* save M in u1 */ 402 if (BN_bin2bn(dgst, dgst_len, &u1) == NULL) { 403 goto err; 404 } 405 406 /* u1 = M * w mod q */ 407 if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx)) { 408 goto err; 409 } 410 411 /* u2 = r * w mod q */ 412 if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx)) { 413 goto err; 414 } 415 416 417#if 0 418 if (dsa->flags & DSA_FLAG_CACHE_MONT_P) { 419 mont = BN_MONT_CTX_set_locked(&dsa->method_mont_p, 420 CRYPTO_LOCK_DSA, dsa->p, ctx); 421 if (!mont) { 422 goto err; 423 } 424 } 425#endif 426 427 /* v = g^u1 * y^u2 mod p mod q */ 428#if 1 429 DSA_MOD_EXP(goto err, dsa, &t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx, mont); 430#else 431 /* u1 = g^u1 mod p */ 432 if (!BN_mod_exp(&u1, dsa->g, &u1, dsa->p, ctx)) { 433 goto err; 434 } 435 /* u2 = y^u2 mod p */ 436 if (!BN_mod_exp(&u2, dsa->pub_key, &u2, dsa->p, ctx)) { 437 goto err; 438 } 439 /* t1 = u1 * u2 mod p */ 440 if (!BN_mod_mul(&t1, &u1, &u2, dsa->p, ctx)) { 441 goto err; 442 } 443#endif 444 /* BN_copy(&u1,&t1); */ 445 /* let u1 = u1 mod q */ 446 if (!BN_mod(&u1, &t1, dsa->q, ctx)) { 447 goto err; 448 } 449 450 /* V is now in u1. If the signature is correct, it will be 451 * equal to R. */ 452 ret = (BN_ucmp(&u1, sig->r) == 0); 453 454err: 455 456 /* XXX: surely this is wrong - if ret is 0, it just didn't verify; 457 * there is no error in BN. Test should be ret == -1 (Ben) */ 458 /* if (ret != 1) DSAerr(DSA_F_DSA_DO_VERIFY,ERR_R_BN_LIB); */ 459 if (ctx != NULL) { 460 BN_CTX_free(ctx); 461 } 462 BN_free(&u1); 463 BN_free(&u2); 464 BN_free(&t1); 465 return (ret); 466} 467 468 469static int dsa_init(DSA *dsa) 470{ 471 /* dsa->flags|=DSA_FLAG_CACHE_MONT_P; */ 472 return (1); 473} 474 475 476static int dsa_finish(DSA *dsa) 477{ 478 if (dsa->method_mont_p) { 479 BN_MONT_CTX_free(dsa->method_mont_p); 480 } 481 return (1); 482} 483 484 485const DSA_METHOD _ossl_dsa_eay_method = 486{ 487 .name = "EAY DSA", 488 .dsa_do_sign = eay_dsa_do_sign, 489 .dsa_sign_setup = eay_dsa_sign_setup, 490 .dsa_do_verify = eay_dsa_do_verify, 491 .dsa_mod_exp = NULL, /* dsa_mod_exp, */ 492 .bn_mod_exp = NULL, /* dsa_bn_mod_exp, */ 493 .init = dsa_init, 494 .finish = dsa_finish, 495 .flags = 0, 496 .app_data = NULL, 497 .dsa_paramgen = NULL, 498 .dsa_keygen = NULL 499}; 500 501#endif /* ! defined(PR_10488503_FIXED) */ 502 503const DSA_METHOD * 504DSA_eay_method(void) 505{ 506#if !defined(PR_10488503_FIXED) 507 return (&_ossl_dsa_eay_method); 508 509#else 510 return (NULL); 511#endif 512} 513