dh.c (14931B)
1 /* This Source Code Form is subject to the terms of the Mozilla Public 2 * License, v. 2.0. If a copy of the MPL was not distributed with this 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 4 5 /* 6 * Diffie-Hellman parameter generation, key generation, and secret derivation. 7 * KEA secret generation and verification. 8 */ 9 #ifdef FREEBL_NO_DEPEND 10 #include "stubs.h" 11 #endif 12 13 #include "prerr.h" 14 #include "secerr.h" 15 16 #include "blapi.h" 17 #include "blapii.h" 18 #include "secitem.h" 19 #include "mpi.h" 20 #include "secmpi.h" 21 22 #define KEA_DERIVED_SECRET_LEN 128 23 24 /* Lengths are in bytes. */ 25 static unsigned int 26 dh_GetSecretKeyLen(unsigned int primeLen) 27 { 28 /* Based on Table 2 in NIST SP 800-57. */ 29 if (primeLen >= 1920) { /* 15360 bits */ 30 return 64; /* 512 bits */ 31 } 32 if (primeLen >= 960) { /* 7680 bits */ 33 return 48; /* 384 bits */ 34 } 35 if (primeLen >= 384) { /* 3072 bits */ 36 return 32; /* 256 bits */ 37 } 38 if (primeLen >= 256) { /* 2048 bits */ 39 return 28; /* 224 bits */ 40 } 41 return 20; /* 160 bits */ 42 } 43 44 SECStatus 45 DH_GenParam(int primeLen, DHParams **params) 46 { 47 PLArenaPool *arena; 48 DHParams *dhparams; 49 unsigned char *ab = NULL; 50 mp_int p, q, a, h, psub1, test; 51 mp_err err = MP_OKAY; 52 SECStatus rv = SECSuccess; 53 if (!params || primeLen < 0) { 54 PORT_SetError(SEC_ERROR_INVALID_ARGS); 55 return SECFailure; 56 } 57 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE); 58 if (!arena) { 59 PORT_SetError(SEC_ERROR_NO_MEMORY); 60 return SECFailure; 61 } 62 dhparams = (DHParams *)PORT_ArenaZAlloc(arena, sizeof(DHParams)); 63 if (!dhparams) { 64 PORT_SetError(SEC_ERROR_NO_MEMORY); 65 PORT_FreeArena(arena, PR_TRUE); 66 return SECFailure; 67 } 68 dhparams->arena = arena; 69 MP_DIGITS(&p) = 0; 70 MP_DIGITS(&q) = 0; 71 MP_DIGITS(&a) = 0; 72 MP_DIGITS(&h) = 0; 73 MP_DIGITS(&psub1) = 0; 74 MP_DIGITS(&test) = 0; 75 CHECK_MPI_OK(mp_init(&p)); 76 CHECK_MPI_OK(mp_init(&q)); 77 CHECK_MPI_OK(mp_init(&a)); 78 CHECK_MPI_OK(mp_init(&h)); 79 CHECK_MPI_OK(mp_init(&psub1)); 80 CHECK_MPI_OK(mp_init(&test)); 81 /* generate prime with MPI, uses Miller-Rabin to generate safe prime. */ 82 CHECK_SEC_OK(generate_prime(&p, primeLen)); 83 /* construct Sophie-Germain prime q = (p-1)/2. */ 84 CHECK_MPI_OK(mp_sub_d(&p, 1, &psub1)); 85 CHECK_MPI_OK(mp_div_2(&psub1, &q)); 86 /* construct a generator from the prime. */ 87 ab = PORT_Alloc(primeLen); 88 if (!ab) { 89 PORT_SetError(SEC_ERROR_NO_MEMORY); 90 rv = SECFailure; 91 goto cleanup; 92 } 93 /* generate a candidate number a in p's field */ 94 CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(ab, primeLen)); 95 CHECK_MPI_OK(mp_read_unsigned_octets(&a, ab, primeLen)); 96 /* force a < p (note that quot(a/p) <= 1) */ 97 if (mp_cmp(&a, &p) > 0) 98 CHECK_MPI_OK(mp_sub(&a, &p, &a)); 99 do { 100 /* check that a is in the range [2..p-1] */ 101 if (mp_cmp_d(&a, 2) < 0 || mp_cmp(&a, &psub1) >= 0) { 102 /* a is outside of the allowed range. Set a=3 and keep going. */ 103 mp_set(&a, 3); 104 } 105 /* if a**q mod p != 1 then a is a generator */ 106 CHECK_MPI_OK(mp_exptmod(&a, &q, &p, &test)); 107 if (mp_cmp_d(&test, 1) != 0) 108 break; 109 /* increment the candidate and try again. */ 110 CHECK_MPI_OK(mp_add_d(&a, 1, &a)); 111 } while (PR_TRUE); 112 MPINT_TO_SECITEM(&p, &dhparams->prime, arena); 113 MPINT_TO_SECITEM(&a, &dhparams->base, arena); 114 *params = dhparams; 115 cleanup: 116 mp_clear(&p); 117 mp_clear(&q); 118 mp_clear(&a); 119 mp_clear(&h); 120 mp_clear(&psub1); 121 mp_clear(&test); 122 if (ab) { 123 PORT_ZFree(ab, primeLen); 124 } 125 if (err) { 126 MP_TO_SEC_ERROR(err); 127 rv = SECFailure; 128 } 129 if (rv != SECSuccess) { 130 PORT_FreeArena(arena, PR_TRUE); 131 } 132 return rv; 133 } 134 135 SECStatus 136 DH_NewKey(DHParams *params, DHPrivateKey **privKey) 137 { 138 PLArenaPool *arena; 139 DHPrivateKey *key; 140 mp_int g, xa, p, Ya; 141 mp_err err = MP_OKAY; 142 SECStatus rv = SECSuccess; 143 if (!params || !privKey) { 144 PORT_SetError(SEC_ERROR_INVALID_ARGS); 145 return SECFailure; 146 } 147 arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE); 148 if (!arena) { 149 PORT_SetError(SEC_ERROR_NO_MEMORY); 150 return SECFailure; 151 } 152 key = (DHPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DHPrivateKey)); 153 if (!key) { 154 PORT_SetError(SEC_ERROR_NO_MEMORY); 155 PORT_FreeArena(arena, PR_TRUE); 156 return SECFailure; 157 } 158 key->arena = arena; 159 MP_DIGITS(&g) = 0; 160 MP_DIGITS(&xa) = 0; 161 MP_DIGITS(&p) = 0; 162 MP_DIGITS(&Ya) = 0; 163 CHECK_MPI_OK(mp_init(&g)); 164 CHECK_MPI_OK(mp_init(&xa)); 165 CHECK_MPI_OK(mp_init(&p)); 166 CHECK_MPI_OK(mp_init(&Ya)); 167 /* Set private key's p */ 168 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->prime, ¶ms->prime)); 169 SECITEM_TO_MPINT(key->prime, &p); 170 /* Set private key's g */ 171 CHECK_SEC_OK(SECITEM_CopyItem(arena, &key->base, ¶ms->base)); 172 SECITEM_TO_MPINT(key->base, &g); 173 /* Generate private key xa */ 174 SECITEM_AllocItem(arena, &key->privateValue, 175 dh_GetSecretKeyLen(params->prime.len)); 176 CHECK_SEC_OK(RNG_GenerateGlobalRandomBytes(key->privateValue.data, 177 key->privateValue.len)); 178 SECITEM_TO_MPINT(key->privateValue, &xa); 179 /* xa < p */ 180 CHECK_MPI_OK(mp_mod(&xa, &p, &xa)); 181 /* Compute public key Ya = g ** xa mod p */ 182 #ifndef UNSAFE_FUZZER_MODE 183 CHECK_MPI_OK(mp_exptmod(&g, &xa, &p, &Ya)); 184 #endif 185 MPINT_TO_SECITEM(&Ya, &key->publicValue, key->arena); 186 *privKey = key; 187 cleanup: 188 mp_clear(&g); 189 mp_clear(&xa); 190 mp_clear(&p); 191 mp_clear(&Ya); 192 if (err) { 193 MP_TO_SEC_ERROR(err); 194 rv = SECFailure; 195 } 196 if (rv) { 197 *privKey = NULL; 198 PORT_FreeArena(arena, PR_TRUE); 199 } 200 return rv; 201 } 202 203 SECStatus 204 DH_Derive(SECItem *publicValue, 205 SECItem *prime, 206 SECItem *privateValue, 207 SECItem *derivedSecret, 208 unsigned int outBytes) 209 { 210 mp_int p, Xa, Yb, ZZ, psub1; 211 mp_err err = MP_OKAY; 212 unsigned int len = 0; 213 unsigned int nb; 214 unsigned char *secret = NULL; 215 if (!publicValue || !publicValue->len || !prime || !prime->len || 216 !privateValue || !privateValue->len || !derivedSecret) { 217 PORT_SetError(SEC_ERROR_INVALID_ARGS); 218 return SECFailure; 219 } 220 memset(derivedSecret, 0, sizeof *derivedSecret); 221 MP_DIGITS(&p) = 0; 222 MP_DIGITS(&Xa) = 0; 223 MP_DIGITS(&Yb) = 0; 224 MP_DIGITS(&ZZ) = 0; 225 MP_DIGITS(&psub1) = 0; 226 CHECK_MPI_OK(mp_init(&p)); 227 CHECK_MPI_OK(mp_init(&Xa)); 228 CHECK_MPI_OK(mp_init(&Yb)); 229 CHECK_MPI_OK(mp_init(&ZZ)); 230 CHECK_MPI_OK(mp_init(&psub1)); 231 SECITEM_TO_MPINT(*publicValue, &Yb); 232 SECITEM_TO_MPINT(*privateValue, &Xa); 233 SECITEM_TO_MPINT(*prime, &p); 234 CHECK_MPI_OK(mp_sub_d(&p, 1, &psub1)); 235 236 /* We assume that the modulus, p, is a safe prime. That is, p = 2q+1 where 237 * q is also a prime. Thus the orders of the subgroups are factors of 2q: 238 * namely 1, 2, q and 2q. 239 * 240 * We check that the peer's public value isn't zero (which isn't in the 241 * group), one (subgroup of order one) or p-1 (subgroup of order 2). We 242 * also check that the public value is less than p, to avoid being fooled 243 * by values like p+1 or 2*p-1. 244 * 245 * Thus we must be operating in the subgroup of size q or 2q. */ 246 if (mp_cmp_d(&Yb, 1) <= 0 || 247 mp_cmp(&Yb, &psub1) >= 0) { 248 err = MP_BADARG; 249 goto cleanup; 250 } 251 252 /* ZZ = (Yb)**Xa mod p */ 253 CHECK_MPI_OK(mp_exptmod(&Yb, &Xa, &p, &ZZ)); 254 /* number of bytes in the derived secret */ 255 len = mp_unsigned_octet_size(&ZZ); 256 if (len <= 0) { 257 err = MP_BADARG; 258 goto cleanup; 259 } 260 261 /* 262 * We check to make sure that ZZ is not equal to 0, 1 or -1 mod p. 263 * This helps guard against small subgroup attacks, since an attacker 264 * using a subgroup of size N will produce 0, 1 or -1 with probability 1/N. 265 * When the protocol is executed within a properly large subgroup, the 266 * probability of this result will be negligibly small. For example, 267 * with a safe prime of the form 2q+1, the probability will be 1/q. 268 * 269 * We return MP_BADARG because this is probably the result of a bad 270 * public value or a bad prime having been provided. 271 */ 272 if (mp_cmp_d(&ZZ, 0) == 0 || mp_cmp_d(&ZZ, 1) == 0 || 273 mp_cmp(&ZZ, &psub1) == 0) { 274 err = MP_BADARG; 275 goto cleanup; 276 } 277 278 /* allocate a buffer which can hold the entire derived secret. */ 279 secret = PORT_Alloc(len); 280 if (secret == NULL) { 281 err = MP_MEM; 282 goto cleanup; 283 } 284 /* grab the derived secret */ 285 err = mp_to_unsigned_octets(&ZZ, secret, len); 286 if (err >= 0) 287 err = MP_OKAY; 288 /* 289 ** if outBytes is 0 take all of the bytes from the derived secret. 290 ** if outBytes is not 0 take exactly outBytes from the derived secret, zero 291 ** pad at the beginning if necessary, and truncate beginning bytes 292 ** if necessary. 293 */ 294 if (outBytes > 0) 295 nb = outBytes; 296 else 297 nb = len; 298 if (SECITEM_AllocItem(NULL, derivedSecret, nb) == NULL) { 299 err = MP_MEM; 300 goto cleanup; 301 } 302 if (len < nb) { 303 unsigned int offset = nb - len; 304 memset(derivedSecret->data, 0, offset); 305 memcpy(derivedSecret->data + offset, secret, len); 306 } else { 307 memcpy(derivedSecret->data, secret + len - nb, nb); 308 } 309 cleanup: 310 mp_clear(&p); 311 mp_clear(&Xa); 312 mp_clear(&Yb); 313 mp_clear(&ZZ); 314 mp_clear(&psub1); 315 if (secret) { 316 /* free the buffer allocated for the full secret. */ 317 PORT_ZFree(secret, len); 318 } 319 if (err) { 320 MP_TO_SEC_ERROR(err); 321 if (derivedSecret->data) 322 PORT_ZFree(derivedSecret->data, derivedSecret->len); 323 return SECFailure; 324 } 325 return SECSuccess; 326 } 327 328 SECStatus 329 KEA_Derive(SECItem *prime, 330 SECItem *public1, 331 SECItem *public2, 332 SECItem *private1, 333 SECItem *private2, 334 SECItem *derivedSecret) 335 { 336 mp_int p, Y, R, r, x, t, u, w; 337 mp_err err; 338 unsigned char *secret = NULL; 339 unsigned int len = 0, offset; 340 if (!prime || !public1 || !public2 || !private1 || !private2 || 341 !derivedSecret) { 342 PORT_SetError(SEC_ERROR_INVALID_ARGS); 343 return SECFailure; 344 } 345 memset(derivedSecret, 0, sizeof *derivedSecret); 346 MP_DIGITS(&p) = 0; 347 MP_DIGITS(&Y) = 0; 348 MP_DIGITS(&R) = 0; 349 MP_DIGITS(&r) = 0; 350 MP_DIGITS(&x) = 0; 351 MP_DIGITS(&t) = 0; 352 MP_DIGITS(&u) = 0; 353 MP_DIGITS(&w) = 0; 354 CHECK_MPI_OK(mp_init(&p)); 355 CHECK_MPI_OK(mp_init(&Y)); 356 CHECK_MPI_OK(mp_init(&R)); 357 CHECK_MPI_OK(mp_init(&r)); 358 CHECK_MPI_OK(mp_init(&x)); 359 CHECK_MPI_OK(mp_init(&t)); 360 CHECK_MPI_OK(mp_init(&u)); 361 CHECK_MPI_OK(mp_init(&w)); 362 SECITEM_TO_MPINT(*prime, &p); 363 SECITEM_TO_MPINT(*public1, &Y); 364 SECITEM_TO_MPINT(*public2, &R); 365 SECITEM_TO_MPINT(*private1, &r); 366 SECITEM_TO_MPINT(*private2, &x); 367 /* t = DH(Y, r, p) = Y ** r mod p */ 368 CHECK_MPI_OK(mp_exptmod(&Y, &r, &p, &t)); 369 /* u = DH(R, x, p) = R ** x mod p */ 370 CHECK_MPI_OK(mp_exptmod(&R, &x, &p, &u)); 371 /* w = (t + u) mod p */ 372 CHECK_MPI_OK(mp_addmod(&t, &u, &p, &w)); 373 /* allocate a buffer for the full derived secret */ 374 len = mp_unsigned_octet_size(&w); 375 secret = PORT_Alloc(len); 376 if (secret == NULL) { 377 err = MP_MEM; 378 goto cleanup; 379 } 380 /* grab the secret */ 381 err = mp_to_unsigned_octets(&w, secret, len); 382 if (err > 0) 383 err = MP_OKAY; 384 /* allocate output buffer */ 385 if (SECITEM_AllocItem(NULL, derivedSecret, KEA_DERIVED_SECRET_LEN) == NULL) { 386 err = MP_MEM; 387 goto cleanup; 388 } 389 memset(derivedSecret->data, 0, derivedSecret->len); 390 /* copy in the 128 lsb of the secret */ 391 if (len >= KEA_DERIVED_SECRET_LEN) { 392 memcpy(derivedSecret->data, secret + (len - KEA_DERIVED_SECRET_LEN), 393 KEA_DERIVED_SECRET_LEN); 394 } else { 395 offset = KEA_DERIVED_SECRET_LEN - len; 396 memcpy(derivedSecret->data + offset, secret, len); 397 } 398 cleanup: 399 mp_clear(&p); 400 mp_clear(&Y); 401 mp_clear(&R); 402 mp_clear(&r); 403 mp_clear(&x); 404 mp_clear(&t); 405 mp_clear(&u); 406 mp_clear(&w); 407 if (secret) 408 PORT_ZFree(secret, len); 409 if (err) { 410 MP_TO_SEC_ERROR(err); 411 if (derivedSecret->data) 412 PORT_ZFree(derivedSecret->data, derivedSecret->len); 413 return SECFailure; 414 } 415 return SECSuccess; 416 } 417 418 /* Test counts based on the fact the prime and subprime 419 * were given to us */ 420 static int 421 dh_prime_testcount(int prime_length) 422 { 423 if (prime_length < 1024) { 424 return 50; 425 } else if (prime_length < 2048) { 426 return 40; 427 } else if (prime_length < 3072) { 428 return 56; 429 } 430 return 64; 431 } 432 433 PRBool 434 KEA_PrimeCheck(SECItem *prime) 435 { 436 mp_int p; 437 mp_err err = 0; 438 MP_DIGITS(&p) = 0; 439 CHECK_MPI_OK(mp_init(&p)); 440 SECITEM_TO_MPINT(*prime, &p); 441 CHECK_MPI_OK(mpp_pprime_secure(&p, dh_prime_testcount(prime->len))); 442 cleanup: 443 mp_clear(&p); 444 return err ? PR_FALSE : PR_TRUE; 445 } 446 447 PRBool 448 KEA_Verify(SECItem *Y, SECItem *prime, SECItem *subPrime) 449 { 450 mp_int p, q, y, r, psub1; 451 mp_err err; 452 int cmp = 1; /* default is false */ 453 if (!Y || !prime || !subPrime) { 454 PORT_SetError(SEC_ERROR_INVALID_ARGS); 455 return SECFailure; 456 } 457 MP_DIGITS(&p) = 0; 458 MP_DIGITS(&q) = 0; 459 MP_DIGITS(&y) = 0; 460 MP_DIGITS(&r) = 0; 461 MP_DIGITS(&psub1) = 0; 462 CHECK_MPI_OK(mp_init(&p)); 463 CHECK_MPI_OK(mp_init(&q)); 464 CHECK_MPI_OK(mp_init(&y)); 465 CHECK_MPI_OK(mp_init(&r)); 466 CHECK_MPI_OK(mp_init(&psub1)); 467 SECITEM_TO_MPINT(*prime, &p); 468 SECITEM_TO_MPINT(*subPrime, &q); 469 SECITEM_TO_MPINT(*Y, &y); 470 CHECK_MPI_OK(mp_sub_d(&p, 1, &psub1)); 471 /* 472 * We check that the public value isn't zero (which isn't in the 473 * group), one (subgroup of order one) or p-1 (subgroup of order 2). We 474 * also check that the public value is less than p, to avoid being fooled 475 * by values like p+1 or 2*p-1. 476 * This check is required by SP-800-56Ar3. It's also done in derive, 477 * but this is only called in various FIPS cases, so put it here to help 478 * reviewers find it. 479 */ 480 if (mp_cmp_d(&y, 1) <= 0 || 481 mp_cmp(&y, &psub1) >= 0) { 482 err = MP_BADARG; 483 goto cleanup; 484 } 485 /* compute r = y**q mod p */ 486 CHECK_MPI_OK(mp_exptmod(&y, &q, &p, &r)); 487 /* compare to 1 */ 488 cmp = mp_cmp_d(&r, 1); 489 cleanup: 490 mp_clear(&p); 491 mp_clear(&q); 492 mp_clear(&y); 493 mp_clear(&r); 494 mp_clear(&psub1); 495 if (err) { 496 MP_TO_SEC_ERROR(err); 497 return PR_FALSE; 498 } 499 return (cmp == 0) ? PR_TRUE : PR_FALSE; 500 }