475090 - not enough entropy for PRNG on windows

Status: RESOLVED DUPLICATE of bug 466745

(NSS :: Libraries, defect)

Description

[Brad Lassey [:blassey] (use needinfo?)]

+++ This bug was initially created as a clone of Bug #466745 +++
> 
> When navigating to any site over https in fennec on windows ce, we get a page
> load error and a pop up that reads:
>
> SSL experienced a failure of its random number generator.
> 
>(Error code: ssl_error_generate_random_failure)

The root cause of this bug is not enough entropy.  After measuring entropy as Nelson requested on windows ce and windows desktop, we found out windows desktop does not have enough entropy to create sufficiently random numbers.

Comment 1

[Nelson Bolyard (seldom reads bugmail)]

I'm not sure we did find that.  I think this bug is based on my statement 
in bug 466745 comment 24, where I wrote: 

> There is a view that a PRNG should be seeded with an amount of truly random
> entropy that exceeds the size of the largest key that will be generated 
> from the output of that PRNG.  By that measure, most of the sets of numbers
> gathered here don't contain enough seed entropy to generate a mere 1k bit
> RSA key, much less a 2k bit key or 3k or 4k bit key.

That statement was mistaken in one important detail.  For keys for 
algorithms whose security derives from certain big number problems (RSA,
Diffie-Hellman, etc.), the number of bits of effective security is not 
equal to the number of bits in the key, but is (much) less.  The 
requirement is not that the amount of actual entropy exceed the number 
of bits in the key, but rather that it exceed to the number of bits of 
effective security for the key size.  Current recommendations are that
it exceed 150% of the effective security.

Now, here is a table that relates effective key sizes to actual key sizes 
of various algorithms.  It comes from NIST SP 800-57 part 1 tables 2-3.

Bits of   block                                          Signature  MAC KDF
security  cipher       DSA, DH        RSA        ECC       Hash      Hash
-------- ------- ----------------- --------- ----------- ---------  -------
80       2DES    L = 1024  N = 160 k = 1024  f = 160-223  SHA-1     SHA-1
112      3DES    L = 2048  N = 224 k = 2048  f = 224-255  SHA-224   SHA-1
128      AES-128 L = 3072  N = 256 k = 3072  f = 256-383  SHA-256   SHA-1
192      AES-192 L = 7680  N = 384 k = 7680  f = 384-511  SHA-384   SHA-224
256      AES-256 L = 15360 N = 512 k = 15360 f = 512+     SHA-512   SHA-256

That says that even for a 3k bit RSA key, there are only 128-bits of 
security, and only 192 bits of entropy are needed.  

NSS currently targets the 256-bit level, so it really needs 384 bits of 
entropy.  I wrote this in bug 466745 comment 27.

Comment 2

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Yeah, we need to make sure SSL works on WinCE.

Comment 3

[Brad Lassey [:blassey] (use needinfo?)]

Sorry, this was meant to be the bug for potential issues with desktop windows.  Please see bug 466745 for the windows ce specific issues.

Comment 4

[Honza Bambas (:mayhemer)]

Is there already any proposal how to exactly fix this? I am gathering some info on entropy collection and random functions in win5.0+ now, and could potentially work on this bug.

Comment 5

[Honza Bambas (:mayhemer)]

So, on windows desktops (NT, XP, Vista) we (currently) use RNG_SystemRNG function to initially gather random noise. It is called from prng_fips1861.c that goes away after patch for bug 457045 lands. fips1861 RNG demands 1024 bytes of noise. New drbg_nist800_90 demands according to comments at the top at most 880 bits, that means 110 bytes, ten times less.

While tracing on windows xp I can see that SystemFunction036 (called first) has no problem to return 1024 bytes of rnd noise. CryptGenRandom user when SystemFunction036 failed also has no problem with it.

Personally I would ensure to give a try to CryptGenRandom first before SystemFunction036 that is, AFAIK, vulnerable to prediction attacks. CryptGenRandom has changed in win vista sp1 and win server 2008 (not sure which sp number at the moment) to be FIPS-140-2 compliant and not to be vulnerable to this attack any more, it no more forwards to SystemFunction036 (RtlGenRandom). I didn't find evidence this has been fixed in windows xp sp3.

Or am I completely out?

Comment 6

[Nelson Bolyard (seldom reads bugmail)]

Honza, there is a big difference between "bits of entropy" and "bits of input".
When collecting entropy from sources whose amount of entropy is not known 
to be 100%, it is necessary to collect more bits of input than the required
number of bits of entropy.  

I think the concerns expressed in this bug are probably going to be resolved 
as part of Bug 466745, from which this bug was duplicated.

Comment 7

[Nelson Bolyard (seldom reads bugmail)]

I believe this bug is now resolved by the checkin for bug 466745, so I 
am marking this bug as a duplicate of that one.  Reopen this if you 
disagree.