298512 - Ensure the seed and seed key input for RNG do not have same value for FIPS 140-2

Status: RESOLVED FIXED

(NSS :: Libraries, defect, P1)

Description

[glen beasley]

Ensure the seed and seed key input for RNG do not have same value for FIPS 140-2 
see VE 07.09.01

Comment 1

[Wan-Teh Chang]

Attachment: Preliminary patch

This patch shows the approach I plan to take.  It
will change because I am going to implement the
revised RNG algorithm in Change Notice 1 of FIPS 186-2.

Comment 2

[Wan-Teh Chang]

Comment on attachment 191249 [details] [diff] [review]
Preliminary patch

Bob, Nelson, please take a look at this patch, which outlined
the approach I plan to take to meet this new FIPS 140-2 requirement
on RNG.

In this approach, if the "seed" (fresh entropy) is equal to the
"seed key" (RNG's internal state), I hash the "seed" and use the
hash instead.  If the hash is still equal to the "seed key", I
give up and throw it away.

An alternative is to simply throw away the "seed" if it is equal
to the "seed key".  In this approach, the view is that the "seed"
that has the same value as the "seed key" may be an attack on the
RNG, and therefore should not be used in any form.

I will ask the testing lab for guidance, but I'd like to hear
your opinions.

Comment 3

[Nelson Bolyard (seldom reads bugmail)]

Wan-Teh, please give a URL for the document that contains the requirement 
that you're trying to achieve with this patch.  Thanks.
Is the requirement only to ignore the input if it matches the state?

Comment 4

[Nelson Bolyard (seldom reads bugmail)]

I found and reviewed the PRNG requirements in these documents:
http://csrc.nist.gov/publications/fips/fips140-2/fips1402.pdf
http://csrc.nist.gov/publications/fips/fips140-2/fips1402annexc.pdf
http://csrc.nist.gov/cryptval/140-1/FIPS1401IG.pdf
http://csrc.nist.gov/cryptval/140-1/FIPS1402IG.pdf

In particular, I found the following sentence several times in FIPS 140-2:
"The seed and seed key shall not have the same value."

I spent several hours thinking about possible attacks on this PRNG, and
in the process I discovered how easy it is to get this PRNG to keep 
outputting the same result over and over, without knowing the internal 
"seed key".  Clearly this is why the PRNG is required to detect this 
situation (repeated outputs) and stop cold when it occurs.  I think I 
also know how to get it to output the same two outputs alternately, 
which the required test for repeated results won't detect.  I thought 
of numerous other attacks, none of which are thwarted by the requirement 
that the seed and seed key not match.  

I concluded that if an attacker really knows the seed key value, there are
numerous other more powerful attacks available to him that do not require 
him to enter the seed key value itself as the seed.  

One conceivable interpretation of the FIPS statement about seed and seed key 
is simply that it is telling implementors that seed and seed key are intended
to be separate, not the same thing, and that implementations that attempt to
always use the seed value as the seed key, or vice versa, are fundamentally
wrong.  IOW, the statement warns against the mistake of confusing seed with 
seed key.  In that interpretation, the statement means "shall not ALWAYS be 
the same value", rather than "shall never have the same value, not even 
coincidentally."  

One consequence of implementing seed such that it is always a copy of the 
current value of seed key at the beginning of algorithm 3.1 is that the 
value input to the SHA1-like hash in that algorithm would be seed key 
shifted left one bit, with the LSB forced to zero.  This would cut the 
space of possible outputs from that SHA1-like hash in half.  

The probability that this possible interpretation is the correct one seems 
somewhat strengthed by the fast that there is no quidance given about what 
to do if they ever are the same.  There are many possible things that an 
implementation could do to modify the seed input when it matches the seed 
key that produce worse results.  (Consider for example replacing seed with 
its twos complement when it matches seed key! Ouch!). Yet the FIPS document 
provides no guidance against such bad ideas, and neither does it tell the 
implementor that the PRNG must halt when seed matches seed key (as the doc 
does require for repeated outputs).  This suggests to me that the authors of 
that requirements did not consider that an implementation would change the 
seed input dynamically to meet this requirement, nor even detect it.  It 
suggests that the authors intended this requirement as a design requirement, 
namely that the design shall not implement seed such that it is always a 
copy of seed key, or vice versa.  

We know that our implementation does not implement seed such that it is 
always a copy of seed key, or vice versa.  We could prove that design 
decision without a run time check, if that is the correct interpretation.

So I think the choices of what to do about seed matching seed key include:
a) don't even detect it, since seed is not always a copy of seed key.
b) halt the PRNG when it is detected (that is, set rng->isValid = PR_FALSE; 
   and return SECFailure;
c) simply drop the seed input, and "turn the crank" without any new seed 
   input, when seed matches seed key.
d) alter the seed input when seed matches seed key.  
But I do not know which of those is best.

Of the various ways to alter the seed input, the only one that seems safe 
to me is the one you implemented in the patch above, using a hash of the same
size as seed key (e.g. SHA1) to derive a new seed.  I say that, believing 
that the SHA1 (or other hash algorithm) output would be unbiased -- each bit 
having a 50% probability of being a 1 independently of the other bits' values.  

Comment 5

[Wan-Teh Chang]

Nelson, how do you get the to output the same two outputs alternately?
Does that require knowing the seed key value?

Comment 6

[Wan-Teh Chang]

Attachment: Proposed patch

If seed equals seed key, alg_fips186_2_cn_1 fails.

Because we now implement the Change Notice 1 algorithm,
we compare the seed to the seed key twice (the algorithm
now runs two iterations each time).  I make sure the
RNG's state is not updated and it doesn't output anything
unless both iterations have completed successfully.
Because of this, I have to avoid updating the RNG's state
(rng->XKEY) right after the first iteration (i=0) and
have to use a local copy of the state (XKEY_1).

Comment 7

[Wan-Teh Chang]

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

I forgot to ask this question: if the seed equals seed key,
I set the error code SEC_ERROR_INVALID_ARGS because there is
no suitable error code.  Should we add a new error code
SEC_ERROR_BAD_RNG_SEED for this error condition?

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

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

r=nelson
Here is a suggestion for your consideration (not required). 
Arrange the 4 arrays of PRUint8 to be contiguous, so that a single memset call can be used to clear them all, rather than 4 memset calls, as this patch does.  
There are several ways that could be done, including 
a) putting all the functions local variables into a struct, and clearing that struct, or 
b) having one array of PRUint8, and define the 4 smaller arrays as offsets into that array.

Comment 9

[Wan-Teh Chang]

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

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

Comment 10

[Robert Relyea]

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

r=relyea