868860 - Initialize Math.random() PRNG with a better seed

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Chris Peterson [:cpeterson]]

Attachment: random-seed.patch

In bug 322529 comment 87, bsmith suggested opening a new bug to discuss improving Math.random()'s seed. This patch implements something similar to daw's "Level 2" suggestion from bug 322529 comment 74: seed Math.random() from something secure without changing the current PRNG algorithm.

This patch seeds Math.random() from /dev/urandom (on XP_UNIX, including OSX) or rand_s() (on Windows). Seeding is done lazily so compartments that never call Math.random() have no overhead. JSRuntime no longer needs rngNonce because each compartment should be getting a very random seed, even for compartments that are seeded at the same PRMJ_Now() time.

I investigated calling NSS' PK11_GenerateRandomOnSlot(), but that approach seemed messier. Firefox initializes SpiderMonkey before NSS, so JSRuntime would need to call NSS_Init() (and I don't know what side effects initializing NSS earlier might introduce). Firefox also unloads NSS before SpiderMonkey, so an "xpcom-shutdown" observer could call Math.random() and NSS would be gone.

Comment 1

[Zack Weinberg (:zwol)]

I think it might be more appropriate to use CryptGenRandom for the seed on Windows.  The rand_s documentation doesn't give me the warm fuzzies regarding its cryptographic soundness.

Comment 2

[Chris Peterson [:cpeterson]]

(In reply to Zack Weinberg (:zwol) from comment #1)
> I think it might be more appropriate to use CryptGenRandom for the seed on
> Windows.  The rand_s documentation doesn't give me the warm fuzzies
> regarding its cryptographic soundness.

MSDN says rand_s() "depends on" RtlGenRandom(). And according to Wikipedia and other sources [1], CryptGenRandom() itself is implemented using RtlGenRandom() (plus the CryptoAPI overhead for CryptAcquireContext()).

[1] http://cryptodox.com/CryptGenRandom

Comment 3

[Luke Wagner [:luke]]

(cc'ing some other people that may know more about the history of Math.random)

Could you explain a bit more about the security concern and problem being solved here?

Comment 4

[Chris Peterson [:cpeterson]]

Bug 322529 has a discussion of some concerns about Math.random(), including web content unwisely using Math.random() for JS crypto; side channel attacks from other compartments on the predictable seed; and the seed leaking addresses of heap or stack memory. Also, window.crypto.getRandomValues() is not available to workers.

A more radical proposal from bug 322529 was to replace Math.random()'s PRNG algorithm, not just the seed, with output from window.crypto.getRandomValues().

Comment 5

[Zack Weinberg (:zwol)]

(In reply to Luke Wagner [:luke] from comment #3)
> Could you explain a bit more about the security concern and problem being
> solved here?

*For this bug*, the principal concern being addressed is cross-compartment information leakage via the random seeds not being different enough, AIUI.  As Chris says, see bug 322529 for more.

(In reply to Chris Peterson (:cpeterson) from comment #2)
> MSDN says rand_s() "depends on" RtlGenRandom(). And according to Wikipedia
> and other sources [1], CryptGenRandom() itself is implemented using
> RtlGenRandom() (plus the CryptoAPI overhead for CryptAcquireContext()).

Oh, that's unfortunate; it was RtlGenRandom itself that was not giving me the warm fuzzies.  Still, that does mean there's no reason not to go for the simpler rand_s interface.

Comment 6

[:Gavin Sharp [email: [e-mail]]]

(In reply to Zack Weinberg (:zwol) from comment #5)
> Oh, that's unfortunate; it was RtlGenRandom itself that was not giving me
> the warm fuzzies.

Related: bug 504270, and specifically bug 504270 comment 6.

Comment 7

[Zack Weinberg (:zwol)]

Let me clarify that it is the *cryptographic soundness* of RtlGenRandom that is not giving me the warm fuzzies.  Specifically, the description here of its internal algorithm:

https://blogs.msdn.com/b/michael_howard/archive/2005/01/14/353379.aspx?Redirected=true#353493

gives me the impression that on any single machine, nearly all the intra-machine variation is coming from various cycle counters, and so it may not actually be equivalent to /dev/urandom in terms of "true" randomness produced.

Having said that, I only objected because I had been under the impression that CryptGenRandom was a stronger RNG.  If this is the best one can get right now on Windows, then that's going to have to do.

Comment 8

[Luke Wagner [:luke]]

Comment on attachment 745699 [details] [diff] [review]
random-seed.patch

Review of attachment 745699 [details] [diff] [review]:
-----------------------------------------------------------------

Oops, this fell off my radar.

Yes, the information leakage between compartments via JSRuntime::rngNonce makes sense.  I'm in no position of experience to evaluate the OS-specific seeding calls in random_generateSeed, so I'll delegate that portion of the review to Zack, although feel free to suggest a more appropriate reviewer.

::: js/src/jsmath.cpp
@@ +13,5 @@
> +#define _CRT_RAND_S
> +#endif
> +
> +#include <fcntl.h>
> +#include <stdlib.h>

According to https://wiki.mozilla.org/JavaScript:SpiderMonkey:C_Coding_Style#Includes, could you put fncntl.h and stdlib.h #includes below the mozilla/ #includes, before jstypes.h?

@@ +599,5 @@
> +    MOZ_ASSERT((*rngState & 0xffff000000000000ULL) == 0, "Bad rngState");
> +    MOZ_ASSERT(bits > 0 && bits <= 48, "bits is out of range");
> +
> +    if (*rngState == 0) {
> +        random_initState(rngState);

No { } around single-line then branch.

Comment 9

[Zack Weinberg (:zwol)]

Comment on attachment 745699 [details] [diff] [review]
random-seed.patch

The platform-specific gunk looks good to me.

Comment 10

[Chris Peterson [:cpeterson]]

(In reply to Luke Wagner [:luke] from comment #8)
> ::: js/src/jsmath.cpp
> @@ +13,5 @@
> > +#define _CRT_RAND_S
> > +#endif
> > +
> > +#include <fcntl.h>
> > +#include <stdlib.h>
> 
> According to
> https://wiki.mozilla.org/JavaScript:SpiderMonkey:C_Coding_Style#Includes,
> could you put fncntl.h and stdlib.h #includes below the mozilla/ #includes,
> before jstypes.h?

If any of the mozilla/ headers #include Windows' stdlib.h before _CRT_RAND_S is #defined, then stdlib.h won't expose the rand_s() function prototype.

If move the fcntl.h and stdlib.h #includes to their proper order, I could just leave #define _CRT_RAND_S at the top of jsmath.cpp or #define _CRT_RAND_S in the JS makefile. I think that should work. However, #defining the macro in the makefile would affect more .cpp files than necessary.

Do you have a preference?

Comment 11

[Luke Wagner [:luke]]

Thanks for the thoughtful consideration.  The option you mentioned of leaving the #define at the top of jsmath.cpp sounds like the right thing to do.  If we needed this a second place, I'd probably want to put this in jswin.h (our Windows fudge-file).

Comment 12

[Chris Peterson [:cpeterson]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/ddfd95298835

Comment 13

[Chris Peterson [:cpeterson]]

Fix bustage: XP_UNIX must #include unistd.h to get read() and close() definitions.

https://hg.mozilla.org/integration/mozilla-inbound/rev/ac913f0cde8e

Comment 14

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/ddfd95298835
https://hg.mozilla.org/mozilla-central/rev/ac913f0cde8e