Re: Math.random

Dr J R Stockton :

I cannot tell whether you have recently looked at my
<URL:http://www.merlyn.demon.co.uk/js-randm.htm#RR> ;

I have. We obviously have different coding styles as well as different
views on PRNGs. E.g, I only use identifiers starting with an upper-case
letter for constructor functions, as a reminder that they should be
called with "new".

I've not been able to remember as much as I would wish to about
methods other than Lehmer.

Lehmer's algorithm with a well-chosen multiplier was the method of
choice thirty years ago. Today, it is mainly used as a one-liner to
seed other methods with less statistical bias and whose output cannot
not be as easily predicted from a few known samples.

In a JavaScript context, there must be five classes of algorithms
for implementing Math.random :

1 The low-grade muck in actual browsers;

Actually, IMHO, quite adequate for its intended uses: somewhat
unpredictable visual effects, games, recreational simulations, etc.

It cannot be used, e.g., to generate UUIDs, or for serious Monte-Carlo
tests (for which ECMASCript would hardly be the language of choice
anyway).

But neither can your function RRN1(). It is actually worse than most
Math.random implementations - 32 bits vs. 48.

2 Lehmer with at least 53 bits and conversion to IEEE Double done
properly. That would give all multiples of 2^-53 in the range with
equal probability and gave a cycle length of at least 2^53;

Each value would occur exactly the same number of times in a cycle -
but so would a simple counter. Apart from that, I fail to see what
probability would be equal. For instance, the lowest-order bit would
alternate quite regularly between 0 and 1.

3 Something in between 2 & 4;

4 Cryptographically sound, commercial grade;

5 Cryptographically sound, national security grade.

I fail to see the distinction. Any vendor that sells a "commercial
grade" CSPRNG which are not "national security grade" is a swindler,
since there are plenty of public domain CSPRNGs that are as secure
as anyone, even the NSA or the GCHQ, may use or fear.

Of those, 1 should be eradicated, and 2 seems good enough for
Math.random (however, the ISO/IEC standard should say something
about expected quality, e.g. Cryptographic quality is not expected;
but <as above>).

I disagree on both points, as above.

of the others, 5 & 4 are beyond me;

There are quite decent ECMASCript implementations of excellent hash
and encryption algorithms that can be used to make even "national
security grade" CSPRNGs by the standard methods using cryptographic
primitives. E.g.: http://www.movable-type.co.uk/scripts/sha1.html
and http://www.movable-type.co.uk/scripts/aes.html. 256 bit AES in
counter mode should really be as secure as anyone would wish, or fear.
(It is approved by the NSA even for TOP SECRET classified documents.)
The main problem is that it requires quite elaborate code.

and 3 seems horribly like falling between two stools (hoping you
know the expression).

It seems to me that your placement of the stools is rather arbitrary.
I would definitely set 2 much higher, since there are many PRNGs available
which much better statistical behaviour than Lehmer's algorithm, and
more entropy.

On the other hand, even 256 bit AES does not, per se, address the
problem of seeding the generator in a suitably impredictable way.

[Seeds]

They can be set, as in my cited page, by passing in an Object
containing those numbers; then, by having several Objects, one can
have several random streams. There can be an Object checker, too.

Something like this?

function Lehmer(seed) {
var x = seed;

function lehmer27() {
x = x * 1664525 + 12345 >>> 0;
// The multiplier 1664525 is #25 in Knuth, TAOCP, 3.3.4, Table 1

return x >>> 5;
// Discard the 5 not very random lowest-order bits, yielding 27 bits:
// an integer in [0..134217727]
}

this.random = function() {
return (lehmer27() / 134217728 + lehmer27()) / 134217728;
}

this.state = function() {
return x;
}
}

A possible usage would be

myPRNG = new Lehmer(new Date());
var firstState = myPRNG.state();
var firstResult = myPRNG.random();

myPRNG = new Lehmer(new Date());
var secondResult = myPRNG.random(); // secondResult != firstResult

myPRNG = new Lehmer(firstState);
var thirdResult = myPRNG.random(); // thirdResult == firstResult

My suggestion is to replace Lehmer, e.g., by Marsaglia's KISS32. It
is not much more complicated and passes much more stringent
statistical tests. It also is much less easily predictable from
observed output. Finally, its internal state has slightly more valid
values than there are valid RFC 4122 UUIDs, which makes it at least
as resistant to accidental collisions. Provided, that is, that one
finds a way to seed it with truly random values...

If you've not read Amit Klein's paper (/via/
<http://www.trusteer.com/temporary-user-tracking-in-major-browsers>),
then I think you should.

Quite interesting, thank you. I would not dream of using Math.random to
generate boundary strings for POST requests - I use my own ECMAScript
UUID generator, to which this discussion is related - but apparently
some fools do. Perhaps you are right about "eradicating" the "low-grade
muck", if people insist on using it for things it was not intended for.

Essentially : if the results of Math.random depend on *information*
in the computer, then a Web page using Math.random can be a security
leak for that information. ISTM that the pool must be much larger
than at first seems necessary, if the tasty ducks and tadpoles in
it are not to be in some danger of being caught.

Quite. One single call to the timer in order to seed the generator will
never suffice to ensure secrecy, the number of possible milliseconds can
easily be inspected by brute force, and even all the 2^32 possible states of
a 32-bit Lehmer generator would not pose a major problem.

On the other hand, with more than 125 bits of internal state seeded by
something much less predictable than startup time, it is IMHO possible
to achieve a quite negligible probability that two applications ever
generate the same sequence of "random" numbers.

[Entropy pools]

The problem is how to access them in ECMAScript.

That should be impossible, rather than a problem.

As long as it does not violate the Same Origin Policy, I cannot see why.
Even in a browser (and ECMSACript is not restricted to browsers), the
page may originate on http:/localhost/ or file:/ for local use.

But it is not a practical solution for the World Wide Web. The challenge
there is to maintain a large enough entropy pool with only the information
available to the browser. I think it is possible - but not by looking
up RAND corporation's One Million Random Digits, or, indeed, on relying
on voluntary user input, which tends not to be random at all.

--
Johannes
.

Relevant Pages

  • Re: Random Seeding
    ... provided by it's inventors allows for longer seeds. ... used to perturb the deterministic generator now and then. ... D.H. Lehmer used something very like this ... Since this multiplier ...
    (comp.lang.c)
  • Re: Random number generation IP Sharp APL?
    ... The built in random number generator in every APL implementation that I have ... In general, in a linear congruential sequence, the next member of the sequence ... Usually this is done by choosing the modulus first, ... You achieve this by picking four seeds that are far ...
    (comp.lang.apl)
  • Re: Math.random
    ... methods other than Lehmer. ... An IEEE Double with a regular alternating pattern in its LSB, ... a smaller one can perhaps be an odd multiple of 2^-54. ...
    (comp.lang.javascript)
  • Re: random numbers in fortran
    ... I make sure that I have a generator capabable of producing any of the ... I understand also that with a short cycle, ... Generally in practice then, could I not compensate for a short cycle by ... The sample driver here prompts for N and 3 seeds. ...
    (comp.lang.fortran)
  • Re: How to generate random numbers in C
    ... roulette, etc.) for real money using pseudo-random numbers, you're ... There are PRNGs with a period so large it would not repeat if every ... cripple the Mersenne Twister ... If there's only 32k or 64k possible seeds, ...
    (comp.lang.c)