302998 - We should check for zero DSA parameters x and k.

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Wan-Teh Chang]

The x and k parameters of DSA are specified to be
    0 < x < q
    0 < k < q

Our DSA code uses our RNG to generate parameters
x and k, but does not check for zero values.

The x and k values are computed by reducing the
160-bit output of the G function mod q.  So if the
output of the G function (built using SHA-1) happens
to be 0 or q, we get a zero.  The probability is
<= 2*2^-160 = 2^-159.

I also have a question: although FIPS 186-2 allows
x to be 1, if x is 1, y is g, whose discrete log
(base g) can be easily taken.  So I don't understand
why FIPS 186-2 allows an x of 1.

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

Let's disallow a value of 1 for variable x, also.

Comment 2

[Wan-Teh Chang]

I verified with a test that if the DSA_GenerateGlobalRandomBytes
call in DSA_NewKey fills the 'seed' array with zeros (so x=0), we
get a key pair with x=0 and y=1, and PK11_GenerateKeyPair returns
successfully.

If the DSA_GenerateGlobalRandomBytes call in DSA_SignDigest fills
the 'kSeed' array with zeros (so k=0), dsa_SignDigest fails with
SEC_ERROR_BAD_DATA (-8190) because the mp_invmod(&k, &q, &k) call
(which inverts k=0) fails with MP_RANGE (-3).

Comment 3

[Wan-Teh Chang]

Attachment: Proposed patch (diff -w)

This patch is generated with whitespace ignored (-w).

It disallows values of 0 and 1 for parameter x.

It disallows a value of 0 for parameter k.

It retries for 10 times.  The error code on failure is
SEC_ERROR_NEED_RANDOM, which may not be appropriate.

Comment 4

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 191282 [details] [diff] [review]
Proposed patch (diff -w)

r=nelson@bolyard.   

Here's a suggestion that you may ignore.

>+	for (i = 0; i <DSA_SUBPRIME_LEN-1; i++) {
>+	    if (seed[i] != 0) {
>+		good = PR_TRUE;
>+		break;
>+	    }
>+	}
>+	if (!good && seed[i] != 0 && seed[i] != 1) {

I'd prefer if that was:

 +	if (!good && seed[DSA_SUBPRIME_LEN-1] > 1) {

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

Comment 5

[Wan-Teh Chang]

Attachment: Patch as checked in (diff -w)

I implemented half of Nelson's suggestion
(change xxx != 0 && xxx != 1 to xxx > 1).

Comment 6

[Wan-Teh Chang]

Attachment: Patch as checked in

Comment 7

[Wan-Teh Chang]

Patch checked in on the NSS tip (NSS 3.11).

Checking in dsa.c;
/cvsroot/mozilla/security/nss/lib/freebl/dsa.c,v  <--  dsa.c
new revision: 1.18; previous revision: 1.17
done