The Tor Browser / file revision

 /*

  *

  * This Source Code Form is subject to the terms of the Mozilla Public

  * License, v. 2.0. If a copy of the MPL was not distributed with this

  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

 #ifdef FREEBL_NO_DEPEND

 #include "stubs.h"

 #endif

 #include "prerror.h"

 #include "secerr.h"

 #include "prtypes.h"

 #include "prinit.h"

 #include "blapi.h"

 #include "nssilock.h"

 #include "secitem.h"

 #include "blapi.h"

 #include "mpi.h"

 #include "secmpi.h"

 #include "pqg.h"

  /* XXX to be replaced by define in blapit.h */

 #define NSS_FREEBL_DSA_DEFAULT_CHUNKSIZE 2048

 /*

  * FIPS 186-2 requires result from random output to be reduced mod q when 

  * generating random numbers for DSA. 

  *

  * Input: w, 2*qLen bytes

  *        q, qLen bytes

  * Output: xj, qLen bytes

  */

 static SECStatus

 fips186Change_ReduceModQForDSA(const PRUint8 *w, const PRUint8 *q,

                                unsigned int qLen, PRUint8 * xj)

 {

     mp_int W, Q, Xj;

     mp_err err;

     SECStatus rv = SECSuccess;

     /* Initialize MPI integers. */

     MP_DIGITS(&W) = 0;

     MP_DIGITS(&Q) = 0;

     MP_DIGITS(&Xj) = 0;

     CHECK_MPI_OK( mp_init(&W) );

     CHECK_MPI_OK( mp_init(&Q) );

     CHECK_MPI_OK( mp_init(&Xj) );

     /*

      * Convert input arguments into MPI integers.

      */

     CHECK_MPI_OK( mp_read_unsigned_octets(&W, w, 2*qLen) );

     CHECK_MPI_OK( mp_read_unsigned_octets(&Q, q, qLen) );

     /*

      * Algorithm 1 of FIPS 186-2 Change Notice 1, Step 3.3

      *

      * xj = (w0 || w1) mod q

      */

     CHECK_MPI_OK( mp_mod(&W, &Q, &Xj) );

     CHECK_MPI_OK( mp_to_fixlen_octets(&Xj, xj, qLen) );

 cleanup:

     mp_clear(&W);

     mp_clear(&Q);

     mp_clear(&Xj);

     if (err) {

 	MP_TO_SEC_ERROR(err);

 	rv = SECFailure;

     }

     return rv;

 }

 /*

  * FIPS 186-2 requires result from random output to be reduced mod q when 

  * generating random numbers for DSA. 

  */

 SECStatus

 FIPS186Change_ReduceModQForDSA(const unsigned char *w,

                                const unsigned char *q,

                                unsigned char *xj) {

     return fips186Change_ReduceModQForDSA(w, q, DSA1_SUBPRIME_LEN, xj);

 }

 /*

  * The core of Algorithm 1 of FIPS 186-2 Change Notice 1.

  *

  * We no longer support FIPS 186-2 RNG. This function was exported

  * for power-up self tests and FIPS tests. Keep this stub, which fails,

  * to prevent crashes, but also to signal to test code that FIPS 186-2

  * RNG is no longer supported.

  */

 SECStatus

 FIPS186Change_GenerateX(PRUint8 *XKEY, const PRUint8 *XSEEDj,

                         PRUint8 *x_j)

 {

     PORT_SetError(PR_NOT_IMPLEMENTED_ERROR);

     return SECFailure;

 }

 /*

  * Specialized RNG for DSA

  *

  * As per Algorithm 1 of FIPS 186-2 Change Notice 1, in step 3.3 the value

  * Xj should be reduced mod q, a 160-bit prime number.  Since this parameter

  * is only meaningful in the context of DSA, the above RNG functions

  * were implemented without it.  They are re-implemented below for use

  * with DSA.

  */

 /*

 ** Generate some random bytes, using the global random number generator

 ** object.  In DSA mode, so there is a q.

 */

 static SECStatus 

 dsa_GenerateGlobalRandomBytes(const SECItem * qItem, PRUint8 * dest,

                               unsigned int * destLen, unsigned int maxDestLen)

 {

     SECStatus rv;

     SECItem w;

     const PRUint8 * q = qItem->data;

     unsigned int qLen = qItem->len;

     if (*q == 0) {

         ++q;

         --qLen;

     }

     if (maxDestLen < qLen) {

         /* This condition can occur when DSA_SignDigest is passed a group

            with a subprime that is larger than DSA_MAX_SUBPRIME_LEN. */

         PORT_SetError(SEC_ERROR_INVALID_ARGS);

         return SECFailure;

     }

     w.data = NULL; /* otherwise SECITEM_AllocItem asserts */

     if (!SECITEM_AllocItem(NULL, &w, 2*qLen)) {

         return SECFailure;

     }

     *destLen = qLen;

     rv = RNG_GenerateGlobalRandomBytes(w.data, w.len);

     if (rv == SECSuccess) {

         rv = fips186Change_ReduceModQForDSA(w.data, q, qLen, dest);

     }

     SECITEM_FreeItem(&w, PR_FALSE);

     return rv;

 }

 static void translate_mpi_error(mp_err err)

 {

     MP_TO_SEC_ERROR(err);

 }

 static SECStatus 

 dsa_NewKeyExtended(const PQGParams *params, const SECItem * seed,

                    DSAPrivateKey **privKey)

 {

     mp_int p, g;

     mp_int x, y;

     mp_err err;

     PLArenaPool *arena;

     DSAPrivateKey *key;

     /* Check args. */

     if (!params || !privKey || !seed || !seed->data) {

 	PORT_SetError(SEC_ERROR_INVALID_ARGS);

 	return SECFailure;

     }

     /* Initialize an arena for the DSA key. */

     arena = PORT_NewArena(NSS_FREEBL_DSA_DEFAULT_CHUNKSIZE);

     if (!arena) {

 	PORT_SetError(SEC_ERROR_NO_MEMORY);

 	return SECFailure;

     }

     key = (DSAPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DSAPrivateKey));

     if (!key) {

 	PORT_SetError(SEC_ERROR_NO_MEMORY);

 	PORT_FreeArena(arena, PR_TRUE);

 	return SECFailure;

     }

     key->params.arena = arena;

     /* Initialize MPI integers. */

     MP_DIGITS(&p) = 0;

     MP_DIGITS(&g) = 0;

     MP_DIGITS(&x) = 0;

     MP_DIGITS(&y) = 0;

     CHECK_MPI_OK( mp_init(&p) );

     CHECK_MPI_OK( mp_init(&g) );

     CHECK_MPI_OK( mp_init(&x) );

     CHECK_MPI_OK( mp_init(&y) );

     /* Copy over the PQG params */

     CHECK_MPI_OK( SECITEM_CopyItem(arena, &key->params.prime,

                                           &params->prime) );

     CHECK_MPI_OK( SECITEM_CopyItem(arena, &key->params.subPrime,

                                           &params->subPrime) );

     CHECK_MPI_OK( SECITEM_CopyItem(arena, &key->params.base, &params->base) );

     /* Convert stored p, g, and received x into MPI integers. */

     SECITEM_TO_MPINT(params->prime, &p);

     SECITEM_TO_MPINT(params->base,  &g);

     OCTETS_TO_MPINT(seed->data, &x, seed->len);

     /* Store x in private key */

     SECITEM_AllocItem(arena, &key->privateValue, seed->len);

     PORT_Memcpy(key->privateValue.data, seed->data, seed->len);

     /* Compute public key y = g**x mod p */

     CHECK_MPI_OK( mp_exptmod(&g, &x, &p, &y) );

     /* Store y in public key */

     MPINT_TO_SECITEM(&y, &key->publicValue, arena);

     *privKey = key;

     key = NULL;

 cleanup:

     mp_clear(&p);

     mp_clear(&g);

     mp_clear(&x);

     mp_clear(&y);

     if (key)

 	PORT_FreeArena(key->params.arena, PR_TRUE);

     if (err) {

 	translate_mpi_error(err);

 	return SECFailure;

     }

     return SECSuccess;

 }

 SECStatus

 DSA_NewRandom(PLArenaPool * arena, const SECItem * q, SECItem * seed)

 {

     int retries = 10;

     unsigned int i;

     PRBool good;

     if (q == NULL || q->data == NULL || q->len == 0 ||

         (q->data[0] == 0 && q->len == 1)) {

         PORT_SetError(SEC_ERROR_INVALID_ARGS);

         return SECFailure;

     }

     if (!SECITEM_AllocItem(arena, seed, q->len)) {

         return SECFailure;

     }

     do {

 	/* Generate seed bytes for x according to FIPS 186-1 appendix 3 */

         if (dsa_GenerateGlobalRandomBytes(q, seed->data, &seed->len,

                                           seed->len)) {

             goto loser;

         }

 	/* Disallow values of 0 and 1 for x. */

 	good = PR_FALSE;

 	for (i = 0; i < seed->len-1; i++) {

 	    if (seed->data[i] != 0) {

 		good = PR_TRUE;

 		break;

 	    }

 	}

 	if (!good && seed->data[i] > 1) {

 	    good = PR_TRUE;

 	}

     } while (!good && --retries > 0);

     if (!good) {

 	PORT_SetError(SEC_ERROR_NEED_RANDOM);

 loser:	if (arena != NULL) {

             SECITEM_FreeItem(seed, PR_FALSE);

         }

 	return SECFailure;

     }

     return SECSuccess;

 }

 /*

 ** Generate and return a new DSA public and private key pair,

 **	both of which are encoded into a single DSAPrivateKey struct.

 **	"params" is a pointer to the PQG parameters for the domain

 **	Uses a random seed.

 */

 SECStatus 

 DSA_NewKey(const PQGParams *params, DSAPrivateKey **privKey)

 {

     SECItem seed;

     SECStatus rv;

     rv = PQG_Check(params);

     if (rv != SECSuccess) {

 	return rv;

     }

     seed.data = NULL;

     rv = DSA_NewRandom(NULL, &params->subPrime, &seed);

     if (rv == SECSuccess) {

         if (seed.len != PQG_GetLength(&params->subPrime)) {

             PORT_SetError(SEC_ERROR_INVALID_ARGS);

             rv = SECFailure;

         } else {

             rv = dsa_NewKeyExtended(params, &seed, privKey);

         }

     }

     SECITEM_FreeItem(&seed, PR_FALSE);

     return rv;

 }

 /* For FIPS compliance testing. Seed must be exactly the size of subPrime  */

 SECStatus 

 DSA_NewKeyFromSeed(const PQGParams *params, 

                    const unsigned char *seed,

                    DSAPrivateKey **privKey)

 {

     SECItem seedItem;

     seedItem.data = (unsigned char*) seed;

     seedItem.len = PQG_GetLength(&params->subPrime);

     return dsa_NewKeyExtended(params, &seedItem, privKey);

 }

 static SECStatus 

 dsa_SignDigest(DSAPrivateKey *key, SECItem *signature, const SECItem *digest,

                const unsigned char *kb)

 {

     mp_int p, q, g;  /* PQG parameters */

     mp_int x, k;     /* private key & pseudo-random integer */

     mp_int r, s;     /* tuple (r, s) is signature) */

     mp_err err   = MP_OKAY;

     SECStatus rv = SECSuccess;

     unsigned int dsa_subprime_len, dsa_signature_len, offset;

     SECItem localDigest;

     unsigned char localDigestData[DSA_MAX_SUBPRIME_LEN];

     /* FIPS-compliance dictates that digest is a SHA hash. */

     /* Check args. */

     if (!key || !signature || !digest) {

 	PORT_SetError(SEC_ERROR_INVALID_ARGS);

 	return SECFailure;

     }

     dsa_subprime_len = PQG_GetLength(&key->params.subPrime);

     dsa_signature_len = dsa_subprime_len*2;

     if ((signature->len < dsa_signature_len) ||

 	(digest->len > HASH_LENGTH_MAX)  ||

 	(digest->len < SHA1_LENGTH)) {

 	PORT_SetError(SEC_ERROR_INVALID_ARGS);

 	return SECFailure;

     }

     /* DSA accepts digests not equal to dsa_subprime_len, if the 

      * digests are greater, then they are truncated to the size of 

      * dsa_subprime_len, using the left most bits. If they are less

      * then they are padded on the left.*/

     PORT_Memset(localDigestData, 0, dsa_subprime_len);

     offset = (digest->len < dsa_subprime_len) ? 

 			(dsa_subprime_len - digest->len) : 0;

     PORT_Memcpy(localDigestData+offset, digest->data, 

 		dsa_subprime_len - offset);

     localDigest.data = localDigestData;

     localDigest.len = dsa_subprime_len;

     /* Initialize MPI integers. */

     MP_DIGITS(&p) = 0;

     MP_DIGITS(&q) = 0;

     MP_DIGITS(&g) = 0;

     MP_DIGITS(&x) = 0;

     MP_DIGITS(&k) = 0;

     MP_DIGITS(&r) = 0;

     MP_DIGITS(&s) = 0;

     CHECK_MPI_OK( mp_init(&p) );

     CHECK_MPI_OK( mp_init(&q) );

     CHECK_MPI_OK( mp_init(&g) );

     CHECK_MPI_OK( mp_init(&x) );

     CHECK_MPI_OK( mp_init(&k) );

     CHECK_MPI_OK( mp_init(&r) );

     CHECK_MPI_OK( mp_init(&s) );

     /*

     ** Convert stored PQG and private key into MPI integers.

     */

     SECITEM_TO_MPINT(key->params.prime,    &p);

     SECITEM_TO_MPINT(key->params.subPrime, &q);

     SECITEM_TO_MPINT(key->params.base,     &g);

     SECITEM_TO_MPINT(key->privateValue,    &x);

     OCTETS_TO_MPINT(kb, &k, dsa_subprime_len);

     /*

     ** FIPS 186-1, Section 5, Step 1

     **

     ** r = (g**k mod p) mod q

     */

     CHECK_MPI_OK( mp_exptmod(&g, &k, &p, &r) ); /* r = g**k mod p */

     CHECK_MPI_OK(     mp_mod(&r, &q, &r) );     /* r = r mod q    */

     /*                                  

     ** FIPS 186-1, Section 5, Step 2

     **

     ** s = (k**-1 * (HASH(M) + x*r)) mod q

     */

     SECITEM_TO_MPINT(localDigest, &s);          /* s = HASH(M)     */

     CHECK_MPI_OK( mp_invmod(&k, &q, &k) );      /* k = k**-1 mod q */

     CHECK_MPI_OK( mp_mulmod(&x, &r, &q, &x) );  /* x = x * r mod q */

     CHECK_MPI_OK( mp_addmod(&s, &x, &q, &s) );  /* s = s + x mod q */

     CHECK_MPI_OK( mp_mulmod(&s, &k, &q, &s) );  /* s = s * k mod q */

     /*

     ** verify r != 0 and s != 0

     ** mentioned as optional in FIPS 186-1.

     */

     if (mp_cmp_z(&r) == 0 || mp_cmp_z(&s) == 0) {

 	PORT_SetError(SEC_ERROR_NEED_RANDOM);

 	rv = SECFailure;

 	goto cleanup;

     }

     /*

     ** Step 4

     **

     ** Signature is tuple (r, s)

     */

     err = mp_to_fixlen_octets(&r, signature->data, dsa_subprime_len);

     if (err < 0) goto cleanup; 

     err = mp_to_fixlen_octets(&s, signature->data + dsa_subprime_len, 

                                   dsa_subprime_len);

     if (err < 0) goto cleanup; 

     err = MP_OKAY;

     signature->len = dsa_signature_len;

 cleanup:

     PORT_Memset(localDigestData, 0, DSA_MAX_SUBPRIME_LEN);

     mp_clear(&p);

     mp_clear(&q);

     mp_clear(&g);

     mp_clear(&x);

     mp_clear(&k);

     mp_clear(&r);

     mp_clear(&s);

     if (err) {

 	translate_mpi_error(err);

 	rv = SECFailure;

     }

     return rv;

 }

 /* signature is caller-supplied buffer of at least 40 bytes.

 ** On input,  signature->len == size of buffer to hold signature.

 **            digest->len    == size of digest.

 ** On output, signature->len == size of signature in buffer.

 ** Uses a random seed.

 */

 SECStatus 

 DSA_SignDigest(DSAPrivateKey *key, SECItem *signature, const SECItem *digest)

 {

     SECStatus rv;

     int       retries = 10;

     unsigned char kSeed[DSA_MAX_SUBPRIME_LEN];

     unsigned int kSeedLen = 0;

     unsigned int i;

     unsigned int dsa_subprime_len = PQG_GetLength(&key->params.subPrime);

     PRBool    good;

     PORT_SetError(0);

     do {

 	rv = dsa_GenerateGlobalRandomBytes(&key->params.subPrime,

                                            kSeed, &kSeedLen, sizeof kSeed);

 	if (rv != SECSuccess) 

 	    break;

         if (kSeedLen != dsa_subprime_len) {

             PORT_SetError(SEC_ERROR_INVALID_ARGS);

             rv = SECFailure;

             break;

         }

 	/* Disallow a value of 0 for k. */

 	good = PR_FALSE;

 	for (i = 0; i < kSeedLen; i++) {

 	    if (kSeed[i] != 0) {

 		good = PR_TRUE;

 		break;

 	    }

 	}

 	if (!good) {

 	    PORT_SetError(SEC_ERROR_NEED_RANDOM);

 	    rv = SECFailure;

 	    continue;

 	}

 	rv = dsa_SignDigest(key, signature, digest, kSeed);

     } while (rv != SECSuccess && PORT_GetError() == SEC_ERROR_NEED_RANDOM &&

 	     --retries > 0);

     return rv;

 }

 /* For FIPS compliance testing. Seed must be exactly 20 bytes. */

 SECStatus 

 DSA_SignDigestWithSeed(DSAPrivateKey * key,

                        SECItem *       signature,

                        const SECItem * digest,

                        const unsigned char * seed)

 {

     SECStatus rv;

     rv = dsa_SignDigest(key, signature, digest, seed);

     return rv;

 }

 /* signature is caller-supplied buffer of at least 20 bytes.

 ** On input,  signature->len == size of buffer to hold signature.

 **            digest->len    == size of digest.

 */

 SECStatus 

 DSA_VerifyDigest(DSAPublicKey *key, const SECItem *signature, 

                  const SECItem *digest)

 {

     /* FIPS-compliance dictates that digest is a SHA hash. */

     mp_int p, q, g;      /* PQG parameters */

     mp_int r_, s_;       /* tuple (r', s') is received signature) */

     mp_int u1, u2, v, w; /* intermediate values used in verification */

     mp_int y;            /* public key */

     mp_err err;

     int dsa_subprime_len, dsa_signature_len, offset;

     SECItem localDigest;

     unsigned char localDigestData[DSA_MAX_SUBPRIME_LEN];

     SECStatus verified = SECFailure;

     /* Check args. */

     if (!key || !signature || !digest ) {

 	PORT_SetError(SEC_ERROR_INVALID_ARGS);

 	return SECFailure;

     }

     dsa_subprime_len = PQG_GetLength(&key->params.subPrime);

     dsa_signature_len = dsa_subprime_len*2;

     if ((signature->len != dsa_signature_len) ||

 	(digest->len > HASH_LENGTH_MAX)  ||

 	(digest->len < SHA1_LENGTH)) {

 	PORT_SetError(SEC_ERROR_INVALID_ARGS);

 	return SECFailure;

     }

     /* DSA accepts digests not equal to dsa_subprime_len, if the 

      * digests are greater, than they are truncated to the size of 

      * dsa_subprime_len, using the left most bits. If they are less

      * then they are padded on the left.*/

     PORT_Memset(localDigestData, 0, dsa_subprime_len);

     offset = (digest->len < dsa_subprime_len) ? 

 			(dsa_subprime_len - digest->len) : 0;

     PORT_Memcpy(localDigestData+offset, digest->data, 

 		dsa_subprime_len - offset);

     localDigest.data = localDigestData;

     localDigest.len = dsa_subprime_len;

     /* Initialize MPI integers. */

     MP_DIGITS(&p)  = 0;

     MP_DIGITS(&q)  = 0;

     MP_DIGITS(&g)  = 0;

     MP_DIGITS(&y)  = 0;

     MP_DIGITS(&r_) = 0;

     MP_DIGITS(&s_) = 0;

     MP_DIGITS(&u1) = 0;

     MP_DIGITS(&u2) = 0;

     MP_DIGITS(&v)  = 0;

     MP_DIGITS(&w)  = 0;

     CHECK_MPI_OK( mp_init(&p)  );

     CHECK_MPI_OK( mp_init(&q)  );

     CHECK_MPI_OK( mp_init(&g)  );

     CHECK_MPI_OK( mp_init(&y)  );

     CHECK_MPI_OK( mp_init(&r_) );

     CHECK_MPI_OK( mp_init(&s_) );

     CHECK_MPI_OK( mp_init(&u1) );

     CHECK_MPI_OK( mp_init(&u2) );

     CHECK_MPI_OK( mp_init(&v)  );

     CHECK_MPI_OK( mp_init(&w)  );

     /*

     ** Convert stored PQG and public key into MPI integers.

     */

     SECITEM_TO_MPINT(key->params.prime,    &p);

     SECITEM_TO_MPINT(key->params.subPrime, &q);

     SECITEM_TO_MPINT(key->params.base,     &g);

     SECITEM_TO_MPINT(key->publicValue,     &y);

     /*

     ** Convert received signature (r', s') into MPI integers.

     */

     OCTETS_TO_MPINT(signature->data, &r_, dsa_subprime_len);

     OCTETS_TO_MPINT(signature->data + dsa_subprime_len, &s_, dsa_subprime_len);

     /*

     ** Verify that 0 < r' < q and 0 < s' < q

     */

     if (mp_cmp_z(&r_) <= 0 || mp_cmp_z(&s_) <= 0 ||

         mp_cmp(&r_, &q) >= 0 || mp_cmp(&s_, &q) >= 0) {

 	/* err is zero here. */

 	PORT_SetError(SEC_ERROR_BAD_SIGNATURE);

 	goto cleanup; /* will return verified == SECFailure */

     }

     /*

     ** FIPS 186-1, Section 6, Step 1

     **

     ** w = (s')**-1 mod q

     */

     CHECK_MPI_OK( mp_invmod(&s_, &q, &w) );      /* w = (s')**-1 mod q */

     /*

     ** FIPS 186-1, Section 6, Step 2

     **

     ** u1 = ((Hash(M')) * w) mod q

     */

     SECITEM_TO_MPINT(localDigest, &u1);              /* u1 = HASH(M')     */

     CHECK_MPI_OK( mp_mulmod(&u1, &w, &q, &u1) ); /* u1 = u1 * w mod q */

     /*

     ** FIPS 186-1, Section 6, Step 3

     **

     ** u2 = ((r') * w) mod q

     */

     CHECK_MPI_OK( mp_mulmod(&r_, &w, &q, &u2) );

     /*

     ** FIPS 186-1, Section 6, Step 4

     **

     ** v = ((g**u1 * y**u2) mod p) mod q

     */

     CHECK_MPI_OK( mp_exptmod(&g, &u1, &p, &g) ); /* g = g**u1 mod p */

     CHECK_MPI_OK( mp_exptmod(&y, &u2, &p, &y) ); /* y = y**u2 mod p */

     CHECK_MPI_OK(  mp_mulmod(&g, &y, &p, &v)  ); /* v = g * y mod p */

     CHECK_MPI_OK(     mp_mod(&v, &q, &v)      ); /* v = v mod q     */

     /*

     ** Verification:  v == r'

     */

     if (mp_cmp(&v, &r_)) {

 	PORT_SetError(SEC_ERROR_BAD_SIGNATURE);

 	verified = SECFailure; /* Signature failed to verify. */

     } else {

 	verified = SECSuccess; /* Signature verified. */

     }

 cleanup:

     mp_clear(&p);

     mp_clear(&q);

     mp_clear(&g);

     mp_clear(&y);

     mp_clear(&r_);

     mp_clear(&s_);

     mp_clear(&u1);

     mp_clear(&u2);

     mp_clear(&v);

     mp_clear(&w);

     if (err) {

 	translate_mpi_error(err);

     }

     return verified;

 }