/src/nss/lib/freebl/dsa.c

Source (jump to first uncovered line)
/*
 *
 * 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 "blapit.h"
#include "mpi.h"
#include "secmpi.h"
#include "pqg.h"

/*
 * 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_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_ZfreeItem(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_ZfreeItem(&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 *kbytes)
{
    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_int t;       /* holding tmp values */
    mp_int ar;      /* holding blinding values */
    mp_digit fuzz;  /* blinding multiplier for q */
    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];
    SECItem t2 = { siBuffer, NULL, 0 };

    /* 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;
    MP_DIGITS(&t) = 0;
    MP_DIGITS(&ar) = 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));
    CHECK_MPI_OK(mp_init(&t));
    CHECK_MPI_OK(mp_init(&ar));

    /*
    ** 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(kbytes, &k, dsa_subprime_len);

    /* k blinding  create a single value that has the high bit set in
     * the mp_digit*/
    if (RNG_GenerateGlobalRandomBytes(&fuzz, sizeof(mp_digit)) != SECSuccess) {
        PORT_SetError(SEC_ERROR_NEED_RANDOM);
        rv = SECFailure;
        goto cleanup;
    }
    fuzz |= 1ULL << ((sizeof(mp_digit) * PR_BITS_PER_BYTE - 1));
    /*
    ** FIPS 186-1, Section 5, Step 1
    **
    ** r = (g**k mod p) mod q
    */
    CHECK_MPI_OK(mp_mul_d(&q, fuzz, &t)); /* t = q*fuzz */
    CHECK_MPI_OK(mp_add(&k, &t, &t));     /* t = k+q*fuzz */
    /* length of t is now fixed, bits in k have been blinded */
    CHECK_MPI_OK(mp_exptmod(&g, &t, &p, &r)); /* r = g**t mod p */
    /* r is now g**(k+q*fuzz) == g**k mod p */
    CHECK_MPI_OK(mp_mod(&r, &q, &r)); /* r = r mod q    */
    /* make sure fuzz is cleared off the stack and not optimized away */
    *(volatile mp_digit *)&fuzz = 0;

    /*
    ** FIPS 186-1, Section 5, Step 2
    **
    ** s = (k**-1 * (HASH(M) + x*r)) mod q
    */
    if (DSA_NewRandom(NULL, &key->params.subPrime, &t2) != SECSuccess) {
        PORT_SetError(SEC_ERROR_NEED_RANDOM);
        rv = SECFailure;
        goto cleanup;
    }
    SECITEM_TO_MPINT(t2, &t); /* t <-$ Zq */
    SECITEM_ZfreeItem(&t2, PR_FALSE);
    if (DSA_NewRandom(NULL, &key->params.subPrime, &t2) != SECSuccess) {
        PORT_SetError(SEC_ERROR_NEED_RANDOM);
        rv = SECFailure;
        goto cleanup;
    }
    SECITEM_TO_MPINT(t2, &ar); /* ar <-$ Zq */
    SECITEM_ZfreeItem(&t2, PR_FALSE);

    /* Using mp_invmod on k directly would leak bits from k. */
    CHECK_MPI_OK(mp_mul(&k, &ar, &k));       /* k = k * ar */
    CHECK_MPI_OK(mp_mulmod(&k, &t, &q, &k)); /* k = k * t mod q */
    /* k is now k*t*ar */
    CHECK_MPI_OK(mp_invmod(&k, &q, &k)); /* k = k**-1 mod q */
    /* k is now (k*t*ar)**-1 */
    CHECK_MPI_OK(mp_mulmod(&k, &t, &q, &k)); /* k = k * t mod q */
    /* k is now (k*ar)**-1 */
    SECITEM_TO_MPINT(localDigest, &s); /* s = HASH(M)     */
    /* To avoid leaking secret bits here the addition is blinded. */
    CHECK_MPI_OK(mp_mul(&x, &ar, &x)); /* x = x * ar */
    /* x is now x*ar */
    CHECK_MPI_OK(mp_mulmod(&x, &r, &q, &x)); /* x = x * r mod q */
    /* x is now x*r*ar */
    CHECK_MPI_OK(mp_mulmod(&s, &ar, &q, &t)); /* t = s * ar mod q */
    /* t is now hash(M)*ar */
    CHECK_MPI_OK(mp_add(&t, &x, &s)); /* s = t + x */
    /* s is now (HASH(M)+x*r)*ar */
    CHECK_MPI_OK(mp_mulmod(&s, &k, &q, &s)); /* s = s * k mod q */
    /* s is now (HASH(M)+x*r)*ar*(k*ar)**-1 = (k**-1)*(HASH(M)+x*r) */

    /*
    ** 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_SafeZero(localDigestData, 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);
    mp_clear(&t);
    mp_clear(&ar);
    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);
    PORT_SafeZero(kSeed, sizeof kSeed);
    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;
    unsigned 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:
    PORT_SafeZero(localDigestData, sizeof localDigestData);
    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;
}

Coverage Report

Created: 2025-07-01 06:25

Line	Count	Source (jump to first uncovered line)
1		/*
2		*
3		* This Source Code Form is subject to the terms of the Mozilla Public
4		* License, v. 2.0. If a copy of the MPL was not distributed with this
5		* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7		#ifdef FREEBL_NO_DEPEND
8		#include "stubs.h"
9		#endif
10
11		#include "prerror.h"
12		#include "secerr.h"
13
14		#include "prtypes.h"
15		#include "prinit.h"
16		#include "blapi.h"
17		#include "nssilock.h"
18		#include "secitem.h"
19		#include "blapit.h"
20		#include "mpi.h"
21		#include "secmpi.h"
22		#include "pqg.h"
23
24		/*
25		* FIPS 186-2 requires result from random output to be reduced mod q when
26		* generating random numbers for DSA.
27		*
28		* Input: w, 2*qLen bytes
29		* q, qLen bytes
30		* Output: xj, qLen bytes
31		*/
32		static SECStatus
33		fips186Change_ReduceModQForDSA(const PRUint8 w, const PRUint8 q,
34		unsigned int qLen, PRUint8 *xj)
35	0	{
36	0	mp_int W, Q, Xj;
37	0	mp_err err;
38	0	SECStatus rv = SECSuccess;
39
40		/* Initialize MPI integers. */
41	0	MP_DIGITS(&W) = 0;
42	0	MP_DIGITS(&Q) = 0;
43	0	MP_DIGITS(&Xj) = 0;
44	0	CHECK_MPI_OK(mp_init(&W));
45	0	CHECK_MPI_OK(mp_init(&Q));
46	0	CHECK_MPI_OK(mp_init(&Xj));
47		/*
48		* Convert input arguments into MPI integers.
49		*/
50	0	CHECK_MPI_OK(mp_read_unsigned_octets(&W, w, 2 * qLen));
51	0	CHECK_MPI_OK(mp_read_unsigned_octets(&Q, q, qLen));
52
53		/*
54		* Algorithm 1 of FIPS 186-2 Change Notice 1, Step 3.3
55		*
56		* xj = (w0 \|\| w1) mod q
57		*/
58	0	CHECK_MPI_OK(mp_mod(&W, &Q, &Xj));
59	0	CHECK_MPI_OK(mp_to_fixlen_octets(&Xj, xj, qLen));
60	0	cleanup:
61	0	mp_clear(&W);
62	0	mp_clear(&Q);
63	0	mp_clear(&Xj);
64	0	if (err) {
65	0	MP_TO_SEC_ERROR(err);
66	0	rv = SECFailure;
67	0	}
68	0	return rv;
69	0	}
70
71		/*
72		* FIPS 186-2 requires result from random output to be reduced mod q when
73		* generating random numbers for DSA.
74		*/
75		SECStatus
76		FIPS186Change_ReduceModQForDSA(const unsigned char *w,
77		const unsigned char *q,
78		unsigned char *xj)
79	0	{
80	0	return fips186Change_ReduceModQForDSA(w, q, DSA1_SUBPRIME_LEN, xj);
81	0	}
82
83		/*
84		* The core of Algorithm 1 of FIPS 186-2 Change Notice 1.
85		*
86		* We no longer support FIPS 186-2 RNG. This function was exported
87		* for power-up self tests and FIPS tests. Keep this stub, which fails,
88		* to prevent crashes, but also to signal to test code that FIPS 186-2
89		* RNG is no longer supported.
90		*/
91		SECStatus
92		FIPS186Change_GenerateX(PRUint8 XKEY, const PRUint8 XSEEDj,
93		PRUint8 *x_j)
94	0	{
95	0	PORT_SetError(PR_NOT_IMPLEMENTED_ERROR);
96	0	return SECFailure;
97	0	}
98
99		/*
100		* Specialized RNG for DSA
101		*
102		* As per Algorithm 1 of FIPS 186-2 Change Notice 1, in step 3.3 the value
103		* Xj should be reduced mod q, a 160-bit prime number. Since this parameter
104		* is only meaningful in the context of DSA, the above RNG functions
105		* were implemented without it. They are re-implemented below for use
106		* with DSA.
107		*/
108
109		/*
110		** Generate some random bytes, using the global random number generator
111		** object. In DSA mode, so there is a q.
112		*/
113		static SECStatus
114		dsa_GenerateGlobalRandomBytes(const SECItem qItem, PRUint8 dest,
115		unsigned int *destLen, unsigned int maxDestLen)
116	0	{
117	0	SECStatus rv;
118	0	SECItem w;
119	0	const PRUint8 *q = qItem->data;
120	0	unsigned int qLen = qItem->len;
121
122	0	if (*q == 0) {
123	0	++q;
124	0	--qLen;
125	0	}
126	0	if (maxDestLen < qLen) {
127		/* This condition can occur when DSA_SignDigest is passed a group
128		with a subprime that is larger than DSA_MAX_SUBPRIME_LEN. */
129	0	PORT_SetError(SEC_ERROR_INVALID_ARGS);
130	0	return SECFailure;
131	0	}
132	0	w.data = NULL; /* otherwise SECITEM_AllocItem asserts */
133	0	if (!SECITEM_AllocItem(NULL, &w, 2 * qLen)) {
134	0	return SECFailure;
135	0	}
136	0	*destLen = qLen;
137
138	0	rv = RNG_GenerateGlobalRandomBytes(w.data, w.len);
139	0	if (rv == SECSuccess) {
140	0	rv = fips186Change_ReduceModQForDSA(w.data, q, qLen, dest);
141	0	}
142
143	0	SECITEM_FreeItem(&w, PR_FALSE);
144	0	return rv;
145	0	}
146
147		static void
148		translate_mpi_error(mp_err err)
149	0	{
150	0	MP_TO_SEC_ERROR(err);
151	0	}
152
153		static SECStatus
154		dsa_NewKeyExtended(const PQGParams params, const SECItem seed,
155		DSAPrivateKey **privKey)
156	0	{
157	0	mp_int p, g;
158	0	mp_int x, y;
159	0	mp_err err;
160	0	PLArenaPool *arena;
161	0	DSAPrivateKey *key;
162		/* Check args. */
163	0	if (!params \|\| !privKey \|\| !seed \|\| !seed->data) {
164	0	PORT_SetError(SEC_ERROR_INVALID_ARGS);
165	0	return SECFailure;
166	0	}
167		/* Initialize an arena for the DSA key. */
168	0	arena = PORT_NewArena(NSS_FREEBL_DEFAULT_CHUNKSIZE);
169	0	if (!arena) {
170	0	PORT_SetError(SEC_ERROR_NO_MEMORY);
171	0	return SECFailure;
172	0	}
173	0	key = (DSAPrivateKey *)PORT_ArenaZAlloc(arena, sizeof(DSAPrivateKey));
174	0	if (!key) {
175	0	PORT_SetError(SEC_ERROR_NO_MEMORY);
176	0	PORT_FreeArena(arena, PR_TRUE);
177	0	return SECFailure;
178	0	}
179	0	key->params.arena = arena;
180		/* Initialize MPI integers. */
181	0	MP_DIGITS(&p) = 0;
182	0	MP_DIGITS(&g) = 0;
183	0	MP_DIGITS(&x) = 0;
184	0	MP_DIGITS(&y) = 0;
185	0	CHECK_MPI_OK(mp_init(&p));
186	0	CHECK_MPI_OK(mp_init(&g));
187	0	CHECK_MPI_OK(mp_init(&x));
188	0	CHECK_MPI_OK(mp_init(&y));
189		/* Copy over the PQG params */
190	0	CHECK_MPI_OK(SECITEM_CopyItem(arena, &key->params.prime,
191	0	&params->prime));
192	0	CHECK_MPI_OK(SECITEM_CopyItem(arena, &key->params.subPrime,
193	0	&params->subPrime));
194	0	CHECK_MPI_OK(SECITEM_CopyItem(arena, &key->params.base, &params->base));
195		/* Convert stored p, g, and received x into MPI integers. */
196	0	SECITEM_TO_MPINT(params->prime, &p);
197	0	SECITEM_TO_MPINT(params->base, &g);
198	0	OCTETS_TO_MPINT(seed->data, &x, seed->len);
199		/* Store x in private key */
200	0	SECITEM_AllocItem(arena, &key->privateValue, seed->len);
201	0	PORT_Memcpy(key->privateValue.data, seed->data, seed->len);
202		/* Compute public key y = g*x mod p /
203	0	CHECK_MPI_OK(mp_exptmod(&g, &x, &p, &y));
204		/* Store y in public key */
205	0	MPINT_TO_SECITEM(&y, &key->publicValue, arena);
206	0	*privKey = key;
207	0	key = NULL;
208	0	cleanup:
209	0	mp_clear(&p);
210	0	mp_clear(&g);
211	0	mp_clear(&x);
212	0	mp_clear(&y);
213	0	if (key) {
214	0	PORT_FreeArena(key->params.arena, PR_TRUE);
215	0	}
216	0	if (err) {
217	0	translate_mpi_error(err);
218	0	return SECFailure;
219	0	}
220	0	return SECSuccess;
221	0	}
222
223		SECStatus
224		DSA_NewRandom(PLArenaPool arena, const SECItem q, SECItem *seed)
225	0	{
226	0	int retries = 10;
227	0	unsigned int i;
228	0	PRBool good;
229
230	0	if (q == NULL \|\| q->data == NULL \|\| q->len == 0 \|\|
231	0	(q->data[0] == 0 && q->len == 1)) {
232	0	PORT_SetError(SEC_ERROR_INVALID_ARGS);
233	0	return SECFailure;
234	0	}
235
236	0	if (!SECITEM_AllocItem(arena, seed, q->len)) {
237	0	return SECFailure;
238	0	}
239
240	0	do {
241		/* Generate seed bytes for x according to FIPS 186-1 appendix 3 */
242	0	if (dsa_GenerateGlobalRandomBytes(q, seed->data, &seed->len,
243	0	seed->len)) {
244	0	goto loser;
245	0	}
246		/* Disallow values of 0 and 1 for x. */
247	0	good = PR_FALSE;
248	0	for (i = 0; i < seed->len - 1; i++) {
249	0	if (seed->data[i] != 0) {
250	0	good = PR_TRUE;
251	0	break;
252	0	}
253	0	}
254	0	if (!good && seed->data[i] > 1) {
255	0	good = PR_TRUE;
256	0	}
257	0	} while (!good && --retries > 0);
258
259	0	if (!good) {
260	0	PORT_SetError(SEC_ERROR_NEED_RANDOM);
261	0	loser:
262	0	if (arena != NULL) {
263	0	SECITEM_ZfreeItem(seed, PR_FALSE);
264	0	}
265	0	return SECFailure;
266	0	}
267
268	0	return SECSuccess;
269	0	}
270
271		/*
272		** Generate and return a new DSA public and private key pair,
273		** both of which are encoded into a single DSAPrivateKey struct.
274		** "params" is a pointer to the PQG parameters for the domain
275		** Uses a random seed.
276		*/
277		SECStatus
278		DSA_NewKey(const PQGParams params, DSAPrivateKey *privKey)
279	0	{
280	0	SECItem seed;
281	0	SECStatus rv;
282
283	0	rv = PQG_Check(params);
284	0	if (rv != SECSuccess) {
285	0	return rv;
286	0	}
287	0	seed.data = NULL;
288
289	0	rv = DSA_NewRandom(NULL, &params->subPrime, &seed);
290	0	if (rv == SECSuccess) {
291	0	if (seed.len != PQG_GetLength(&params->subPrime)) {
292	0	PORT_SetError(SEC_ERROR_INVALID_ARGS);
293	0	rv = SECFailure;
294	0	} else {
295	0	rv = dsa_NewKeyExtended(params, &seed, privKey);
296	0	}
297	0	}
298	0	SECITEM_ZfreeItem(&seed, PR_FALSE);
299	0	return rv;
300	0	}
301
302		/* For FIPS compliance testing. Seed must be exactly the size of subPrime */
303		SECStatus
304		DSA_NewKeyFromSeed(const PQGParams *params,
305		const unsigned char *seed,
306		DSAPrivateKey **privKey)
307	0	{
308	0	SECItem seedItem;
309	0	seedItem.data = (unsigned char *)seed;
310	0	seedItem.len = PQG_GetLength(&params->subPrime);
311	0	return dsa_NewKeyExtended(params, &seedItem, privKey);
312	0	}
313
314		static SECStatus
315		dsa_SignDigest(DSAPrivateKey key, SECItem signature, const SECItem *digest,
316		const unsigned char *kbytes)
317	0	{
318	0	mp_int p, q, g; /* PQG parameters */
319	0	mp_int x, k; /* private key & pseudo-random integer */
320	0	mp_int r, s; /* tuple (r, s) is signature) */
321	0	mp_int t; /* holding tmp values */
322	0	mp_int ar; /* holding blinding values */
323	0	mp_digit fuzz; /* blinding multiplier for q */
324	0	mp_err err = MP_OKAY;
325	0	SECStatus rv = SECSuccess;
326	0	unsigned int dsa_subprime_len, dsa_signature_len, offset;
327	0	SECItem localDigest;
328	0	unsigned char localDigestData[DSA_MAX_SUBPRIME_LEN];
329	0	SECItem t2 = { siBuffer, NULL, 0 };
330
331		/* FIPS-compliance dictates that digest is a SHA hash. */
332		/* Check args. */
333	0	if (!key \|\| !signature \|\| !digest) {
334	0	PORT_SetError(SEC_ERROR_INVALID_ARGS);
335	0	return SECFailure;
336	0	}
337
338	0	dsa_subprime_len = PQG_GetLength(&key->params.subPrime);
339	0	dsa_signature_len = dsa_subprime_len * 2;
340	0	if ((signature->len < dsa_signature_len) \|\|
341	0	(digest->len > HASH_LENGTH_MAX) \|\|
342	0	(digest->len < SHA1_LENGTH)) {
343	0	PORT_SetError(SEC_ERROR_INVALID_ARGS);
344	0	return SECFailure;
345	0	}
346
347		/* DSA accepts digests not equal to dsa_subprime_len, if the
348		* digests are greater, then they are truncated to the size of
349		* dsa_subprime_len, using the left most bits. If they are less
350		* then they are padded on the left.*/
351	0	PORT_Memset(localDigestData, 0, dsa_subprime_len);
352	0	offset = (digest->len < dsa_subprime_len) ? (dsa_subprime_len - digest->len) : 0;
353	0	PORT_Memcpy(localDigestData + offset, digest->data,
354	0	dsa_subprime_len - offset);
355	0	localDigest.data = localDigestData;
356	0	localDigest.len = dsa_subprime_len;
357
358		/* Initialize MPI integers. */
359	0	MP_DIGITS(&p) = 0;
360	0	MP_DIGITS(&q) = 0;
361	0	MP_DIGITS(&g) = 0;
362	0	MP_DIGITS(&x) = 0;
363	0	MP_DIGITS(&k) = 0;
364	0	MP_DIGITS(&r) = 0;
365	0	MP_DIGITS(&s) = 0;
366	0	MP_DIGITS(&t) = 0;
367	0	MP_DIGITS(&ar) = 0;
368	0	CHECK_MPI_OK(mp_init(&p));
369	0	CHECK_MPI_OK(mp_init(&q));
370	0	CHECK_MPI_OK(mp_init(&g));
371	0	CHECK_MPI_OK(mp_init(&x));
372	0	CHECK_MPI_OK(mp_init(&k));
373	0	CHECK_MPI_OK(mp_init(&r));
374	0	CHECK_MPI_OK(mp_init(&s));
375	0	CHECK_MPI_OK(mp_init(&t));
376	0	CHECK_MPI_OK(mp_init(&ar));
377
378		/*
379		** Convert stored PQG and private key into MPI integers.
380		*/
381	0	SECITEM_TO_MPINT(key->params.prime, &p);
382	0	SECITEM_TO_MPINT(key->params.subPrime, &q);
383	0	SECITEM_TO_MPINT(key->params.base, &g);
384	0	SECITEM_TO_MPINT(key->privateValue, &x);
385	0	OCTETS_TO_MPINT(kbytes, &k, dsa_subprime_len);
386
387		/* k blinding create a single value that has the high bit set in
388		* the mp_digit*/
389	0	if (RNG_GenerateGlobalRandomBytes(&fuzz, sizeof(mp_digit)) != SECSuccess) {
390	0	PORT_SetError(SEC_ERROR_NEED_RANDOM);
391	0	rv = SECFailure;
392	0	goto cleanup;
393	0	}
394	0	fuzz \|= 1ULL << ((sizeof(mp_digit) * PR_BITS_PER_BYTE - 1));
395		/*
396		** FIPS 186-1, Section 5, Step 1
397		**
398		r = (gk mod p) mod q
399		*/
400	0	CHECK_MPI_OK(mp_mul_d(&q, fuzz, &t)); /* t = qfuzz /
401	0	CHECK_MPI_OK(mp_add(&k, &t, &t)); /* t = k+qfuzz /
402		/* length of t is now fixed, bits in k have been blinded */
403	0	CHECK_MPI_OK(mp_exptmod(&g, &t, &p, &r)); /* r = g*t mod p /
404		/* r is now g*(k+qfuzz) == g*k mod p /
405	0	CHECK_MPI_OK(mp_mod(&r, &q, &r)); /* r = r mod q */
406		/* make sure fuzz is cleared off the stack and not optimized away */
407	0	(volatile mp_digit )&fuzz = 0;
408
409		/*
410		** FIPS 186-1, Section 5, Step 2
411		**
412		s = (k-1 * (HASH(M) + x*r)) mod q
413		*/
414	0	if (DSA_NewRandom(NULL, &key->params.subPrime, &t2) != SECSuccess) {
415	0	PORT_SetError(SEC_ERROR_NEED_RANDOM);
416	0	rv = SECFailure;
417	0	goto cleanup;
418	0	}
419	0	SECITEM_TO_MPINT(t2, &t); /* t <-$ Zq */
420	0	SECITEM_ZfreeItem(&t2, PR_FALSE);
421	0	if (DSA_NewRandom(NULL, &key->params.subPrime, &t2) != SECSuccess) {
422	0	PORT_SetError(SEC_ERROR_NEED_RANDOM);
423	0	rv = SECFailure;
424	0	goto cleanup;
425	0	}
426	0	SECITEM_TO_MPINT(t2, &ar); /* ar <-$ Zq */
427	0	SECITEM_ZfreeItem(&t2, PR_FALSE);
428
429		/* Using mp_invmod on k directly would leak bits from k. */
430	0	CHECK_MPI_OK(mp_mul(&k, &ar, &k)); /* k = k * ar */
431	0	CHECK_MPI_OK(mp_mulmod(&k, &t, &q, &k)); /* k = k * t mod q */
432		/* k is now ktar */
433	0	CHECK_MPI_OK(mp_invmod(&k, &q, &k)); /* k = k*-1 mod q /
434		/* k is now (ktar)*-1 /
435	0	CHECK_MPI_OK(mp_mulmod(&k, &t, &q, &k)); /* k = k * t mod q */
436		/* k is now (kar)-1 /
437	0	SECITEM_TO_MPINT(localDigest, &s); /* s = HASH(M) */
438		/* To avoid leaking secret bits here the addition is blinded. */
439	0	CHECK_MPI_OK(mp_mul(&x, &ar, &x)); /* x = x * ar */
440		/* x is now xar /
441	0	CHECK_MPI_OK(mp_mulmod(&x, &r, &q, &x)); /* x = x * r mod q */
442		/* x is now xrar */
443	0	CHECK_MPI_OK(mp_mulmod(&s, &ar, &q, &t)); /* t = s * ar mod q */
444		/* t is now hash(M)ar /
445	0	CHECK_MPI_OK(mp_add(&t, &x, &s)); /* s = t + x */
446		/* s is now (HASH(M)+xr)ar */
447	0	CHECK_MPI_OK(mp_mulmod(&s, &k, &q, &s)); /* s = s * k mod q */
448		/* s is now (HASH(M)+xr)ar(kar)-1 = (k-1)(HASH(M)+xr) */
449
450		/*
451		** verify r != 0 and s != 0
452		** mentioned as optional in FIPS 186-1.
453		*/
454	0	if (mp_cmp_z(&r) == 0 \|\| mp_cmp_z(&s) == 0) {
455	0	PORT_SetError(SEC_ERROR_NEED_RANDOM);
456	0	rv = SECFailure;
457	0	goto cleanup;
458	0	}
459		/*
460		** Step 4
461		**
462		** Signature is tuple (r, s)
463		*/
464	0	err = mp_to_fixlen_octets(&r, signature->data, dsa_subprime_len);
465	0	if (err < 0)
466	0	goto cleanup;
467	0	err = mp_to_fixlen_octets(&s, signature->data + dsa_subprime_len,
468	0	dsa_subprime_len);
469	0	if (err < 0)
470	0	goto cleanup;
471	0	err = MP_OKAY;
472	0	signature->len = dsa_signature_len;
473	0	cleanup:
474	0	PORT_SafeZero(localDigestData, DSA_MAX_SUBPRIME_LEN);
475	0	mp_clear(&p);
476	0	mp_clear(&q);
477	0	mp_clear(&g);
478	0	mp_clear(&x);
479	0	mp_clear(&k);
480	0	mp_clear(&r);
481	0	mp_clear(&s);
482	0	mp_clear(&t);
483	0	mp_clear(&ar);
484	0	if (err) {
485	0	translate_mpi_error(err);
486	0	rv = SECFailure;
487	0	}
488	0	return rv;
489	0	}
490
491		/* signature is caller-supplied buffer of at least 40 bytes.
492		** On input, signature->len == size of buffer to hold signature.
493		** digest->len == size of digest.
494		** On output, signature->len == size of signature in buffer.
495		** Uses a random seed.
496		*/
497		SECStatus
498		DSA_SignDigest(DSAPrivateKey key, SECItem signature, const SECItem *digest)
499	0	{
500	0	SECStatus rv;
501	0	int retries = 10;
502	0	unsigned char kSeed[DSA_MAX_SUBPRIME_LEN];
503	0	unsigned int kSeedLen = 0;
504	0	unsigned int i;
505	0	unsigned int dsa_subprime_len = PQG_GetLength(&key->params.subPrime);
506	0	PRBool good;
507
508	0	PORT_SetError(0);
509	0	do {
510	0	rv = dsa_GenerateGlobalRandomBytes(&key->params.subPrime,
511	0	kSeed, &kSeedLen, sizeof kSeed);
512	0	if (rv != SECSuccess)
513	0	break;
514	0	if (kSeedLen != dsa_subprime_len) {
515	0	PORT_SetError(SEC_ERROR_INVALID_ARGS);
516	0	rv = SECFailure;
517	0	break;
518	0	}
519		/* Disallow a value of 0 for k. */
520	0	good = PR_FALSE;
521	0	for (i = 0; i < kSeedLen; i++) {
522	0	if (kSeed[i] != 0) {
523	0	good = PR_TRUE;
524	0	break;
525	0	}
526	0	}
527	0	if (!good) {
528	0	PORT_SetError(SEC_ERROR_NEED_RANDOM);
529	0	rv = SECFailure;
530	0	continue;
531	0	}
532	0	rv = dsa_SignDigest(key, signature, digest, kSeed);
533	0	} while (rv != SECSuccess && PORT_GetError() == SEC_ERROR_NEED_RANDOM &&
534	0	--retries > 0);
535	0	PORT_SafeZero(kSeed, sizeof kSeed);
536	0	return rv;
537	0	}
538
539		/* For FIPS compliance testing. Seed must be exactly 20 bytes. */
540		SECStatus
541		DSA_SignDigestWithSeed(DSAPrivateKey *key,
542		SECItem *signature,
543		const SECItem *digest,
544		const unsigned char *seed)
545	0	{
546	0	SECStatus rv;
547	0	rv = dsa_SignDigest(key, signature, digest, seed);
548	0	return rv;
549	0	}
550
551		/* signature is caller-supplied buffer of at least 20 bytes.
552		** On input, signature->len == size of buffer to hold signature.
553		** digest->len == size of digest.
554		*/
555		SECStatus
556		DSA_VerifyDigest(DSAPublicKey key, const SECItem signature,
557		const SECItem *digest)
558	0	{
559		/* FIPS-compliance dictates that digest is a SHA hash. */
560	0	mp_int p, q, g; /* PQG parameters */
561	0	mp_int r_, s_; /* tuple (r', s') is received signature) */
562	0	mp_int u1, u2, v, w; /* intermediate values used in verification */
563	0	mp_int y; /* public key */
564	0	mp_err err;
565	0	unsigned int dsa_subprime_len, dsa_signature_len, offset;
566	0	SECItem localDigest;
567	0	unsigned char localDigestData[DSA_MAX_SUBPRIME_LEN];
568	0	SECStatus verified = SECFailure;
569
570		/* Check args. */
571	0	if (!key \|\| !signature \|\| !digest) {
572	0	PORT_SetError(SEC_ERROR_INVALID_ARGS);
573	0	return SECFailure;
574	0	}
575
576	0	dsa_subprime_len = PQG_GetLength(&key->params.subPrime);
577	0	dsa_signature_len = dsa_subprime_len * 2;
578	0	if ((signature->len != dsa_signature_len) \|\|
579	0	(digest->len > HASH_LENGTH_MAX) \|\|
580	0	(digest->len < SHA1_LENGTH)) {
581	0	PORT_SetError(SEC_ERROR_INVALID_ARGS);
582	0	return SECFailure;
583	0	}
584
585		/* DSA accepts digests not equal to dsa_subprime_len, if the
586		* digests are greater, than they are truncated to the size of
587		* dsa_subprime_len, using the left most bits. If they are less
588		* then they are padded on the left.*/
589	0	PORT_Memset(localDigestData, 0, dsa_subprime_len);
590	0	offset = (digest->len < dsa_subprime_len) ? (dsa_subprime_len - digest->len) : 0;
591	0	PORT_Memcpy(localDigestData + offset, digest->data,
592	0	dsa_subprime_len - offset);
593	0	localDigest.data = localDigestData;
594	0	localDigest.len = dsa_subprime_len;
595
596		/* Initialize MPI integers. */
597	0	MP_DIGITS(&p) = 0;
598	0	MP_DIGITS(&q) = 0;
599	0	MP_DIGITS(&g) = 0;
600	0	MP_DIGITS(&y) = 0;
601	0	MP_DIGITS(&r_) = 0;
602	0	MP_DIGITS(&s_) = 0;
603	0	MP_DIGITS(&u1) = 0;
604	0	MP_DIGITS(&u2) = 0;
605	0	MP_DIGITS(&v) = 0;
606	0	MP_DIGITS(&w) = 0;
607	0	CHECK_MPI_OK(mp_init(&p));
608	0	CHECK_MPI_OK(mp_init(&q));
609	0	CHECK_MPI_OK(mp_init(&g));
610	0	CHECK_MPI_OK(mp_init(&y));
611	0	CHECK_MPI_OK(mp_init(&r_));
612	0	CHECK_MPI_OK(mp_init(&s_));
613	0	CHECK_MPI_OK(mp_init(&u1));
614	0	CHECK_MPI_OK(mp_init(&u2));
615	0	CHECK_MPI_OK(mp_init(&v));
616	0	CHECK_MPI_OK(mp_init(&w));
617		/*
618		** Convert stored PQG and public key into MPI integers.
619		*/
620	0	SECITEM_TO_MPINT(key->params.prime, &p);
621	0	SECITEM_TO_MPINT(key->params.subPrime, &q);
622	0	SECITEM_TO_MPINT(key->params.base, &g);
623	0	SECITEM_TO_MPINT(key->publicValue, &y);
624		/*
625		** Convert received signature (r', s') into MPI integers.
626		*/
627	0	OCTETS_TO_MPINT(signature->data, &r_, dsa_subprime_len);
628	0	OCTETS_TO_MPINT(signature->data + dsa_subprime_len, &s_, dsa_subprime_len);
629		/*
630		** Verify that 0 < r' < q and 0 < s' < q
631		*/
632	0	if (mp_cmp_z(&r_) <= 0 \|\| mp_cmp_z(&s_) <= 0 \|\|
633	0	mp_cmp(&r_, &q) >= 0 \|\| mp_cmp(&s_, &q) >= 0) {
634		/* err is zero here. */
635	0	PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
636	0	goto cleanup; /* will return verified == SECFailure */
637	0	}
638		/*
639		** FIPS 186-1, Section 6, Step 1
640		**
641		w = (s')-1 mod q
642		*/
643	0	CHECK_MPI_OK(mp_invmod(&s_, &q, &w)); /* w = (s')*-1 mod q /
644		/*
645		** FIPS 186-1, Section 6, Step 2
646		**
647		** u1 = ((Hash(M')) * w) mod q
648		*/
649	0	SECITEM_TO_MPINT(localDigest, &u1); /* u1 = HASH(M') */
650	0	CHECK_MPI_OK(mp_mulmod(&u1, &w, &q, &u1)); /* u1 = u1 * w mod q */
651		/*
652		** FIPS 186-1, Section 6, Step 3
653		**
654		** u2 = ((r') * w) mod q
655		*/
656	0	CHECK_MPI_OK(mp_mulmod(&r_, &w, &q, &u2));
657		/*
658		** FIPS 186-1, Section 6, Step 4
659		**
660		v = ((gu1 * y**u2) mod p) mod q
661		*/
662	0	CHECK_MPI_OK(mp_exptmod(&g, &u1, &p, &g)); /* g = g*u1 mod p /
663	0	CHECK_MPI_OK(mp_exptmod(&y, &u2, &p, &y)); /* y = y*u2 mod p /
664	0	CHECK_MPI_OK(mp_mulmod(&g, &y, &p, &v)); /* v = g * y mod p */
665	0	CHECK_MPI_OK(mp_mod(&v, &q, &v)); /* v = v mod q */
666		/*
667		** Verification: v == r'
668		*/
669	0	if (mp_cmp(&v, &r_)) {
670	0	PORT_SetError(SEC_ERROR_BAD_SIGNATURE);
671	0	verified = SECFailure; /* Signature failed to verify. */
672	0	} else {
673	0	verified = SECSuccess; /* Signature verified. */
674	0	}
675	0	cleanup:
676	0	PORT_SafeZero(localDigestData, sizeof localDigestData);
677	0	mp_clear(&p);
678	0	mp_clear(&q);
679	0	mp_clear(&g);
680	0	mp_clear(&y);
681	0	mp_clear(&r_);
682	0	mp_clear(&s_);
683	0	mp_clear(&u1);
684	0	mp_clear(&u2);
685	0	mp_clear(&v);
686	0	mp_clear(&w);
687	0	if (err) {
688	0	translate_mpi_error(err);
689	0	}
690	0	return verified;
691	0	}