| 1 |
/* Copyright (C) 1995-1998 Eric Young ([email protected]) |
| 2 |
* All rights reserved. |
| 3 |
* |
| 4 |
* This package is an SSL implementation written |
| 5 |
* by Eric Young ([email protected]). |
| 6 |
* The implementation was written so as to conform with Netscapes SSL. |
| 7 |
* |
| 8 |
* This library is free for commercial and non-commercial use as long as |
| 9 |
* the following conditions are aheared to. The following conditions |
| 10 |
* apply to all code found in this distribution, be it the RC4, RSA, |
| 11 |
* lhash, DES, etc., code; not just the SSL code. The SSL documentation |
| 12 |
* included with this distribution is covered by the same copyright terms |
| 13 |
* except that the holder is Tim Hudson ([email protected]). |
| 14 |
* |
| 15 |
* Copyright remains Eric Young's, and as such any Copyright notices in |
| 16 |
* the code are not to be removed. |
| 17 |
* If this package is used in a product, Eric Young should be given attribution |
| 18 |
* as the author of the parts of the library used. |
| 19 |
* This can be in the form of a textual message at program startup or |
| 20 |
* in documentation (online or textual) provided with the package. |
| 21 |
* |
| 22 |
* Redistribution and use in source and binary forms, with or without |
| 23 |
* modification, are permitted provided that the following conditions |
| 24 |
* are met: |
| 25 |
* 1. Redistributions of source code must retain the copyright |
| 26 |
* notice, this list of conditions and the following disclaimer. |
| 27 |
* 2. Redistributions in binary form must reproduce the above copyright |
| 28 |
* notice, this list of conditions and the following disclaimer in the |
| 29 |
* documentation and/or other materials provided with the distribution. |
| 30 |
* 3. All advertising materials mentioning features or use of this software |
| 31 |
* must display the following acknowledgement: |
| 32 |
* "This product includes cryptographic software written by |
| 33 |
* Eric Young ([email protected])" |
| 34 |
* The word 'cryptographic' can be left out if the rouines from the library |
| 35 |
* being used are not cryptographic related :-). |
| 36 |
* 4. If you include any Windows specific code (or a derivative thereof) from |
| 37 |
* the apps directory (application code) you must include an acknowledgement: |
| 38 |
* "This product includes software written by Tim Hudson ([email protected])" |
| 39 |
* |
| 40 |
* THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND |
| 41 |
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| 42 |
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| 43 |
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
| 44 |
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| 45 |
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| 46 |
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| 47 |
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| 48 |
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| 49 |
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| 50 |
* SUCH DAMAGE. |
| 51 |
* |
| 52 |
* The licence and distribution terms for any publically available version or |
| 53 |
* derivative of this code cannot be changed. i.e. this code cannot simply be |
| 54 |
* copied and put under another distribution licence |
| 55 |
* [including the GNU Public Licence.] |
| 56 |
* |
| 57 |
* The DSS routines are based on patches supplied by |
| 58 |
* Steven Schoch <[email protected]>. */ |
| 59 |
|
| 60 |
#include <openssl/dsa.h> |
| 61 |
|
| 62 |
#include <string.h> |
| 63 |
|
| 64 |
#include <openssl/bn.h> |
| 65 |
#include <openssl/dh.h> |
| 66 |
#include <openssl/digest.h> |
| 67 |
#include <openssl/engine.h> |
| 68 |
#include <openssl/err.h> |
| 69 |
#include <openssl/ex_data.h> |
| 70 |
#include <openssl/mem.h> |
| 71 |
#include <openssl/rand.h> |
| 72 |
#include <openssl/sha.h> |
| 73 |
#include <openssl/thread.h> |
| 74 |
|
| 75 |
#include "../internal.h" |
| 76 |
|
| 77 |
|
| 78 |
#define OPENSSL_DSA_MAX_MODULUS_BITS 10000 |
| 79 |
|
| 80 |
/* Primality test according to FIPS PUB 186[-1], Appendix 2.1: 50 rounds of |
| 81 |
* Rabin-Miller */ |
| 82 |
#define DSS_prime_checks 50 |
| 83 |
|
| 84 |
static CRYPTO_EX_DATA_CLASS g_ex_data_class = CRYPTO_EX_DATA_CLASS_INIT; |
| 85 |
|
| 86 |
DSA *DSA_new(void) { |
| 87 |
DSA *dsa = OPENSSL_malloc(sizeof(DSA)); |
| 88 |
if (dsa == NULL) { |
| 89 |
OPENSSL_PUT_ERROR(DSA, ERR_R_MALLOC_FAILURE); |
| 90 |
return NULL; |
| 91 |
} |
| 92 |
|
| 93 |
memset(dsa, 0, sizeof(DSA)); |
| 94 |
|
| 95 |
dsa->references = 1; |
| 96 |
|
| 97 |
CRYPTO_MUTEX_init(&dsa->method_mont_p_lock); |
| 98 |
CRYPTO_new_ex_data(&dsa->ex_data); |
| 99 |
|
| 100 |
return dsa; |
| 101 |
} |
| 102 |
|
| 103 |
void DSA_free(DSA *dsa) { |
| 104 |
if (dsa == NULL) { |
| 105 |
return; |
| 106 |
} |
| 107 |
|
| 108 |
if (!CRYPTO_refcount_dec_and_test_zero(&dsa->references)) { |
| 109 |
return; |
| 110 |
} |
| 111 |
|
| 112 |
CRYPTO_free_ex_data(&g_ex_data_class, dsa, &dsa->ex_data); |
| 113 |
|
| 114 |
BN_clear_free(dsa->p); |
| 115 |
BN_clear_free(dsa->q); |
| 116 |
BN_clear_free(dsa->g); |
| 117 |
BN_clear_free(dsa->pub_key); |
| 118 |
BN_clear_free(dsa->priv_key); |
| 119 |
BN_clear_free(dsa->kinv); |
| 120 |
BN_clear_free(dsa->r); |
| 121 |
BN_MONT_CTX_free(dsa->method_mont_p); |
| 122 |
CRYPTO_MUTEX_cleanup(&dsa->method_mont_p_lock); |
| 123 |
OPENSSL_free(dsa); |
| 124 |
} |
| 125 |
|
| 126 |
int DSA_up_ref(DSA *dsa) { |
| 127 |
CRYPTO_refcount_inc(&dsa->references); |
| 128 |
return 1; |
| 129 |
} |
| 130 |
|
| 131 |
int DSA_generate_parameters_ex(DSA *dsa, unsigned bits, const uint8_t *seed_in, |
| 132 |
size_t seed_len, int *out_counter, |
| 133 |
unsigned long *out_h, BN_GENCB *cb) { |
| 134 |
int ok = 0; |
| 135 |
unsigned char seed[SHA256_DIGEST_LENGTH]; |
| 136 |
unsigned char md[SHA256_DIGEST_LENGTH]; |
| 137 |
unsigned char buf[SHA256_DIGEST_LENGTH], buf2[SHA256_DIGEST_LENGTH]; |
| 138 |
BIGNUM *r0, *W, *X, *c, *test; |
| 139 |
BIGNUM *g = NULL, *q = NULL, *p = NULL; |
| 140 |
BN_MONT_CTX *mont = NULL; |
| 141 |
int k, n = 0, m = 0; |
| 142 |
unsigned i; |
| 143 |
int counter = 0; |
| 144 |
int r = 0; |
| 145 |
BN_CTX *ctx = NULL; |
| 146 |
unsigned int h = 2; |
| 147 |
unsigned qsize; |
| 148 |
const EVP_MD *evpmd; |
| 149 |
|
| 150 |
evpmd = (bits >= 2048) ? EVP_sha256() : EVP_sha1(); |
| 151 |
qsize = EVP_MD_size(evpmd); |
| 152 |
|
| 153 |
if (bits < 512) { |
| 154 |
bits = 512; |
| 155 |
} |
| 156 |
|
| 157 |
bits = (bits + 63) / 64 * 64; |
| 158 |
|
| 159 |
if (seed_in != NULL) { |
| 160 |
if (seed_len < (size_t)qsize) { |
| 161 |
return 0; |
| 162 |
} |
| 163 |
if (seed_len > (size_t)qsize) { |
| 164 |
/* Only consume as much seed as is expected. */ |
| 165 |
seed_len = qsize; |
| 166 |
} |
| 167 |
memcpy(seed, seed_in, seed_len); |
| 168 |
} |
| 169 |
|
| 170 |
ctx = BN_CTX_new(); |
| 171 |
if (ctx == NULL) { |
| 172 |
goto err; |
| 173 |
} |
| 174 |
BN_CTX_start(ctx); |
| 175 |
|
| 176 |
mont = BN_MONT_CTX_new(); |
| 177 |
if (mont == NULL) { |
| 178 |
goto err; |
| 179 |
} |
| 180 |
|
| 181 |
r0 = BN_CTX_get(ctx); |
| 182 |
g = BN_CTX_get(ctx); |
| 183 |
W = BN_CTX_get(ctx); |
| 184 |
q = BN_CTX_get(ctx); |
| 185 |
X = BN_CTX_get(ctx); |
| 186 |
c = BN_CTX_get(ctx); |
| 187 |
p = BN_CTX_get(ctx); |
| 188 |
test = BN_CTX_get(ctx); |
| 189 |
|
| 190 |
if (test == NULL || !BN_lshift(test, BN_value_one(), bits - 1)) { |
| 191 |
goto err; |
| 192 |
} |
| 193 |
|
| 194 |
for (;;) { |
| 195 |
/* Find q. */ |
| 196 |
for (;;) { |
| 197 |
/* step 1 */ |
| 198 |
if (!BN_GENCB_call(cb, 0, m++)) { |
| 199 |
goto err; |
| 200 |
} |
| 201 |
|
| 202 |
int use_random_seed = (seed_in == NULL); |
| 203 |
if (use_random_seed) { |
| 204 |
if (!RAND_bytes(seed, qsize)) { |
| 205 |
goto err; |
| 206 |
} |
| 207 |
} else { |
| 208 |
/* If we come back through, use random seed next time. */ |
| 209 |
seed_in = NULL; |
| 210 |
} |
| 211 |
memcpy(buf, seed, qsize); |
| 212 |
memcpy(buf2, seed, qsize); |
| 213 |
/* precompute "SEED + 1" for step 7: */ |
| 214 |
for (i = qsize - 1; i < qsize; i--) { |
| 215 |
buf[i]++; |
| 216 |
if (buf[i] != 0) { |
| 217 |
break; |
| 218 |
} |
| 219 |
} |
| 220 |
|
| 221 |
/* step 2 */ |
| 222 |
if (!EVP_Digest(seed, qsize, md, NULL, evpmd, NULL) || |
| 223 |
!EVP_Digest(buf, qsize, buf2, NULL, evpmd, NULL)) { |
| 224 |
goto err; |
| 225 |
} |
| 226 |
for (i = 0; i < qsize; i++) { |
| 227 |
md[i] ^= buf2[i]; |
| 228 |
} |
| 229 |
|
| 230 |
/* step 3 */ |
| 231 |
md[0] |= 0x80; |
| 232 |
md[qsize - 1] |= 0x01; |
| 233 |
if (!BN_bin2bn(md, qsize, q)) { |
| 234 |
goto err; |
| 235 |
} |
| 236 |
|
| 237 |
/* step 4 */ |
| 238 |
r = BN_is_prime_fasttest_ex(q, DSS_prime_checks, ctx, use_random_seed, cb); |
| 239 |
if (r > 0) { |
| 240 |
break; |
| 241 |
} |
| 242 |
if (r != 0) { |
| 243 |
goto err; |
| 244 |
} |
| 245 |
|
| 246 |
/* do a callback call */ |
| 247 |
/* step 5 */ |
| 248 |
} |
| 249 |
|
| 250 |
if (!BN_GENCB_call(cb, 2, 0) || !BN_GENCB_call(cb, 3, 0)) { |
| 251 |
goto err; |
| 252 |
} |
| 253 |
|
| 254 |
/* step 6 */ |
| 255 |
counter = 0; |
| 256 |
/* "offset = 2" */ |
| 257 |
|
| 258 |
n = (bits - 1) / 160; |
| 259 |
|
| 260 |
for (;;) { |
| 261 |
if ((counter != 0) && !BN_GENCB_call(cb, 0, counter)) { |
| 262 |
goto err; |
| 263 |
} |
| 264 |
|
| 265 |
/* step 7 */ |
| 266 |
BN_zero(W); |
| 267 |
/* now 'buf' contains "SEED + offset - 1" */ |
| 268 |
for (k = 0; k <= n; k++) { |
| 269 |
/* obtain "SEED + offset + k" by incrementing: */ |
| 270 |
for (i = qsize - 1; i < qsize; i--) { |
| 271 |
buf[i]++; |
| 272 |
if (buf[i] != 0) { |
| 273 |
break; |
| 274 |
} |
| 275 |
} |
| 276 |
|
| 277 |
if (!EVP_Digest(buf, qsize, md, NULL, evpmd, NULL)) { |
| 278 |
goto err; |
| 279 |
} |
| 280 |
|
| 281 |
/* step 8 */ |
| 282 |
if (!BN_bin2bn(md, qsize, r0) || |
| 283 |
!BN_lshift(r0, r0, (qsize << 3) * k) || |
| 284 |
!BN_add(W, W, r0)) { |
| 285 |
goto err; |
| 286 |
} |
| 287 |
} |
| 288 |
|
| 289 |
/* more of step 8 */ |
| 290 |
if (!BN_mask_bits(W, bits - 1) || |
| 291 |
!BN_copy(X, W) || |
| 292 |
!BN_add(X, X, test)) { |
| 293 |
goto err; |
| 294 |
} |
| 295 |
|
| 296 |
/* step 9 */ |
| 297 |
if (!BN_lshift1(r0, q) || |
| 298 |
!BN_mod(c, X, r0, ctx) || |
| 299 |
!BN_sub(r0, c, BN_value_one()) || |
| 300 |
!BN_sub(p, X, r0)) { |
| 301 |
goto err; |
| 302 |
} |
| 303 |
|
| 304 |
/* step 10 */ |
| 305 |
if (BN_cmp(p, test) >= 0) { |
| 306 |
/* step 11 */ |
| 307 |
r = BN_is_prime_fasttest_ex(p, DSS_prime_checks, ctx, 1, cb); |
| 308 |
if (r > 0) { |
| 309 |
goto end; /* found it */ |
| 310 |
} |
| 311 |
if (r != 0) { |
| 312 |
goto err; |
| 313 |
} |
| 314 |
} |
| 315 |
|
| 316 |
/* step 13 */ |
| 317 |
counter++; |
| 318 |
/* "offset = offset + n + 1" */ |
| 319 |
|
| 320 |
/* step 14 */ |
| 321 |
if (counter >= 4096) { |
| 322 |
break; |
| 323 |
} |
| 324 |
} |
| 325 |
} |
| 326 |
end: |
| 327 |
if (!BN_GENCB_call(cb, 2, 1)) { |
| 328 |
goto err; |
| 329 |
} |
| 330 |
|
| 331 |
/* We now need to generate g */ |
| 332 |
/* Set r0=(p-1)/q */ |
| 333 |
if (!BN_sub(test, p, BN_value_one()) || |
| 334 |
!BN_div(r0, NULL, test, q, ctx)) { |
| 335 |
goto err; |
| 336 |
} |
| 337 |
|
| 338 |
if (!BN_set_word(test, h) || |
| 339 |
!BN_MONT_CTX_set(mont, p, ctx)) { |
| 340 |
goto err; |
| 341 |
} |
| 342 |
|
| 343 |
for (;;) { |
| 344 |
/* g=test^r0%p */ |
| 345 |
if (!BN_mod_exp_mont(g, test, r0, p, ctx, mont)) { |
| 346 |
goto err; |
| 347 |
} |
| 348 |
if (!BN_is_one(g)) { |
| 349 |
break; |
| 350 |
} |
| 351 |
if (!BN_add(test, test, BN_value_one())) { |
| 352 |
goto err; |
| 353 |
} |
| 354 |
h++; |
| 355 |
} |
| 356 |
|
| 357 |
if (!BN_GENCB_call(cb, 3, 1)) { |
| 358 |
goto err; |
| 359 |
} |
| 360 |
|
| 361 |
ok = 1; |
| 362 |
|
| 363 |
err: |
| 364 |
if (ok) { |
| 365 |
BN_free(dsa->p); |
| 366 |
BN_free(dsa->q); |
| 367 |
BN_free(dsa->g); |
| 368 |
dsa->p = BN_dup(p); |
| 369 |
dsa->q = BN_dup(q); |
| 370 |
dsa->g = BN_dup(g); |
| 371 |
if (dsa->p == NULL || dsa->q == NULL || dsa->g == NULL) { |
| 372 |
ok = 0; |
| 373 |
goto err; |
| 374 |
} |
| 375 |
if (out_counter != NULL) { |
| 376 |
*out_counter = counter; |
| 377 |
} |
| 378 |
if (out_h != NULL) { |
| 379 |
*out_h = h; |
| 380 |
} |
| 381 |
} |
| 382 |
|
| 383 |
if (ctx) { |
| 384 |
BN_CTX_end(ctx); |
| 385 |
BN_CTX_free(ctx); |
| 386 |
} |
| 387 |
|
| 388 |
BN_MONT_CTX_free(mont); |
| 389 |
|
| 390 |
return ok; |
| 391 |
} |
| 392 |
|
| 393 |
DSA *DSAparams_dup(const DSA *dsa) { |
| 394 |
DSA *ret = DSA_new(); |
| 395 |
if (ret == NULL) { |
| 396 |
return NULL; |
| 397 |
} |
| 398 |
ret->p = BN_dup(dsa->p); |
| 399 |
ret->q = BN_dup(dsa->q); |
| 400 |
ret->g = BN_dup(dsa->g); |
| 401 |
if (ret->p == NULL || ret->q == NULL || ret->g == NULL) { |
| 402 |
DSA_free(ret); |
| 403 |
return NULL; |
| 404 |
} |
| 405 |
return ret; |
| 406 |
} |
| 407 |
|
| 408 |
int DSA_generate_key(DSA *dsa) { |
| 409 |
int ok = 0; |
| 410 |
BN_CTX *ctx = NULL; |
| 411 |
BIGNUM *pub_key = NULL, *priv_key = NULL; |
| 412 |
BIGNUM prk; |
| 413 |
|
| 414 |
ctx = BN_CTX_new(); |
| 415 |
if (ctx == NULL) { |
| 416 |
goto err; |
| 417 |
} |
| 418 |
|
| 419 |
priv_key = dsa->priv_key; |
| 420 |
if (priv_key == NULL) { |
| 421 |
priv_key = BN_new(); |
| 422 |
if (priv_key == NULL) { |
| 423 |
goto err; |
| 424 |
} |
| 425 |
} |
| 426 |
|
| 427 |
do { |
| 428 |
if (!BN_rand_range(priv_key, dsa->q)) { |
| 429 |
goto err; |
| 430 |
} |
| 431 |
} while (BN_is_zero(priv_key)); |
| 432 |
|
| 433 |
pub_key = dsa->pub_key; |
| 434 |
if (pub_key == NULL) { |
| 435 |
pub_key = BN_new(); |
| 436 |
if (pub_key == NULL) { |
| 437 |
goto err; |
| 438 |
} |
| 439 |
} |
| 440 |
|
| 441 |
BN_init(&prk); |
| 442 |
BN_with_flags(&prk, priv_key, BN_FLG_CONSTTIME); |
| 443 |
|
| 444 |
if (!BN_mod_exp(pub_key, dsa->g, &prk, dsa->p, ctx)) { |
| 445 |
goto err; |
| 446 |
} |
| 447 |
|
| 448 |
dsa->priv_key = priv_key; |
| 449 |
dsa->pub_key = pub_key; |
| 450 |
ok = 1; |
| 451 |
|
| 452 |
err: |
| 453 |
if (dsa->pub_key == NULL) { |
| 454 |
BN_free(pub_key); |
| 455 |
} |
| 456 |
if (dsa->priv_key == NULL) { |
| 457 |
BN_free(priv_key); |
| 458 |
} |
| 459 |
BN_CTX_free(ctx); |
| 460 |
|
| 461 |
return ok; |
| 462 |
} |
| 463 |
|
| 464 |
DSA_SIG *DSA_SIG_new(void) { |
| 465 |
DSA_SIG *sig; |
| 466 |
sig = OPENSSL_malloc(sizeof(DSA_SIG)); |
| 467 |
if (!sig) { |
| 468 |
return NULL; |
| 469 |
} |
| 470 |
sig->r = NULL; |
| 471 |
sig->s = NULL; |
| 472 |
return sig; |
| 473 |
} |
| 474 |
|
| 475 |
void DSA_SIG_free(DSA_SIG *sig) { |
| 476 |
if (!sig) { |
| 477 |
return; |
| 478 |
} |
| 479 |
|
| 480 |
BN_free(sig->r); |
| 481 |
BN_free(sig->s); |
| 482 |
OPENSSL_free(sig); |
| 483 |
} |
| 484 |
|
| 485 |
DSA_SIG *DSA_do_sign(const uint8_t *digest, size_t digest_len, DSA *dsa) { |
| 486 |
BIGNUM *kinv = NULL, *r = NULL, *s = NULL; |
| 487 |
BIGNUM m; |
| 488 |
BIGNUM xr; |
| 489 |
BN_CTX *ctx = NULL; |
| 490 |
int reason = ERR_R_BN_LIB; |
| 491 |
DSA_SIG *ret = NULL; |
| 492 |
int noredo = 0; |
| 493 |
|
| 494 |
BN_init(&m); |
| 495 |
BN_init(&xr); |
| 496 |
|
| 497 |
if (!dsa->p || !dsa->q || !dsa->g) { |
| 498 |
reason = DSA_R_MISSING_PARAMETERS; |
| 499 |
goto err; |
| 500 |
} |
| 501 |
|
| 502 |
s = BN_new(); |
| 503 |
if (s == NULL) { |
| 504 |
goto err; |
| 505 |
} |
| 506 |
ctx = BN_CTX_new(); |
| 507 |
if (ctx == NULL) { |
| 508 |
goto err; |
| 509 |
} |
| 510 |
|
| 511 |
redo: |
| 512 |
if (dsa->kinv == NULL || dsa->r == NULL) { |
| 513 |
if (!DSA_sign_setup(dsa, ctx, &kinv, &r)) { |
| 514 |
goto err; |
| 515 |
} |
| 516 |
} else { |
| 517 |
kinv = dsa->kinv; |
| 518 |
dsa->kinv = NULL; |
| 519 |
r = dsa->r; |
| 520 |
dsa->r = NULL; |
| 521 |
noredo = 1; |
| 522 |
} |
| 523 |
|
| 524 |
if (digest_len > BN_num_bytes(dsa->q)) { |
| 525 |
/* if the digest length is greater than the size of q use the |
| 526 |
* BN_num_bits(dsa->q) leftmost bits of the digest, see |
| 527 |
* fips 186-3, 4.2 */ |
| 528 |
digest_len = BN_num_bytes(dsa->q); |
| 529 |
} |
| 530 |
|
| 531 |
if (BN_bin2bn(digest, digest_len, &m) == NULL) { |
| 532 |
goto err; |
| 533 |
} |
| 534 |
|
| 535 |
/* Compute s = inv(k) (m + xr) mod q */ |
| 536 |
if (!BN_mod_mul(&xr, dsa->priv_key, r, dsa->q, ctx)) { |
| 537 |
goto err; /* s = xr */ |
| 538 |
} |
| 539 |
if (!BN_add(s, &xr, &m)) { |
| 540 |
goto err; /* s = m + xr */ |
| 541 |
} |
| 542 |
if (BN_cmp(s, dsa->q) > 0) { |
| 543 |
if (!BN_sub(s, s, dsa->q)) { |
| 544 |
goto err; |
| 545 |
} |
| 546 |
} |
| 547 |
if (!BN_mod_mul(s, s, kinv, dsa->q, ctx)) { |
| 548 |
goto err; |
| 549 |
} |
| 550 |
|
| 551 |
/* Redo if r or s is zero as required by FIPS 186-3: this is |
| 552 |
* very unlikely. */ |
| 553 |
if (BN_is_zero(r) || BN_is_zero(s)) { |
| 554 |
if (noredo) { |
| 555 |
reason = DSA_R_NEED_NEW_SETUP_VALUES; |
| 556 |
goto err; |
| 557 |
} |
| 558 |
goto redo; |
| 559 |
} |
| 560 |
ret = DSA_SIG_new(); |
| 561 |
if (ret == NULL) { |
| 562 |
goto err; |
| 563 |
} |
| 564 |
ret->r = r; |
| 565 |
ret->s = s; |
| 566 |
|
| 567 |
err: |
| 568 |
if (ret == NULL) { |
| 569 |
OPENSSL_PUT_ERROR(DSA, reason); |
| 570 |
BN_free(r); |
| 571 |
BN_free(s); |
| 572 |
} |
| 573 |
BN_CTX_free(ctx); |
| 574 |
BN_clear_free(&m); |
| 575 |
BN_clear_free(&xr); |
| 576 |
BN_clear_free(kinv); |
| 577 |
|
| 578 |
return ret; |
| 579 |
} |
| 580 |
|
| 581 |
int DSA_do_verify(const uint8_t *digest, size_t digest_len, DSA_SIG *sig, |
| 582 |
const DSA *dsa) { |
| 583 |
int valid; |
| 584 |
if (!DSA_do_check_signature(&valid, digest, digest_len, sig, dsa)) { |
| 585 |
return -1; |
| 586 |
} |
| 587 |
return valid; |
| 588 |
} |
| 589 |
|
| 590 |
int DSA_do_check_signature(int *out_valid, const uint8_t *digest, |
| 591 |
size_t digest_len, DSA_SIG *sig, const DSA *dsa) { |
| 592 |
BN_CTX *ctx; |
| 593 |
BIGNUM u1, u2, t1; |
| 594 |
int ret = 0; |
| 595 |
unsigned i; |
| 596 |
|
| 597 |
*out_valid = 0; |
| 598 |
|
| 599 |
if (!dsa->p || !dsa->q || !dsa->g) { |
| 600 |
OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS); |
| 601 |
return 0; |
| 602 |
} |
| 603 |
|
| 604 |
i = BN_num_bits(dsa->q); |
| 605 |
/* fips 186-3 allows only different sizes for q */ |
| 606 |
if (i != 160 && i != 224 && i != 256) { |
| 607 |
OPENSSL_PUT_ERROR(DSA, DSA_R_BAD_Q_VALUE); |
| 608 |
return 0; |
| 609 |
} |
| 610 |
|
| 611 |
if (BN_num_bits(dsa->p) > OPENSSL_DSA_MAX_MODULUS_BITS) { |
| 612 |
OPENSSL_PUT_ERROR(DSA, DSA_R_MODULUS_TOO_LARGE); |
| 613 |
return 0; |
| 614 |
} |
| 615 |
|
| 616 |
BN_init(&u1); |
| 617 |
BN_init(&u2); |
| 618 |
BN_init(&t1); |
| 619 |
|
| 620 |
ctx = BN_CTX_new(); |
| 621 |
if (ctx == NULL) { |
| 622 |
goto err; |
| 623 |
} |
| 624 |
|
| 625 |
if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || |
| 626 |
BN_ucmp(sig->r, dsa->q) >= 0) { |
| 627 |
ret = 1; |
| 628 |
goto err; |
| 629 |
} |
| 630 |
if (BN_is_zero(sig->s) || BN_is_negative(sig->s) || |
| 631 |
BN_ucmp(sig->s, dsa->q) >= 0) { |
| 632 |
ret = 1; |
| 633 |
goto err; |
| 634 |
} |
| 635 |
|
| 636 |
/* Calculate W = inv(S) mod Q |
| 637 |
* save W in u2 */ |
| 638 |
if (BN_mod_inverse(&u2, sig->s, dsa->q, ctx) == NULL) { |
| 639 |
goto err; |
| 640 |
} |
| 641 |
|
| 642 |
/* save M in u1 */ |
| 643 |
if (digest_len > (i >> 3)) { |
| 644 |
/* if the digest length is greater than the size of q use the |
| 645 |
* BN_num_bits(dsa->q) leftmost bits of the digest, see |
| 646 |
* fips 186-3, 4.2 */ |
| 647 |
digest_len = (i >> 3); |
| 648 |
} |
| 649 |
|
| 650 |
if (BN_bin2bn(digest, digest_len, &u1) == NULL) { |
| 651 |
goto err; |
| 652 |
} |
| 653 |
|
| 654 |
/* u1 = M * w mod q */ |
| 655 |
if (!BN_mod_mul(&u1, &u1, &u2, dsa->q, ctx)) { |
| 656 |
goto err; |
| 657 |
} |
| 658 |
|
| 659 |
/* u2 = r * w mod q */ |
| 660 |
if (!BN_mod_mul(&u2, sig->r, &u2, dsa->q, ctx)) { |
| 661 |
goto err; |
| 662 |
} |
| 663 |
|
| 664 |
if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p, |
| 665 |
(CRYPTO_MUTEX *)&dsa->method_mont_p_lock, dsa->p, |
| 666 |
ctx)) { |
| 667 |
goto err; |
| 668 |
} |
| 669 |
|
| 670 |
if (!BN_mod_exp2_mont(&t1, dsa->g, &u1, dsa->pub_key, &u2, dsa->p, ctx, |
| 671 |
dsa->method_mont_p)) { |
| 672 |
goto err; |
| 673 |
} |
| 674 |
|
| 675 |
/* BN_copy(&u1,&t1); */ |
| 676 |
/* let u1 = u1 mod q */ |
| 677 |
if (!BN_mod(&u1, &t1, dsa->q, ctx)) { |
| 678 |
goto err; |
| 679 |
} |
| 680 |
|
| 681 |
/* V is now in u1. If the signature is correct, it will be |
| 682 |
* equal to R. */ |
| 683 |
*out_valid = BN_ucmp(&u1, sig->r) == 0; |
| 684 |
ret = 1; |
| 685 |
|
| 686 |
err: |
| 687 |
if (ret != 1) { |
| 688 |
OPENSSL_PUT_ERROR(DSA, ERR_R_BN_LIB); |
| 689 |
} |
| 690 |
BN_CTX_free(ctx); |
| 691 |
BN_free(&u1); |
| 692 |
BN_free(&u2); |
| 693 |
BN_free(&t1); |
| 694 |
|
| 695 |
return ret; |
| 696 |
} |
| 697 |
|
| 698 |
int DSA_sign(int type, const uint8_t *digest, size_t digest_len, |
| 699 |
uint8_t *out_sig, unsigned int *out_siglen, DSA *dsa) { |
| 700 |
DSA_SIG *s; |
| 701 |
|
| 702 |
s = DSA_do_sign(digest, digest_len, dsa); |
| 703 |
if (s == NULL) { |
| 704 |
*out_siglen = 0; |
| 705 |
return 0; |
| 706 |
} |
| 707 |
|
| 708 |
*out_siglen = i2d_DSA_SIG(s, &out_sig); |
| 709 |
DSA_SIG_free(s); |
| 710 |
return 1; |
| 711 |
} |
| 712 |
|
| 713 |
int DSA_verify(int type, const uint8_t *digest, size_t digest_len, |
| 714 |
const uint8_t *sig, size_t sig_len, const DSA *dsa) { |
| 715 |
int valid; |
| 716 |
if (!DSA_check_signature(&valid, digest, digest_len, sig, sig_len, dsa)) { |
| 717 |
return -1; |
| 718 |
} |
| 719 |
return valid; |
| 720 |
} |
| 721 |
|
| 722 |
int DSA_check_signature(int *out_valid, const uint8_t *digest, |
| 723 |
size_t digest_len, const uint8_t *sig, size_t sig_len, |
| 724 |
const DSA *dsa) { |
| 725 |
DSA_SIG *s = NULL; |
| 726 |
int ret = 0; |
| 727 |
uint8_t *der = NULL; |
| 728 |
|
| 729 |
s = DSA_SIG_new(); |
| 730 |
if (s == NULL) { |
| 731 |
goto err; |
| 732 |
} |
| 733 |
|
| 734 |
const uint8_t *sigp = sig; |
| 735 |
if (d2i_DSA_SIG(&s, &sigp, sig_len) == NULL || sigp != sig + sig_len) { |
| 736 |
goto err; |
| 737 |
} |
| 738 |
|
| 739 |
/* Ensure that the signature uses DER and doesn't have trailing garbage. */ |
| 740 |
int der_len = i2d_DSA_SIG(s, &der); |
| 741 |
if (der_len < 0 || (size_t)der_len != sig_len || memcmp(sig, der, sig_len)) { |
| 742 |
goto err; |
| 743 |
} |
| 744 |
|
| 745 |
ret = DSA_do_check_signature(out_valid, digest, digest_len, s, dsa); |
| 746 |
|
| 747 |
err: |
| 748 |
OPENSSL_free(der); |
| 749 |
DSA_SIG_free(s); |
| 750 |
return ret; |
| 751 |
} |
| 752 |
|
| 753 |
/* der_len_len returns the number of bytes needed to represent a length of |len| |
| 754 |
* in DER. */ |
| 755 |
static size_t der_len_len(size_t len) { |
| 756 |
if (len < 0x80) { |
| 757 |
return 1; |
| 758 |
} |
| 759 |
size_t ret = 1; |
| 760 |
while (len > 0) { |
| 761 |
ret++; |
| 762 |
len >>= 8; |
| 763 |
} |
| 764 |
return ret; |
| 765 |
} |
| 766 |
|
| 767 |
int DSA_size(const DSA *dsa) { |
| 768 |
size_t order_len = BN_num_bytes(dsa->q); |
| 769 |
/* Compute the maximum length of an |order_len| byte integer. Defensively |
| 770 |
* assume that the leading 0x00 is included. */ |
| 771 |
size_t integer_len = 1 /* tag */ + der_len_len(order_len + 1) + 1 + order_len; |
| 772 |
if (integer_len < order_len) { |
| 773 |
return 0; |
| 774 |
} |
| 775 |
/* A DSA signature is two INTEGERs. */ |
| 776 |
size_t value_len = 2 * integer_len; |
| 777 |
if (value_len < integer_len) { |
| 778 |
return 0; |
| 779 |
} |
| 780 |
/* Add the header. */ |
| 781 |
size_t ret = 1 /* tag */ + der_len_len(value_len) + value_len; |
| 782 |
if (ret < value_len) { |
| 783 |
return 0; |
| 784 |
} |
| 785 |
return ret; |
| 786 |
} |
| 787 |
|
| 788 |
int DSA_sign_setup(const DSA *dsa, BN_CTX *ctx_in, BIGNUM **out_kinv, |
| 789 |
BIGNUM **out_r) { |
| 790 |
BN_CTX *ctx; |
| 791 |
BIGNUM k, kq, *K, *kinv = NULL, *r = NULL; |
| 792 |
int ret = 0; |
| 793 |
|
| 794 |
if (!dsa->p || !dsa->q || !dsa->g) { |
| 795 |
OPENSSL_PUT_ERROR(DSA, DSA_R_MISSING_PARAMETERS); |
| 796 |
return 0; |
| 797 |
} |
| 798 |
|
| 799 |
BN_init(&k); |
| 800 |
BN_init(&kq); |
| 801 |
|
| 802 |
ctx = ctx_in; |
| 803 |
if (ctx == NULL) { |
| 804 |
ctx = BN_CTX_new(); |
| 805 |
if (ctx == NULL) { |
| 806 |
goto err; |
| 807 |
} |
| 808 |
} |
| 809 |
|
| 810 |
r = BN_new(); |
| 811 |
if (r == NULL) { |
| 812 |
goto err; |
| 813 |
} |
| 814 |
|
| 815 |
/* Get random k */ |
| 816 |
do { |
| 817 |
if (!BN_rand_range(&k, dsa->q)) { |
| 818 |
goto err; |
| 819 |
} |
| 820 |
} while (BN_is_zero(&k)); |
| 821 |
|
| 822 |
BN_set_flags(&k, BN_FLG_CONSTTIME); |
| 823 |
|
| 824 |
if (!BN_MONT_CTX_set_locked((BN_MONT_CTX **)&dsa->method_mont_p, |
| 825 |
(CRYPTO_MUTEX *)&dsa->method_mont_p_lock, dsa->p, |
| 826 |
ctx)) { |
| 827 |
goto err; |
| 828 |
} |
| 829 |
|
| 830 |
/* Compute r = (g^k mod p) mod q */ |
| 831 |
if (!BN_copy(&kq, &k)) { |
| 832 |
goto err; |
| 833 |
} |
| 834 |
|
| 835 |
/* We do not want timing information to leak the length of k, |
| 836 |
* so we compute g^k using an equivalent exponent of fixed length. |
| 837 |
* |
| 838 |
* (This is a kludge that we need because the BN_mod_exp_mont() |
| 839 |
* does not let us specify the desired timing behaviour.) */ |
| 840 |
|
| 841 |
if (!BN_add(&kq, &kq, dsa->q)) { |
| 842 |
goto err; |
| 843 |
} |
| 844 |
if (BN_num_bits(&kq) <= BN_num_bits(dsa->q) && !BN_add(&kq, &kq, dsa->q)) { |
| 845 |
goto err; |
| 846 |
} |
| 847 |
|
| 848 |
BN_set_flags(&kq, BN_FLG_CONSTTIME); |
| 849 |
K = &kq; |
| 850 |
|
| 851 |
if (!BN_mod_exp_mont(r, dsa->g, K, dsa->p, ctx, dsa->method_mont_p)) { |
| 852 |
goto err; |
| 853 |
} |
| 854 |
if (!BN_mod(r, r, dsa->q, ctx)) { |
| 855 |
goto err; |
| 856 |
} |
| 857 |
|
| 858 |
/* Compute part of 's = inv(k) (m + xr) mod q' */ |
| 859 |
kinv = BN_mod_inverse(NULL, &k, dsa->q, ctx); |
| 860 |
if (kinv == NULL) { |
| 861 |
goto err; |
| 862 |
} |
| 863 |
|
| 864 |
BN_clear_free(*out_kinv); |
| 865 |
*out_kinv = kinv; |
| 866 |
kinv = NULL; |
| 867 |
BN_clear_free(*out_r); |
| 868 |
*out_r = r; |
| 869 |
ret = 1; |
| 870 |
|
| 871 |
err: |
| 872 |
if (!ret) { |
| 873 |
OPENSSL_PUT_ERROR(DSA, ERR_R_BN_LIB); |
| 874 |
if (r != NULL) { |
| 875 |
BN_clear_free(r); |
| 876 |
} |
| 877 |
} |
| 878 |
|
| 879 |
if (ctx_in == NULL) { |
| 880 |
BN_CTX_free(ctx); |
| 881 |
} |
| 882 |
BN_clear_free(&k); |
| 883 |
BN_clear_free(&kq); |
| 884 |
return ret; |
| 885 |
} |
| 886 |
|
| 887 |
int DSA_get_ex_new_index(long argl, void *argp, CRYPTO_EX_unused *unused, |
| 888 |
CRYPTO_EX_dup *dup_func, CRYPTO_EX_free *free_func) { |
| 889 |
int index; |
| 890 |
if (!CRYPTO_get_ex_new_index(&g_ex_data_class, &index, argl, argp, dup_func, |
| 891 |
free_func)) { |
| 892 |
return -1; |
| 893 |
} |
| 894 |
return index; |
| 895 |
} |
| 896 |
|
| 897 |
int DSA_set_ex_data(DSA *d, int idx, void *arg) { |
| 898 |
return CRYPTO_set_ex_data(&d->ex_data, idx, arg); |
| 899 |
} |
| 900 |
|
| 901 |
void *DSA_get_ex_data(const DSA *d, int idx) { |
| 902 |
return CRYPTO_get_ex_data(&d->ex_data, idx); |
| 903 |
} |
| 904 |
|
| 905 |
DH *DSA_dup_DH(const DSA *r) { |
| 906 |
DH *ret = NULL; |
| 907 |
|
| 908 |
if (r == NULL) { |
| 909 |
goto err; |
| 910 |
} |
| 911 |
ret = DH_new(); |
| 912 |
if (ret == NULL) { |
| 913 |
goto err; |
| 914 |
} |
| 915 |
if (r->q != NULL) { |
| 916 |
ret->priv_length = BN_num_bits(r->q); |
| 917 |
if ((ret->q = BN_dup(r->q)) == NULL) { |
| 918 |
goto err; |
| 919 |
} |
| 920 |
} |
| 921 |
if ((r->p != NULL && (ret->p = BN_dup(r->p)) == NULL) || |
| 922 |
(r->g != NULL && (ret->g = BN_dup(r->g)) == NULL) || |
| 923 |
(r->pub_key != NULL && (ret->pub_key = BN_dup(r->pub_key)) == NULL) || |
| 924 |
(r->priv_key != NULL && (ret->priv_key = BN_dup(r->priv_key)) == NULL)) { |
| 925 |
goto err; |
| 926 |
} |
| 927 |
|
| 928 |
return ret; |
| 929 |
|
| 930 |
err: |
| 931 |
DH_free(ret); |
| 932 |
return NULL; |
| 933 |
} |