Last Comment Bug 355297 - Improve the very first RNG_RandomUpdate call
: Improve the very first RNG_RandomUpdate call
Status: RESOLVED FIXED
:
Product: NSS
Classification: Components
Component: Libraries (show other bugs)
: 3.11.3
: All All
: P1 normal (vote)
: 3.11.4
Assigned To: Wan-Teh Chang
:
:
Mentors:
Depends on:
Blocks:
  Show dependency treegraph
 
Reported: 2006-10-03 15:14 PDT by Wan-Teh Chang
Modified: 2007-11-13 01:39 PST (History)
7 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---


Attachments
Dump of rng->XKEY while running the pk11mode test program (31.50 KB, text/plain)
2006-10-03 17:17 PDT, Wan-Teh Chang
no flags Details
Dump of rng->KEY with NSS modified to initialize XKEY to all zeroes (30.59 KB, text/plain)
2006-10-03 17:21 PDT, Wan-Teh Chang
no flags Details
Proposed patch (9.44 KB, patch)
2006-10-04 17:17 PDT, Wan-Teh Chang
julien.pierre: review-
Details | Diff | Splinter Review
Proposed patch v2 (11.02 KB, patch)
2006-10-05 15:34 PDT, Wan-Teh Chang
no flags Details | Diff | Splinter Review
Proposed patch v3 (9.86 KB, patch)
2006-10-06 13:20 PDT, Wan-Teh Chang
julien.pierre: review-
Details | Diff | Splinter Review
Change the way we reseed the RNG (10.21 KB, patch)
2006-10-06 15:33 PDT, Wan-Teh Chang
no flags Details | Diff | Splinter Review
Change the way we reseed the RNG v2 (13.84 KB, patch)
2006-10-09 18:51 PDT, Wan-Teh Chang
no flags Details | Diff | Splinter Review
Change the way we reseed the RNG v2.1 (13.87 KB, patch)
2006-10-09 19:00 PDT, Wan-Teh Chang
no flags Details | Diff | Splinter Review
Proposed patch v4 (checked in) (11.91 KB, patch)
2006-10-10 15:12 PDT, Wan-Teh Chang
julien.pierre: review+
rrelyea: superreview+
Details | Diff | Splinter Review
Change the way we reseed the RNG v3 (9.92 KB, patch)
2006-10-10 18:21 PDT, Wan-Teh Chang
nelson: review+
julien.pierre: superreview+
Details | Diff | Splinter Review
use sysinfo call in unix_rand.c (checked in) (1.07 KB, patch)
2006-10-11 19:39 PDT, Wan-Teh Chang
neil.williams: review+
glenbeasley: superreview+
Details | Diff | Splinter Review
Change the way we reseed the RNG (as checked in) (11.10 KB, patch)
2006-10-13 10:05 PDT, Wan-Teh Chang
no flags Details | Diff | Splinter Review

Description Wan-Teh Chang 2006-10-03 15:14:58 PDT
In NSS 3.11.x, the internal state of our RNG has been increased
from 160 bits to 256 bits.  So ideally we need to initialize the
internal state of the RNG with 256 bits of entropy.

The very first RNG_RandomUpdate call is used to initialize the
internal state (the 'XKEY' buffer) of our RNG.  The quality of
the entropy added by this call is more important than the
subsequent RNG_RandomUpdate call because the subsequent calls
"compress" the input bytes to 160 bits using the SHA-1 like G
function before adding them to the internal state of the RNG.

Another problem is that we use memcpy to initialize the internal
state of our RNG, overwriting the previous contents in the XKEY
buffer.  So bug 353910, which Julien fixed to preserve the entropy
across NSS shutdown, turned out to be in vain.  I guess we can
use XOR instead to mix in the initial entropy.

I will attach debug printf outputs that clearly show the subsequent
RNG_RandomUpdate calls leave the most significant ~90
(256 - 160 - a small number) bits unchanged.

This is the very first RNG_RandomUpdate call on HP-UX.  It's
probably the same on all platforms.

Breakpoint 1, prng_RandomUpdate (rng=0x7e83b990, data=0x7ffff4a0, bytes=16)
    at prng_fips1861.c:397
397         SECStatus rv = SECSuccess;
(gdb) where
#0  prng_RandomUpdate (rng=0x7e83b990, data=0x7ffff4a0, bytes=16)
    at prng_fips1861.c:397
#1  0x200000007e85e410:0 in RNG_RandomUpdate (data=0x7ffff4a0, bytes=16)
    at prng_fips1861.c:470
#2  0x200000007e85e380:0 in rng_init () at prng_fips1861.c:367
#3  0x200000007ef23970:0 in PR_CallOnce (once=0x7e83ba00, func=0x7e83a090)
    at ../../../../pr/src/misc/prinit.c:809
#4  0x200000007e85e4c0:0 in RNG_RNGInit () at prng_fips1861.c:385
#5  0x200000007e9e3290:0 in RNG_RNGInit () at loader.c:922
#6  0x200000007e9a0790:0 in nsc_CommonInitialize (pReserved=0x7ffff5f0,
    isFIPS=1) at pkcs11.c:2998
#7  0x200000007e94dc40:0 in FC_Initialize (pReserved=0x7ffff5f0)
    at fipstokn.c:455
#8  0x4009660:0 in main (argc=1, argv=0x7ffffaf8) at pk11mode.c:626

The input to that RNG_RandomUpdate call is the output of RNG_GetNoise,
which seems to be a few high-resolution time stamps.  We should use
/dev/urandom (Unix/Linux/Mac OS X, if available) or CryptGenRandom
(Windows) instead.
Comment 1 Julien Pierre 2006-10-03 15:23:54 PDT
Wan-Teh,

If the first RNG_RandomUpdate call is more important than others, I think that significantly invalidates much of the code that currently initializes the RNG on many platforms. The code I wrote recently for libkstat for example doesn't try to make the first call more important. It may even be that the first call uses static data. I didn't examine all the kernel data. The assumption was that the quantity of the data and the fact that it contained entropy would offset any amounts of static data. The code passed review so I assumed doing this was OK. I would wager that netstat output also may not work too well since it passes output one line at a time. The first line is probably static data on all platforms.
Comment 2 Wan-Teh Chang 2006-10-03 17:17:03 PDT
Created attachment 241133 [details]
Dump of rng->XKEY while running the pk11mode test program

I added column numbers at the top to help you count
which hex digits change and which don't.

The abrupt change of XKEY contents in the middle is
because of a softoken shutdown and re-initialization.

Julien, the entropy is still fed into the RNG.  It's
just that unless the very first RNG_RandomUpdate call
initializes the RNG with very good entropy, it'll take
2^90 subsequent RNG_RandomUpdate calls to change the
most significant bit of the XKEY buffer.  So the strength
of our RNG is only slightly more than 160 bits even
though we increased its internal state to 256 bits.
160 bits are what we had before and are the strength of
>= 4096 bit RSA keys.
Comment 3 Wan-Teh Chang 2006-10-03 17:21:10 PDT
Created attachment 241134 [details]
Dump of rng->KEY with NSS modified to initialize XKEY to all zeroes

I modified NSS to treat the very first RNG_RandomUpdate
call the same way as the subsequent ones.  This allows
rng->XKEY to begin with all zeroes, and it's easier to
see that the high-order bytes aren't changed by the
RNG_RandomUpdate calls this way.
Comment 4 Julien Pierre 2006-10-03 17:47:29 PDT
Wan-Teh,

In the current NSS architecture, NSS_Shutdown and C_Finalize unload libfreel thanks to the fix for bug 115951 . libfreebl happens to be where the RNG context lives, so there is no hope of preserving any entropy data accross NSS_Shutdown calls . If preserving the entropy data is required, then the RNG context should be moved out of freebl and into softoken . But I don't think it should be required.
Comment 5 Wan-Teh Chang 2006-10-03 17:56:36 PDT
I want to clarify one sentence in my comment 2.  It should read:

  So if we don't pass high quality entropy to the very first
  RNG_RandomUpdate call, the strength of our RNG will be only
  slightly more than 160 bits even though we increased its
  internal state to 256 bits.
Comment 6 Julien Pierre 2006-10-03 18:00:49 PDT
Wan-Teh,

Shouldn't RNG_RandomUpdate change the higher bits more frequently than that and not depend so much on the entropy provided in the very first call ?

Is there any other FIPS140-2 approved algorithm we can use which would have that property ? AFAIK we are using SHA-256 at the moment.

It seems unlikely that we can consistently and on all platforms ensure that the entropy provided to the first call is "very good". It certainly isn't the case right now.
Comment 7 Wan-Teh Chang 2006-10-03 18:18:19 PDT
There are other FIPS Approved RNG algorithms.  See
http://csrc.nist.gov/cryptval/rng/rngval.html

But I am not familiar with them (ANSI X9.62 and ANSI X9.31).
Comment 8 Nelson Bolyard (seldom reads bugmail) 2006-10-03 20:42:16 PDT
> it'll take 2^90 subsequent RNG_RandomUpdate calls to change the
> most significant bit of the XKEY buffer. 

Then, IMO, the PRNG is SERIOUSLY broken.  
I don't see how it could pass FIPS testing with this issue.  
IMO, the solution is NOT to "Improve the very first RNG_RandomUpdate call".
It is to make every RNG_RandomUpdate call affect the whole PRNG state.
Comment 9 Wan-Teh Chang 2006-10-04 17:17:46 PDT
Created attachment 241259 [details] [diff] [review]
Proposed patch

Please review this patch today or tomorrow (Thursday).
This bug blocks FIPS testing. (Nelson, you're also invited
to review this patch.)

Our RNG passed the NIST RNG algorithm validation because
it is a faithful implementation of the FIPS 186-2 RNG
algorithm.

This bug is caused by a limitation of the FIPS 186-2 RNG
algorithm and our decision to implement RNG_RandomUpdate
using the XSEEDj input rather than directly modifying XKEY.
Recall that XSEEDj is really the optional user input when
the user wants to generate a DSA private key (x).  When
XKEY was 160-bit long, how we implement RNG_RandomUpdate
didn't matter.  But now that XKEY is longer than 160 bits,
it matters.

We can change RNG_RandomUpdate to directly modify XKEY,
but it will open a can of worms.  First, should we set
XKEY to the new seed, do a bitwise XOR of the XKEY and
the new seed, or hash with SHA-256 the concatendation of
XKEY and the new seed?  Second, directly modifying XKEY
may be considered to be "entering the seed-key", which
is subject to some FIPS 140-2 requirements that don't
apply to our crypto module right now.

Given our time constraint, I propose that we simply
improve the quality of the entropy that we pass to the
very first RNG_RandomUpdate call for this FIPS validation.

Here is a summary of the patch.

1. On Unix, we read 1024 bytes from /dev/urandom if it
exists.

2. On Solaris, if /dev/urandom doesn't exist, we call
kstat as an alternative.

3. On Windows, we call CryptGenRandom to generate 1024
random bytes.  Note that under MSVC 6.0 I must define
_WIN32_WINNT to be 0x0400 because <wincrypt.h> requires
_WIN32_WINNT to be >= 0x0400.

4. After the above, we still call RNG_GetRandomNoise on
all platforms as we did before.

5. These random bytes are mixed and whitened with SHA-256
before being passed to the very first RNG_RandomUpdate call.
The very first RNG_RandomUpdate call initializes XKEY with
its input.
Comment 10 Wan-Teh Chang 2006-10-04 17:30:02 PDT
Comment on attachment 241259 [details] [diff] [review]
Proposed patch

I forgot to mention one issue -- we can remove the
RNG_FileUpdate("/dev/urandom", 1024) and RNG_kstat
calls from RNG_SystemInfoForRNG in unix_rand.c because
we now do the equivalent in rng_init with a better
effect, affecting the whole XKEY rather than only the
low 160 bits.

Do you want me to do that?
Comment 11 Julien Pierre 2006-10-04 17:31:49 PDT
Wan-Teh,

A few weeks ago when I was modifying code in this area, it was agreed that the collection of the entropy data was outside of the scope of the FIPS140-2 validation - only the PRNG algorithm itself was within the scope of FIPS140-2. Unless that has recently changed, how can this bug - which is relevant only to the collection of entropy data - now block FIPS testing ?
Comment 12 Wan-Teh Chang 2006-10-04 17:52:54 PDT
There are two validations:
1. FIPS 140-2 validation of the crypto module, and
2. Validation of the implementations of the various crypto algorithms.

This bug does not block the RNG algorithm testing (#2) but blocks
the crypto module testing (#1).  Previous, I mistakenly thought that
FIPS 140-2 didn't have any requirement on entropy collection, so I
only considered the RNG algorithm validation when reviewing your
recent change to unix_rand.c.  But I just learned on Monday that
requirement AS07.13 in the FIPS 140-2 Derived Test Requirements is
concerned with proper seeding of the RNG:

  AS07.13: (Levels 1, 2, 3, and 4) Compromising the security of the
  key generation method (e.g., guessing the seed value to initialize
  the deterministic RNG) shall require at least as many operations as
  determining the value of the generated key.

Since our crypto module generates 256-bit AES keys, we must justify
that the seed value used to initialize our RNG has 256 bits of
entropy.

It's my fault to fail to see the connection of AS07.13 to entropy
collection.
Comment 13 Julien Pierre 2006-10-04 19:45:03 PDT
Comment on attachment 241259 [details] [diff] [review]
Proposed patch

Wan-Teh,

Thanks, that clarifies it. It much makes much sense from a security point of view to care about the entropy collection. I'm glad that FIPS140-2 cares about it, but sorry that we are finding out about this requirement so late.

I would much prefer that we fix the PRNG algorithm so that it doesn't depend so much on the initial RNG_RandomUpdate call, ie. doing changes to RNG_RandomUpdate to modify XKEY as you outlined in comment 9 . This may be a big can of worms, but it is one that we should only have to open once for all platforms, current and future, and they would all have a PRNG with an effective state of 256 bits, not just the FIPS platforms that this patch is trying to fix. If we don't do this now, any minor changes to the entropy collection for the initial RNG_RandomUpdate call we make could invalidate the certification. The PRNG algorithm should be less sensitive to those details.

I would like Nelson's opinion about the preferred way to proceed here - fix RNG_RandomUpdate, or change the initial entropy collection, so I'm adding a 3rd review request.

This patch is also a big can of worms and has implications for all platforms.

If we agree that we want to fix the problem by changing the initial entropy collection, then the following issues exist in the patch, and are the reason for the r- :

- rng_rnginit does not check the return value of  RNG_GenerateSeedKey . There is only an assertion. rng_rnginit should fail if a seed key of the proper size can't be generated

- on Windows, CAPI didn't exist in the original release of Win95. According to MSDN, the calls are available only if IE 3.02 or later is installed on Win95 . If we are still officially supporting Win95 without IE, then there is extra work to be done to dynamically load the CryptAcquireContext / CryptReleaseContext symbols, or freebl3.dll won't load . I would be equally happy if we decided to just stop Win95 support, though.

- For the Solaris implementation of kstat, you duplicate much of the code that was in RNG_kstat() into rng_HashKernelStats , but you removed the buffering. The buffering was necessary for performance, given the potentially very large number of buffers. Doing SHA256_Update on kstat data without any buffering is a performance issue. The buffering needs to be there in both cases. I would also prefer if the kstat code wasn't duplicated to make it more maintainable. Perhaps RNG_kstat() could take a callback function argument, that would invoke either SHA256_Update or RNG_RandomUpdate on the data, as needed by the caller.
Comment 14 Wan-Teh Chang 2006-10-05 15:34:09 PDT
Created attachment 241379 [details] [diff] [review]
Proposed patch v2

1. I moved the RNG_GetNoise call out of the RNG_GenerateSeedKey
function.  This is for proper counting of rng->seedCount.

In the previous patch, if the OS doesn't have a random number
generation service, RNG_GenerateSeedKey would only use the output
of RNG_GetNoise, which is usually only 8 or 16 bytes.  Because
of the SHA-256 hash, RNG_GenerateSeedKey returns 32 bytes, so
when we call RNG_RandomUpdate, rng->seedCount would be incremented
by 32, which is more than what RNG_GetNoise returned.

In this patch, RNG_GenerateSeedKey actually underreports its
seed count as 32 (actual seed count is 1024 for /dev/urandom and
CryptGenRandom, or a huge number like 411772 for Solaris kstat).

2. I added a comment to rng_init to explain the importance of
the first RNG_RandomUpdate call and the consequences of not
implementing RNG_GenerateSeedKey.

3. I check the return values of RNG_GenerateSeedKey and RNG_GetNoise
in rng_init.  Note that rng_init doesn't fail if RNG_GenerateSeedKey
or RNG_GetNoise fails.  I am relying on rng->seedCount.  When a user
calls the RNG, the RNG fails with the error SEC_ERROR_NEED_RANDOM
if rng->seedCount is less than MIN_SEED_COUNT (1024 bytes).

4. On Windows, I now load advapi32.dll and look up the three CryptoAPI
functions we need at run time, so that our code works on Windows 95
before OSR2.

5. In the Solaris kstat implementation, we don't need to buffer the
input for SHA256_Update because SHA256_Update operates block by
block in streaming mode.  Since I don't buffer the kstat data, the
for loop in my code is very simple.  I did a Web search for "Solaris kstat"
and found a sample code of that for loop in Example 3 of this article:

http://developers.sun.com/solaris/articles/kstatc.html

So it's not necessary to combine rng_HashKernelStats and RNG_kstat into
one function and use callbacks.  In this case the best way to remove
duplicate code is to remove RNG_kstat.

I've tested this patch in the debugger on Windows, Linux, HP-UX
(with and without /dev/urandom), and Solaris (with and without
/dev/urandom).  I will now look into exactly how much work it is to
change RNG_RandomUpdate to modify the whole rng->XKEY (RNG's internal
state).
Comment 15 Wan-Teh Chang 2006-10-06 13:20:02 PDT
Created attachment 241489 [details] [diff] [review]
Proposed patch v3

I improved the patch further.

I renamed the new function RNG_SystemRNG and changed it to not
hash the random bytes with SHA-256.  The SHA-256 hash will be
done in RNG_RandomUpdate.  This makes the rng->seedCount more
accurate.

I removed the rng_HashKernelStats function for Solaris.  Based
on my Internet search, Trusted Solaris 8 has /dev/urandom, and
there are patches for regular Solaris 8 to add /dev/urandom
(patch ID 112438 for SPARC, patch ID 112439 for Intel).  This
simplified the Unix code.

Finally, I found that latest Windows versions have the RtlGenRandom
function, which is much cheaper than CryptGenRandom.  So we now try
to use RtlGenRandom first.  See the sample code at
http://blogs.msdn.com/michael_howard/archive/2005/01/14/353379.aspx
Comment 16 Wan-Teh Chang 2006-10-06 15:33:08 PDT
Created attachment 241499 [details] [diff] [review]
Change the way we reseed the RNG

This is the alternative patch I promised.  I studied a lot
of materials on RNGs.  The most useful document is NIST SP
800-90, which defines a general model for RNG and specifies
several RNGs.  After I read SP 800-90, it's clear to me that
we are abusing the XSEEDj optional user input as the entropy
input for reseeding.

The problem is that FIPS 186-2 doesn't specify how to reseed
the RNG, and the FIPS 186-2 RNG is not one of the RNGs in SP
800-90.  I can only retrofit our FIPS 186-2 with a modified
version of a reseed function from SP 800-90.  So I am not sure
if the reseed function is secure.  But it seems secure.  Using
the terminology of SP 800-90, here are the Instantiate and
Reseed functions I proposed for our FIPS 186-2 RNG:

Instantiate (initial seeding):

XKEY = SHA-256(entropy_input)

Reseed:

XKEY = SHA-256(XKEY || entropy_input)

where || means concatenation.

An alternative is to initialize XKEY to all zeros, and use the
same function for Instantiate and Reseed:

XKEY = SHA-256(XKEY || entropy_input)

This alternative will be necessary when we're able to reuse the
entropy we preserve in RNG_RNGShutdown/freeRNGContext.

I also included the new Windows code to call the system RNG.
I ask for 1024 bytes because that's the number of bytes we
read from /dev/urandom on Unix, and I call the system RNG
at the very end of RNG_SystemInfoForRNG (not sure where is
the best place to call).
Comment 17 Nelson Bolyard (seldom reads bugmail) 2006-10-06 22:25:47 PDT
Comment on attachment 241499 [details] [diff] [review]
Change the way we reseed the RNG

Wan-Teh, I really like the approach in this patch.  
I have a suggestion to improve it, and a question or two.

1. Rather than allocating a SHA256 Context with SHA256_NewContext, and 
storing the address of that context in the RNGContent, I suggest that you 
reserve enough space for that context here in the RNGContext, and use that 
space directly.  Then you don't have to deal with allocation failure, and 
there's (at least) one fewer allocation required.  Since the RNG code and 
the SHA code are both private to FreeBL, this seems reasonable to me.

2. I thought we dropped support for Win95 (the OS, not the ABI) LONG ago.  
No?

3. Michael Howard (small world!) writes that "you can get good random numbers, 
without the memory overhead of pulling in all of CryptoAPI!"  But it appears
to me that this patch loads one and the same DLL for both sets of code, 
so I don't see the memory savings he describes.  Maybe that savings is due
to advapi not dynamically loading yet more DLLs.
Comment 18 Wan-Teh Chang 2006-10-07 12:14:35 PDT
Indeed, changing the way we reseed the RNG turned out to be
simpler than I thought.  But I am not sure if the Reseed function
I proposed is secure.  It is what most "engineers" would
use, and is very similar to two reseed functions in NIST SP
800-90 and the reseed function in Ferguson and Schneier's
Practical Cryptography book (for their Fortuna RNG).  I don't
know, for example, if we should hash the entropy_input first
before combining the current XKEY with it.  XKEY is only 32
bytes, but we often call RNG_RandomUpdate with 1K bytes.  It
seems that the new data would dominate in contributing to the
new seed.  So, I have some concerns about the way I adapted
these other reseed functions for the FIPS 186-2 RNG.

I also don't like the way RNG_SystemInfoForRNG calls RNG_RandomUpdate
with small chunks of data rather than pooling all the bytes and
call RNG_RandomUpdate only once.  But I don't have time to address
this.

I will look into allocating SHA256Context as a local variable
in prng_RandomUpdate.

When Julien brought up the Windows 95 issue in comment 13, it
reminded me that neil@parkwaycc.co.uk is running a MOZILLA_1_8_BRANCH
(the branch for the upcoming Firefox 2.0 release) tinderbox on
Windows NT 3.51.  (See bug 326168 comment 37.  He told me
his tinderbox was running Windows NT 3.51 in private email.)
To prevent any more obstacle for my patch, I decided to look up
the CryptoAPI functions at run time.

I believe Michael Howard is referring to the memory overhead of
loading of the default Windows CSP, which is a DLL.
Comment 19 Wan-Teh Chang 2006-10-09 18:51:54 PDT
Created attachment 241780 [details] [diff] [review]
Change the way we reseed the RNG v2

I don't want to allocate enough space and cast a pointer to it
to SHA256Context *.  So I decided to move the definition of
struct SHA256ContextStr to a new header file.  Originally I wanted
to name the new header sha512.h because it comes from sha512.c,
but it's hard to also move the definition of struct SHA512ContextStr
to the new header because sha512.c undefines HAVE_LONG_LONG before
including prtypes.h so that PRInt64/PRUint64 is defined as a structure.

If the result is not what you wanted, I can revert to the original
patch.  Thanks.
Comment 20 Wan-Teh Chang 2006-10-09 19:00:12 PDT
Created attachment 241781 [details] [diff] [review]
Change the way we reseed the RNG v2.1
Comment 21 Wan-Teh Chang 2006-10-09 19:00:53 PDT
Comment on attachment 241781 [details] [diff] [review]
Change the way we reseed the RNG v2.1

Minor fixes.
Comment 22 Julien Pierre 2006-10-09 20:25:49 PDT
Comment on attachment 241489 [details] [diff] [review]
Proposed patch v3

Wan-Teh,

The patch is mostly good, but there are a couple of minor issues :

1) you are changing the size of the "bytes" static buffer in rng_init . There is no macro or comment explaining why the buffer needs to be this size. Since the size was chosen carefully and there are FIPS140-2 requirements for that many bytes, there should be a macro with an explicit name, or a comment about the array size near the declaration

2) rng_init should deal with the case where RNG_SystemRNG returns 0 bytes for a reason other than PR_NOT_IMPLEMENTED_ERROR . I know you said that you don't want rng_init to fail because you are relying on rng->seedCount, but IMO it would be appropriate to at least assert here in debug builds to detect a complete failure of the platform-specific code on some QA machines that are running the debug builds . If more than 0 bytes are returned but less than the required amount, it may be OK to rely on rng->seedCount being too low to report the error

3) In unix_rand, in RNG_SystemRNG , if we are able to successfully open /dev/urandom, but get 0 bytes, IMO the function should not set PR_NOT_IMPLEMENTED_ERROR, but some other error code 

4) similarly, in win_rand, if we are able to load advapi32 and get at least one of the set of symbol pointers needed to obtain entropy, then the function should not return PR_NOT_IMPLEMENTED_ERROR, but some other errors, if the Windows system calls fail to return any entropy
Comment 23 Robert Relyea 2006-10-10 13:58:57 PDT
Comment on attachment 241489 [details] [diff] [review]
Proposed patch v3

the patch has moved on, clearing review request.
Comment 24 Wan-Teh Chang 2006-10-10 15:12:22 PDT
Created attachment 241884 [details] [diff] [review]
Proposed patch v4 (checked in)

I implemented all of Julien's suggested changes.

1. Define the macro SYSTEM_RNG_SEED_COUNT as 1024, and use this
macro for the size of the buffer passed to RNG_SystemRNG.

2. If RNG_SystemRNG fails with an error code other than
PR_NOT_IMPLEMENTED_ERROR, rng_init fails.  This causes the
PKCS #11 NSC/FC_Initialize function to fail with CKR_DEVICE_ERROR.

3. If /dev/urandom or the Windows system XXXGenRandom function exists,
but we fail to get the specified number of bytes from it, we fail
with the error code SEC_ERROR_NEED_RANDOM.  Note: this error code
is the closest error code I can find.  Its meaning is close enough
to the error condition ("the system RNG failed") that I decided to
use it rather than adding a new code.

4. RNG_SystemRNG returns all or nothing.  It is theoretically possible
to read only a partial buffer from /dev/urandom, but I decided to
handle that unlikely case as if no bytes were read.
Comment 25 Wan-Teh Chang 2006-10-10 18:21:43 PDT
Created attachment 241905 [details] [diff] [review]
Change the way we reseed the RNG v3

I removed the Windows CryptoAPI code from this patch, so
that this patch does only one thing -- change the way we
reseed the RNG.  This patch is now completely independent
of "Proposed patch v4".

I also added a check to ensure that seed != seed key.  This
is a FIPS 140-2 requirement, previously enforced in the
alg_fips186_2_cn_1 function.  Since prng_RandomUpdate no longer
calls alg_fips186_2_cn_1, it needs to perform this check, too.
(It's possible that this check is no longer applicable,
but it's faster for me to just implement the check than asking
NIST.)

As a reminder, this patch seeds and reseeds the RNG as
follows.  XKEY is the RNG's 256-bit internal state.
|| means concatenation.

1. Seeding: initializing XKEY

XKEY = SHA-256(entropy_input)

2. Reseeding: mixing additional entropy into XKEY

XKEY = SHA-256(XKEY || entropy_input)
Comment 26 Nelson Bolyard (seldom reads bugmail) 2006-10-10 20:29:06 PDT
Comment on attachment 241905 [details] [diff] [review]
Change the way we reseed the RNG v3

The changes in this patch look like they should produce excellent
results from a randomness perspective.  
My only concern about all these changes to the PRNG code is that
I fear they may slow it down significantly.  That may be AOK for
operation in "FIPS mode", but may be less than ideal in situations
where FIPS mode is not required and performance is paramount. 

So we may want to have effectively two PRNG implementations, one
for FIPS mode and one for non-FIPS mode, if the performance
difference justifies it.
Comment 27 Wan-Teh Chang 2006-10-10 22:10:25 PDT
Comment on attachment 241905 [details] [diff] [review]
Change the way we reseed the RNG v3

Thanks.  This patch will only slow down NSC/FC_Initialize
and NSC/FC_SeedRandom because this patch only modifies
the RNG_SeedRandom function.  It won't affect the performance
of random number generation or key generation.

This patch is not about FIPS mode but rather about our
users' ability to *reseed* our RNG with more than 160
bits of entropy.  Reseeding the RNG is actually not mentioned
in FIPS 140-2 although it's a commonly recommended practice.
This patch is also somewhat important to the initial seeding
because our softoken uses the "reseed" function (RNG_RandomUpdate)
to perform the second half of the initial seeding of the RNG
(RNG_SystemInfoForRNG).

If it is a problem to degrade the performance of
NSC/FC_Initialize and NSC/FC_SeedRandom, we can do without
this patch.
Comment 28 Nelson Bolyard (seldom reads bugmail) 2006-10-11 02:04:35 PDT
Comment on attachment 241905 [details] [diff] [review]
Change the way we reseed the RNG v3

I thought we called RNG_RandomUpdate more frequently than just at startup.  But if not, then I have no objection to this patch at all.
Comment 29 Wan-Teh Chang 2006-10-11 13:56:04 PDT
Comment on attachment 241905 [details] [diff] [review]
Change the way we reseed the RNG v3

I just verified with LXR
(http://lxr.mozilla.org/security/ident?i=RNG_RandomUpdate)
that RNG_RandomUpdate is only called by
1. rng_init
2. RNG_SystemInfoForRNG
3. NSC_SeedRandom

I also realized that my patch actually will speed up
RNG_RandomUpdate.  Right now, if the entropy input
is not exactly 32 bytes (which is the most common case),
RNG_RandomUpdate calls SHA256_HashBuf (B_HASH_BUF) to
compress/expand it to 32 bytes before calling
alg_fips186_2_cn_1, which calls the SHA-1-like G function.
With my patch applied, RNG_RandomUpdate will (always) do
SHA-256 but won't call alg_fips186_2_cn_1.  So in general
we save the cost of the G function (the same as the cost
of SHA-1).
Comment 30 Robert Relyea 2006-10-11 18:30:19 PDT
Comment on attachment 241884 [details] [diff] [review]
Proposed patch v4 (checked in)

r+ assume we want this implemented semantic:

if a highvalue entropy source is not available, we fall back to GetNoise().

if it is available, but fails to get any data, we fail the random number initialization.
Comment 31 Julien Pierre 2006-10-11 18:51:02 PDT
Bob,

This semantic is the only way to ensure that the high-value entropy actually gets used on those platforms that offer it. For FIPS 140 testing, we couldn't guarantee that it gets used if we automatically and silently fall back to the low-value entropy. It seems to me that for all FIPS 140 platforms, we need to enforce the use of the high-value entropy. But it would be OK to fall back silently on platforms that we aren't validating for FIPS 140 .

Comment 32 Wan-Teh Chang 2006-10-11 19:25:22 PDT
Comment on attachment 241884 [details] [diff] [review]
Proposed patch v4 (checked in)

I checked in this patch (with an additional comment in unix_rand.c)
on the NSS trunk (NSS 3.12) and the NSS_3_11_BRANCH (NSS 3.11.4).

Checking in os2_rand.c;
/cvsroot/mozilla/security/nss/lib/freebl/os2_rand.c,v  <--  os2_rand.c
new revision: 1.5; previous revision: 1.4
done
Checking in prng_fips1861.c;
/cvsroot/mozilla/security/nss/lib/freebl/prng_fips1861.c,v  <--  prng_fips1861.c
new revision: 1.26; previous revision: 1.25
done
Checking in secrng.h;
/cvsroot/mozilla/security/nss/lib/freebl/secrng.h,v  <--  secrng.h
new revision: 1.6; previous revision: 1.5
done
Checking in unix_rand.c;
/cvsroot/mozilla/security/nss/lib/freebl/unix_rand.c,v  <--  unix_rand.c
new revision: 1.21; previous revision: 1.20
done
Checking in win_rand.c;
/cvsroot/mozilla/security/nss/lib/freebl/win_rand.c,v  <--  win_rand.c
new revision: 1.11; previous revision: 1.10
done

Checking in os2_rand.c;
/cvsroot/mozilla/security/nss/lib/freebl/os2_rand.c,v  <--  os2_rand.c
new revision: 1.4.28.1; previous revision: 1.4
done
Checking in prng_fips1861.c;
/cvsroot/mozilla/security/nss/lib/freebl/prng_fips1861.c,v  <--  prng_fips1861.c
new revision: 1.22.2.3; previous revision: 1.22.2.2
done
Checking in secrng.h;
/cvsroot/mozilla/security/nss/lib/freebl/secrng.h,v  <--  secrng.h
new revision: 1.5.28.1; previous revision: 1.5
done
Checking in unix_rand.c;
/cvsroot/mozilla/security/nss/lib/freebl/unix_rand.c,v  <--  unix_rand.c
new revision: 1.17.10.4; previous revision: 1.17.10.3
done
Checking in win_rand.c;
/cvsroot/mozilla/security/nss/lib/freebl/win_rand.c,v  <--  win_rand.c
new revision: 1.9.28.1; previous revision: 1.9
done
Comment 33 Wan-Teh Chang 2006-10-11 19:39:46 PDT
Created attachment 242022 [details] [diff] [review]
use sysinfo call in unix_rand.c (checked in)

When I stepped through RNG_SystemInfoForRNG in the debugger, I
found two problems in unix_rand.c.

1. The GiveSystemInfo function is commented out for Linux.
But the commented-out code is correct.

2. The test for a successful gethostname call is wrong.
gethostname returns 0 rather than a positive number
on success.
Comment 34 Neil Williams 2006-10-12 14:54:19 PDT
Comment on attachment 242022 [details] [diff] [review]
use sysinfo call in unix_rand.c (checked in)

Looks good.
Comment 35 glen beasley 2006-10-12 15:51:11 PDT
checked in patch for Wan-teh on 3_11 branch and trunk. 
/cvsroot/mozilla/security/nss/lib/freebl/unix_rand.c,v  <--  unix_rand.c
new revision: 1.17.10.5; previous revision: 1.17.10.4
done

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

Comment 36 Nelson Bolyard (seldom reads bugmail) 2006-10-12 20:08:40 PDT
Two of the 3 attached and reviweed patches have been checked in.
Please complete this by checking in the third patch as well.
Comment 37 Wan-Teh Chang 2006-10-13 10:05:05 PDT
Created attachment 242207 [details] [diff] [review]
Change the way we reseed the RNG (as checked in)

I checked in this patch on the NSS trunk (NSS 3.12) and
NSS_3_11_BRANCH (NSS 3.11.4).  I had to remove a comment
in rng_init that was added in proposed patch v4 because
that comment is no longer true with this patch applied.

Checking in manifest.mn;
/cvsroot/mozilla/security/nss/lib/freebl/manifest.mn,v  <--  manifest.mn
new revision: 1.49; previous revision: 1.48
done
Checking in prng_fips1861.c;
/cvsroot/mozilla/security/nss/lib/freebl/prng_fips1861.c,v  <--  prng_fips1861.c
new revision: 1.27; previous revision: 1.26
done
RCS file: /cvsroot/mozilla/security/nss/lib/freebl/sha256.h,v
done
Checking in sha256.h;
/cvsroot/mozilla/security/nss/lib/freebl/sha256.h,v  <--  sha256.h
initial revision: 1.1
done
Checking in sha512.c;
/cvsroot/mozilla/security/nss/lib/freebl/sha512.c,v  <--  sha512.c
new revision: 1.9; previous revision: 1.8
done

Checking in manifest.mn;
/cvsroot/mozilla/security/nss/lib/freebl/manifest.mn,v  <--  manifest.mn
new revision: 1.44.2.3; previous revision: 1.44.2.2
done
Checking in prng_fips1861.c;
/cvsroot/mozilla/security/nss/lib/freebl/prng_fips1861.c,v  <--  prng_fips1861.c
new revision: 1.22.2.4; previous revision: 1.22.2.3
done
Checking in sha256.h;
/cvsroot/mozilla/security/nss/lib/freebl/sha256.h,v  <--  sha256.h
new revision: 1.1.2.1; previous revision: 1.1
done
Checking in sha512.c;
/cvsroot/mozilla/security/nss/lib/freebl/sha512.c,v  <--  sha512.c
new revision: 1.8.2.1; previous revision: 1.8
done
Comment 38 Nelson Bolyard (seldom reads bugmail) 2007-11-13 01:39:27 PST
A cryptographically significant flaw has been found in the function 
CryptGenRandom.  See http://eprint.iacr.org/2007/419.pdf

Note You need to log in before you can comment on or make changes to this bug.