1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/dh.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,412 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +/*
1.9 + * Diffie-Hellman parameter generation, key generation, and secret derivation.
1.10 + * KEA secret generation and verification.
1.11 + */
1.12 +#ifdef FREEBL_NO_DEPEND
1.13 +#include "stubs.h"
1.14 +#endif
1.15 +
1.16 +#include "prerr.h"
1.17 +#include "secerr.h"
1.18 +
1.19 +#include "blapi.h"
1.20 +#include "secitem.h"
1.21 +#include "mpi.h"
1.22 +#include "mpprime.h"
1.23 +#include "secmpi.h"
1.24 +
1.25 +#define KEA_DERIVED_SECRET_LEN 128
1.26 +
1.27 +/* Lengths are in bytes. */
1.28 +static unsigned int
1.29 +dh_GetSecretKeyLen(unsigned int primeLen)
1.30 +{
1.31 + /* Based on Table 2 in NIST SP 800-57. */
1.32 + if (primeLen >= 1920) { /* 15360 bits */
1.33 + return 64; /* 512 bits */
1.34 + }
1.35 + if (primeLen >= 960) { /* 7680 bits */
1.36 + return 48; /* 384 bits */
1.37 + }
1.38 + if (primeLen >= 384) { /* 3072 bits */
1.39 + return 32; /* 256 bits */
1.40 + }
1.41 + if (primeLen >= 256) { /* 2048 bits */
1.42 + return 28; /* 224 bits */
1.43 + }
1.44 + return 20; /* 160 bits */
1.45 +}
1.46 +
1.47 +SECStatus
1.48 +DH_GenParam(int primeLen, DHParams **params)
1.49 +{
1.50 + PLArenaPool *arena;
1.51 + DHParams *dhparams;
1.52 + unsigned char *pb = NULL;
1.53 + unsigned char *ab = NULL;
1.54 + unsigned long counter = 0;
1.55 + mp_int p, q, a, h, psub1, test;
1.56 + mp_err err = MP_OKAY;
1.57 + SECStatus rv = SECSuccess;
1.58 + if (!params || primeLen < 0) {
1.59 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.60 + return SECFailure;
1.61 + }
1.62 + arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
1.63 + if (!arena) {
1.64 + PORT_SetError(SEC_ERROR_NO_MEMORY);
1.65 + return SECFailure;
1.66 + }
1.67 + dhparams = (DHParams *)PORT_ArenaZAlloc(arena, sizeof(DHParams));
1.68 + if (!dhparams) {
1.69 + PORT_SetError(SEC_ERROR_NO_MEMORY);
1.70 + PORT_FreeArena(arena, PR_TRUE);
1.71 + return SECFailure;
1.72 + }
1.73 + dhparams->arena = arena;
1.74 + MP_DIGITS(&p) = 0;
1.75 + MP_DIGITS(&q) = 0;
1.76 + MP_DIGITS(&a) = 0;
1.77 + MP_DIGITS(&h) = 0;
1.78 + MP_DIGITS(&psub1) = 0;
1.79 + MP_DIGITS(&test) = 0;
1.80 + CHECK_MPI_OK( mp_init(&p) );
1.81 + CHECK_MPI_OK( mp_init(&q) );
1.82 + CHECK_MPI_OK( mp_init(&a) );
1.83 + CHECK_MPI_OK( mp_init(&h) );
1.84 + CHECK_MPI_OK( mp_init(&psub1) );
1.85 + CHECK_MPI_OK( mp_init(&test) );
1.86 + /* generate prime with MPI, uses Miller-Rabin to generate strong prime. */
1.87 + pb = PORT_Alloc(primeLen);
1.88 + CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(pb, primeLen) );
1.89 + pb[0] |= 0x80; /* set high-order bit */
1.90 + pb[primeLen-1] |= 0x01; /* set low-order bit */
1.91 + CHECK_MPI_OK( mp_read_unsigned_octets(&p, pb, primeLen) );
1.92 + CHECK_MPI_OK( mpp_make_prime(&p, primeLen * 8, PR_TRUE, &counter) );
1.93 + /* construct Sophie-Germain prime q = (p-1)/2. */
1.94 + CHECK_MPI_OK( mp_sub_d(&p, 1, &psub1) );
1.95 + CHECK_MPI_OK( mp_div_2(&psub1, &q) );
1.96 + /* construct a generator from the prime. */
1.97 + ab = PORT_Alloc(primeLen);
1.98 + /* generate a candidate number a in p's field */
1.99 + CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(ab, primeLen) );
1.100 + CHECK_MPI_OK( mp_read_unsigned_octets(&a, ab, primeLen) );
1.101 + /* force a < p (note that quot(a/p) <= 1) */
1.102 + if ( mp_cmp(&a, &p) > 0 )
1.103 + CHECK_MPI_OK( mp_sub(&a, &p, &a) );
1.104 + do {
1.105 + /* check that a is in the range [2..p-1] */
1.106 + if ( mp_cmp_d(&a, 2) < 0 || mp_cmp(&a, &psub1) >= 0) {
1.107 + /* a is outside of the allowed range. Set a=3 and keep going. */
1.108 + mp_set(&a, 3);
1.109 + }
1.110 + /* if a**q mod p != 1 then a is a generator */
1.111 + CHECK_MPI_OK( mp_exptmod(&a, &q, &p, &test) );
1.112 + if ( mp_cmp_d(&test, 1) != 0 )
1.113 + break;
1.114 + /* increment the candidate and try again. */
1.115 + CHECK_MPI_OK( mp_add_d(&a, 1, &a) );
1.116 + } while (PR_TRUE);
1.117 + MPINT_TO_SECITEM(&p, &dhparams->prime, arena);
1.118 + MPINT_TO_SECITEM(&a, &dhparams->base, arena);
1.119 + *params = dhparams;
1.120 +cleanup:
1.121 + mp_clear(&p);
1.122 + mp_clear(&q);
1.123 + mp_clear(&a);
1.124 + mp_clear(&h);
1.125 + mp_clear(&psub1);
1.126 + mp_clear(&test);
1.127 + if (pb) PORT_ZFree(pb, primeLen);
1.128 + if (ab) PORT_ZFree(ab, primeLen);
1.129 + if (err) {
1.130 + MP_TO_SEC_ERROR(err);
1.131 + rv = SECFailure;
1.132 + }
1.133 + if (rv)
1.134 + PORT_FreeArena(arena, PR_TRUE);
1.135 + return rv;
1.136 +}
1.137 +
1.138 +SECStatus
1.139 +DH_NewKey(DHParams *params, DHPrivateKey **privKey)
1.140 +{
1.141 + PLArenaPool *arena;
1.142 + DHPrivateKey *key;
1.143 + mp_int g, xa, p, Ya;
1.144 + mp_err err = MP_OKAY;
1.145 + SECStatus rv = SECSuccess;
1.146 + if (!params || !privKey) {
1.147 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.148 + return SECFailure;
1.149 + }
1.150 + arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
1.151 + if (!arena) {
1.152 + PORT_SetError(SEC_ERROR_NO_MEMORY);
1.153 + return SECFailure;
1.154 + }
1.155 + key = (DHPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DHPrivateKey));
1.156 + if (!key) {
1.157 + PORT_SetError(SEC_ERROR_NO_MEMORY);
1.158 + PORT_FreeArena(arena, PR_TRUE);
1.159 + return SECFailure;
1.160 + }
1.161 + key->arena = arena;
1.162 + MP_DIGITS(&g) = 0;
1.163 + MP_DIGITS(&xa) = 0;
1.164 + MP_DIGITS(&p) = 0;
1.165 + MP_DIGITS(&Ya) = 0;
1.166 + CHECK_MPI_OK( mp_init(&g) );
1.167 + CHECK_MPI_OK( mp_init(&xa) );
1.168 + CHECK_MPI_OK( mp_init(&p) );
1.169 + CHECK_MPI_OK( mp_init(&Ya) );
1.170 + /* Set private key's p */
1.171 + CHECK_SEC_OK( SECITEM_CopyItem(arena, &key->prime, ¶ms->prime) );
1.172 + SECITEM_TO_MPINT(key->prime, &p);
1.173 + /* Set private key's g */
1.174 + CHECK_SEC_OK( SECITEM_CopyItem(arena, &key->base, ¶ms->base) );
1.175 + SECITEM_TO_MPINT(key->base, &g);
1.176 + /* Generate private key xa */
1.177 + SECITEM_AllocItem(arena, &key->privateValue,
1.178 + dh_GetSecretKeyLen(params->prime.len));
1.179 + RNG_GenerateGlobalRandomBytes(key->privateValue.data,
1.180 + key->privateValue.len);
1.181 + SECITEM_TO_MPINT( key->privateValue, &xa );
1.182 + /* xa < p */
1.183 + CHECK_MPI_OK( mp_mod(&xa, &p, &xa) );
1.184 + /* Compute public key Ya = g ** xa mod p */
1.185 + CHECK_MPI_OK( mp_exptmod(&g, &xa, &p, &Ya) );
1.186 + MPINT_TO_SECITEM(&Ya, &key->publicValue, key->arena);
1.187 + *privKey = key;
1.188 +cleanup:
1.189 + mp_clear(&g);
1.190 + mp_clear(&xa);
1.191 + mp_clear(&p);
1.192 + mp_clear(&Ya);
1.193 + if (err) {
1.194 + MP_TO_SEC_ERROR(err);
1.195 + rv = SECFailure;
1.196 + }
1.197 + if (rv)
1.198 + PORT_FreeArena(arena, PR_TRUE);
1.199 + return rv;
1.200 +}
1.201 +
1.202 +SECStatus
1.203 +DH_Derive(SECItem *publicValue,
1.204 + SECItem *prime,
1.205 + SECItem *privateValue,
1.206 + SECItem *derivedSecret,
1.207 + unsigned int outBytes)
1.208 +{
1.209 + mp_int p, Xa, Yb, ZZ, psub1;
1.210 + mp_err err = MP_OKAY;
1.211 + int len = 0;
1.212 + unsigned int nb;
1.213 + unsigned char *secret = NULL;
1.214 + if (!publicValue || !prime || !privateValue || !derivedSecret) {
1.215 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.216 + return SECFailure;
1.217 + }
1.218 + memset(derivedSecret, 0, sizeof *derivedSecret);
1.219 + MP_DIGITS(&p) = 0;
1.220 + MP_DIGITS(&Xa) = 0;
1.221 + MP_DIGITS(&Yb) = 0;
1.222 + MP_DIGITS(&ZZ) = 0;
1.223 + MP_DIGITS(&psub1) = 0;
1.224 + CHECK_MPI_OK( mp_init(&p) );
1.225 + CHECK_MPI_OK( mp_init(&Xa) );
1.226 + CHECK_MPI_OK( mp_init(&Yb) );
1.227 + CHECK_MPI_OK( mp_init(&ZZ) );
1.228 + CHECK_MPI_OK( mp_init(&psub1) );
1.229 + SECITEM_TO_MPINT(*publicValue, &Yb);
1.230 + SECITEM_TO_MPINT(*privateValue, &Xa);
1.231 + SECITEM_TO_MPINT(*prime, &p);
1.232 + CHECK_MPI_OK( mp_sub_d(&p, 1, &psub1) );
1.233 +
1.234 + /* We assume that the modulus, p, is a safe prime. That is, p = 2q+1 where
1.235 + * q is also a prime. Thus the orders of the subgroups are factors of 2q:
1.236 + * namely 1, 2, q and 2q.
1.237 + *
1.238 + * We check that the peer's public value isn't zero (which isn't in the
1.239 + * group), one (subgroup of order one) or p-1 (subgroup of order 2). We
1.240 + * also check that the public value is less than p, to avoid being fooled
1.241 + * by values like p+1 or 2*p-1.
1.242 + *
1.243 + * Thus we must be operating in the subgroup of size q or 2q. */
1.244 + if (mp_cmp_d(&Yb, 1) <= 0 ||
1.245 + mp_cmp(&Yb, &psub1) >= 0) {
1.246 + err = MP_BADARG;
1.247 + goto cleanup;
1.248 + }
1.249 +
1.250 + /* ZZ = (Yb)**Xa mod p */
1.251 + CHECK_MPI_OK( mp_exptmod(&Yb, &Xa, &p, &ZZ) );
1.252 + /* number of bytes in the derived secret */
1.253 + len = mp_unsigned_octet_size(&ZZ);
1.254 + if (len <= 0) {
1.255 + err = MP_BADARG;
1.256 + goto cleanup;
1.257 + }
1.258 + /* allocate a buffer which can hold the entire derived secret. */
1.259 + secret = PORT_Alloc(len);
1.260 + /* grab the derived secret */
1.261 + err = mp_to_unsigned_octets(&ZZ, secret, len);
1.262 + if (err >= 0) err = MP_OKAY;
1.263 + /*
1.264 + ** if outBytes is 0 take all of the bytes from the derived secret.
1.265 + ** if outBytes is not 0 take exactly outBytes from the derived secret, zero
1.266 + ** pad at the beginning if necessary, and truncate beginning bytes
1.267 + ** if necessary.
1.268 + */
1.269 + if (outBytes > 0)
1.270 + nb = outBytes;
1.271 + else
1.272 + nb = len;
1.273 + SECITEM_AllocItem(NULL, derivedSecret, nb);
1.274 + if (len < nb) {
1.275 + unsigned int offset = nb - len;
1.276 + memset(derivedSecret->data, 0, offset);
1.277 + memcpy(derivedSecret->data + offset, secret, len);
1.278 + } else {
1.279 + memcpy(derivedSecret->data, secret + len - nb, nb);
1.280 + }
1.281 +cleanup:
1.282 + mp_clear(&p);
1.283 + mp_clear(&Xa);
1.284 + mp_clear(&Yb);
1.285 + mp_clear(&ZZ);
1.286 + mp_clear(&psub1);
1.287 + if (secret) {
1.288 + /* free the buffer allocated for the full secret. */
1.289 + PORT_ZFree(secret, len);
1.290 + }
1.291 + if (err) {
1.292 + MP_TO_SEC_ERROR(err);
1.293 + if (derivedSecret->data)
1.294 + PORT_ZFree(derivedSecret->data, derivedSecret->len);
1.295 + return SECFailure;
1.296 + }
1.297 + return SECSuccess;
1.298 +}
1.299 +
1.300 +SECStatus
1.301 +KEA_Derive(SECItem *prime,
1.302 + SECItem *public1,
1.303 + SECItem *public2,
1.304 + SECItem *private1,
1.305 + SECItem *private2,
1.306 + SECItem *derivedSecret)
1.307 +{
1.308 + mp_int p, Y, R, r, x, t, u, w;
1.309 + mp_err err;
1.310 + unsigned char *secret = NULL;
1.311 + unsigned int len = 0, offset;
1.312 + if (!prime || !public1 || !public2 || !private1 || !private2 ||
1.313 + !derivedSecret) {
1.314 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.315 + return SECFailure;
1.316 + }
1.317 + memset(derivedSecret, 0, sizeof *derivedSecret);
1.318 + MP_DIGITS(&p) = 0;
1.319 + MP_DIGITS(&Y) = 0;
1.320 + MP_DIGITS(&R) = 0;
1.321 + MP_DIGITS(&r) = 0;
1.322 + MP_DIGITS(&x) = 0;
1.323 + MP_DIGITS(&t) = 0;
1.324 + MP_DIGITS(&u) = 0;
1.325 + MP_DIGITS(&w) = 0;
1.326 + CHECK_MPI_OK( mp_init(&p) );
1.327 + CHECK_MPI_OK( mp_init(&Y) );
1.328 + CHECK_MPI_OK( mp_init(&R) );
1.329 + CHECK_MPI_OK( mp_init(&r) );
1.330 + CHECK_MPI_OK( mp_init(&x) );
1.331 + CHECK_MPI_OK( mp_init(&t) );
1.332 + CHECK_MPI_OK( mp_init(&u) );
1.333 + CHECK_MPI_OK( mp_init(&w) );
1.334 + SECITEM_TO_MPINT(*prime, &p);
1.335 + SECITEM_TO_MPINT(*public1, &Y);
1.336 + SECITEM_TO_MPINT(*public2, &R);
1.337 + SECITEM_TO_MPINT(*private1, &r);
1.338 + SECITEM_TO_MPINT(*private2, &x);
1.339 + /* t = DH(Y, r, p) = Y ** r mod p */
1.340 + CHECK_MPI_OK( mp_exptmod(&Y, &r, &p, &t) );
1.341 + /* u = DH(R, x, p) = R ** x mod p */
1.342 + CHECK_MPI_OK( mp_exptmod(&R, &x, &p, &u) );
1.343 + /* w = (t + u) mod p */
1.344 + CHECK_MPI_OK( mp_addmod(&t, &u, &p, &w) );
1.345 + /* allocate a buffer for the full derived secret */
1.346 + len = mp_unsigned_octet_size(&w);
1.347 + secret = PORT_Alloc(len);
1.348 + /* grab the secret */
1.349 + err = mp_to_unsigned_octets(&w, secret, len);
1.350 + if (err > 0) err = MP_OKAY;
1.351 + /* allocate output buffer */
1.352 + SECITEM_AllocItem(NULL, derivedSecret, KEA_DERIVED_SECRET_LEN);
1.353 + memset(derivedSecret->data, 0, derivedSecret->len);
1.354 + /* copy in the 128 lsb of the secret */
1.355 + if (len >= KEA_DERIVED_SECRET_LEN) {
1.356 + memcpy(derivedSecret->data, secret + (len - KEA_DERIVED_SECRET_LEN),
1.357 + KEA_DERIVED_SECRET_LEN);
1.358 + } else {
1.359 + offset = KEA_DERIVED_SECRET_LEN - len;
1.360 + memcpy(derivedSecret->data + offset, secret, len);
1.361 + }
1.362 +cleanup:
1.363 + mp_clear(&p);
1.364 + mp_clear(&Y);
1.365 + mp_clear(&R);
1.366 + mp_clear(&r);
1.367 + mp_clear(&x);
1.368 + mp_clear(&t);
1.369 + mp_clear(&u);
1.370 + mp_clear(&w);
1.371 + if (secret)
1.372 + PORT_ZFree(secret, len);
1.373 + if (err) {
1.374 + MP_TO_SEC_ERROR(err);
1.375 + return SECFailure;
1.376 + }
1.377 + return SECSuccess;
1.378 +}
1.379 +
1.380 +PRBool
1.381 +KEA_Verify(SECItem *Y, SECItem *prime, SECItem *subPrime)
1.382 +{
1.383 + mp_int p, q, y, r;
1.384 + mp_err err;
1.385 + int cmp = 1; /* default is false */
1.386 + if (!Y || !prime || !subPrime) {
1.387 + PORT_SetError(SEC_ERROR_INVALID_ARGS);
1.388 + return SECFailure;
1.389 + }
1.390 + MP_DIGITS(&p) = 0;
1.391 + MP_DIGITS(&q) = 0;
1.392 + MP_DIGITS(&y) = 0;
1.393 + MP_DIGITS(&r) = 0;
1.394 + CHECK_MPI_OK( mp_init(&p) );
1.395 + CHECK_MPI_OK( mp_init(&q) );
1.396 + CHECK_MPI_OK( mp_init(&y) );
1.397 + CHECK_MPI_OK( mp_init(&r) );
1.398 + SECITEM_TO_MPINT(*prime, &p);
1.399 + SECITEM_TO_MPINT(*subPrime, &q);
1.400 + SECITEM_TO_MPINT(*Y, &y);
1.401 + /* compute r = y**q mod p */
1.402 + CHECK_MPI_OK( mp_exptmod(&y, &q, &p, &r) );
1.403 + /* compare to 1 */
1.404 + cmp = mp_cmp_d(&r, 1);
1.405 +cleanup:
1.406 + mp_clear(&p);
1.407 + mp_clear(&q);
1.408 + mp_clear(&y);
1.409 + mp_clear(&r);
1.410 + if (err) {
1.411 + MP_TO_SEC_ERROR(err);
1.412 + return PR_FALSE;
1.413 + }
1.414 + return (cmp == 0) ? PR_TRUE : PR_FALSE;
1.415 +}
