Last Comment Bug 322529 - Upgrade Math.random() to the better XorShift128+ algorithm
: Upgrade Math.random() to the better XorShift128+ algorithm
Status: RESOLVED FIXED
[adv-main45-]
: sec-want
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Trunk
: All All
: -- normal with 7 votes (vote)
: mozilla45
Assigned To: Jan de Mooij [:jandem]
:
Mentors:
http://www.math.sci.hiroshima-u.ac.jp...
: 502420 (view as bug list)
Depends on: 440046 868860 1228182 1231163
Blocks:
  Show dependency treegraph
 
Reported: 2006-01-05 16:53 PST by Michael Daumling
Modified: 2016-02-29 12:14 PST (History)
60 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---
fixed


Attachments
Patch to run TestU01 / BigCrush (2.12 KB, patch)
2015-11-26 23:56 PST, Jan de Mooij [:jandem]
no flags Details | Diff | Splinter Review
Part 1 - Use XorShift128+ RNG (7.35 KB, patch)
2015-11-27 05:07 PST, Jan de Mooij [:jandem]
jwalden+bmo: review+
Details | Diff | Splinter Review
Part 2 - Add xor64 and add64 to macro-assemblers (10.54 KB, patch)
2015-11-27 05:32 PST, Jan de Mooij [:jandem]
no flags Details | Diff | Splinter Review
Part 2 - Add xor64 and add64 to macro-assemblers (10.54 KB, patch)
2015-11-27 05:47 PST, Jan de Mooij [:jandem]
arai.unmht: review+
Details | Diff | Splinter Review
Part 3 - Update JIT code (14.16 KB, patch)
2015-11-27 05:50 PST, Jan de Mooij [:jandem]
arai.unmht: review+
jwalden+bmo: review+
Details | Diff | Splinter Review
Part 4 - Fix math-random.js (3.99 KB, patch)
2015-11-27 05:52 PST, Jan de Mooij [:jandem]
arai.unmht: review+
Details | Diff | Splinter Review
Part 5 - Fix Windows ExecutableAllocator (3.18 KB, patch)
2015-11-27 05:54 PST, Jan de Mooij [:jandem]
jwalden+bmo: review+
Details | Diff | Splinter Review
Combined patch (38.96 KB, patch)
2015-11-27 06:14 PST, Jan de Mooij [:jandem]
no flags Details | Diff | Splinter Review

Description Michael Daumling 2006-01-05 16:53:21 PST
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.
Comment 1 Brendan Eich [:brendan] 2006-01-05 17:02:30 PST
(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
Comment 2 Brendan Eich [:brendan] 2006-01-06 11:00:02 PST
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
Comment 3 Michael Daumling 2006-01-15 11:08:32 PST
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?

Comment 4 Brendan Eich [:brendan] 2006-01-15 13:55:05 PST
Michael: We have 64-bit integer type support on all platforms, finally.  What 64-bit portability problems were you worried about?

/be
Comment 5 Michael Daumling 2006-01-15 18:25:10 PST
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.
Comment 6 Brendan Eich [:brendan] 2006-01-15 20:14:27 PST
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
Comment 7 Michael Daumling 2006-01-15 20:50:53 PST
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.
Comment 8 Graydon Hoare :graydon 2006-01-15 21:17:05 PST
(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.
Comment 9 Michael Daumling 2006-01-16 07:58:32 PST
Well, we actually want a double between 0 and 1, whose mantissa is 53 bits. Would 32 bits still do then?
Comment 10 Brendan Eich [:brendan] 2006-02-13 21:57:07 PST
There's a wish for MT-19937 in NSPR, for all code (C or C++) to share.  Wan-Teh, what do you think?

/be
Comment 11 Wan-Teh Chang 2006-02-17 21:21:12 PST
Brendan, what is MT-19937?
Comment 12 Michael Daumling 2006-02-17 22:22:21 PST
Please read here: 

http://www.cliki.net/MT19937
Comment 13 Alfred Kayser 2006-04-24 04:12:37 PDT
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?
Comment 14 Wan-Teh Chang 2006-04-24 09:36:50 PDT
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.
Comment 15 Wan-Teh Chang 2006-08-19 13:58:05 PDT
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?
Comment 16 Brendan Eich [:brendan] 2007-02-05 17:22:29 PST
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
Comment 17 Brendan Eich [:brendan] 2007-02-05 18:26:19 PST
Ok, see bug 369390 comment 4.

/be
Comment 18 Brian Crowder 2007-02-06 11:19:32 PST
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?
Comment 19 Boris Zbarsky [:bz] 2007-02-06 11:41:39 PST
> 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.
Comment 20 Brian Crowder 2007-02-06 12:00:25 PST
Where/what are those APIs?  Are they documented?  Available to JavaScript code?  Do they work cross-browser?
Comment 21 Boris Zbarsky [:bz] 2007-02-06 12:02:29 PST
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. ;)
Comment 22 Brian Crowder 2007-02-06 12:23:59 PST
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.
Comment 23 Brian Crowder 2007-02-06 12:28:31 PST
(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?
Comment 24 Brendan Eich [:brendan] 2007-02-06 13:26:14 PST
(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
Comment 25 Jo Hermans 2007-02-06 14:50:44 PST
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.
Comment 26 Brian Crowder 2007-02-06 15:00:16 PST
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.
Comment 27 Nelson Bolyard (seldom reads bugmail) 2007-02-10 07:02:02 PST
> 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, 
Comment 28 Wan-Teh Chang 2007-02-10 07:53:46 PST
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
Comment 29 Brendan Eich [:brendan] 2007-02-10 12:32:55 PST
(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
Comment 30 Wan-Teh Chang 2007-02-10 16:35:05 PST
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.
Comment 31 Brendan Eich [:brendan] 2007-02-10 17:16:02 PST
(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
Comment 32 :Gavin Sharp [email: gavin@gavinsharp.com] 2007-02-10 17:56:45 PST
(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.
Comment 33 Wan-Teh Chang 2007-02-11 09:08:43 PST
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.
Comment 34 Boris Zbarsky [:bz] 2007-02-11 09:22:33 PST
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.
Comment 35 Brendan Eich [:brendan] 2007-02-11 12:38:54 PST
bz's right, sorry for using this bug as a discussion forum. I'll continue this thread in bug 338601.

/be
Comment 36 Eric H. Jung 2008-06-18 10:34:03 PDT
(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.
Comment 37 Brian Crowder 2008-06-18 10:38:53 PDT
If we're going to provide a DOM solution to this, and not a JS-integrated solution, then perhaps we should WONTFIX this bug?
Comment 38 Brandon Sterne (:bsterne) 2008-11-10 11:29:02 PST
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.
Comment 39 Brian Crowder 2009-05-04 10:29:23 PDT
Mass unowning JS bugs...  I'm not likely to be able to move these forward.
Comment 40 Kevin Brosnan 2009-07-04 19:55:08 PDT
*** Bug 502420 has been marked as a duplicate of this bug. ***
Comment 41 Michael Gilbert 2009-07-04 20:13:38 PDT
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.
Comment 42 Nelson Bolyard (seldom reads bugmail) 2009-07-04 20:55:29 PDT
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.
Comment 43 Boris Zbarsky [:bz] 2009-07-05 12:39:09 PDT
My question got answered in comment 36, I think.  This bug is stalled on someone actually doing the work, I think.
Comment 44 Jesse Ruderman 2009-07-05 13:03:19 PDT
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 (???)
Comment 45 Michael Gilbert 2009-07-05 13:13:52 PDT
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.
Comment 46 Eric H. Jung 2009-07-05 15:13:21 PDT
(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)
Comment 47 Michael Gilbert 2009-07-05 16:28:47 PDT
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.
Comment 48 Brendan Eich [:brendan] 2009-07-05 19:06:01 PDT
Michael Gilbert: the only "precautionary principle" I've heard of is politicized nonsense. What definition are you using?

/be
Comment 49 Michael Gilbert 2009-07-05 20:31:24 PDT
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.
Comment 50 Brendan Eich [:brendan] 2009-07-05 22:25:20 PDT
   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
Comment 51 Graydon Hoare :graydon 2009-07-06 10:53:02 PDT
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.
Comment 52 Brendan Eich [:brendan] 2009-07-06 11:39:17 PDT
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
Comment 53 Brendan Eich [:brendan] 2009-07-06 11:43:06 PDT
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
Comment 54 Honza Bambas (:mayhemer) 2009-07-06 14:11:04 PDT
My vote:
Let Math.random() be based on Mersenne Twister, let window.crypto.random(num) use security/manager/ssl/src/nsRandomGenerator.cpp (nsIRandomGenerator.idl).
Comment 55 Honza Bambas (:mayhemer) 2009-07-13 12:45:27 PDT
I can do the work, but I need to know what's the conclusion.
Comment 56 Michael Gilbert 2009-07-13 13:17:52 PDT
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
Comment 57 Brian Crowder 2009-07-13 13:28:31 PDT
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.
Comment 58 Brian Crowder 2009-07-13 13:30:29 PDT
(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?
Comment 59 Brian Crowder 2009-07-13 13:31:42 PDT
My vote is to implement comment #54.
Comment 60 Brian Crowder 2009-07-13 13:38:19 PDT
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?
Comment 61 Graydon Hoare :graydon 2009-07-13 15:44:10 PDT
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.
Comment 62 Brendan Eich [:brendan] 2009-07-13 15:50:11 PDT
Graydon: great, we're on the same page about trying this experiment -- does this mean you are gonna take this bug? :-P

/be
Comment 63 Graydon Hoare :graydon 2009-07-13 15:55:39 PDT
Ok, but only after a few parts of the NJ worklist get knocked down :)
Comment 64 Michael Gilbert 2009-07-13 16:56:25 PDT
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.
Comment 65 Brendan Eich [:brendan] 2009-07-13 16:59:11 PDT
(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
Comment 66 Graydon Hoare :graydon 2009-07-13 17:24:40 PDT
(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 :)
Comment 67 Jesse Ruderman 2009-07-13 18:12:22 PDT
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?
Comment 68 Nelson Bolyard (seldom reads bugmail) 2009-07-13 18:46:09 PDT
(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
Comment 69 Jesse Ruderman 2009-07-13 18:53:54 PDT
Wow, nice.
Comment 70 Brendan Eich [:brendan] 2009-09-15 12:59:34 PDT
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
Comment 71 daw-redhatbugzilla 2010-09-28 16:05:43 PDT
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.
Comment 72 daw-redhatbugzilla 2010-09-28 16:20:57 PDT
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.)
Comment 73 Brendan Eich [:brendan] 2012-06-11 15:54:56 PDT
(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
Comment 74 daw-redhatbugzilla 2012-06-11 17:23:49 PDT
(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.
Comment 75 Dave Webber 2012-06-11 22:21:43 PDT
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?
Comment 76 daw-redhatbugzilla 2012-06-12 01:03:33 PDT
(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.
Comment 77 Dave Webber 2012-06-13 16:26:51 PDT
(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?
Comment 78 Carlo Alberto Ferraris 2012-06-14 12:12:45 PDT
FWIW, Ivy Bridge has a builtin RNG (https://en.wikipedia.org/wiki/RdRand) that could be either used directly or to seed a PRNG.
Comment 79 Johnathan Nightingale [:johnath] 2013-02-19 05:55:08 PST
David/Graydon - does the resolution of bug 440046 give us any happy feelings, here?
Comment 80 Graydon Hoare :graydon 2013-02-19 14:06:41 PST
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.
Comment 81 David Dahl :ddahl 2013-02-19 15:42:44 PST
(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.
Comment 82 Graydon Hoare :graydon 2013-02-19 16:26:49 PST
(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.
Comment 83 Viljo Viitanen 2013-04-09 11:59:07 PDT
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.
Comment 84 Jesse Ruderman 2013-04-09 12:10:50 PDT
We might have fixed that in bug 820180.  Anyway, it's separate from this bug.
Comment 85 Viljo Viitanen 2013-04-09 13:59:12 PDT
(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.
Comment 86 Boris Zbarsky [:bz] 2013-04-09 14:06:53 PDT
A compartment is a DOM Window, basically.
Comment 87 Brian Smith (:briansmith, :bsmith, use NEEDINFO?) 2013-04-09 14:29:59 PDT
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.
Comment 88 Viljo Viitanen 2013-04-09 16:30:25 PDT
(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.
Comment 89 Zack Weinberg (:zwol) 2013-04-11 10:02:37 PDT
(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.)
Comment 90 Chris Peterson [:cpeterson] 2013-05-05 13:57:38 PDT
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.
Comment 91 eurythrace 2013-12-04 07:37:35 PST
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?
Comment 92 eurythrace 2013-12-04 07:50:02 PST
(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.
Comment 93 David Finch 2013-12-04 12:15:11 PST
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.
Comment 94 Karl Dubost :karlcow 2015-11-19 17:22:47 PST
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
Comment 95 Jeff Walden [:Waldo] (remove +bmo to email) 2015-11-19 19:15:41 PST
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.
Comment 96 Daniel Veditz [:dveditz] 2015-11-19 20:04:09 PST
Another entry in the "lack of randomness in Math.random() bites again" column:
https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d
Comment 97 Xidorn Quan [:xidorn] (UTC+10) 2015-11-25 17:54:18 PST
(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?
Comment 98 Jeff Walden [:Waldo] (remove +bmo to email) 2015-11-25 18:50:58 PST
(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.)
Comment 99 Jan de Mooij [:jandem] 2015-11-26 01:08:01 PST
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.
Comment 100 Jan de Mooij [:jandem] 2015-11-26 07:30:34 PST
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.
Comment 101 Jan de Mooij [:jandem] 2015-11-26 23:56:46 PST
Created attachment 8692824 [details] [diff] [review]
Patch to run TestU01 / BigCrush

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.
Comment 102 Jan de Mooij [:jandem] 2015-11-27 05:07:18 PST
Created attachment 8692947 [details] [diff] [review]
Part 1 - Use XorShift128+ RNG
Comment 103 Jan de Mooij [:jandem] 2015-11-27 05:32:15 PST
Created attachment 8692950 [details] [diff] [review]
Part 2 - Add xor64 and add64 to macro-assemblers

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.
Comment 104 Jan de Mooij [:jandem] 2015-11-27 05:47:43 PST
Created attachment 8692953 [details] [diff] [review]
Part 2 - Add xor64 and add64 to macro-assemblers
Comment 105 Jan de Mooij [:jandem] 2015-11-27 05:50:16 PST
Created attachment 8692954 [details] [diff] [review]
Part 3 - Update JIT code
Comment 106 Jan de Mooij [:jandem] 2015-11-27 05:52:04 PST
Created attachment 8692955 [details] [diff] [review]
Part 4 - Fix math-random.js

Fixes the math-random.js jit-test and setRNGState shell function.
Comment 107 Jan de Mooij [:jandem] 2015-11-27 05:54:42 PST
Created attachment 8692957 [details] [diff] [review]
Part 5 - Fix Windows ExecutableAllocator

On Windows, ExecutableAllocator called random_next. Also its state was `static`; that seems wrong. This patch gives each ExecutableAllocator its own XorShift128PlusRNG on Windows.
Comment 108 Jan de Mooij [:jandem] 2015-11-27 06:14:23 PST
Created attachment 8692962 [details] [diff] [review]
Combined patch
Comment 109 Xidorn Quan [:xidorn] (UTC+10) 2015-11-27 06:24:01 PST
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.
Comment 110 Jan de Mooij [:jandem] 2015-11-27 07:08:17 PST
(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).
Comment 111 Tooru Fujisawa [:arai] 2015-11-27 12:05:21 PST
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 112 Tooru Fujisawa [:arai] 2015-11-27 12:08:34 PST
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?
Comment 113 Jan de Mooij [:jandem] 2015-11-28 06:03:03 PST
(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 114 Tooru Fujisawa [:arai] 2015-11-28 18:10:35 PST
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 :)
Comment 115 Tooru Fujisawa [:arai] 2015-11-28 18:15:39 PST
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.
Comment 116 Jan de Mooij [:jandem] 2015-12-01 00:31:39 PST
(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 117 Jeff Walden [:Waldo] (remove +bmo to email) 2015-12-01 12:09:51 PST
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.
Comment 118 Jeff Walden [:Waldo] (remove +bmo to email) 2015-12-01 15:33:13 PST
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().
Comment 119 Jeff Walden [:Waldo] (remove +bmo to email) 2015-12-01 15:36:29 PST
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.
Comment 122 Sebastiano Vigna 2015-12-22 11:05:45 PST
(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;
}

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