We should check for zero DSA parameters x and k.

RESOLVED FIXED in 3.11

Status

NSS
Libraries
P1
normal
RESOLVED FIXED
12 years ago
12 years ago

People

(Reporter: Wan-Teh Chang, Assigned: Wan-Teh Chang)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(3 attachments)

(Assignee)

Description

12 years ago
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.
Let's disallow a value of 1 for variable x, also.
(Assignee)

Comment 2

12 years ago
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).
Status: NEW → ASSIGNED
Priority: -- → P1
Target Milestone: --- → 3.11
(Assignee)

Comment 3

12 years ago
Created attachment 191282 [details] [diff] [review]
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.
Attachment #191282 - Flags: review?(nelson)
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);
Attachment #191282 - Flags: review?(nelson) → review+
(Assignee)

Comment 5

12 years ago
Created attachment 199240 [details] [diff] [review]
Patch as checked in (diff -w)

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

Comment 6

12 years ago
Created attachment 199241 [details] [diff] [review]
Patch as checked in
(Assignee)

Comment 7

12 years ago
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
Status: ASSIGNED → RESOLVED
Last Resolved: 12 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.