Ensure the seed and seed key input for RNG do not have same value for FIPS 140-2 see VE 07.09.01
Created attachment 191249 [details] [diff] [review] 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 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.
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?
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.
Nelson, how do you get the to output the same two outputs alternately? Does that require knowing the seed key value?
Created attachment 198859 [details] [diff] [review] 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 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 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.
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 on attachment 198859 [details] [diff] [review] Proposed patch r=relyea