andre@0: /* This Source Code Form is subject to the terms of the Mozilla Public
andre@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
andre@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
andre@0: 
andre@0: /*
andre@0:  * Diffie-Hellman parameter generation, key generation, and secret derivation.
andre@0:  * KEA secret generation and verification.
andre@0:  */
andre@0: #ifdef FREEBL_NO_DEPEND
andre@0: #include "stubs.h"
andre@0: #endif
andre@0: 
andre@0: #include "prerr.h"
andre@0: #include "secerr.h"
andre@0: 
andre@0: #include "blapi.h"
andre@0: #include "secitem.h"
andre@0: #include "mpi.h"
andre@0: #include "mpprime.h"
andre@0: #include "secmpi.h"
andre@0: 
andre@0: #define KEA_DERIVED_SECRET_LEN 128
andre@0: 
andre@0: /* Lengths are in bytes. */
andre@0: static unsigned int
andre@0: dh_GetSecretKeyLen(unsigned int primeLen)
andre@0: {
andre@0:     /* Based on Table 2 in NIST SP 800-57. */
andre@0:     if (primeLen >= 1920) { /* 15360 bits */
andre@0:         return 64;  /* 512 bits */
andre@0:     }
andre@0:     if (primeLen >= 960) { /* 7680 bits */
andre@0:         return 48;  /* 384 bits */
andre@0:     }
andre@0:     if (primeLen >= 384) { /* 3072 bits */
andre@0:         return 32;  /* 256 bits */
andre@0:     }
andre@0:     if (primeLen >= 256) { /* 2048 bits */
andre@0:         return 28;  /* 224 bits */
andre@0:     }
andre@0:     return 20;  /* 160 bits */
andre@0: }
andre@0: 
andre@0: SECStatus 
andre@0: DH_GenParam(int primeLen, DHParams **params)
andre@0: {
andre@0:     PLArenaPool *arena;
andre@0:     DHParams *dhparams;
andre@0:     unsigned char *pb = NULL;
andre@0:     unsigned char *ab = NULL;
andre@0:     unsigned long counter = 0;
andre@0:     mp_int p, q, a, h, psub1, test;
andre@0:     mp_err err = MP_OKAY;
andre@0:     SECStatus rv = SECSuccess;
andre@0:     if (!params || primeLen < 0) {
andre@0: 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
andre@0:     if (!arena) {
andre@0: 	PORT_SetError(SEC_ERROR_NO_MEMORY);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     dhparams = (DHParams *)PORT_ArenaZAlloc(arena, sizeof(DHParams));
andre@0:     if (!dhparams) {
andre@0: 	PORT_SetError(SEC_ERROR_NO_MEMORY);
andre@0: 	PORT_FreeArena(arena, PR_TRUE);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     dhparams->arena = arena;
andre@0:     MP_DIGITS(&p) = 0;
andre@0:     MP_DIGITS(&q) = 0;
andre@0:     MP_DIGITS(&a) = 0;
andre@0:     MP_DIGITS(&h) = 0;
andre@0:     MP_DIGITS(&psub1) = 0;
andre@0:     MP_DIGITS(&test) = 0;
andre@0:     CHECK_MPI_OK( mp_init(&p) );
andre@0:     CHECK_MPI_OK( mp_init(&q) );
andre@0:     CHECK_MPI_OK( mp_init(&a) );
andre@0:     CHECK_MPI_OK( mp_init(&h) );
andre@0:     CHECK_MPI_OK( mp_init(&psub1) );
andre@0:     CHECK_MPI_OK( mp_init(&test) );
andre@0:     /* generate prime with MPI, uses Miller-Rabin to generate strong prime. */
andre@0:     pb = PORT_Alloc(primeLen);
andre@0:     CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(pb, primeLen) );
andre@0:     pb[0]          |= 0x80; /* set high-order bit */
andre@0:     pb[primeLen-1] |= 0x01; /* set low-order bit  */
andre@0:     CHECK_MPI_OK( mp_read_unsigned_octets(&p, pb, primeLen) );
andre@0:     CHECK_MPI_OK( mpp_make_prime(&p, primeLen * 8, PR_TRUE, &counter) );
andre@0:     /* construct Sophie-Germain prime q = (p-1)/2. */
andre@0:     CHECK_MPI_OK( mp_sub_d(&p, 1, &psub1) );
andre@0:     CHECK_MPI_OK( mp_div_2(&psub1, &q)    );
andre@0:     /* construct a generator from the prime. */
andre@0:     ab = PORT_Alloc(primeLen);
andre@0:     /* generate a candidate number a in p's field */
andre@0:     CHECK_SEC_OK( RNG_GenerateGlobalRandomBytes(ab, primeLen) );
andre@0:     CHECK_MPI_OK( mp_read_unsigned_octets(&a, ab, primeLen) );
andre@0:     /* force a < p (note that quot(a/p) <= 1) */
andre@0:     if ( mp_cmp(&a, &p) > 0 )
andre@0: 	CHECK_MPI_OK( mp_sub(&a, &p, &a) );
andre@0:     do {
andre@0: 	/* check that a is in the range [2..p-1] */
andre@0: 	if ( mp_cmp_d(&a, 2) < 0 || mp_cmp(&a, &psub1) >= 0) {
andre@0: 	    /* a is outside of the allowed range.  Set a=3 and keep going. */
andre@0:             mp_set(&a, 3);
andre@0: 	}
andre@0: 	/* if a**q mod p != 1 then a is a generator */
andre@0: 	CHECK_MPI_OK( mp_exptmod(&a, &q, &p, &test) );
andre@0: 	if ( mp_cmp_d(&test, 1) != 0 )
andre@0: 	    break;
andre@0: 	/* increment the candidate and try again. */
andre@0: 	CHECK_MPI_OK( mp_add_d(&a, 1, &a) );
andre@0:     } while (PR_TRUE);
andre@0:     MPINT_TO_SECITEM(&p, &dhparams->prime, arena);
andre@0:     MPINT_TO_SECITEM(&a, &dhparams->base, arena);
andre@0:     *params = dhparams;
andre@0: cleanup:
andre@0:     mp_clear(&p);
andre@0:     mp_clear(&q);
andre@0:     mp_clear(&a);
andre@0:     mp_clear(&h);
andre@0:     mp_clear(&psub1);
andre@0:     mp_clear(&test);
andre@0:     if (pb) PORT_ZFree(pb, primeLen);
andre@0:     if (ab) PORT_ZFree(ab, primeLen);
andre@0:     if (err) {
andre@0: 	MP_TO_SEC_ERROR(err);
andre@0: 	rv = SECFailure;
andre@0:     }
andre@0:     if (rv)
andre@0: 	PORT_FreeArena(arena, PR_TRUE);
andre@0:     return rv;
andre@0: }
andre@0: 
andre@0: SECStatus 
andre@0: DH_NewKey(DHParams *params, DHPrivateKey **privKey)
andre@0: {
andre@0:     PLArenaPool *arena;
andre@0:     DHPrivateKey *key;
andre@0:     mp_int g, xa, p, Ya;
andre@0:     mp_err   err = MP_OKAY;
andre@0:     SECStatus rv = SECSuccess;
andre@0:     if (!params || !privKey) {
andre@0: 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
andre@0:     if (!arena) {
andre@0: 	PORT_SetError(SEC_ERROR_NO_MEMORY);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     key = (DHPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DHPrivateKey));
andre@0:     if (!key) {
andre@0: 	PORT_SetError(SEC_ERROR_NO_MEMORY);
andre@0: 	PORT_FreeArena(arena, PR_TRUE);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     key->arena = arena;
andre@0:     MP_DIGITS(&g)  = 0;
andre@0:     MP_DIGITS(&xa) = 0;
andre@0:     MP_DIGITS(&p)  = 0;
andre@0:     MP_DIGITS(&Ya) = 0;
andre@0:     CHECK_MPI_OK( mp_init(&g)  );
andre@0:     CHECK_MPI_OK( mp_init(&xa) );
andre@0:     CHECK_MPI_OK( mp_init(&p)  );
andre@0:     CHECK_MPI_OK( mp_init(&Ya) );
andre@0:     /* Set private key's p */
andre@0:     CHECK_SEC_OK( SECITEM_CopyItem(arena, &key->prime, &params->prime) );
andre@0:     SECITEM_TO_MPINT(key->prime, &p);
andre@0:     /* Set private key's g */
andre@0:     CHECK_SEC_OK( SECITEM_CopyItem(arena, &key->base, &params->base) );
andre@0:     SECITEM_TO_MPINT(key->base, &g);
andre@0:     /* Generate private key xa */
andre@0:     SECITEM_AllocItem(arena, &key->privateValue,
andre@0:                       dh_GetSecretKeyLen(params->prime.len));
andre@0:     RNG_GenerateGlobalRandomBytes(key->privateValue.data, 
andre@0:                                   key->privateValue.len);
andre@0:     SECITEM_TO_MPINT( key->privateValue, &xa );
andre@0:     /* xa < p */
andre@0:     CHECK_MPI_OK( mp_mod(&xa, &p, &xa) );
andre@0:     /* Compute public key Ya = g ** xa mod p */
andre@0:     CHECK_MPI_OK( mp_exptmod(&g, &xa, &p, &Ya) );
andre@0:     MPINT_TO_SECITEM(&Ya, &key->publicValue, key->arena);
andre@0:     *privKey = key;
andre@0: cleanup:
andre@0:     mp_clear(&g);
andre@0:     mp_clear(&xa);
andre@0:     mp_clear(&p);
andre@0:     mp_clear(&Ya);
andre@0:     if (err) {
andre@0: 	MP_TO_SEC_ERROR(err);
andre@0: 	rv = SECFailure;
andre@0:     }
andre@0:     if (rv)
andre@0: 	PORT_FreeArena(arena, PR_TRUE);
andre@0:     return rv;
andre@0: }
andre@0: 
andre@0: SECStatus 
andre@0: DH_Derive(SECItem *publicValue, 
andre@0:           SECItem *prime, 
andre@0:           SECItem *privateValue, 
andre@0:           SECItem *derivedSecret, 
andre@0:           unsigned int outBytes)
andre@0: {
andre@0:     mp_int p, Xa, Yb, ZZ, psub1;
andre@0:     mp_err err = MP_OKAY;
andre@0:     int len = 0;
andre@0:     unsigned int nb;
andre@0:     unsigned char *secret = NULL;
andre@0:     if (!publicValue || !prime || !privateValue || !derivedSecret) {
andre@0: 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     memset(derivedSecret, 0, sizeof *derivedSecret);
andre@0:     MP_DIGITS(&p)  = 0;
andre@0:     MP_DIGITS(&Xa) = 0;
andre@0:     MP_DIGITS(&Yb) = 0;
andre@0:     MP_DIGITS(&ZZ) = 0;
andre@0:     MP_DIGITS(&psub1) = 0;
andre@0:     CHECK_MPI_OK( mp_init(&p)  );
andre@0:     CHECK_MPI_OK( mp_init(&Xa) );
andre@0:     CHECK_MPI_OK( mp_init(&Yb) );
andre@0:     CHECK_MPI_OK( mp_init(&ZZ) );
andre@0:     CHECK_MPI_OK( mp_init(&psub1) );
andre@0:     SECITEM_TO_MPINT(*publicValue,  &Yb);
andre@0:     SECITEM_TO_MPINT(*privateValue, &Xa);
andre@0:     SECITEM_TO_MPINT(*prime,        &p);
andre@0:     CHECK_MPI_OK( mp_sub_d(&p, 1, &psub1) );
andre@0: 
andre@0:     /* We assume that the modulus, p, is a safe prime. That is, p = 2q+1 where
andre@0:      * q is also a prime. Thus the orders of the subgroups are factors of 2q:
andre@0:      * namely 1, 2, q and 2q.
andre@0:      *
andre@0:      * We check that the peer's public value isn't zero (which isn't in the
andre@0:      * group), one (subgroup of order one) or p-1 (subgroup of order 2). We
andre@0:      * also check that the public value is less than p, to avoid being fooled
andre@0:      * by values like p+1 or 2*p-1.
andre@0:      *
andre@0:      * Thus we must be operating in the subgroup of size q or 2q. */
andre@0:     if (mp_cmp_d(&Yb, 1) <= 0 ||
andre@0: 	mp_cmp(&Yb, &psub1) >= 0) {
andre@0: 	err = MP_BADARG;
andre@0: 	goto cleanup;
andre@0:     }
andre@0: 
andre@0:     /* ZZ = (Yb)**Xa mod p */
andre@0:     CHECK_MPI_OK( mp_exptmod(&Yb, &Xa, &p, &ZZ) );
andre@0:     /* number of bytes in the derived secret */
andre@0:     len = mp_unsigned_octet_size(&ZZ);
andre@0:     if (len <= 0) {
andre@0:         err = MP_BADARG;
andre@0:         goto cleanup;
andre@0:     }
andre@0:     /* allocate a buffer which can hold the entire derived secret. */
andre@0:     secret = PORT_Alloc(len);
andre@0:     /* grab the derived secret */
andre@0:     err = mp_to_unsigned_octets(&ZZ, secret, len);
andre@0:     if (err >= 0) err = MP_OKAY;
andre@0:     /* 
andre@0:     ** if outBytes is 0 take all of the bytes from the derived secret.
andre@0:     ** if outBytes is not 0 take exactly outBytes from the derived secret, zero
andre@0:     ** pad at the beginning if necessary, and truncate beginning bytes 
andre@0:     ** if necessary.
andre@0:     */
andre@0:     if (outBytes > 0)
andre@0: 	nb = outBytes;
andre@0:     else
andre@0: 	nb = len;
andre@0:     SECITEM_AllocItem(NULL, derivedSecret, nb);
andre@0:     if (len < nb) {
andre@0: 	unsigned int offset = nb - len;
andre@0: 	memset(derivedSecret->data, 0, offset);
andre@0: 	memcpy(derivedSecret->data + offset, secret, len);
andre@0:     } else {
andre@0: 	memcpy(derivedSecret->data, secret + len - nb, nb);
andre@0:     }
andre@0: cleanup:
andre@0:     mp_clear(&p);
andre@0:     mp_clear(&Xa);
andre@0:     mp_clear(&Yb);
andre@0:     mp_clear(&ZZ);
andre@0:     mp_clear(&psub1);
andre@0:     if (secret) {
andre@0: 	/* free the buffer allocated for the full secret. */
andre@0: 	PORT_ZFree(secret, len);
andre@0:     }
andre@0:     if (err) {
andre@0: 	MP_TO_SEC_ERROR(err);
andre@0: 	if (derivedSecret->data) 
andre@0: 	    PORT_ZFree(derivedSecret->data, derivedSecret->len);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     return SECSuccess;
andre@0: }
andre@0: 
andre@0: SECStatus 
andre@0: KEA_Derive(SECItem *prime, 
andre@0:            SECItem *public1, 
andre@0:            SECItem *public2, 
andre@0:            SECItem *private1, 
andre@0:            SECItem *private2,
andre@0:            SECItem *derivedSecret)
andre@0: {
andre@0:     mp_int p, Y, R, r, x, t, u, w;
andre@0:     mp_err err;
andre@0:     unsigned char *secret = NULL;
andre@0:     unsigned int len = 0, offset;
andre@0:     if (!prime || !public1 || !public2 || !private1 || !private2 ||
andre@0:         !derivedSecret) {
andre@0: 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     memset(derivedSecret, 0, sizeof *derivedSecret);
andre@0:     MP_DIGITS(&p) = 0;
andre@0:     MP_DIGITS(&Y) = 0;
andre@0:     MP_DIGITS(&R) = 0;
andre@0:     MP_DIGITS(&r) = 0;
andre@0:     MP_DIGITS(&x) = 0;
andre@0:     MP_DIGITS(&t) = 0;
andre@0:     MP_DIGITS(&u) = 0;
andre@0:     MP_DIGITS(&w) = 0;
andre@0:     CHECK_MPI_OK( mp_init(&p) );
andre@0:     CHECK_MPI_OK( mp_init(&Y) );
andre@0:     CHECK_MPI_OK( mp_init(&R) );
andre@0:     CHECK_MPI_OK( mp_init(&r) );
andre@0:     CHECK_MPI_OK( mp_init(&x) );
andre@0:     CHECK_MPI_OK( mp_init(&t) );
andre@0:     CHECK_MPI_OK( mp_init(&u) );
andre@0:     CHECK_MPI_OK( mp_init(&w) );
andre@0:     SECITEM_TO_MPINT(*prime,    &p);
andre@0:     SECITEM_TO_MPINT(*public1,  &Y);
andre@0:     SECITEM_TO_MPINT(*public2,  &R);
andre@0:     SECITEM_TO_MPINT(*private1, &r);
andre@0:     SECITEM_TO_MPINT(*private2, &x);
andre@0:     /* t = DH(Y, r, p) = Y ** r mod p */
andre@0:     CHECK_MPI_OK( mp_exptmod(&Y, &r, &p, &t) );
andre@0:     /* u = DH(R, x, p) = R ** x mod p */
andre@0:     CHECK_MPI_OK( mp_exptmod(&R, &x, &p, &u) );
andre@0:     /* w = (t + u) mod p */
andre@0:     CHECK_MPI_OK( mp_addmod(&t, &u, &p, &w) );
andre@0:     /* allocate a buffer for the full derived secret */
andre@0:     len = mp_unsigned_octet_size(&w);
andre@0:     secret = PORT_Alloc(len);
andre@0:     /* grab the secret */
andre@0:     err = mp_to_unsigned_octets(&w, secret, len);
andre@0:     if (err > 0) err = MP_OKAY;
andre@0:     /* allocate output buffer */
andre@0:     SECITEM_AllocItem(NULL, derivedSecret, KEA_DERIVED_SECRET_LEN);
andre@0:     memset(derivedSecret->data, 0, derivedSecret->len);
andre@0:     /* copy in the 128 lsb of the secret */
andre@0:     if (len >= KEA_DERIVED_SECRET_LEN) {
andre@0: 	memcpy(derivedSecret->data, secret + (len - KEA_DERIVED_SECRET_LEN),
andre@0: 	       KEA_DERIVED_SECRET_LEN);
andre@0:     } else {
andre@0: 	offset = KEA_DERIVED_SECRET_LEN - len;
andre@0: 	memcpy(derivedSecret->data + offset, secret, len);
andre@0:     }
andre@0: cleanup:
andre@0:     mp_clear(&p);
andre@0:     mp_clear(&Y);
andre@0:     mp_clear(&R);
andre@0:     mp_clear(&r);
andre@0:     mp_clear(&x);
andre@0:     mp_clear(&t);
andre@0:     mp_clear(&u);
andre@0:     mp_clear(&w);
andre@0:     if (secret)
andre@0: 	PORT_ZFree(secret, len);
andre@0:     if (err) {
andre@0: 	MP_TO_SEC_ERROR(err);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     return SECSuccess;
andre@0: }
andre@0: 
andre@0: PRBool 
andre@0: KEA_Verify(SECItem *Y, SECItem *prime, SECItem *subPrime)
andre@0: {
andre@0:     mp_int p, q, y, r;
andre@0:     mp_err err;
andre@0:     int cmp = 1;  /* default is false */
andre@0:     if (!Y || !prime || !subPrime) {
andre@0: 	PORT_SetError(SEC_ERROR_INVALID_ARGS);
andre@0: 	return SECFailure;
andre@0:     }
andre@0:     MP_DIGITS(&p) = 0;
andre@0:     MP_DIGITS(&q) = 0;
andre@0:     MP_DIGITS(&y) = 0;
andre@0:     MP_DIGITS(&r) = 0;
andre@0:     CHECK_MPI_OK( mp_init(&p) );
andre@0:     CHECK_MPI_OK( mp_init(&q) );
andre@0:     CHECK_MPI_OK( mp_init(&y) );
andre@0:     CHECK_MPI_OK( mp_init(&r) );
andre@0:     SECITEM_TO_MPINT(*prime,    &p);
andre@0:     SECITEM_TO_MPINT(*subPrime, &q);
andre@0:     SECITEM_TO_MPINT(*Y,        &y);
andre@0:     /* compute r = y**q mod p */
andre@0:     CHECK_MPI_OK( mp_exptmod(&y, &q, &p, &r) );
andre@0:     /* compare to 1 */
andre@0:     cmp = mp_cmp_d(&r, 1);
andre@0: cleanup:
andre@0:     mp_clear(&p);
andre@0:     mp_clear(&q);
andre@0:     mp_clear(&y);
andre@0:     mp_clear(&r);
andre@0:     if (err) {
andre@0: 	MP_TO_SEC_ERROR(err);
andre@0: 	return PR_FALSE;
andre@0:     }
andre@0:     return (cmp == 0) ? PR_TRUE : PR_FALSE;
andre@0: }