Closed Bug 322529 Opened 19 years ago Closed 8 years ago

Upgrade Math.random() to the better XorShift128+ algorithm

Categories

(Core :: JavaScript Engine, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla45
Tracking Status
firefox45 --- fixed

People

(Reporter: daumling, Assigned: jandem)

References

()

Details

(Keywords: sec-want, Whiteboard: [adv-main45-])

Attachments

(7 files, 1 obsolete file)

Change Math.random() to the MT-19937 algorithm, which is found at the above URL.

The file mentioned in the URL contains a copyright notice - lincensing issues need to be checked before adding the code.
Status: NEW → ASSIGNED
(In reply to comment #0)
> The file mentioned in the URL contains a copyright notice - licensing issues
> need to be checked before adding the code.

Copyright holders do not assign copyright to mozilla.org when contributing patches so the copyright notice is ok, it's the license terms the copyright holders picked that matter.  Shaver said "looks like BSD-with-attribution."

I've mailed licensing gurus and I will comment with the results of that inquiry when it has reached a conclusion.

/be
Michael, did you mean to take assignment?  Usually a bug isn't marked ASSIGNED without the assignee being a real person, not general@js.bugs.

/be
Assignee: general → daumling
Status: ASSIGNED → NEW
I would expect portability problems with the 64-bit version of the algorithm, so I'd rather implement the 32-bit version, found at:

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c

Comments?

Brendan, you mentioned that Graydon Hoare has joined Mozilla - could you add him to the cc list?

Status: NEW → ASSIGNED
Michael: We have 64-bit integer type support on all platforms, finally.  What 64-bit portability problems were you worried about?

/be
There are numerous ways to express unsigned 64-bit constants. Do all platforms support xxxULL? What about minimachines like cellphones? I bet that SM is in use there, too. Are we aware of any 64-bit issues there? I think that we could just as well use the 32-bit version to be on the safe side.
Our compilers are either from GNU or MS, and both support LL and ULL.  We have had > 10 years at this, and so we had to use prlong.h or its standalone-SpiderMonkey fork jslong.h.  The macros defined there allowed us to emulate long long where it was broken or missing, but we haven't had any problems in ages.  Still, if we did, we could keep using jslong.h for a bit longer, especially in SpiderMonkey.

My question was more about what we lose if we don't use more bits, though.

/be
Good question. My math skills are rudimentary at best - Graydon, would you like to step in? Can you compare the two algorithms (32 vs 64 bits) and let me know which one to implement? Thanks.
(caveat: I'm *not* a PRNG-analyst)

I don't think it's "using more bits" in any important sense. The period size is the same, the dimensionality and distribution is the same, the state vector has the same size, and the algorithm is very similar at each step (except that one returns 64-bit numbers rather than 32-bit ones). 

I'd go ahead and use the 32-bit one, given the target value you want is 32 bits.
Well, we actually want a double between 0 and 1, whose mantissa is 53 bits. Would 32 bits still do then?
There's a wish for MT-19937 in NSPR, for all code (C or C++) to share.  Wan-Teh, what do you think?

/be
Brendan, what is MT-19937?
Please read here: 

http://www.cliki.net/MT19937
Some one else also has provided code for Mersenne Twister random number generation:
http://www.qbrundage.com/michaelb/pubs/essays/random_number_generation.html
So, may be that one can be used more easily?
Brendan, you asked in comment #10:
> There's a wish for MT-19937 in NSPR, for all code (C or C++) to share. 
> Wan-Teh, what do you think?

Alfred found that there is an existing RFE for a thread-safe pseudorandom
number generator in NSPR (bug 143493).  The code in
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/C-LANG/mt19937-64.c
and http://www.qbrundage.com/michaelb/pubs/essays/random_number_generation.html
both stores the states in static/global variables, so they need to be made
thread-safe.
Brendan,

I recently read about Mersenne Twister in a magazine.
Let's do it.

What should the API be?  Modeled after rand() and srand()
and thread-safe?
Summary: Upgrade Math.random() to a better algorithm → Upgrade Math.random() to a better algorithm, such as Mersenne Twister
wtc: I'm fine with libc-like API but thread-safe and reentrant -- no hidden globals or statics.

Brian, can you knock this one down?

/be
Assignee: daumling → crowder
Status: ASSIGNED → NEW
It seems like we have competing criteria for our RNG here.  Do we want fast or do we want cryptographically secure?  Perhaps we really need to have multiple RNG alternatives...  it might be interesting to consider providing a few different RNG objects, natively implemented for speed, but with different randomness/performance characteristics.  For example, at the browser level (outside the language) it seems like we ought to be able to find some good entropy sources to feed a less-"psuedo" RNG (mouse-movement, typing, loaded data, etc.), while we could use either MT or the current RNG as a "fast" PRNG (for people who require "predictable" random results from a given seed and don't care about crypto), and then offer Blum Blum Shub as a better crypto alternative for people who need that?

What is the legal status of MT or Blum Blum Shub?  Are these encumbered algorithms?

Also, none of this has anything to do with web-standards.  :)  What would ECMA think of introducing more/better RNG alternatives into the JavaScript spec?  Would it make sense to talk about a DOM equivalent of /dev/random for the browser?
Status: NEW → ASSIGNED
> it seems like we ought to be able to find some good entropy sources to feed a
> less-"psuedo" RNG

We already have entropy collector APIs that NSS uses.

In fact, if we're talking about "cryptographically secure" stuff we should really be ccing NSS folks.
Where/what are those APIs?  Are they documented?  Available to JavaScript code?  Do they work cross-browser?
Well, at the moment NSS is a consumer of entropy. See nsIEntropyCollector (which it implements).

So it could expose an API to provide seeds and such, possibly, using this entropy.  It's already got all the actual code for its own purposes.

And pretty much by definition NSS stuff is not cross-browser. ;)
So that would help for chrome issues (bug 369390), but not for this bug in particular.  Then, the question is whether or not the JavaScript PRNG should concern itself more with being cryptographically secure or more with being fast, or as I mentioned previously, we should provide interfaces to different RNGs somehow.
(In reply to comment #1)
> I've mailed licensing gurus and I will comment with the results of that inquiry
> when it has reached a conclusion.

Did you reply with this data and I missed it?  What about Blum Blum Shub?
(In reply to comment #22)
> So that would help for chrome issues (bug 369390), but not for this bug in
> particular.  Then, the question is whether or not the JavaScript PRNG should
> concern itself more with being cryptographically secure

There's no need for it for Web JS, and it could be an interoperation problem if Math.random() slows down a lot.

We have XPCOM and JS bridged, so we can interface to lots of native PRNGs. This bug is really about Math.random.  Likewise, more entropy for ECMA APIs is a topic for es4-discuss@mozilla.org, not this bug.  FWIW, see

http://lxr.mozilla.org/mozilla/ident?i=nsIEntropyCollector

and follow the links. IIRC we still have very bogus "entropy" collection in NSS that should use /dev/*random.

/be
Can't we just use srandom/random instead of srand/rand, at least for an easy fix ? They have the same interface, are just as fast, but produce slightly better random numbers. The difference is that rand() produces a much less random sequence; in fact, the low dozen bits generated go through a cyclic pattern. All the bits generated by random() are usable. For example, random()&0x01 produces a random binary value, unlike rand()&0x01.

The only problem is that srandom/random is not available on Windows and on some older Unix platforms. That's why you often find this code in header-files :
#define srandom srand
#define random rand

People that want access to a better PRNG (interfaces with NSS I suppose) need a different interface anyway. Most PRNG's don't produce integer-sized random numbers for instance.

I've used srandom/random myself a few times to replace srand/rand, to quickly fix some security issues (rand is really predictable !). Other solutions (SHA-256 in block cipher mode for instance, as used in Yarrow and Fortuna) where often too slow.
Math.random() in spidermonkey doesn't actually use rand() or srand(), it uses a relatively common PRNG algorithm.  I don't know enough to compare them mathemetically, but you can examine it for yourself here:

http://mxr.mozilla.org/seamonkey/source/js/src/jsmath.c#366

I don't know how most Unixes do srandom()/random(), but I'd be surprised if it's too different from either this (which is basically an old Knuth algorithm, essentially) or MT-19937.
> IIRC we still have very bogus "entropy" collection in NSS that should use 
> /dev/*random.

Thanks for the vote of confidence, Brandan :-/

NSS has a cryptographically secure prng, which it seeds with numerous sources,
and which the application may help to seed.  It was created over 10 years ago 
to solve the very same problem that is reported here.  Srand seeded with time_t,
whose output is far too predictable.  SO, now that someone has rediscovered 
that problem, it's ironic that you would be turning people away from, not
towards, 
Brendan, NSS 3.11.x uses the system RNG (/dev/urandom on Unix and Linux)
as one of the entropy sources for its PRNG.  See
http://lxr.mozilla.org/seamonkey/ident?i=RNG_SystemRNG
(In reply to comment #27)
> > IIRC we still have very bogus "entropy" collection in NSS that should use 
> > /dev/*random.
> 
> Thanks for the vote of confidence, Brandan :-/

You and I go back to SGI, you know you have my confidence (although misspelling my name gives me pause :-P).

> NSS has a cryptographically secure prng, which it seeds with numerous sources,
> and which the application may help to seed.  It was created over 10 years ago 
> to solve the very same problem that is reported here.

Yeah, I was at Netscape then (not sure whether you were yet). Lots of struggling to get >512 bits of entropy. Not all of the results were sound.

I'm thinking of bug 96058 and bug 338601 here, both still open (validly open?).

> Srand seeded with
> time_t,
> whose output is far too predictable.

Sure, that's not being disputed.

> SO, now that someone has rediscovered 
> that problem, it's ironic that you would be turning people away from, not
> towards, 

Your comment was cut off here.

(In reply to comment #28)
> Brendan, NSS 3.11.x uses the system RNG (/dev/urandom on Unix and Linux)
> as one of the entropy sources for its PRNG.  See
> http://lxr.mozilla.org/seamonkey/ident?i=RNG_SystemRNG

Great -- sorry I missed that and impugned NSS for not using /dev/random. Does NSS still also read and/or stat a bunch of OS files?

How about Windows and Mac OS X?

This is all topic for other bugs, some of which seem unfixed. My memory is not matching bugzilla query results, but I recall existing code still reading (data or attributes) from system files hoping for entropy, and I even recall a defense of UMRs in NSS code (reading alignment padding) on the grounds that such UMRs were a source of entropy. I don't believe that's sound at all.

Apologies again if my memory is of fixed bugs, but flashing back to 10 or 11 years ago (or was it 12 now?) does not give me confidence.

/be
NSS uses /dev/urandom (rather than /dev/random) on Unix, Linux,
and Mac OS X.  NSS also uses the system random number generator
(either CryptoAPI's CryptGenRandom or the new RtlGenRandom function)
on Windows.  NSS still reads and stats a bunch of OS files.  The
UMRs in NSS PRNG code were eliminated on 2006-04-03.
(In reply to comment #30)
> NSS uses /dev/urandom (rather than /dev/random) on Unix, Linux,
> and Mac OS X.  NSS also uses the system random number generator
> (either CryptoAPI's CryptGenRandom or the new RtlGenRandom function)
> on Windows.

Great -- should bug 331314 be closed?

> NSS still reads and stats a bunch of OS files.

How many bits of entropy worst case does this provide?  This still seems bogus to me (amateur info-theorist and old Unix hacker that I am).

> The UMRs in NSS PRNG code were eliminated on 2006-04-03.

Sorry I couldn't find that bug (I don't know why) -- could you cite its number.

/be
(In reply to comment #31)
> > The UMRs in NSS PRNG code were eliminated on 2006-04-03.
> 
> Sorry I couldn't find that bug (I don't know why) -- could you cite its number.

Bug 287116.
Brendan, entropy is relative to how much the attacker knows
about the system (*conditional* probabilities).  If the attacker
is another user on the same system, then reading and stat'ing
those (static) OS files provides 0 bits of entropy.  If the attacker
is remote and doesn't know the exact configuration of the system
(the more common case), it will provide some bits of entropy.
Guys, we're getting far afield here.  See comment 21.  We all agree NSS collects entropy and has a good random-number generator.  Does it expose this random-number generator to consumers?  If so, what's the relevant API?  We should  just use this random-number generator in whatever code needs random numbers in most of Gecko.  See also bug 369428, which might be a better place for the discussion about the non-JS stuff.
bz's right, sorry for using this bug as a discussion forum. I'll continue this thread in bug 338601.

/be
(In reply to comment #34)
> Does it expose this
> random-number generator to consumers?  If so, what's the relevant API?  We
> should  just use this random-number generator in whatever code needs random
> numbers in most of Gecko.

nsIDOMCrypto.random(), which is also exposed as window.crypto.random(). Marking this bug as dependent on 440046.
Depends on: 440046
If we're going to provide a DOM solution to this, and not a JS-integrated solution, then perhaps we should WONTFIX this bug?
I just filed bug 464071 which highlights exploitable weakness in our implementation of Math.random.  We may, therefore, want to take another look at this bug.
Mass unowning JS bugs...  I'm not likely to be able to move these forward.
Assignee: crowder → general
Status: ASSIGNED → NEW
so, the bug i just submitted, which is a security vulnerability in the current math.random() PRNG, was tagged as a duplicate of this one.  not sure if this is accurate or not, but the suggestion to use a Mersenne Twister for this would be insufficient since that algorithm is not cryptographically secure.  an appropriate solution would be to use one of the system's PRNGs with sufficient entropy or something provable unpredictable like Blum Blum Shub.
Is this bug stalled waiting for an answer to Boris's questions in comment 34?
Those are really PSM questions, not NSS questions, I believe.  
NSS certainly makes its PRNG available to all NSS users.  If PSM doesn't 
offer a suitable XPCOM wrapper (and I simply don't know if it does or not),
then that should be easy (or at least straight-forward) to fix.
My question got answered in comment 36, I think.  This bug is stalled on someone actually doing the work, I think.
Did we ever decide whether to make Math.random() cryptographically secure?  What perf impact would that have?  Is that even possible, given that it's not allowed to throw?  As opposed to:

* Upgrade Math.random() to Mersenne Twister to increase the period size, making it better for fuzzing and mathematical simulations.

* Expose a new API to web pages that want cryptographically secure randomness, which might need to throw when NSS is out of entropy.

* Somehow prevent cross-domain tracking (???)
all PRNGs in all web browsers should be cryptographically secure to prevent against unknown attacks (not just this one).  note that libbsd on linux provides arc4random, which has similar performance to random and is cryptographically secure.
(In reply to comment #45)
> all PRNGs in all web browsers should be cryptographically secure to prevent
> against unknown attacks

It's not as dire as you make it sound. The web server providing the content can also provide PRNGs. Having said that, I realize there are circumstances where there is no web server (e.g. local file system content and addons)
i don't see how that statement would be interpreted as "dire".  my point is that security decisions should be made based on the precautionary principle.  if you can use a cryptographically secure PRNG and prevent future unknown "predictability" attack vectors (with reasonable performance), then why not do so?

i would hope that the webservers are using cryptographically secure PRNGs as well.
Michael Gilbert: the only "precautionary principle" I've heard of is politicized nonsense. What definition are you using?

/be
so, the wikipedia article is a reasonable starting point, but perhaps too focused one case: the environment.  the concept i am alluding to is similar to the medical profession's hipcratic oath; do no harm.  extrapolating to software; do not accept risk for your users (even if you can't exactly define what that risk is) if there are (reasonable) solutions that can effectively nullify that risk.
   Hey you, stop being... so unsafe!  Smitty!  Safen up!
   -- Homer tries to look busy, ``Burns Verkaufen der Kraftwerk''

Risk = cost * probability.

A threat may seem serious enough, even if it's unlikely, that we should throw cycles at mitigation. But we don't know all the costs (including opportunity costs, that is, costs of not exploring alternatives) and we definitely don't know all the probabilities.

"Do no harm" has specific meaning when intervening in medicine according to well-studied procedures and outcomes, but it is not well-defined when cause and effect are not understood or quantified (as in this bug viz "security" vs. other costs and benefits).

One can take arbitrary "precautions" by ignoring direct and opportunity costs, and thereby create a disaster -- this is a big problem in regulatory policy. For example the U.S. federal government effectively values a human life, or a certain number of years of life extension beyond the average, in wildly inconsistent ways and dollar amounts, depending on the risk particulars and the regulatory domain.

The downside of making Math.random a cryptographically strong PRNG is that some web sites probably depend on the current 1995-vintage linear congruential piece of crap cloned from Java, which we have shipped forever, in the sense that they'd notice performance regressions if Math.random grew slower (albeit stronger).

There ain't no such thing as a free lunch. We know less than we think. Therefore invoking the PP doesn't help make the case for a computationally expensive fix to this particular bug.

On the other hand, we have had Moore's Law compounding since 1995. It would be interesting to try an experiment for mozilla1.9.2 (current mozilla-central trunk) of swapping in a crypto PRNG for Math.random. It may be that no one would notice the perf hit. But we need someone to volunteer to write the patch and take over assignment of this bug. Anyone game?

/be
As per comment 36, is "write the patch" equivalent to "copy the code that exposes  nsIDOMCrypto.random() as window.crypto.random(), and have the copy also expose nsIDOMCrypto.random() as Math.random()"? Plus or minus return-value-expectations that might differ between window.crypto.random() and Math.random()? 

Just trying to clarify.
Main thing is return value -- Math.random returns a double, nsIDOMCrypto.random returns bytes in uint16s in a DOMString, IIRC.

I get this

Error: uncaught exception: [Exception... "Component returned failure code: 0x80004001 (NS_ERROR_NOT_IMPLEMENTED) [nsIDOMCrypto.random]"  nsresult: "0x80004001 (NS_ERROR_NOT_IMPLEMENTED)"  location: "JS frame :: javascript:alert(crypto.random(16)) :: <TOP_LEVEL> :: line 1"  data: no]

trying javascript:alert(crypto.random(16))

/be
Here are some popular benchmarks that will probably regress (even if only by an ms or two):

$ grep -w Math.random t/*.js v8/*.js
t/string-base64.js:        str += String.fromCharCode( (25 * Math.random()) + 97 );
t/string-validate-input.js:      var l = Math.floor(26*Math.random());
t/string-validate-input.js:      var l = Math.floor(9*Math.random());
v8/crypto.js:  while(rng_pptr < rng_psize) {  // extract some randomness from Math.random()
v8/crypto.js:    t = Math.floor(65536 * Math.random());
v8/earley-boyer.js:           (peephole (hole 1 "Math.floor(Math.random()*" 'n ")")))
v8/earley-boyer.js:    return Math.floor(Math.random()*n);

/be
My vote:
Let Math.random() be based on Mersenne Twister, let window.crypto.random(num) use security/manager/ssl/src/nsRandomGenerator.cpp (nsIRandomGenerator.idl).
I can do the work, but I need to know what's the conclusion.
in order to sufficiently address security concerns, a cryptographically secure PRNG should be used.  see, for example, libbsd's arc4random, which lynx uses to address this issue.  see discusion [1] and in particular see [2],[3] for solution.

[1] http://lists.gnu.org/archive/html/lynx-dev/2009-07/msg00000.html
[2] http://lists.gnu.org/archive/html/lynx-dev/2009-07/msg00004.html
[3] http://lists.gnu.org/archive/html/lynx-dev/2009-07/msg00010.html
I don't think the question here has ever been about whether or not Math.random() is cryptographically secure.  We concede that it isn't.  The question is about whether or not it needs to be and what the costs are of making it be.
(or whether something in-between -- that is, still not cryptographically secure, but better randomness, like M-T -- would serve as a good compromise)

Perhaps an extension which provides a cryptographically secure RNG could be made separately?
My vote is to implement comment #54.
It'd be interesting to microbenchmark M-T versus the old Knuth-style algorithm to see how much worse it is (better?), too.  Honza, have you tried that?
Aside: MT19937 is *not* a CSPRNG, nor is any RC4 / arc4 derivative, including the thingy on BSD (it does not claim to be). Please don't use either of these, or keep asking for anything related to them in such bugs; you are gaining no security at all by using one. They only "look good" for simulation and non-security contexts. Indeed, the use of an RC4-variant in historical versions of windows CryptGenRandom is the root of the reason NSS doesn't trust CryptGenRandom even as a <em>seed</em>, much less an exposed-to-the-user PRNG stream. Which is IMO sort of overkill since exploiting it requires breaking into the machine, and since NSS <em>itself</em> is using NIST SP 800-90 in Hash_DRBG and relying on the (rapidly crumbling) cryptographic strength of the SHA-1 family of CHFs. NSS should shift to something else -- ISAAC, BlumBlumShub or at least 800-90 Dual_EC_DRBG -- and seed from CryptGenRandom alone. But that's in another bug.

(Take a look through http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator and http://www.eecs.berkeley.edu/~daw/rnd/index.html if you care about any of this business)

Related to *this* bug: I disagree with comment 54 and reiterate my proposal in comment 51. I think we have to bite the bullet and take the hit of directing Math.random() into the same place as window.crypto.random(): NSS. If linking to NSS in shell builds is complex, we need to port the NSS CSPRNG to the shell, to keep benchmark numbers similar between shell and browser. Adding *new* implementations of Math.random() alone, using simulation-oriented PRNGs, is a distraction. Users will use Math.random() in places they need a CSPRNG. Content attacks are the root of all this. We have actual exploits open. Since when do we avoid fixing exploits to win benchmarks?

Besides, a little reading-the-code shows that in string-base64, Math.random() is only used to initialize the test, not run the expensive loop; the v8 crypto test is actually an implementation or arc4, again only using Math.random() as a seed; and in earley-boyer you're looking at a machine-translation of two benchmarks from scheme (charming!) in which that the scheme library translator emitted some wrappers that call Math.random(), but nothing actually calls them from the benchmarks. 

I think you'll only see substantial affects in string-validate-input. And in all these cases, it's actually pretty corny to have any nondeterminism in there; I'm sure Apple and Google would be happy to remove PRNGs even from the margins of their benchmark suites, or bake-in a pre-seeded LFSR written in js, overriding Math.random(), or similar.

As for breaking existing content: JavaScriptCore switches, by platform, between arc4random() on darwin, rand_s() on windows and random() on unix. And we hit our own homebrew LFSR. I don't know what IE does but I wager it doesn't hit our LFSR. Unless content relies on *timing* the PRNG -- or on it being a specific speed -- I would expect such content is already incompatible with everyone except IE.
Graydon: great, we're on the same page about trying this experiment -- does this mean you are gonna take this bug? :-P

/be
Ok, but only after a few parts of the NJ worklist get knocked down :)
Assignee: general → graydon
since there is once again new discusison on mersenne twister, clarification must be needed.  m-t cannot be considered secure because its state space is predictable.  given k known bits, an attacker can predict the (k+1)'th bit in polynomial time.  game over.
(In reply to comment #64)
> since there is once again new discusison on mersenne twister, clarification
> must be needed.

Lose the passive voice!

>  m-t cannot be considered secure because its state space is
> predictable.  given k known bits, an attacker can predict the (k+1)'th bit in
> polynomial time.  game over.

Yes, this is why Graydon has kindly taken ownership of the bug; he knows all about crypto.

/be
(In reply to comment #65)
> Yes, this is why Graydon has kindly taken ownership of the bug; he knows all
> about crypto.

Ha! I get it wrong almost every time, and only vaguely understand what's going on in most papers. But in this case there are some federal recommendations to follow, and some NSS guys to ask for review. I think we'll be ok so long as we avoid actually trying to write a CSPRNG ourselves :)
How many calls would a CSPRNG-backed Math.random() be able to take before it would have to start throwing?  Would a lot of games break?
(In reply to comment #67)
> How many calls would a CSPRNG-backed Math.random() be able to take before it
> would have to start throwing? 

Do you expect that to be a finite number?  

NSS 3.12.3's PRNG (actually a DRBG :) can handle up to 2^48 calls before 
reseeding, but it just reseeds itself and goes on.  No throwing required.

http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/security/nss/lib/freebl/drbg.c&rev=1.9&mark=71-78#71
Wow, nice.
It turns out Math.random calls in SunSpider and (IIRC) V8 do matter and they do show up in profiles -- Andreas removed ancient locking around runtime-wide (like process wide in Unix terms) RNG state in order to cure this, in bug 511328.

We need to use deterministic benchmarks. We should *shun* non-deterministic ones.

/be
I thought I'd throw in a poke: it might be a good time to look again at making Math.random() take numbers from a cryptographic-strength PRNG.

There have been several security vulnerabilities related to Math.random(), including one fairly recent problem.  See, e.g.,
 * http://seclists.org/bugtraq/2010/Sep/114 (and bug #577512)
 * http://www.trusteer.com/files/Temporary_User_Tracking_in_Major_Browsers.pdf (and bug #464071)
 * side channels in Javascript sandboxes (e.g., http://code.google.com/p/google-caja/issues/detail?id=448)
Any time you have multiple related security issues, I recommend examining the root cause and checking whether there are any steps that could be taken to prevent future problems and eliminate entire classes of failure modes.  In this case, the fact that Math.random() is not cryptographically secure seems to be a source of non-obvious security problems.

CSPRNGs can be fast (e.g., arc4random(), AES-CTR, /dev/urandom).  I cannot rule out the possibility of apparent performance regressions on microbenchmarks, but I would expect the real-world performance impact of shifting to a CSPRNG to be small.

Mersenne Twister (MT) is not cryptographically secure.

CSPRNGs never need to throw.  Usually CSPRNGs do not require reseeding; they can generate an effectively infinite stream of pseudorandom bits.  (If reseeding should be necessary, one can simply automatically reseed: I don't know why you'd throw an exception.  But reseeding usually isn't needed for modern cryptographic algorithms anyway.)

I'm surprised to see a claim that arc4random() isn't cryptographically secure.  Do you know something I don't?  As far as I know, if arc4random() is properly seeded, it's cryptographically secure.  That said, using a CSPRNG from NSS should be fine, too.  I'm not trying to push any particular choice of CSPRNG.
Since bug #577512 is not open to the public (even though the underlying vulnerability seems to be public), I'll post here.

1. Has anyone looked at whether the current Math.random() implementation poses any risks to ASLR?  As I understand it, currently Math.random() is seeded with time ^ ptr1 ^ ptr2, and Javascript code that calls Math.random() can reconstruct the seed.  Javascript can also form a fairly good guess at the time of seeding.  This suggests that malicious Javascript may be able to gain some information about ptr1 ^ ptr2.  In general, revealing pointer values may undermine the security benefits of ASLR, making it easier to exploit other browser vulnerabilities.  I don't know whether, in this particular case, the xor of two pointer values leaks information that could be used to defeat ASLR.  Has anyone looked at this?

2. Does the Math.random() seeding process create a side channel that could be used by a malicious web page to spy on other windows/tabs/frames from other origins?  Malicious Javascript can call Math.random() and recover the initial seed; by forming a guess at the time of seeding, it can presumably also recover partial information about ptr1 ^ ptr2.  A malicious site can open many pages in different frames (each of which will get its own seed) and recover each such seed.  Does this allow the malicious site to gain information about the behavior of the memory allocator?  For instance, if the malicious site does this once every 10ms, can it get partial information about how many new objects were allocated, as a function of time?  If the malicious site can gain this kind of information, does it create a side channel that might enable it to learn something about secret values being processed in windows/tabs/frames?  In general, in cryptography we have long experience suggesting that any time an attacker can observe a value that is measurably correlated to a secret, side channel attacks are a serious threat (even if there is a good deal of noise.)  Has anyone looked at this?  (I expect the answer to be platform-dependent.)

I have no clue whether either of these pose any practical risk.  But perhaps I should pose the question like this: How confident are we that none of the scenarios raised above pose any practical security risk to users of Firefox?  How confident are we that we won't see a new Amit Klein paper next year that exploits these properties of Math.random()?  If the answer is anything less than "very confident", that may be an argument to transition Math.random() to a CSPRNG.

(I don't think re-seeding the Math.random() PRNG on every page load/every page instance eliminates these concerns.)
(In reply to daw-redhatbugzilla from comment #72)
> Since bug #577512 is not open to the public (even though the underlying
> vulnerability seems to be public), I'll post here.

Hi David -- thanks for raising these, sorry I missed them till now.

> 1. Has anyone looked at whether the current Math.random() implementation
> poses any risks to ASLR?  As I understand it, currently Math.random() is
> seeded with time ^ ptr1 ^ ptr2, and Javascript code that calls Math.random()
> can reconstruct the seed.  Javascript can also form a fairly good guess at
> the time of seeding.  This suggests that malicious Javascript may be able to
> gain some information about ptr1 ^ ptr2.  In general, revealing pointer
> values may undermine the security benefits of ASLR, making it easier to
> exploit other browser vulnerabilities.  I don't know whether, in this
> particular case, the xor of two pointer values leaks information that could
> be used to defeat ASLR.  Has anyone looked at this?

These are heap pointers, so not correlated with ASLR'ed code addresses as far as dveditz and I know -- anyone know better?

> 2. Does the Math.random() seeding process create a side channel that could
> be used by a malicious web page to spy on other windows/tabs/frames from
> other origins?  Malicious Javascript can call Math.random() and recover the
> initial seed; by forming a guess at the time of seeding, it can presumably
> also recover partial information about ptr1 ^ ptr2.  A malicious site can
> open many pages in different frames (each of which will get its own seed)
> and recover each such seed.  Does this allow the malicious site to gain
> information about the behavior of the memory allocator?

Probably.

> For instance, if
> the malicious site does this once every 10ms, can it get partial information
> about how many new objects were allocated, as a function of time?  If the
> malicious site can gain this kind of information, does it create a side
> channel that might enable it to learn something about secret values being
> processed in windows/tabs/frames?  In general, in cryptography we have long
> experience suggesting that any time an attacker can observe a value that is
> measurably correlated to a secret, side channel attacks are a serious threat
> (even if there is a good deal of noise.)  Has anyone looked at this?  (I
> expect the answer to be platform-dependent.)

I doubt anyone has looked at this since you asked, lo these couple of years ago.

The way to avoid worrying, if practical, would be to use something other than pointers, that is cheap to compute and that's hard to attack. Any suggestions?

/be
(In reply to Brendan Eich [:brendan] from comment #73)
> These are heap pointers, so not correlated with ASLR'ed code addresses as
> far as dveditz and I know -- anyone know better?

They are heap pointers, so the concern is that they might reveal information about the randomization of heap addresses.  Background: Generally speaking, ASLR includes randomization of the entire address space, including not just code, but also heap.  For instance, Windows ASLR randomizes the location of the heap, as a partial mitigation against heap exploits.  Revealing the address of heap pointers reduces the value of these mitigations.

> The way to avoid worrying, if practical, would be to use something other
> than pointers, that is cheap to compute and that's hard to attack. Any
> suggestions?

One approach to address the security concerns about revealing information about pointer addresses would be: seed using some output from a CSPRNG, instead of using heap pointers.  This could be the same algorithm used for window.crypto.random(), or any other CSPRNG you like.



Looking more broadly at the entire discussion, I can see four different "levels" of security one could try to shoot for:

Level 0: Have one or more instances of the Math.random() rng (possibly one global instance, shared across all origins, threads, tabs, etc., or maybe multiple instances, again possibly shared across multiple origins/tabs/etc.).  Seed each instance with something non-cryptographic.  Use the current algorithm to generate output.  Is this how Mozilla currently works?  Does it share Math.random() rng instances among different tabs/origins?

Level 1: Use the output from a CSPRNG to *seed* each instance of Math.random(), but don't change the algorithm used to generate output once it has been seeded; feel free to have only a single instance of the Math.random() state, which is read/updated/shared by all origins.

Level 2: Have one instance of the Math.random() rng's state per origin (no instance is ever shared across multiple origins).  Seed each instance using output from a CSPRNG.  Don't change the algorithm to generate output once it has been seeded.

Level 3: Replace the random-number generation algorithm in Math.random() with a CSPRNG.  In other words, this is more than just changing how you seed it: also change the output generation algorithm.  Once it is a CSPRNG, it no longer matters from a security perspective whether there is a single global instance of the CSPRNG, or one instance per origin, or one per thread, or whatever you want.

(Do you get the distinction I'm making between changing the way the rng is seeded, vs changing the way it generates output?  For instance, you can have a non-cryptographic rng that is seeded using a seed generated by a CSPRNG.  Also, do you see the distinction I'm drawing between a rng that has a separate instance per origin, vs one that might be shared by pages loaded from multiple different origins?  Hopefully those two distinctions make sense.)

You get increasing levels of security as you go up the levels, and also potentially increasing performance overhead.

Here's my current best guess at security implications: 

- The concerns in Comment 72 (about revealing heap pointer addresses) come from seeding using heap addresses.  Those concerns go away in any of Levels 1-3, since they all seed with output from a CSPRNG.

- Bug #464071 relates to the fact that a Math.random() instance is global (or shared across domains), and the fact that its output generation algorithm is not cryptographically secure.  It is fixed by Levels 2-3, but not by Levels 0-1.  Same goes for bug #577512.

- Another concern is that a page from attacker.com might be able to spy on the activities occuring on a page from victim.com (in particular, spying on how it uses Math.random()), if Math.random() on both pages accesses the same rng instance.  This is caused by the same factors as the previous item.  Thus, it is a concern at Levels 0-1 but the risk goes away with Levels 2-3.

- Another concern is that some existing users of Math.random() may be relying upon it to be unguessable (e.g., improperly using it to generate random passwords or crypto keys).  This would be fixed by Level 3, or possibly in some cases Level 2, but not by Levels 0-1.  On the other hand, this concern might be out of scope.

I think.  I hope I got that right.

I'm in the dark about performance implications.  I would expect that merely changing the way that the Math.random() rng is seeded would raise less concern about performance impact than changing the way that the Math.random() rng generates output, but I'll have to leave the implications to others to analyze.
I'm no expert in cryptography, but if partially exposing the memory layout is the concern, then would there be any use in replacing time ^ ptr1 ^ ptr2 with H(time ^ ptr1 ^ ptr2), where H() is an appropriate hash function?
(In reply to David Webb from comment #75)
> I'm no expert in cryptography, but if partially exposing the memory layout
> is the concern, then would there be any use in replacing time ^ ptr1 ^ ptr2
> with H(time ^ ptr1 ^ ptr2), where H() is an appropriate hash function?

I dunno.  Maybe.  It might need some careful analysis.  I don't think it's obvious that it would make the concern go away -- it doesn't seem like a no-brainer to me.

Here's why: if x has enough entropy, then H(x) will conceal x (you can't recover x, given H(x)).  However if x doesn't have enough entropy, then H(x) does not conceal x effectively (given H(x), you can try all possibilities for x and learn which is the correct one, as long as there aren't too many possibilities for x).  In the latter case hashing doesn't really help.  So the question becomes: is there enough entropy in time ^ ptr1 ^ ptr2 to make hashing useful?  I don't know the answer.  (For point of reference, I've read statements that ASLR on 32-bit Windows Vista adds 5 bits of entropy to heap addresses, but I think it adds a lot more entropy on 64-bit systems.  The time has only a modest amount of entropy.)

That said, I don't even know if the original concern is a real and significant threat or not.  Sorry to pour on so much speculation, without hard numbers or experiments to back it up.
(In reply to daw-redhatbugzilla from comment #76)
> [I]f x has enough entropy, then H(x) will conceal x (you can't
> recover x, given H(x)).  However if x doesn't have enough entropy, then H(x)
> does not conceal x effectively (given H(x), you can try all possibilities
> for x and learn which is the correct one, as long as there aren't too many
> possibilities for x).  In the latter case hashing doesn't really help. 

It seems to me like this issue could benefit from throwing some more salt into the xor soup. Are there other pieces of information which aren't very sensitive, but which vary with low predictability and with little-to-no correlation to the time and the two pointers? Someone correct me if I'm wrong, but from what I understand, A ^ B is at least as random as whichever of A or B is the most random. Are there a couple other sufficiently entropic pieces of state such that H(state1 ^ state2), if they're the same length, or H(state1) ^ H(state2), if they're not, do not increase the user's risk if a web application can deduce that some bits of the soup were more probably a 1 or 0?

What about using "just enough" bits from a CSPRNG to fill in the missing entropy, so you can spare as much high-quality randomness as possible for security-critical applications?
FWIW, Ivy Bridge has a builtin RNG (https://en.wikipedia.org/wiki/RdRand) that could be either used directly or to seed a PRNG.
David/Graydon - does the resolution of bug 440046 give us any happy feelings, here?
Well, it's long since time for me to abandon ownership of this bug since I'm in no position to fix it; but in terms of "what I think we should do", I'm still mostly in agreement with what I said back in comment #61: just feed the CSPRNG -- which should be asking the OS CSPRNG and/or the CPU hardware RNG -- into anything asking for randomness. Any randomness. No making up guesses about entropy-content of various sources, and no reason to imagine web content depends on our LFSR given the field-variability of Math.random across other browsers already. If performance is honestly a problem there's something wrong with NSS: a CSPRNG shouldn't be slow. An Arc4 or AES or ISAAC CSPRNG should not be a bottleneck.

It's _nicer_ of course if people can now call getRandomValues if they know to look for it. But other content that expects randomness is presently ... not really getting it.
(In reply to Johnathan Nightingale [:johnath] from comment #79)
> David/Graydon - does the resolution of bug 440046 give us any happy
> feelings, here?

Upon reading some more of this bug, it seems to me that this bug has more to do with JavaScript than the DOM and the fact that we have crypto.getRandomValues is a step forward, but does not resolve this bug.
(In reply to David Dahl :ddahl from comment #81)
> (In reply to Johnathan Nightingale [:johnath] from comment #79)
> > David/Graydon - does the resolution of bug 440046 give us any happy
> > feelings, here?
> 
> Upon reading some more of this bug, it seems to me that this bug has more to
> do with JavaScript than the DOM and the fact that we have
> crypto.getRandomValues is a step forward, but does not resolve this bug.

Totally agree there. I was very pleased to see getRandomValues land. Good times! Thanks for the persistent effort.
http://ifsec.blogspot.fi/2012/05/cross-domain-mathrandom-prediction.html - here's a practical attack on Firefox Math.random() . Perhaps it's time to try to do something about this bug.

Math.random() probably needs not be cryptographically secure but still it needs to be unpredictable and not leak information about its state too easily. I would suggest reseeding the PRNG on each page load or other similar events, and use something like this:

state = Hash(old state + page url + other easily collected variables + time^pointer1^pointer2)

or even just

state = Hash(old state+current algorithm)

Even the simple version increases the PRNG unpredictability a lot after a few page loads.

Not having looked at the code, I would guess this kind of fix to be fairly easily implemented.
We might have fixed that in bug 820180.  Anyway, it's separate from this bug.
(In reply to Jesse Ruderman from comment #84)
> We might have fixed that in bug 820180. Anyway, it's separate from this bug.

In the bug 820180 the prng lost the "context" seed and instead gained a small(?) integer per compartment. I don't think it fixes anything other than giving guarantee of getting different random numbers on each compartment (but to be honest, I don't know what compartment here means. A tab/window perhaps?) Anyway I don't know how many compartments there usually are, or in what range the nonce number typically is, but still the numbers looks very predictable to me, even more than before - there are no "pointers" left in seeding, just time and the small(?) number.

Better seeding would make the current simple algorithm better (less predictable), and anyway better seeding is needed whatever algorithm is used, otherwise it will be just as predictable as before.

Having looked at the code, making the current algorithm produce less predictable numbers seem quite easy: treat the current nonce variable as a global "seed" and mix/hash it with current time on each initialization instead of just incrementing it.
A compartment is a DOM Window, basically.
I don't see any requirement for non-predictability of Math.random. Math.random isn't a security feature. If people attempt to build security features on top of Math.random then they are going to have a bad time, in general. That's why we did window.crypto.getRandomValues.

If an application doesn't care about the predictability of the generated values, and it doesn't need a secure PRNG, then it shouldn't have to pay the cost of using a secure PRNG. These are the types of applications that Math.random is for. For example, if I'm doing some kind of randomized simulation then I care a lot about the speed of the simulation and not at all about whether a malicious actor can predict the outcome of the simulation. Perhaps these applications would benefit from having Math.random be "more random" but AFAICT nobody has been concerned about that up to this point.

(In reply to Viljo Viitanen from comment #83)
> state = Hash(old state + page url + other easily collected variables +
> time^pointer1^pointer2)
> 
> or even just
> 
> state = Hash(old state+current algorithm)

I think the concern with Math.random isn't that it is predictable, but rather that it has potential to leak information about your browsing history, and it has the potential to leak information that defeats ASLR.

IMO, that means that we should absolutely avoid (a) sharing state between origins, (b) mixing URIs into the seed, and (c) mixing pointers into the seed.

It seems acceptable to me, then, to simply seed the Math.random PRNG with the output of the window.crypto.getRandomValues PRNG (only), and then carry on with the existing algorithm unless there is some evidence that it isn't good enough for non-security purposes. Perhaps improving the seeding should be a separate bug from this one.
(In reply to Brian Smith (:bsmith) from comment #87)
> It seems acceptable to me, then, to simply seed the Math.random PRNG with
> the output of the window.crypto.getRandomValues PRNG (only), and then carry
> on with the existing algorithm unless there is some evidence that it isn't
> good enough for non-security purposes. Perhaps improving the seeding should
> be a separate bug from this one.

I would very much welcome this.

FWIW, V8 seems to be doing something like that. https://code.google.com/p/v8/codesearch#v8/trunk/src/v8.cc&q=random&sq=package:v8&type=cs&l=130


Anyway, here's an idea for improving the quality of generated random values in a simple way while keeping the current algorithm: when a lot of random numbers are generated, reseed with the secure PRNG with such interval that performance is not an issue, but still reasonably often.
(In reply to Brian Smith (:bsmith) from comment #87)
> If people attempt to build security features on top of Math.random then
> they are going to have a bad time, in general.

Well, yeah, but *people do this anyway*.  I have to agree with Graydon on this one: Math.random should be a CSPRNG.  (I *also* agree with you that it needs to be reseeded per-origin.)
I opened bug 868860 as bsmith  suggested in comment 87 to discuss improving Math.random()'s seed, separate from the discussion of Math.random()'s algorithm.

My proposed patch implements something similar to daw's "Level 2" suggestion from comment 74: seed Math.random() from something secure (/dev/urandom on XP_UNIX (including including OSX) and rand_s() on Windows) without changing the current PRNG algorithm.
Depends on: 868860
Hardware: x86 → All
As a user/consumer of Math.random(), I would find just switching to the originally suggested MT-19937 algorithm to be adequate. I am using it in the Fisher–Yates/Durstenfeld/Knuth Shuffle Algorithm (http://en.wikipedia.org/wiki/Fisher-Yates_Shuffle) to generate a shuffled sequence from an original 0 to N-1 ordered sequence, which depends on a "reasonable" PRNG to generate all possible shuffles, although not necessarily a CSPRNG.

The only *extra* addition that would be nice is the ability to pass in an optional seed value.

I DON'T want or need to use window.crypto.getRandomValues() since this is a non-security application and I don't want to deplete the window.crypto.getRandomValues() entropy pool.

Currently is there any progress on changing the existing (LFSR?) Math.random() algorithm to the suggested MT-19937 algorithm?
(In reply to eurythrace from comment #91)
I forgot to add that using one of the current JS implementations (e.g., https://gist.github.com/banksean/300494) of the MT algorithm over using the native Math.random() function yields a factor of 10 performance penalty, which is too significant for me.
I think the random functions in jsmath.c can be improved a lot without any performance cost. It truncates its internal state to 48 bits instead of 64. Then in random_nextDouble() it calls random_next() twice, but both calls are truncated to 26-27 bits, and the 2nd call only affects about 0.000000015 of the result, concatenating the results rather than mixing them, presumably as a workaround for the 48 bit truncation to fill the double's 53 bits, rather than an attempt to improve the randomness.
Just a head up, when reading an article this morning mainly about Math.random() in V8, but also saying:

> I’ll note, in passing, that Mozilla’s use of the LCG from Java’s 
> util.Random package isn’t much better than MWC1616. So SpiderMonkey 
> should probably go ahead and upgrade too.

https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d
mfbt/XorShift128Mumble.h is one plausible candidate, certainly.  However, it uses 64-bit math for which we lack support in our JIT backends.  And 64-bit math is also fairly hard in JS, if we were to self-host.  Not impossible to do, but 900k bugs later, this is obviously pretty low priority, not least because Math.random() has no official guarantees and other implementations are as shoddy or worse.
Another entry in the "lack of randomness in Math.random() bites again" column:
https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d
Keywords: sec-want
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #95)
> mfbt/XorShift128Mumble.h is one plausible candidate, certainly.  However, it
> uses 64-bit math for which we lack support in our JIT backends.  And 64-bit
> math is also fairly hard in JS, if we were to self-host.  Not impossible to
> do, but 900k bugs later, this is obviously pretty low priority, not least
> because Math.random() has no official guarantees and other implementations
> are as shoddy or worse.

It seems to me our current implementation also use 64-bit math, no?
(In reply to Xidorn Quan [:xidorn] (UTC+10) from comment #97)
> It seems to me our current implementation also use 64-bit math, no?

Hmm.  Either I forgot that, or I was leaning on my knowledge we didn't have 64-bit math support in the JIT backends.  No idea when we picked that up.  So doing XorShift128Mumble is more feasible than I thought.  (Although if someone does it, they'll have to implement 64-bit add/xor in all the backends to do it, looks like.)
Note that V8 upgraded their random number generator to XorShift128+; we already have that one in MFBT so that does seem like a reasonable choice.

I'll try something today. I'm also interested in running BigCrush on our current implementation and verifying XorShift128+ indeed passes it.
Flags: needinfo?(jdemooij)
XorShift128+ turns out to be really nice to inline in the JIT actually, much simpler (especially on x86) and faster than our current RNG.

Generating 100000000 random numbers, x86:

before: 708 ms
after:  439 ms

And x64:

before: 413 ms
after:  258 ms

Next up is running the RNG tests mentioned in the blog post.
For posterity, here's the patch I used to run TestU01's BigCrush suite against our RNG. TestU01 is a library and the best way to run it is to link it to a binary so I added it to the JS shell. (It'd be neat to compile BigCrush to asm.js so we can test the browser's Math.random...)

AFAIK, BigCrush is the most complete RNG test available. It takes ~3 hours to run on my MBP.

Here are the results for our current RNG on OS X 64-bit:

========= Summary results of BigCrush =========

 Version:          TestU01 1.2.3
 Generator:        test
 Number of statistics:  160
 Total CPU time:   02:56:04.34
 The following tests gave p-values outside [0.001, 0.9990]:
 (eps  means a value < 1.0e-300):
 (eps1 means a value < 1.0e-15):

       Test                          p-value
 ----------------------------------------------
 13  BirthdaySpacings, t = 2          eps  
 14  BirthdaySpacings, t = 3          eps  
 15  BirthdaySpacings, t = 4          eps  
 16  BirthdaySpacings, t = 7          eps  
 17  BirthdaySpacings, t = 7          eps  
 18  BirthdaySpacings, t = 8          eps  
 19  BirthdaySpacings, t = 8          eps  
 20  BirthdaySpacings, t = 16         eps  
 21  BirthdaySpacings, t = 16         eps  
 22  ClosePairs NP, t = 3            8.3e-4
 22  ClosePairs mNP, t = 3          1.9e-49
 22  ClosePairs mNP1, t = 3         2.4e-61
 22  ClosePairs mNP2S, t = 3          eps  
 23  ClosePairs mNP, t = 5           4.5e-5
 23  ClosePairs mNP1, t = 5          1.3e-5
 23  ClosePairs mNP2S, t = 5          eps  
 24  ClosePairs mNP1, t = 9          8.6e-4
 24  ClosePairs mNP2S, t = 9       3.7e-169
 25  ClosePairs mNP, t = 16         1.4e-35
 25  ClosePairs mNP1, t = 16        1.6e-45
 25  ClosePairs mNP2S, t = 16         eps  
 32  CouponCollector, r = 20          eps  
 60  WeightDistrib, r = 20            eps  
 ----------------------------------------------
 All other tests were passed

And with the patch to use XorShift128+, all tests pass:

========= Summary results of BigCrush =========

 Version:          TestU01 1.2.3
 Generator:        MRG32k3a
 Number of statistics:  160
 Total CPU time:   03:14:29.78

 All tests were passed

XorShift128+ is known to pass BigCrush but this confirms our implementation does too.
Assignee: graydon → jdemooij
Status: NEW → ASSIGNED
Depends on: 1228182
Flags: needinfo?(jdemooij)
Attachment #8692947 - Flags: review?(jwalden+bmo)
Note that I didn't implement add64 on mips32 as MIPS doesn't build atm and it's not trivial to implement. A build failure is better than a buggy implementation I didn't test.
Attachment #8692950 - Flags: review?(arai.unmht)
Attachment #8692950 - Attachment is obsolete: true
Attachment #8692950 - Flags: review?(arai.unmht)
Attachment #8692953 - Flags: review?(arai.unmht)
Attachment #8692954 - Flags: review?(jwalden+bmo)
Attachment #8692954 - Flags: review?(arai.unmht)
Fixes the math-random.js jit-test and setRNGState shell function.
Attachment #8692955 - Flags: review?(arai.unmht)
On Windows, ExecutableAllocator called random_next. Also its state was `static`; that seems wrong. This patch gives each ExecutableAllocator its own XorShift128PlusRNG on Windows.
Attachment #8692957 - Flags: review?(jwalden+bmo)
Attached patch Combined patchSplinter Review
Errr, you did an ASM implementation of that algorithm? Then I guess we really need to benchmark the real performance of the instructions. In the C++ implementation, I was hoping that compilers pick the best way to optimize the code and probably eliminate the floating-number division completely, which doesn't seem to be done magically here.

We probably should disasm the object files of my test program in bug 1228182 and see exactly what optimization compilers actually apply.
(In reply to Xidorn Quan [:xidorn] (UTC+10) from comment #109)
> We probably should disasm the object files of my test program in bug 1228182
> and see exactly what optimization compilers actually apply.

See comment 100, the JIT code we generate is significantly faster than the previous algorithm so performance seems fine (FWIW, note that it uses a multiplication instead of a division).
Attachment #8692953 - Flags: review?(arai.unmht) → review+
Comment on attachment 8692954 [details] [diff] [review]
Part 3 - Update JIT code

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

Doesn't this RNG reach the state that needs re-initialize, like rngState == 0 in current one?
Comment on attachment 8692955 [details] [diff] [review]
Part 4 - Fix math-random.js

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

::: js/src/builtin/TestingFunctions.cpp
@@ +2990,5 @@
>  static bool
>  SetRNGState(JSContext* cx, unsigned argc, Value* vp)
>  {
>      CallArgs args = CallArgsFromVp(argc, vp);
> +    if (!args.requireAtLeast(cx, "SetRNGState", 2))

https://dxr.mozilla.org/mozilla-central/rev/47b49b0d32360fab04b11ff9120970979c426911/js/src/builtin/TestingFunctions.cpp#3550
Function spec also need to be updated.

::: js/src/jit-test/tests/basic/math-random.js
@@ +25,2 @@
>  
> +  setRNGState(0, 1);

What do these (0, 1) and (0x0fff0101, 0x44440001) states mean?
Are these special cases like previous one that enters OOL?
(In reply to Tooru Fujisawa [:arai] from comment #111)
> Doesn't this RNG reach the state that needs re-initialize, like rngState ==
> 0 in current one?

No, as long as the initial seed is non-zero, the state will always be non-zero (this is important because if the state could be zero, the RNG would always be 'stuck' there).

(In reply to Tooru Fujisawa [:arai] from comment #112)
> What do these (0, 1) and (0x0fff0101, 0x44440001) states mean?
> Are these special cases like previous one that enters OOL?

No just some arbitrary and potentially-interesting states. I'll add a comment :)
Comment on attachment 8692954 [details] [diff] [review]
Part 3 - Update JIT code

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

(In reply to Jan de Mooij [:jandem] from comment #113)
> (In reply to Tooru Fujisawa [:arai] from comment #111)
> > Doesn't this RNG reach the state that needs re-initialize, like rngState ==
> > 0 in current one?
> 
> No, as long as the initial seed is non-zero, the state will always be
> non-zero (this is important because if the state could be zero, the RNG
> would always be 'stuck' there).

I see, in that case this looks good :)
Attachment #8692954 - Flags: review?(arai.unmht) → review+
Comment on attachment 8692955 [details] [diff] [review]
Part 4 - Fix math-random.js

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

r+ with the function spec fix and comment for those states in test.
Attachment #8692955 - Flags: review?(arai.unmht) → review+
(In reply to Jan de Mooij [:jandem] from comment #101)
> (It'd be neat to compile
> BigCrush to asm.js so we can test the browser's Math.random...)

I did this:

https://jandem.github.io/TestU01.js/test.htm
http://jandemooij.nl/blog/2015/11/30/testing-math-random-crushing-the-browser/

I also filed a WebKit bug and they moved to XorShift128+. That means all browsers except IE/Edge will use that RNG.

Test results suggest IE/Edge uses an algorithm *very* similar to the RNG we had in Firefox.
Comment on attachment 8692947 [details] [diff] [review]
Part 1 - Use XorShift128+ RNG

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

::: js/src/jsmath.cpp
@@ +817,5 @@
>  {
> +    // XorShift128PlusRNG must be initialized with a non-zero seed.
> +    do {
> +        GenerateSeed(seed.begin(), mozilla::ArrayLength(seed));
> +    } while (!seed[0] && !seed[1]);

lol, but I guess necessary.  == 0 would be nicer style-wise, IMO.
Attachment #8692947 - Flags: review?(jwalden+bmo) → review+
Comment on attachment 8692954 [details] [diff] [review]
Part 3 - Update JIT code

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

::: js/src/jit/CodeGenerator.cpp
@@ +10338,3 @@
>  #else
> +    Register64 s0Reg = Register64(ToRegister(ins->temp1()), ToRegister(ins->temp2()));
> +    Register64 s1Reg = Register64(ToRegister(ins->temp3()), ToRegister(ins->temp4()));

Seems like |Register64 foo(...)| in both #if-arms would be less repetititious.

@@ +10387,5 @@
> +    static const double ScaleInv = double(1) / (1ULL << MantissaBits);
> +
> +    masm.and64(Imm64((1ULL << MantissaBits) - 1), s1Reg);
> +
> +    masm.convertUInt64ToDouble(s1Reg, tempReg, output);

It feels to me like there should be some sort of bitwise math way to super-optimize this without requiring a multiplication.  On the other hand, my O(months)-old clang++ compiles this:

#include <inttypes.h>
#include <stdio.h>

int main(int argc, const char** argv)
{
  uint64_t u;
  sscanf(argv[1], "%" SCNu64, &u);
  double d = double(u & ((1ULL << 53) - 1));
  printf("%f\n", d / double(1ULL << 53));
}

to equivalent code at -g -O3, so maybe this really is better than doing bitscans to deal with an implied zero and denormals and consing up a biased exponent-component manually.  Or at least this is a heckuva lot easier, and easier to read.  :-)

::: js/src/jit/x86/Lowering-x86.cpp
@@ +440,5 @@
>  
>  void
>  LIRGeneratorX86::visitRandom(MRandom* ins)
>  {
>      // eax and edx are necessary for mull.

This comment should die now.

::: mfbt/XorShift128PlusRNG.h
@@ +37,5 @@
>   * This generator is not suitable as a cryptographically secure random number
>   * generator.
> + *
> + * NB: IonMonkey inlines this RNG in JIT code. Don't change the algorithm below
> + * without also updating the code in CodeGenerator::visitRandom.

mfbt is upstream of IonMonkey, so referring to it directly is somewhat frowned upon.  Let's go with this, so this comment can stay as-is in the unlikely event someone else ends up poking directly at this junk.

"""
The offsetOfState*() methods below are provided so that exceedingly-rare callers that want to observe or poke at RNG state in C++ type-system-ignoring means can do so.  Don't change the next() or nextDouble() algorithms without altering code that uses offsetOfState()!
"""

Also, this comment belongs in next(), not in class-overview comments that are not supposed to be about implementation details.

@@ +92,5 @@
>      mState[0] = aState0;
>      mState[1] = aState1;
>    }
> +
> +  static size_t offsetOfState() {

Rather than "state" generally, add one method for mState[0], one for mState[1] -- offsetOfState0(), offsetOfState1().
Attachment #8692954 - Flags: review?(jwalden+bmo) → review+
Comment on attachment 8692957 [details] [diff] [review]
Part 5 - Fix Windows ExecutableAllocator

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

I suppose this non-cryptographically-secure RNG is no worse than what existed before, in terms of predictivity, is it?  And really we're just salting our JIT addresses by 2**13 or so, and even not-super-great results are good enough to deter scattershot efforts.  So this works adequately.
Attachment #8692957 - Flags: review?(jwalden+bmo) → review+
Summary: Upgrade Math.random() to a better algorithm, such as Mersenne Twister → Upgrade Math.random() to the better XorShift128+ algorithm
(In reply to Jeff Walden [:Waldo] (remove +bmo to email) from comment #118)

> It feels to me like there should be some sort of bitwise math way to
> super-optimize this without requiring a multiplication. 

Yes, you don't need multiplications: if x is your 64-bit pseudorandom value, just build a double as follows:

0x3FF << 12 | x >> 12

This is a uniform double in [1..2). You subtract 1.0 and you get your uniform double in [0..1). E.g., this is the Java code from the DSI utilities:

public double nextDouble() {
	return Double.longBitsToDouble( nextLong() >>> 12 | 0x3FFL << 52 ) - 1.0;
}
Whiteboard: [adv-main45-]
You need to log in before you can comment on or make changes to this bug.