294106 - Implement the recommended PRNG changes described in FIPS 186-2 Change Notice 1

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[Wan-Teh Chang]

FIPS 186-2 Change Notice 1 recommends some changes to the
pseudorandom number generators (PRNGs) specified in Appendix 3
to defend against an unpublished attack on DSA3.

Please see pages 72-74 in the following document

http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf

(In the PDF reader, these are pages 74-76.)

Comment 1

[Wan-Teh Chang]

Attachment: Proposed patch

This patch implements Algorithm 1 of FIPS 186-2 Change
Notice 1, which defends against an attack on DSA that
exploits the bias in the original algorithm for generating
the private key x.

I also increased the size of the seed-key, XKEY (the
internal state of the PRNG) from 160 bits to 256 bits.
This size is BSIZE (in bytes).	But the output of the
SHA1-like compression function G is still 160 bits, so
I added a new macro GSIZE (in bytes) to represent that
size.

It is best to review the patch in the following order.
1. The two DSA_xxx functions at the end.  DSA_RandomUpdate
is dead code, so I removed it.	In the Revised Algorithm,
the general-purpose PRNG and the DSA PRNG are more cleanly
separated, so we only need to do the reduce mod q operation
in the DSA_GenerateGlobalRandomBytes function and don't
need to pass q to other functions.  This eliminates the q
parameter from several functions.

2. dsa_reduce_mod_q: because b is now 256 bits, reducing a
number mod q (160-bit prime) can no longer be implemented
as a subtraction, and must use the mpi library.

3. alg_fips186_2_cn_1: this is where the revised (general-purpose)
PRNG algorithm is implemented.	It may be useful to use "cvs diff -uw"
to look at the changes to this function because the revised algorithm
added a loop of two iterations to the original algorithm.

4. In the rest of the code, make sure I use BSIZE or GSIZE where
appropriate.  I also updated the comments to cite the current
standard numbers (140-2 and 186-2) and the new section or algorithm
step numbers.

Comment 2

[Wan-Teh Chang]

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

Since PRNG is critical to the security of our crypto code,
I need two code reviews, with one from Nelson, who wrote
the original PRNG code.  Thanks a lot.

I will add some debug code in my tree to have a parallel
implementation of the key steps and compare the results.
This patch doesn't have that debug code.

Comment 3

[Robert Relyea]

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

Only one issue for r-, automatic r+ for fixing this issue:

globlrng needs to be reset to NULL if the lock creation fails.

------------------------

Minor style nits and comments:

w_i = x_j + i*GSIZE looked like an integer math statement to me initially. if
it read:
w_i = &x_j[i*GSIZE] I would have realized immediately it was pointers we were
dealing with.

The PORT_SetError() that was replaced with the comment /* set error */ I
believe should have read /* Error set by HASHBUF */ (I've verified that none of
the versions of HASHBUF we call can fail, so the statement is true).

Question: in prng_RandomUpdate(), shouldn't we run all data through our hash
expander/contractor just to mix it, even it it is already perfectly set to
bsize?

Comment 4

[Wan-Teh Chang]

Attachment: Proposed patch v2

I incorporated Bob's review comments.

As to the question whether we should always hash XSEEDj
even if it is exactly b bits, the RNG algorithm
does not specify hashing XSEEDj before using it.  So
the standard does not require hashing, and always hashing
may make us fail the FIPS RNG Validation System
(http://csrc.nist.gov/cryptval/rng/RNGVS.pdf).

Comment 5

[Robert Relyea]

Comment on attachment 197745 [details] [diff] [review]
Proposed patch v2

r+

re hash: Yeah, I know the standard doesn't require it, I was just wondering if
it could mitigate some sorts of attack against the RNG. Since I don't know what
those attacks are, I see not problem with what the code is doing (and has been
doing for a long time).

Comment 6

[Wan-Teh Chang]

Attachment: Proposed patch v2 (with dsa.c change removed)

I removed the trivial change to dsa.c from this
patch to make Bugzilla's interdiff work better.

Comment 7

[Wan-Teh Chang]

Comment on attachment 197772 [details] [diff] [review]
Proposed patch v2 (with dsa.c change removed)

The purpose of this patch is confusing, so I
marked it obsolete.

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 197745 [details] [diff] [review]
Proposed patch v2

One minor nit (not a full review comment).  The original code (and this patch)
use the word "heretofore" improperly.
heretofore means "before now" or "before this point".  The desired word is
"herein" or "hereinafter", I believe.

Comment 9

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 197745 [details] [diff] [review]
Proposed patch v2

IINM, there is an arithmetic error in the new code, causing it 
to not exactly implement the algorithm given in the change notice.
I will email the details of this review.

By the way, once this change notice algorithm is implemented, 
I believe it will defeat the two attacks (repeating, and alternating 
outputs) I described today.  So the additional hashing of the input 
we discussed should not be necessary.

Comment 10

[Wan-Teh Chang]

Attachment: Proposed patch v3

Nelson is right.  It is wrong to pass a GSIZE (20) byte
w_i array to the ADD_B_BIT_PLUS_CARRY macro.  In this patch
I implemented the solution Nelson suggested in private
email.	I made w_i an arrary of BSIZE bytes (instead of
a pointer pointing into the x_j array).  I zero the
leftmost (most significant) BSIZE - GSIZE bytes, and
store the output of G(t, XVAL) in the rightmost GSIZE
bytes.	This solution requires no change to the
ADD_B_BIT_PLUS_CARRY macro, but requires a copy from
the w_i buffer to the x_j buffer.

An alternative solution is to modify the ADD_B_BIT_PLUS_CARRY
macro to add a BSIZE byte number and a GSIZE byte number
(instead of two BSIZE byte numbers).

Comment 11

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 197884 [details] [diff] [review]
Proposed patch v3

I have two minor quibbles with this patch.  
One is just a suggestion, the other needs to be changed.
But I'll give it r+ on the condition that the needed change is done.

>+static SECStatus
>+dsa_reduce_mod_q(const unsigned char *w, const unsigned char *q,
>+    unsigned char *xj)

>+    PORT_Assert(q[0] >= 0x80);

This assertion really isn't needed any more.  The old code 
dependend on it for correctness.  The new mpi-based code does not.
But it doesn't hurt, so you can leave it.

> SECStatus 
>-DSA_GenerateGlobalRandomBytes(void *dest, size_t len, unsigned char *q)
>+DSA_GenerateGlobalRandomBytes(void *dest, size_t len, const unsigned char *q)

>+    PORT_Assert(q && len == DSA_SUBPRIME_LEN);
>+    if (*q == 0) {
>         ++q;
>     }

There needs to be code here to deal with the case where 
len != DSA_SUBPRIME_LEN in non-debug builds.
Otherwise there may be buffer overruns below.

Comment 12

[Robert Relyea]

Comment on attachment 197884 [details] [diff] [review]
Proposed patch v3

I don't see anything wrong (but I didn't in the last patch either;)

Comment 13

[Wan-Teh Chang]

Comment on attachment 197884 [details] [diff] [review]
Proposed patch v3

Nelson, the reason I didn't add a failure return to back
up this assertion in DSA_GenerateGlobalRandomBytes

>+    PORT_Assert(q && len == DSA_SUBPRIME_LEN);

is that DSA_GenerateGlobalRandomBytes is a freebl internal
function.  It is only called by dsa.c.	It is not even declared
in any header file.  It would be a static function if dsa.c
and prng_fips1861.c were one file.

Do you still want me to add a failure return to back up
the assertion?

I've checked in this patch on the NSS trunk (NSS 3.11)

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

new revision: 1.20; previous revision: 1.19
done

Comment 14

[Wan-Teh Chang]

Attachment: Assertion changes

Implement Nelson's suggested changes in comment 11.

Should I set the error SEC_ERROR_LIBRARY_FAILURE
instead?

Comment 15

[Nelson Bolyard (seldom reads bugmail)]

Comment on attachment 197935 [details] [diff] [review]
Assertion changes

That error code looks fine to me.

Comment 16

[Wan-Teh Chang]

I checked in the "Assertion changes" patch on the NSS
trunk (NSS 3.11).

Comment 17

[Wan-Teh Chang]

Attachment: Patch for continuous RNG test

With the revised RNG algorithm in FIPS 186-2 Change Notice 1,
it is ambiguous whether the output

    xj = (w0 || w1)

is one block or two blocks because each wi is a block produced by
the original RNG algorithm in FIPS 186-2.  We interpret xj as one
block.  This patch implements the continuous RNG test for *both*
interpretations; it first does the continuous RNG test considering
w0 and w1 each as a block, and then does the continuous RNG test
considering xj as a block.  Our testing lab says our current
interpretation (xj as a block) is fine.  This is why I didn't
check in this patch.  But this patch may be a good idea, so I
attached it here, at least for archival.