326754 - Two minor bugs with the 'h' parameter in PQG_ParamGenSeedLen

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P2)

Description

[Wan-Teh Chang]

While reviewing the code of lib/freebl/pqg.c, I
found two minor bugs related to the 'h' parameter
in PQG_ParamGenSeedLen.

Comment 1

[Wan-Teh Chang]

Attachment: Proposed patch

Please refer to FIPS 186-2.

This patch fixes two bugs.

1. The constraint on h is 1 < h < p-1.  See FIPS 186-2
Sec. 4, item 3 on page 8.  So we should disallow
h >= p-1 rather than h > p-1.

(The seemingly misaligned comment is caused by the
tab character at the beginning of that line.)

2. The size of the auxiliary SECItem 'hit' is wrong:

    /* Generate h. */
    SECITEM_AllocItem(NULL, &hit, seedBytes); /* h is no longer than p */

I got suspicious when the comment doesn't seem to
match the code.  Recall that SEED only needs to be
at least 160 bits, and has no relation to the length
of p.  See FIPS 186-2, Appendix 2.2, Step 1 on page
14.

So I think 'seedBytes' should be changed to 'L/8',
where 'L' is the length of p in bits.  See FIPS 186-2
Sec. 4, item 1 on page 8.

Comment 2

[Nelson Bolyard (seldom reads bugmail)]

Good catch.  How many FIPS reviews have missed these two bugs?   :-)

Comment 3

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 211448 [details] [diff] [review]
Proposed patch

SR=Nelson.  This patch appears correct, but 
I wonder if this patch will slow down PQG param generation.

Comment 4

[Wan-Teh Chang]

If we are worried about performance, we have two options.

1. Use fixed h=2.  (h doesn't need to be random.)

2. I can also do:

     /* Generate h. */
-    SECITEM_AllocItem(NULL, &hit, seedBytes); /* h is no longer than p */
+    SECITEM_AllocItem(NULL, &hit, PR_MIN(seedBytes, L/8)); /* h is no longer than p */

Since seedBytes can be arbitrarily long, we must make
sure H is no longer than p, otherwise the H mod (p-1)
operation can't be implemented as a subtraction.

Would you like me to do #2?

Comment 5

[Nelson Bolyard (seldom reads bugmail)]

I think that PQG generation is done infrequently. 
So, assuming that this patch doesn't severly hurt performance,
I think it's fine as is.

Comment 6

[Wan-Teh Chang]

I checked in the patch on the NSS trunk (3.12) and
NSS_3_11_BRANCH (3.11.1).

Checking in pqg.c;
/cvsroot/mozilla/security/nss/lib/freebl/pqg.c,v  <--  pqg.c
new revision: 1.10; previous revision: 1.9
done

Checking in pqg.c;
/cvsroot/mozilla/security/nss/lib/freebl/pqg.c,v  <--  pqg.c
new revision: 1.9.2.1; previous revision: 1.9
done

Comment 7

[Wan-Teh Chang]

Attachment: Back out one of the changes

This previous patch made us fail the FIPS DSA PQGGen
test for [mod = 768] only.  I don't know why.  Among
the two changes, this change is more likely to be the
culprit.  So I have backed it out from the NSS trunk
and the NSS_3_11_BRANCH.

Checking in pqg.c;
/cvsroot/mozilla/security/nss/lib/freebl/pqg.c,v  <--  pqg.c
new revision: 1.11; previous revision: 1.10
done

Checking in pqg.c;
/cvsroot/mozilla/security/nss/lib/freebl/pqg.c,v  <--  pqg.c
new revision: 1.9.2.2; previous revision: 1.9.2.1
done

Comment 8

[Wan-Teh Chang]

Comment on attachment 212677 [details] [diff] [review]
Back out one of the changes

We now know we failed the FIPS DSA PQGGen test for
another reason (bug 334533).  So I checked the
reverted change back in on the NSS trunk (3.12)
and the NSS_3_11_BRANCH (3.11.1).

Checking in pqg.c;
/cvsroot/mozilla/security/nss/lib/freebl/pqg.c,v  <--  pqg.c
new revision: 1.12; previous revision: 1.11
done

Checking in pqg.c;
/cvsroot/mozilla/security/nss/lib/freebl/pqg.c,v  <--  pqg.c
new revision: 1.9.2.3; previous revision: 1.9.2.2
done