Math.random
Dr J R Stockton
insecurities is in a 325kB PDF by Amit Klein *via* (!== at)
<http://www.trusteer.com/temporary-user-tracking-in-major-browsers>.
The flaws in the values of Math.random can in principle be overcome by
writing one's own; but the security flaws remain as long as an attacker
can use, in pages that he writes and you read, the present default
Math.random.
It's a good idea to read the newsgroup c.l.j and its FAQ. See below.
--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk IE7 FF3 Op9 Sf3
news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.
Dr J R Stockton
rlyn.invalid>, Tue, 9 Jun 2009 18:15:46, Dr J R Stockton
<repl...@merlyn.demon.co.uk> posted:
>Considerable information about Math.random internals and derived
>insecurities is in a 325kB PDF by Amit Klein *via* (!== at)
><http://www.trusteer.com/temporary-user-tracking-in-major-browsers>.
>
>The flaws in the values of Math.random can in principle be overcome by
>writing one's own;
FYI, I expect soon to have achieved this; for integers, the code should
handle numbers up to the megadigit (hex) range, with acceptable speed
for reasonable sizes. There is, of course, difficulty in generating a
correspondingly-good seed. But, as the seed is exposed, randoms can be
generated reproducibly. Does anyone have the relevant volume of Knuth
handy?
--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.merlyn.demon.co.uk/clpb-faq.txt> RAH Prins : c.l.p.b mFAQ;
<URL:ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ.
Evertjan.
> In comp.lang.javascript message <Cy0nuvZC...@invalid.uk.co.demon.me
> rlyn.invalid>, Tue, 9 Jun 2009 18:15:46, Dr J R Stockton
> <repl...@merlyn.demon.co.uk> posted:
>>Considerable information about Math.random internals and derived
>>insecurities is in a 325kB PDF by Amit Klein *via* (!== at)
>><http://www.trusteer.com/temporary-user-tracking-in-major-browsers>.
>>
>>The flaws in the values of Math.random can in principle be overcome by
>>writing one's own;
>
> FYI, I expect soon to have achieved this; for integers, the code should
> handle numbers up to the megadigit (hex) range, with acceptable speed
> for reasonable sizes. There is, of course, difficulty in generating a
> correspondingly-good seed. But, as the seed is exposed, randoms can be
> generated reproducibly. Does anyone have the relevant volume of Knuth
> handy?
Why megadigit?
99.962468 % of the pseudo-random sequences used in clientside Javascript
are about non negative integers between -0.3 and 365.7.
The perfection of the randomness isn't even that important,
as long as an accidental repeat of the same integer is not within say 4
steps.
So the function can be simple and the seeding can be done by a subset of
+new Date().
A repeatable seed is interesting however for code testing.
--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)
Dr J R Stockton
, Sat, 20 Jun 2009 12:27:27, Evertjan. <exjxw.ha...@interxnl.net>
posted:
>Dr J R Stockton wrote on 19 jun 2009 in comp.lang.javascript:
>
>> In comp.lang.javascript message <Cy0nuvZC...@invalid.uk.co.demon.me
>> rlyn.invalid>, Tue, 9 Jun 2009 18:15:46, Dr J R Stockton
>> <repl...@merlyn.demon.co.uk> posted:
>>>Considerable information about Math.random internals and derived
>>>insecurities is in a 325kB PDF by Amit Klein *via* (!== at)
>>><http://www.trusteer.com/temporary-user-tracking-in-major-browsers>.
>>>
>>>The flaws in the values of Math.random can in principle be overcome by
>>>writing one's own;
>>
>> FYI, I expect soon to have achieved this; for integers, the code should
>> handle numbers up to the megadigit (hex) range, with acceptable speed
>> for reasonable sizes. There is, of course, difficulty in generating a
>> correspondingly-good seed. But, as the seed is exposed, randoms can be
>> generated reproducibly. Does anyone have the relevant volume of Knuth
>> handy?
>
>Why megadigit?
It is necessary to include multidigit. Using just ordinary JavaScript
arithmetic, one cannot without rounding errors produce Randoms of more
that 26 bits of value (exact multiplication is required). The
arithmetic has to be done with arrays of digits. JavaScript arrays are
bounded in size only be available memory, and ISTM that I can have the
necessary number of arrays each with 250,000 elements. The elements I
use are digits base 65536, hence a factor of 4 with some to spare. But
using that many is purely optional.
My <js-randm.htm> demonstrates such a generator more-or-less embedded in
a Form, and I an in the middle of changing its insides to a form-
independent version.
>99.962468 % of the pseudo-random sequences used in clientside Javascript
>are about non negative integers between -0.3 and 365.7.
Fewer that 0.037532% of the Dutch population are EjH ; but that subset
is clearly not insignificant.
>The perfection of the randomness isn't even that important,
>as long as an accidental repeat of the same integer is not within say 4
>steps.
That depends on the application. And algorithms developed in JavaScript
can be re-implemented elsewhere.
>So the function can be simple and the seeding can be done by a subset of
>+new Date().
Amit Klein's cited paper shows that Math.random is commonly not as good
as one might reasonably have hoped, and also is a security leak.
Providing code for an alternative cannot fix the leak; but it can set a
good example. Seeding, however, is difficult; except that the client
can always be asked to enter a suitable seed, which can either. be used
alone or entangled with the time.
>A repeatable seed is interesting however for code testing.
Indisputably.
That could be introduced in ECMA 5+ by simply saying that Math.random()
would do what it "always" has, but Math.random(Object) would use the
object to store the internal state, seed included. With different
Objects, one could have independent Random generators.
--
(c) John Stockton, near London. *@merlyn.demon.co.uk/?.?.Stockton@physics.org
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Correct <= 4-line sig. separator as above, a line precisely "-- " (SoRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SoRFC1036)
Thomas 'PointedEars' Lahn
> Fewer that 0.037532% of the Dutch population are EjH ; but that subset
> is clearly not insignificant.
What does "EjH" mean in this context?
PointedEars
Evertjan.
[..]
>>A repeatable seed is interesting however for code testing.
>
> Indisputably.
>
> That could be introduced in ECMA 5+ by simply saying that Math.random()
> would do what it "always" has, but Math.random(Object) would use the
> object to store the internal state, seed included. With different
> Objects, one could have independent Random generators.
Something like this?
Math.random(myObject)
0..0.99999etc, where:
myObject.seed read/write,
doublevalue or null/undefined/false for auto reseeding,
0 for remember seed/step
myObject.step read/write,
integer step since last seeding, default 0 [= first step],
null/undefined/false or nextstep value for next step
cannot have value higher than next step [???]
Math.random()
Auto seeding on first call,
remember seed/step as in present version
Math.random(Null)
Auto reseeding
Math.random(-3.4,365.3)
Integer autoseeding, fast, easy implementation, perhaps not too
perfect, value interval includes endvalues
Math.random(365)
0... 365 included
Evertjan.
Incomplete quote hides telling context.
Please quote correctly, Thommie. ;-) See the FAQ.
In fact about 6,1614294516327788046826863832409e-6 % of the Dutch
population is EjH and this number is changing minute by the minute,
depending on seed, fatalities and import/export.
This value probably will change to zero percent in an instant,
or become indefinite or 100 % in a major disaster.
Dr J R Stockton
, Sun, 21 Jun 2009 08:40:04, Evertjan. <exjxw.ha...@interxnl.net>
posted:
>Dr J R Stockton wrote on 21 jun 2009 in comp.lang.javascript:
>
>[..]
>
>>>A repeatable seed is interesting however for code testing.
>>
>> Indisputably.
>>
>> That could be introduced in ECMA 5+ by simply saying that Math.random()
>> would do what it "always" has, but Math.random(Object) would use the
>> object to store the internal state, seed included. With different
>> Objects, one could have independent Random generators.
>
>Something like this?
What I had in mind, and have implemented (apart from some necessary
polishing) in <URL:http://www.merlyn.demon.co.uk/js-randm.htm>, is not
greatly like your suggestions.
There, an algorithm of the form
X[n+1] = (X[n]*A + B) % C
is used, and the Object holds integers X A B & log2(C). Since X*A needs
to be exact, and a good A is likely to be of the order of log2(C-1), one
cannot using this and ordinary arithmetic make a reliable 32-bit
generator. Therefore, X A & B are now arrays of 16-bit integers (could
be 24, since 24+24<53), automatically giving the aforementioned
megadigit capability.
That's not the only possible algorithm; but AIUI it's generally
suitable, with well-chosen A B C, for non-crypto work. One could
without much difficulty implement a long shift-register generator; but
it is necessary to determine efficient taps (algorithm uses a very long
array of bits each cycle moves all bits one place to the left, and sets
the vacated LSB to the XOR of the old MSB and some of the other bits).
The function alters the value of X in the Object, and returns what
should be the result of normalising sign = +, mantissa = any 53-bit
integer, exponent is constant, such that the range is 0.0 <= R < 1.0.
One sets the initial X with either a chosen number or a random one
obtained somehow.
>Math.random(myObject)
> 0..0.99999etc, where:
> myObject.seed read/write,
> doublevalue or null/undefined/false for auto reseeding,
> 0 for remember seed/step
> myObject.step read/write,
> integer step since last seeding, default 0 [= first step],
> null/undefined/false or nextstep value for next step
> cannot have value higher than next step [???]
>
>Math.random()
> Auto seeding on first call,
> remember seed/step as in present version
>
>Math.random(Null)
> Auto reseeding
>
>Math.random(-3.4,365.3)
> Integer autoseeding, fast, easy implementation, perhaps not too
> perfect, value interval includes endvalues
>Math.random(365)
> 0... 365 included
I think 0 to 364 would be better; it goes well with zero-based arrays,
and matches other languages.
The core would be more easily implemented in another language, for
example one supporting 32-bit multiplication and 64-bit addition.
--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk BP7, Delphi 3 & 2006.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL:http://www.bancoems.com/CompLangPascalDelphiMisc-MiniFAQ.htm> clpdmFAQ;
NOT <URL:http://support.codegear.com/newsgroups/>: news:borland.* Guidelines
Evertjan.
>>Math.random(365)
>> 0... 365 included
>
> I think 0 to 364 would be better; it goes well with zero-based arrays,
> and matches other languages.
ok
> The core would be more easily implemented in another language, for
> example one supporting 32-bit multiplication and 64-bit addition.
Assembler and Forth would be the best and second best.
Couldn't is be done with binary shifts and and binary and/or/exor only?
That would speed up the process as multiplication has overflow checking
that is not needed in randomizing, methinks.
My binary mathematic skills are not that active.
Automatic seeding would still have to be adressed, my preferences would go
to hardware implementation by measuring spontaneous decay times of a radio
isotope with a t/2>500y.
Cyberutopia?
Dr J R Stockton
, Mon, 22 Jun 2009 08:18:19, Evertjan. <exjxw.ha...@interxnl.net>
posted:
>Dr J R Stockton wrote on 21 jun 2009 in comp.lang.javascript:
>
>>>Math.random(365)
>>> 0... 365 included
>>
>> I think 0 to 364 would be better; it goes well with zero-based arrays,
>> and matches other languages.
>
>ok
>
>> The core would be more easily implemented in another language, for
>> example one supporting 32-bit multiplication and 64-bit addition.
>
>Assembler and Forth would be the best and second best.
Or Delphi, or (one hopes) a language already used for writing JavaScript
engines.
>Couldn't is be done with binary shifts and and binary and/or/exor only?
>
>That would speed up the process as multiplication has overflow checking
>that is not needed in randomizing, methinks.
>
>My binary mathematic skills are not that active.
I think one must use at least some ordinary arithmetic when using
JavaScript to construct from pieces a 53-bit mantissa in a Number. On
other languages it can easily be done more directly - just drop the 64
bits into the mantissa of a suitable Extended value.
A code line can be removed if the internal number-length (right operand
of MOD in the description) is always a multiple of 16.
Improvements may be possible elsewhere in my code; X & 0xFFFF is faster
in FF3 than X % 0x10000 so I should test other browsers : also faster,
and always equivalent. Changed.
>Automatic seeding would still have to be adressed, my preferences would go
>to hardware implementation by measuring spontaneous decay times of a radio
>isotope with a t/2>500y.
A well-designed PC would have a hardware random-bit generator, filling a
few kB of local RAM which would be readable in something like the manner
of the RAM of an RTC chip, or better. By the time the software is ready
to read it, there would be sufficient new bits available. That would be
readable by all languages, including JavaScript.
A purely electronic noise generator could easily enough be used, driving
circuits designed to remove both all possible and all detectable
regularity or bias.
I have seen and partly read a book "One Million Random Digits"; it was
typeset from paper tape by flexowriter; a selection of those could be
entered as a seed.
But see <URL:http://www.merlyn.demon.co.uk/humorous.htm#Rand>.
It was much older than
<http://www.amazon.co.uk/Million-Random-Digits-Normal-Deviates/dp/083303
0477/ref=sr_1_1?ie=UTF8&s=books&qid=1245697700&sr=8-1>; probably a First
Edition.
See <http://en.wikipedia.org/wiki/Random#External_links>.
--
Johannes Baagoe
[Better version of Math.random]
> I think one must use at least some ordinary arithmetic when using
> JavaScript to construct from pieces a 53-bit mantissa in a Number.
Two possible strategies would be:
1. work only with fractional numbers between 0 (included) and 1
(excluded), e.g. by using lines like "x -= Math.floor(x)" as needed,
2. work only with unsigned 32-bit integers, e.g. by using lines like
"x >>>= 0" as needed, and provide a function that takes two such
"random" integers, divide them by suitable constants, add the
results and truncate to deliver a fraction in [0..i).
While Strategy 1 may seem the more straightforward, it has the
major drawback that few PRNG algorithms work with floating point
arithmetic. The most obvious candidate is additive lagged Fibonacci,
but while its "randomness" is arguably better than the Lehmer linear
congruential method that you suggest, the results are not considered
good by current standards, and fail the more demanding tests. Still,
one might try to combine several sources, "shuffle" the output, etc.
Strategy 2 allows one to rely on a much more comprehensive repertoire
of well-researched algorithms, from Marsaglia's pragmatic KISS32
(http://groups.google.com/group/comp.lang.fortran/msg/6edb8ad6ec5421a5)
to the impressive theory behind the Mersenne Twister.
As an example, the following implements KISS32:
function Random() {
var x = 123456789;
var y = 362436069;
var z = 21288629;
var w = 14921776;
var c = 0;
function kiss32() {
x += 545925293;
x >>>= 0;
y ^= y << 13;
y ^= y >>> 17;
y ^= y << 5;
t = z + w + c;
z = w;
c = t >>> 31;
w = t & 0x7fffffff;
return x + y + w >>> 0;
}
this.random = function() { // provides a fraction in [0..1)
var x = (kiss32() / 67108864 + kiss32()) / 67108864;
return x - (x >>> 0);
}
}
However, as it stands, each new Random() yields exactly the same
sequence. The constructor should allow arguments to set the object's
initial state (the variables x, y, z, w and c), making sure that
the constraints are met (Marsaglia: "x can be any 32-bit integer,
y can be any 32-bit integer not 0, z and w any 31-bit integers not
multiples of 7559 c can be 0 or 1.") Further methods may be added to
save the state and reset it to a previously saved value.
> A well-designed PC would have a hardware random-bit generator, filling
> a few kB of local RAM which would be readable in something like the
> manner of the RAM of an RTC chip, or better. By the time the software
> is ready to read it, there would be sufficient new bits available.
> That would be readable by all languages, including JavaScript.
Even without extra hardware, there are enough sources of randomness on
most PCs to maintain an adequate pool of entropy, like /dev/random.
The problem is how to access them in ECMAScript.
--
Johannes
Dr J R Stockton
ws.com>, Mon, 22 Jun 2009 23:04:29, Johannes Baagoe <baa...@baagoe.com>
posted:
>[Better version of Math.random]
I cannot tell whether you have recently looked at my
<URL:http://www.merlyn.demon.co.uk/js-randm.htm#RR> ; but I expect
others here have not, so I'll write without assuming either way.
>> I think one must use at least some ordinary arithmetic when using
>> JavaScript to construct from pieces a 53-bit mantissa in a Number.
>
>Two possible strategies would be:
>
>1. work only with fractional numbers between 0 (included) and 1
>(excluded), e.g. by using lines like "x -= Math.floor(x)" as needed,
>
>2. work only with unsigned 32-bit integers, e.g. by using lines like
>"x >>>= 0" as needed, and provide a function that takes two such
>"random" integers, divide them by suitable constants, add the
>results and truncate to deliver a fraction in [0..i).
Both using some ordinary arithmetic, of course.
>While Strategy 1 may seem the more straightforward, it has the
>major drawback that few PRNG algorithms work with floating point
>arithmetic. The most obvious candidate is additive lagged Fibonacci,
>but while its "randomness" is arguably better than the Lehmer linear
>congruential method that you suggest, the results are not considered
>good by current standards, and fail the more demanding tests. Still,
>one might try to combine several sources, "shuffle" the output, etc.
>
>Strategy 2 allows one to rely on a much more comprehensive repertoire
>of well-researched algorithms, from Marsaglia's pragmatic KISS32
>(http://groups.google.com/group/comp.lang.fortran/msg/6edb8ad6ec5421a5)
>to the impressive theory behind the Mersenne Twister.
I've not been able to remember as much as I would wish to about methods
other than Lehmer. In a JavaScript context, there must be five classes
of algorithms for implementing Math.random :
1 The low-grade muck in actual browsers;
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;
3 Something in between 2 & 4;
4 Cryptographically sound, commercial grade;
5 Cryptographically sound, national security grade.
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>).
of the others, 5 & 4 are beyond me; and 3 seems horribly like falling
between two stools (hoping you know the expression).
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.
>> A well-designed PC would have a hardware random-bit generator, filling
>> a few kB of local RAM which would be readable in something like the
>> manner of the RAM of an RTC chip, or better. By the time the software
>> is ready to read it, there would be sufficient new bits available.
>> That would be readable by all languages, including JavaScript.
>
>Even without extra hardware, there are enough sources of randomness on
>most PCs to maintain an adequate pool of entropy, like /dev/random.
However, one must consider who is getting access to that pool. 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. 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.
>The problem is how to access them in ECMAScript.
That should be impossible, rather than a problem.
--
(c) John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Proper <= 4-line sig. separator as above, a line exactly "-- " (SonOfRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036)
Johannes Baagoe
> 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
Dr J R Stockton
ws.com>, Wed, 24 Jun 2009 10:20:42, Johannes Baagoe <baa...@baagoe.com>
posted:
>Dr J R Stockton :
>> 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.
I'm not so sure about "mainly used"; you may be underestimating
the number who know no better.
>> 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.
Agreed; nevertheless, since an IEEE Double has 53 bits of resolution,
and 64-bit Lehmer is sufficiently easy to implement, and other good,
easy methods are well enough known (if not by me), it seem inexcusable
to provide anything other than an equivalent to a random selection from
the 53-bit integers then divided by 2^53. Things should be as good as
easily possible, even if the necessity is not obvious.
In Safari 4, Math.random seems to be slightly worse, in at least one
respect, than that in Safari 3.1.1.
>But neither can your function RRN1(). It is actually worse than most
>Math.random implementations - 32 bits vs. 48.
It is an emulation of Borland's 32-bit one, in Pascal & Delphi (but not
necessarily the latest Delphi). That might be considered of very
adequate quality when introduced, 22 years ago or earlier; but, for
similar reasons, not now. Random in Delphi should return an Extended;
and all one need do for that is to take a good random Int64 and precede
it by a positive signed word constant for the appropriate coded
exponent.
>> 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.
The stated conditions were intended to be necessary, but not to be
satisfactorily sufficient.
An IEEE Double with a regular alternating pattern in its LSB, while not
ideal, is considerably better that what three recent PC browsers
provide, which appear to be IEEE Doubles with 20 or more LSBs all zero.
But there seems a risk in trying to persuade browser makers to provide
anything better than what I meant in 2; they might then prefer not to
bother.
>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?
<g> IMHO, needs comment : // 134217728 = 2^27 </g>
Something like. Passing in the Seed suffices; my idea would pass in
also the numbers within the function, so that one piece of code could
produce various types of Random.
>function Lehmer(seed) {
> var x = seed; return (lehmer27() / 134217728 + lehmer27()) / 134217728;
> }
I was not sure whether I ought to be able to understand whether, if the
two calls return integers in that range that have no significant
correlation, that should give an IEEE Double with all the desirable
properties = until I realised the value of 2^27. In particular, a
result at least 0.5 must be a multiple of 2^-53, in an IEEE Double; but
a smaller one can perhaps be an odd multiple of 2^-54. It might be
better to use lehmer26 and lehmer27; or to mask out a bit.
>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...
There should be provided an obvious way to seed it with known values
(Delphi : assign to RandSeed); possibly as setRandSeed(X). That moves
the worry into another routine, which the user can provide - somehow.
>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.
That depends on the application. Web pages do not necessarily return
results to the server; they can instead be shown at the client end to
the user. In that case, it's the user's responsibility to enter a seed
with enough entropy for the purpose.
I wonder whether the current RAND book contains the same 1,000,000
digits as the first edition - given the estimate that probably one of
the original digits is wrong?
Is there a small set of URLs that you can recommend to Garrett Smith for
FAQ section 5.5, <http://jibbering.com/faq/index.html#randomNumber>,
ones leading to the world of good Random Number generation? FAQ
reference 1 is OK, 2 content is wrong, and you've seen 3 (which has some
such URLs).
IMHO, your thoughts should be known to those working on ECMA 262 Final
Draft 5
<http://www.ecma-international.org/publications/files/drafts/
tc39-2009-025.pdf>
which includes an address for feedback "by July 15, 2009".
--
(c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike v6.05.
Web <URL:http://www.merlyn.demon.co.uk/> - w. FAQish topics, links, acronyms
PAS EXE etc : <URL:http://www.merlyn.demon.co.uk/programs/> - see 00index.htm
Dates - miscdate.htm estrdate.htm js-dates.htm pas-time.htm critdate.htm etc.
Johannes Baagoe
[Turning two pseudorandom 32-bit integers into one IEEE 754 float in
[0..1)]
> In particular, a result at least 0.5 must be a multiple of 2^-53,
> in an IEEE Double; but a smaller one can perhaps be an odd multiple
> of 2^-54. It might be better to use lehmer26 and lehmer27; or to
> mask out a bit.
It seems that you are right about that:
In early versions of Java, the result was incorrectly calculated as:
return (((long)next(27) << 27) + next(27))
/ (double)(1L << 54);
This might seem to be equivalent, if not better, but in fact it
introduced a large nonuniformity because of the bias in the rounding
of floating-point numbers: it was three times as likely that the
low-order bit of the significand would be 0 than that it would be 1!
This nonuniformity probably doesn't matter much in practice, but
we strive for perfection.
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html#nextDouble()
(It does not matter here that it is Java, not ECMAScript. Both
languages share the idea, also present in Perl and others, of providing
"random" numbers as fractions in [0..1), not as integers. It is IMHO
an excellent idea, since the integer rand() function of C and others
is rather more difficult to use correctly, and very often misused. But
it does place an extra burden on implementers.)
> There should be provided an obvious way to seed [the generator]
> with known values (Delphi : assign to RandSeed); possibly as
> setRandSeed(X). That moves the worry into another routine, which
> the user can provide - somehow.
Yes, but it is not quite trivial to provide a seed that has a
reasonable probability of being *absolutely unique* over zillions of
instances in time and space.
I shall give it an attempt, though, in another post.
> I wonder whether the current RAND book contains the same 1,000,000
> digits as the first edition - given the estimate that probably one
> of the original digits is wrong?
I couldn't say - I only occasionally use an electronic version
(http://www.rand.org/pubs/monograph_reports/2005/digits.txt.zip) in
"Look, no hands!" arguments to show that I have not chosen constants
with a nefarious motive, since the paper version was published before
my birth.
But it must surely qualify as one of the most boring books ever,
notwithstanding the occasional occurrence of such risqué passages as
"69696" (lines 14825 and 15798) and "96969" (lines 10903, 11261 and
18131). (Noted by George Marsaglia, who also recommends the multiplier
69069 for 32-bit Lehmer, since it is quite good and easy to remember).
> Is there a small set of URLs that you can
> recommend to Garrett Smith for FAQ section 5.5,
> <http://jibbering.com/faq/index.html#randomNumber>, ones leading to
> the world of good Random Number generation?
http://en.wikipedia.org/wiki/Pseudorandom_number_generator is good
and should get one started on the subject.
http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf gives
a comprehensive view of actual generators' performances.
But I'm not sure those references belong in the FAQ, general
pseudo-random number generation is hardly an ECMAScript issue.
> FAQ reference 1 is OK, 2 content is wrong,
It is pretty useless, but why is it wrong?
> and you've seen 3 (which has some such URLs).
Yes. Would you please change the link on my name to a more definitive
version as soon as I have written one ? I forgot to declare var t in
function kiss32(), with the abominable result of making t global.
Hardly the sort of thing to recommend.
> IMHO, your thoughts should be known
> to those working on ECMA 262 Final Draft 5
> <http://www.ecma-international.org/publications/files/drafts/
tc39-2009-025.pdf>
> which includes an address for feedback "by July 15, 2009".
I don't know. I rather believe it is an issue to be addressed by
user-defined objects or specialised libraries, since different
solutions may be better for different problems. But if I manage to
bring something together that the group approves of, I shall follow
the consensus.
--
Johannes
Johannes Baagoe
> I shall give it an attempt, though, in another post.
Here it is: introducing the Random object. Comments are welcome.
Synopsis :
var r = new Random(seed1, seed2, ...);
r.random(); // returns a "random" number in [0..1)
The constructor may be called with any number of seeds of any kind -
dates, strings, numbers, events, etc. (They are converted internally
to strings.)
You may, for instance, write things like
r = new Random(
new Date(),
document.location.href,
document.documentElement.clientWidth,
document.documentElement.clientHeight
);
which should make it rather unlikely that two users ever generate the same
sequence of numbers. (Assuming that the three last arguments make sense in
your environment, which should be checked beforehand, of course.)
new Random() with no arguments is equivalent to new Random(new Date()),
for convenience. Apart from this special case, two Random objects
constructed with the same arguments will yield the same sequence.
Other methods :
reSeed(seed1, seed2, ...) alters the existing state by combining it with
the new seeds. As with the constructor, if there is no seed at all, an
implicit seed of new Date() is assumed. If called in an event handler,
one of the seeds (most likely the only one) may be the event itself. The
idea is to collect entropy, in order to make the sequence of "random"
numbers truly unpredictable. No claim to cryptological security is made,
however. (Also, while the implementation should, as far as I can see,
work on any standard-compliant browser, I haven't tested it on anything
but Firefox for Ubuntu. This is where I walk on the thinnest ice.)
getState() returns the internal state of the generator, to allow replays.
setState(state) resets the generator to a state saved with getState().
Code :
function Random() {
var x = 123456789;
var y = 362436069;
var z = 21288629;
var w = 14921776;
var c = 0;
var hash = 31415;
function kiss32() {
x += 545925293;
x >>>= 0;
y ^= y << 13;
y ^= y >>> 17;
y ^= y << 5;
var t = z + w + c;
z = w;
c = t >>> 31;
w = t & 0x7fffffff;
return x + y + w >>> 0;
}
this.random = function() {
return ((kiss32() >>> 5) / 134217728 + (kiss32() >>> 6)) / 67108864;
}
this.reSeed = function() {
var seed = '';
var i, arg, prop;
if (arguments.length === 0) {
this.reSeed(new Date());
}
for (i = 0; i < arguments.length; i++) {
arg = arguments[i];
if (arg instanceof Date) {
seed += arg.getTime();
seed += arg.getTimezoneOffset();
} else if ((typeof Event != 'undefined') && (arg instanceof Event)) {
for (prop in arg) {
seed += arg[prop];
}
} else {
seed += arg;
}
}
for (i = seed.length - 1; i >= 0; i--) {
hash = (hash + seed.charCodeAt(i)) * 69069 >>> 0;
switch (i % 4) {
case 0:
x ^= hash;
break;
case 1:
y ^= hash;
break;
case 2:
z ^= hash;
break;
case 3:
w ^= hash;
break;
}
}
if (y == 0) {
y = 1;
}
c ^= z >>> 31;
z &= 0x7fffffff;
if (!(z % 7559)) {
z++;
}
w &= 0x7fffffff;
if (!(w % 7559)) {
w++;
}
}
this.getState = function() {
return {
x: x,
y: y,
z: z,
w: w,
c: c,
hash: hash
}
}
this.setState = function(state) {
x = state.x;
y = state.y;
z = state.z,
w = state.w;
c = state.c;
hash = state.hash;
}
this.reSeed.apply(this, arguments);
}
WARNING : I know next to nothing about cross-browser issues, I don't
usually write for the World Wide Web. E.g., in reSeed, I assume that if
Event is defined and something is an instanceof Event, that something
is indeed a DOM event whose properties may be implicitly converted
to Strings and concatenated in a for ... in statement, and that the
resulting string will indeed contain at least a timestamp with a
theoretical millisecond resolution, the mouse coordinates in the case
of mouse events, the key involved in the case of key events, etc. For
all I know, these could be wild assumptions in some browsers.
Feedback on such and other issues would be much appreciated.
--
Johannes
Dr J R Stockton
ws.com>, Thu, 25 Jun 2009 05:38:22, Johannes Baagoe <baa...@baagoe.com>
posted:
>Dr J R Stockton :
>> There should be provided an obvious way to seed [the generator]
>> with known values (Delphi : assign to RandSeed); possibly as
>> setRandSeed(X). That moves the worry into another routine, which
>> the user can provide - somehow.
>
>Yes, but it is not quite trivial to provide a seed that has a
>reasonable probability of being *absolutely unique* over zillions of
>instances in time and space.
And therefore the problem should be shifted to a different routine; one
version of that can be provided by the system, but the seed must be
transported from one to the other as the value of a variable (simple or
compound). Then one can use instead a better routine to generate the
seed; or one can re-use the same seed to get, when debugging, the same
random numbers again.
In fact, a seed generator is just a better, slower RNG.
Seed generation, seed insertion, and seed usage should be separated.
>I shall give it an attempt, though, in another post.
>> Is there a small set of URLs that you can
>> recommend to Garrett Smith for FAQ section 5.5,
>> <http://jibbering.com/faq/index.html#randomNumber>, ones leading to
>> the world of good Random Number generation?
>
>http://en.wikipedia.org/wiki/Pseudorandom_number_generator is good
>and should get one started on the subject.
>
>http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf gives
>a comprehensive view of actual generators' performances.
>
>But I'm not sure those references belong in the FAQ, general
>pseudo-random number generation is hardly an ECMAScript issue.
Not the montreal one; but presenting "Pseudorandom_number_generator"
will indicate a route to, presumably, all else. It can replace the
current second link.
>> FAQ reference 1 is OK, 2 content is wrong,
>
>It is pretty useless, but why is it wrong?
Both say, near enough, "between 0 and 1" but 1 remarks "0 (inclusive) to
1 (exclusive)" and 2 does nothing like that.
But I use 2 and its brothers frequently (but local copy of a more
legible no CSS) version).
>> and you've seen 3 (which has some such URLs).
>
>Yes. Would you please change the link on my name to a more definitive
>version as soon as I have written one ? I forgot to declare var t in
>function kiss32(), with the abominable result of making t global.
>Hardly the sort of thing to recommend.
Of course. Let me know. Note : the address of this article includes
ISO 8601 YYWW.
>> IMHO, your thoughts should be known
>> to those working on ECMA 262 Final Draft 5
>> <http://www.ecma-international.org/publications/files/drafts/
>tc39-2009-025.pdf>
>> which includes an address for feedback "by July 15, 2009".
>
>I don't know. I rather believe it is an issue to be addressed by
>user-defined objects or specialised libraries, since different
>solutions may be better for different problems. But if I manage to
>bring something together that the group approves of, I shall follow
>the consensus.
You manifestly know far more than they would want; but pressing for all
53 effective bits of the Number to be evenly-distributed and random
could be useful. I don't know whether a 53 or 64 bit cycle length might
be preferred. And they could add that crypto-grade is not expected,
which serves the useful purpose of pointing out that better
possibilities exist.
Johannes Baagoe
> And therefore the problem should be shifted to a different routine;
> one version of that can be provided by the system, but the seed must
> be transported from one to the other as the value of a variable
> (simple or compound). Then one can use instead a better routine
> to generate the seed; or one can re-use the same seed to get, when
> debugging, the same random numbers again.
> In fact, a seed generator is just a better, slower RNG.
> Seed generation, seed insertion, and seed usage should be separated.
I am not sure I understand what you mean, do my proposed Random
objects meet your specifications ?
I do not guarantee that new Random(seed1, seed2, seed3) will always
yield the same sequence on different implementations of ECMAScript.
Different implementations of the toString() method of Objects may
yield vastly differing results. If all the seeds are either Numbers
or Strings, it should be reasonably safe, though. And a state saved
with getState() should be completely transportable.
But the main problem I wanted to address is that of providing truly
unique sequences that can be used to make UUIDs. If, e.g., I attach
reSeed(event) to keypress events in a form, by the time the user has
filled in the form, she has pressed enough keys at sufficiently random
millisecond intervals to make me reasonably sure that my generator
can produce a separator in a POST request that will be truly unique,
/ubique, semper et ab omnibus/. Especially if I started the generator
at load time with the current Date() and URL.
> I don't know whether a 53 or 64 bit cycle length might be preferred.
Both are much too short, in my opinion. Not that anyone would ever want
to generate 2^53 random numbers in ECMAScript, but it also means that
there are only 53 or 64 bits of state. Given the Birthday Paradox,
it only takes 5.1E9 attempts - less than one per inhabitant of the
Earth - to get a 50 % probability of a collision: two generators
with *exactly* the same state, producing *exactly* the same "random"
numbers. It doesn't matter when shuffling virtual cards, but it could
matter when generating supposedly unique identifiers.
--
Johannes
Dr J R Stockton
ws.com>, Thu, 25 Jun 2009 17:47:00, Johannes Baagoe <baa...@baagoe.com>
posted:
>Johannes Baagoe :
>
>> I shall give it an attempt, though, in another post.
>
>Here it is: introducing the Random object. Comments are welcome.
The link in the master of my page is updated, to <that> at Google.
After discussion finishes, you could very easily put your article onto a
web site as a *.txt file; and publishing future changes would not then
require updating URLs.
Comment here is on details only.
>The constructor may be called with any number of seeds of any kind -
>dates, strings, numbers, events, etc. (They are converted internally
>to strings.)
Conversion of new Date() to string loses randomness, as the strings lack
milliseconds. It also adds cross-browser non-reproducibility, as string
formats vary. I suggest Date Objects should be converted first to
Number, using a unary + sign,
>You may, for instance, write things like
>
> r = new Random(
> new Date(),
+new Date() // if not handled internally
> document.location.href,
> document.documentElement.clientWidth,
> document.documentElement.clientHeight
> );
>
>which should make it rather unlikely that two users ever generate the same
>sequence of numbers.
For test, it is desirable that it should be possible for two colluding
user (or a self-colluding one) to get the same sequence repeatedly. But
the default should be that repeats are grossly improbable.
> function kiss32() {
// IMHO, that needs to cite a reference for kiss32.
> if (arg instanceof Date) {
> seed += arg.getTime();
// or seed += +arg; // should be equivalent.
> seed += arg.getTimezoneOffset();
That gives the *appearance* of adding minutes to milliseconds. It might
need a comment to show that it is not a mistake. World-wide, it only
adds about 5.3 bits of randomness; in a fixed location, 0 or 1 bit. It
may not be worth-while. A user can always put it in as an argument if
wanted.
>Feedback on such and other issues would be much appreciated.
For test purposes, it should be possible for people on different systems
in different places to get the same results. For that, they can use an
external new Date(arguments) to simulate new Date() consistently.
Having getTimezoneOffset internally makes matters location-dependent.
--
(c) John Stockton, nr London, UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links;
Astro stuff via astron-1.htm, gravity0.htm ; quotings.htm, pascal.htm, etc.
No Encoding. Quotes before replies. Snip well. Write clearly. Don't Mail News.
Dr J R Stockton
ws.com>, Thu, 25 Jun 2009 19:46:56, Johannes Baagoe <baa...@baagoe.com>
posted:
>Dr J R Stockton :
>
>> And therefore the problem should be shifted to a different routine;
>> one version of that can be provided by the system, but the seed must
>> be transported from one to the other as the value of a variable
>> (simple or compound). Then one can use instead a better routine
>> to generate the seed; or one can re-use the same seed to get, when
>> debugging, the same random numbers again.
>
>> In fact, a seed generator is just a better, slower RNG.
>
>> Seed generation, seed insertion, and seed usage should be separated.
>
>I am not sure I understand what you mean, do my proposed Random
>objects meet your specifications ?
I'm pretty sure, without actually having executed it yet, that the
version I have most recently seen does so; but not sure about the most
recent one that I had read when I wrote that.
OTOH, you have
reSeed(seed1, seed2, ...), getState(), setState(state)
but no way to generate a state without affecting the generator.
How about offering
makeState(,,,,), setState(state), getState(), reSeed(state)
where reSeed is possibly not needed if any argument of makeState(,,,,)
can be a state? I think it separates the functionality better, which
can often enable users to do things which had not been foreseen.
Analogy : Method getYear, returning 0 to 99 for 1900 to 1999, has that
fault; implementing it as getFullYear would have meant that
those wanting a number less than 100 would have needed to use
%100 (B.C. years can be disregarded here) and those wanting the
full year would always get it. Then, who wants 0 to 99? That's
OK in years 1900-1999, as years 1900-1909 are in the Distant
Past; but in the then-nearly-imminent years 2000 to 2009, it is
"00" to "99" that is needed. Add method getYY, returning a two-
digit string; and +getYY is another way of getting a number 0 to
99 if wanted.
My Date2 Object has a getYY equivalent.
This thread has bifurcated. Perhaps I should say that, while I have
broadband Web access, I still use dial-up for News and Mail. It's a
matter of what software does what with/without an operational licence.
>I do not guarantee that new Random(seed1, seed2, seed3) will always
>yield the same sequence on different implementations of ECMAScript.
>Different implementations of the toString() method of Objects may
>yield vastly differing results. If all the seeds are either Numbers
>or Strings, it should be reasonably safe, though. And a state saved
>with getState() should be completely transportable.
Therefore, .toString on types other than Number or String should be
avoided, where practical. As far as I know, Number.toString is browser-
independent ... but ECMA says it need not be. I imagine it's safe for
integers no bigger than 2^53.
>But the main problem I wanted to address is that of providing truly
>unique sequences that can be used to make UUIDs.
I rather wonder whether one should expect Math.random to do that. It
might be better to have Math.random being essentially numeric 53 or 64
bit, and to have another, slower method to produce GUID strings.
There's surely a lot to be said for having Random seedable so that it
always gives the same sequence while having no chance of thereby
affecting GUID generation.
In fact, if Math.random can be re-seeded and is used for GUIDs, it may
be possible for an attacker to force a known GUID and to achieve a
breach of security.
>> I don't know whether a 53 or 64 bit cycle length might be preferred.
>Both are much too short, in my opinion. Not that anyone would ever want
>to generate 2^53 random numbers in ECMAScript,
> ...
Same response.
FYI : <js-randm.htm> now has a 32-bit routine in which the
multiplication is done with three 16-bit * 16-bit multiplications,
suitably combined without rounding, by first decapitating. That now
gives the right results, matching Pascal's Random. I won't explain more
here because it might be improved. It should be better than some
current Math.random; but it would not make a good Math.random.
Johannes Baagoe
>> You may, for instance, write things like
>> r = new Random(new Date(), document.location.href,
>> document.documentElement.clientWidth,
>> document.documentElement.clientHeight);
>> which should make it rather unlikely that two users ever generate
>> the same sequence of numbers.
Dr J R Stockton :
> For test, it is desirable that it should be possible for two colluding
> user (or a self-colluding one) to get the same sequence repeatedly.
In that case, they should call the constructor with the same arguments,
like new Random('foo', 'bar') or simply new Random('').
My purpose with the given example is to show ways in which an
application programmer could make it very unlikely that two users
generate the same random numbers. If the hashing mechanism of seeds
functions adequately (which should thoroughly analysed and tested),
the biggest risk would be that they both load the same Web page at the
exactly same time in windows of exactly the same size. And if that is
not deemed safe enough, the programmer may add whatever other seeds she
wants to decrease the likelihood even more, perhaps the User-Agent string
or other results of browser sniffing or even cookies.
> But the default should be that repeats are grossly improbable.
There is the problem: I don't know of anything that is universally
accessible to ECMAScript and more unforeseeable than the current
time. It is rather improbable that two users initialise their random
numbers at exactly the same millisecond, but it is not *grossly*
improbable. Not to mention that I do not really trust all platforms
to measure time with true millisecond granularity.
>> function kiss32() {
> // IMHO, that needs to cite a reference for kiss32.
Quite, professor Marsaglia deserves due credit. It seems to be an
amazing generator, with three deceptively simple components (the
first one is just a constant increment !), and yet, if its author
is to be believed, it performs as well as anything else he has come
up with. Since he is a leading specialist in the field and some of
his other creations actually perform better in some ways than the
Mersenne Twister, it is a strong claim. I haven't yet found the time
to submit KISS32 to some new tests I have recently been made aware of,
but so far, it passes all the tests I have tried with flying colours.
>> seed += arg.getTimezoneOffset();
> That gives the *appearance* of adding minutes to milliseconds.
> It might need a comment to show that it is not a mistake.
The whole thing needs lots of comments. I didn't put them in first
to save space.
> World-wide, it only adds about 5.3 bits of randomness; in a fixed
> location, 0 or 1 bit.
Not even that, since two users at the same location *at the same time*
are unlikely to have different TimezoneOffsets. It could only happen
if at least one of them decided to use a foreign time zone setting
on her computer.
> It may not be worth-while. A user can always put it in as an argument
> if wanted.
Agreed. I remove it, and treat Dates by prepending a "+", thus
converting them into milliseconds.
>> Feedback on such and other issues would be much appreciated.
> For test purposes, it should be possible for people on different
> systems in different places to get the same results.
No problem at all, just don't use any of the mechanisms provided to
make the outputs truly *random*. The shortest way to do that is to
call the constructor with the empty string as sole argument, instead
of no argument at all : new Random('') instead of new Random().
> For that, they can use an external new Date(arguments) to simulate
> new Date() consistently.
True, but it is even simpler to call new Random('foo').
--
Johannes
Johannes Baagoe
> pressing for all 53 effective bits of the Number to be
> evenly-distributed and random could be useful
Some thoughts on that :
The problem arises because the vast majority of PRNGs generate
integers, not fractions between 0 (included) and 1 (excluded). And
the ones most suitable for ECMAScript produce 32-bit integers, while
the best resolution one can attain in ECMASCript Numbers is 53 bits.
Let a and b be two "random" unsigned 32-bit integers obtained by some
suitable method. (If they could be signed, "a >>>= 0" and "b >>>= 0"
will convert them to what we want : integers in [0 .. 4294967295].
-1 >>> 0 === 4294967295.)
Let x be the desired fraction in [0..1).
Suppose first that we are lazy, and don't mind ending up with just 32
bits of resolution in x. In that case, we don't need b, we can just write
x = a * Math.pow(2, -32);
If we insist (as we do) on 53 bits of resolution, we could try
x = a * Math.pow(2, -32) + b * Math.pow(2, -53);
But then, the 11 least significant bits of a would "overlap" with the
11 most significant bits of b. Adding them means carries which may
propagate, complicating the analysis of the probabilities of each of
the 23 most significant bits of x. We may even end up with an x >= 1.
That particular case could be cared for with "x -= Math.floor(x)" or
"x -= (x >>> 0)", but still, it is a mess. I am not sure it matters
in the end, but I, for one, am much more easily convinced that all the
bits in x are "random" if we discard a total of 11 bits from a and b,
and simply concatenate the results.
Which ones should go ? Most significant, least significant, from a,
b, or both ?
In the case of Lehmer's linear congruential method, the least
significant bits of both a and b are considerably "less random"
than the most significant, and should be discarded. We should chop
off the last 5 bits from one and the last 6 from the other, thus :
x = (a >>> 5) * Math.pow(2, -27) + (b >>> 6) * Math.pow(2, -53);
or
x = (a >>> 6) * Math.pow(2, -26) + (b >>> 5) * Math.pow(2, -53);
However, with other sources of "random" UInt32s, it may be the
case that the *least* significant bits are the more random, e.g., if
they result from timing physical events. In that case, one should use
x = (a & 0x07ffffff) * Math.pow(2, -27) +
(b & 0x03ffffff) * Math.pow(2, -53);
or
x = (a & 0x03ffffff) * Math.pow(2, -26) +
(b & 0x07ffffff) * Math.pow(2, -53);
It may even be the case that the "best" bits are neither the most nor
the least significant, but somewhere in the middle, e.g., they result
from measurements, but the precision is overrated and produces systematic
zeros in the last bits. The proper treatments are left as an exercise.
Things are simpler if the original source of "random" UInt32s is of
sufficiently high quality for all its bits to be equally "good". In
that case, nothing but a penchant for fairness justifies that one selects
about as many bits from a as from b. If we don't insist on such irrelevant
fantasies, we may simply write
x = a * Math.pow(2, -32) + (b >>> 11) * Math.pow(2, -53);
--
Johannes
Johannes Baagoe
>> But the main problem I wanted to address is that of providing truly
>> unique sequences that can be used to make UUIDs.
Dr J R Stockton :
> I rather wonder whether one should expect Math.random to do that.
> It might be better to have Math.random being essentially numeric 53
> or 64 bit, and to have another, slower method to produce GUID strings.
The problem is that apparently, some people *do* use Math.random to
produce supposedly unique IDs. I suppose they call it repeatedly
in order to generate successive groups of hexadecimal characters,
or something like that. But given that in most implementations, the
sequence of "random" numbers is *only* a function of startup time,
any two users starting at the same millisecond end up generating the
exact same IDs.
> There's surely a lot to be said for having Random seedable so that
> it always gives the same sequence while having no chance of thereby
> affecting GUID generation.
There is also, in my opinion, a lot to be said for having Random
*repeatedly* reseedable, e.g., in event handlers, in order to let
it collect entropy. My reSeed method does just that - please note
that is does not *replace* the existing state, it *combines* it in
a complex way with information from the new seeds.
> In fact, if Math.random can be re-seeded and is used for GUIDs,
> it may be possible for an attacker to force a known GUID and to
> achieve a breach of security.
In my approach, it is entirely up to the user whether or not to
replace Math.random itself. It could easily be done, e.g., with
var myPRNG = new Random('');
Math.random = myPRNG.random;
and this would indeed provide completely predictable successive
Math.random()s, but I fail to see how introducing a new Random constructor
make matters worse than they are (one may redefine Math.random any way
one deems fit, such are the rules of ECMAScript), and I also fail to see
how this could be exploited unless the victim is uncommonly cooperative.
>>> I don't know whether a 53 or 64 bit cycle length might be preferred.
>> Both are much too short, in my opinion. Not that anyone would ever
>> want to generate 2^53 random numbers in ECMAScript, ...
> Same response.
And same response.
Perhaps an indication of why we seem to be arguing about different
things is in your statement on js-randm.htm: "A pseudo-random sequence
generator is probably used. Such have a definite cycle length, which
cannot be more than 2^n for a generator with an n-bit seed."
Not so. The sequence cannot be more than 2^n for a generator with an
n-bit *state*. The length of the *seed* is quite another matter. For
instance, one implementation (*) in ECMAStript of the Mersenne
Twister is *seeded* with an arbitrary, possibly zero, number of 32-bit
unsigned integers, but its period is an amazing 2^19937 − 1, even
if one provides much less than 623 such integers. On the other hand,
if one provides only one seed to the constructor, there can only be
at most 2^32 *different* such periods for the resulting instances.
(*) http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/VERSIONS/JAVASCRIPT/java-script.html
> FYI : <js-randm.htm> now has a 32-bit routine in which the
> multiplication is done with three 16-bit * 16-bit multiplications,
> suitably combined without rounding, by first decapitating. That now
> gives the right results, matching Pascal's Random.
As it happens, I did the same thing some time ago in an attempt to
simplify the aforementioned version of the Mersenne Twister. Here it is :
function mult32(n1, n2) {
var a0 = n1 & 0xffff,
a1 = n1 >>> 16,
b0 = n2 & 0xffff,
b1 = n2 >>> 16;
return a0 * b0 + (a0 * b1 + a1 * b0 << 16) >>> 0;
}
--
Johannes
Dr J R Stockton
ws.com>, Sat, 27 Jun 2009 09:29:08, Johannes Baagoe <baa...@baagoe.com>
posted:
>Johannes Baagoe :
>
>>> But the main problem I wanted to address is that of providing truly
>>> unique sequences that can be used to make UUIDs.
>
>Dr J R Stockton :
>
>> I rather wonder whether one should expect Math.random to do that.
>> It might be better to have Math.random being essentially numeric 53
>> or 64 bit, and to have another, slower method to produce GUID strings.
>
>The problem is that apparently, some people *do* use Math.random to
>produce supposedly unique IDs. I suppose they call it repeatedly
>in order to generate successive groups of hexadecimal characters,
>or something like that. But given that in most implementations, the
>sequence of "random" numbers is *only* a function of startup time,
>any two users starting at the same millisecond end up generating the
>exact same IDs.
The best answer is to stop them doing it. One can provide a GUID-
generator in script independently of Math.random. One can hope that
ECMA will add a GUID-generator to the language, specified to be of
sufficient quality.
One can presumably generate entropy by timing the intervals between
keystrokes, after requesting the user to copy-type a text in mixed Welsh
and Finnish while playing the Overture to Tannhauser on one speaker and
some Stockhausen on the other, for distraction.
Given that, if random numbers are needed for arithmetic, the task
probably calls for a few sequences of a lot of them, the random number
generator should be reasonably fast. However, GUIDs are probably not
wanted at a great rate, but need more entropy. Therefore a good GUID
generator would be good for generating good seeds for numeric-random.
>> There's surely a lot to be said for having Random seedable so that
>> it always gives the same sequence while having no chance of thereby
>> affecting GUID generation.
>
>There is also, in my opinion, a lot to be said for having Random
>*repeatedly* reseedable, e.g., in event handlers, in order to let
>it collect entropy. My reSeed method does just that - please note
>that is does not *replace* the existing state, it *combines* it in
>a complex way with information from the new seeds.
>
>> In fact, if Math.random can be re-seeded and is used for GUIDs,
>> it may be possible for an attacker to force a known GUID and to
>> achieve a breach of security.
>
>In my approach, it is entirely up to the user
No. It is up to the coder of the web page, not the viewer thereof; an
innocuous looking GUID might hold information dependent on the value of
the seed. The local part of my message-ID, for example, encodes at
least part of the time_t of generation, and I think also the identity of
the generating system.
> whether or not to
>replace Math.random itself. It could easily be done, e.g., with
>
> var myPRNG = new Random('');
> Math.random = myPRNG.random;
>
>and this would indeed provide completely predictable successive
>Math.random()s, but I fail to see how introducing a new Random constructor
>make matters worse than they are (one may redefine Math.random any way
>one deems fit, such are the rules of ECMAScript), and I also fail to see
>how this could be exploited unless the victim is uncommonly cooperative.
>
>
>>>> I don't know whether a 53 or 64 bit cycle length might be preferred.
>
>>> Both are much too short, in my opinion. Not that anyone would ever
>>> want to generate 2^53 random numbers in ECMAScript, ...
>
>> Same response.
>
>And same response.
>
>Perhaps an indication of why we seem to be arguing about different
>things is in your statement on js-randm.htm: "A pseudo-random sequence
>generator is probably used. Such have a definite cycle length, which
>cannot be more than 2^n for a generator with an n-bit seed."
Changed. But ISTM that it is common practice to use "seed" to refer to
that from which the next generation of random number is derived; the
Founder of the Line merely being the determining first.
>Not so. The sequence cannot be more than 2^n for a generator with an
>n-bit *state*. The length of the *seed* is quite another matter. For
>instance, one implementation (*) in ECMAStript of the Mersenne
>Twister is *seeded* with an arbitrary, possibly zero, number of 32-bit
>unsigned integers, but its period is an amazing 2^19937 0 >if one provides much less than 623 such integers. On the other hand,
>if one provides only one seed to the constructor, there can only be
>at most 2^32 *different* such periods for the resulting instances.
That seems to me to be a partial seed; either it does not provide enough
bits to determine the initial state, which is otherwise indeterminate,
or sufficient implied bits are provided internally.
A generator should be initialised by a variable sufficient to determine
its entire state, and it should be possible to read that state back into
a variable. The variable must be capable of holding as many bits as the
generator can; but an instance of the variable need not appear to have
that many bits.
Example : I initialise 32-bit Lehmer demonstrations with 0, but
that's shorthand for a 64-bit IEEE Double of which only 32 bits-
worth are actually used.
There should be at least one way of generating such state-variables with
entropy-laden values; and the coder should be able to provide other
ways.
I don't think it is *necessary* to provide a routine to add entropy to
what already exists in the generator proper, since (with the above) one
can read the state, add entropy to that, and fully reinitialise the
generator with that -- and that seems a tidier approach, with good
separation of function. But it may be *convenient* to do so, perhaps by
a non-primitive routine.
>> FYI : <js-randm.htm> now has a 32-bit routine in which the
>> multiplication is done with three 16-bit * 16-bit multiplications,
>> suitably combined without rounding, by first decapitating. That now
>> gives the right results, matching Pascal's Random.
And now it does not, since it now has two 32*16 multiplications instead.
>As it happens, I did the same thing some time ago in an attempt to
>simplify the aforementioned version of the Mersenne Twister. Here it is :
>
> function mult32(n1, n2) {
> var a0 = n1 & 0xffff,
> a1 = n1 >>> 16,
> b0 = n2 & 0xffff,
> b1 = n2 >>> 16;
> return a0 * b0 + (a0 * b1 + a1 * b0 << 16) >>> 0;
> }
Slightly related : the numbers AB and CD, where each of A B C D
represent N (=many) digits can obviously be multiplied in time of the
order of (2N)^2 for calculating AC AD BC BD, plus a few times N for
additions. One can rearrange the work to take 3N^2 for multiplication,
plus a few additions/subtractions. That takes 3/4 of the time. Now
partition A into Aa and C into Cc, and the same trick done also for AD
BC BD gets to 9/16 of the time. Recurse a total of log2(N) times, and
get to (3/4)^log2(N). If interested, a Web search for Brassard
Bratley multiplication might lead to it; and one for ISBN
0-13-023169-X should do so.
Dr J R Stockton
ws.com>, Sat, 27 Jun 2009 07:44:15, Johannes Baagoe <baa...@baagoe.com>
posted:
>Dr J R Stockton :
>
>> pressing for all 53 effective bits of the Number to be
>> evenly-distributed and random could be useful
>
>Some thoughts on that :
>
>The problem arises because the vast majority of PRNGs generate
>integers, not fractions between 0 (included) and 1 (excluded). And
>the ones most suitable for ECMAScript produce 32-bit integers
I disagree strongly. The ones most commonly used may be 32-bit; but
they are NOT suitable. There is no difficulty in programming 64-bit
Lehmer, and 64-bit code using the kiss32 approach, on any modern
machine; it just takes a little more work.
Analogy : I have in the past, on a primitive 8-bit machine with a 1 MHz
clock and 3125 bytes of RAM (and no real OS, bar a loader) programmed
three-channel 16-bit * 16-bit accumulative multiplication of, as I
recall, more than 256 products, with square rooting and output (granted,
it did have an 8-bit multiplier, soldered in by me).
VastRand, in <js-randm.htm>, does exact 64-bit Lehmer in JavaScript in
only a few lines of my code; it would be easier in ASM or Pascal (or, I
presume, on C/C++) on a 32-bit machine, especially if the flexibility
were omitted.
64-bit Lehmer, sagaciously converted to 53 bits, may not be the best
solution of its order of complexity; but it is surely better than what
the inferior browsers use for Math.random, when using Knuth-approved
constants.
Conversion from an integer of sufficient random bits to an IEEE Double
of 53-bit randomness is no real problem; one just inserts the best 53
bits into the mantissa, and normalises. VastRand does that, not
necessarily optimally as yet.
In Pascal/Delphi, where the ten-word Extended type exists with an eight-
byte mantissa, it's even easier; just prepend the correct sign and
exponent in a word, and call it an Extended.
>, while
>the best resolution one can attain in ECMASCript Numbers is 53 bits.
Following details read and largely agreed with.
>Let a and b be two "random" unsigned 32-bit integers obtained by some
>suitable method.
If they are obtained by successive calls of the same 32-bit method using
one 32-bit state, the second call adds no real randomness. One must
have sufficient state bits; and if they are in different generators the
generators should have co-prime lengths (except maybe if they are truly
independently seeded).
--
Dr J R Stockton
ws.com>, Fri, 26 Jun 2009 21:22:05, Johannes Baagoe <baa...@baagoe.com>
posted:
>Johannes Baagoe :
>
>>> You may, for instance, write things like
>
>>> r = new Random(new Date(), document.location.href,
>>> document.documentElement.clientWidth,
>>> document.documentElement.clientHeight);
>
>>> which should make it rather unlikely that two users ever generate
>>> the same sequence of numbers.
>
>Dr J R Stockton :
>
>> For test, it is desirable that it should be possible for two colluding
>> user (or a self-colluding one) to get the same sequence repeatedly.
>
>In that case, they should call the constructor with the same arguments,
>like new Random('foo', 'bar') or simply new Random('').
Indeed; but it is the values of the arguments that matters, not the
written form; 'new Date()' is not the same for long. I suggest that the
examples shown should include
r = new Random("Any arbitrary fixed string will give a fixed sequence")
and the text should say that the order of the arguments matters.
Also : if you instead have a single argument which is an array of
pseudo-arguments, that at worst adds two characters [] to each call, and
it enables the initialisation to be handled as a single entity.
var arr = ["Trondheim", "Boulogne", "Cockfosters", "Spaghetti"]
var r1 = new Random(arr)
var r2 = new Random(arr)
>My purpose with the given example is to show ways in which an
>application programmer could make it very unlikely that two users
>generate the same random numbers. If the hashing mechanism of seeds
>functions adequately (which should thoroughly analysed and tested),
>the biggest risk would be that they both load the same Web page at the
>exactly same time in windows of exactly the same size. And if that is
>not deemed safe enough, the programmer may add whatever other seeds she
>wants to decrease the likelihood even more, perhaps the User-Agent string
>or other results of browser sniffing or even cookies.
>
>> But the default should be that repeats are grossly improbable.
>
>There is the problem: I don't know of anything that is universally
>accessible to ECMAScript and more unforeseeable than the current
>time. It is rather improbable that two users initialise their random
>numbers at exactly the same millisecond, but it is not *grossly*
>improbable. Not to mention that I do not really trust all platforms
>to measure time with true millisecond granularity.
Windows XP sp3 IE7 JScript 5.7.18066 changes the value of +new Date() 64
times per second, jumping by 15 or 16 milliseconds. Ad I recall, Win98
1st Edn IE4 changed it 18.2 times a second. My page section
<URL:http://www.merlyn.demon.co.uk/js-dates.htm#Ress> refers, including
(on yellow) results for your browser.
Browser JavaScript cannot generate unique GUIDs without input by the
user (AIUI, it can open a window showing a site that shows fresh random
numbers, but it cannot see those numbers; it would have to ask for
copy'n'paste).
ISTM that we are mingling two * two = four distinct questions : the
combinations of
Generating random IEEE Doubles
Generating GUIDs
and
Doing those with ECMA 262-3 script
Considering how ECMA 262-N could be better
A scripted GUID generator has only time as a source of randomness; and
if other system information is used then there is a security leak, even
if only that an external attacker who can read the GUIDs may be able to
tell that two GUIDs probably came from the same system.
So I think it would be better not to consider implementing GUIDs in
browser JavaScript - Windows Script Host scripting is another matter,
since that can search the whole computer for entropy sources - or to do
that separately from considering what Math.random should be or could be
substituted by.
>>> seed += arg.getTimezoneOffset();
>> World-wide, it only adds about 5.3 bits of randomness; in a fixed
>> location, 0 or 1 bit.
>
>Not even that, since two users at the same location *at the same time*
>are unlikely to have different TimezoneOffsets. It could only happen
>if at least one of them decided to use a foreign time zone setting
>on her computer.
I meant 0 or 1 bit for a single long-term user. It could also happen if
a travelling user had retained the home setting.
>> For test purposes, it should be possible for people on different
>> systems in different places to get the same results.
>
>No problem at all, just don't use any of the mechanisms provided to
>make the outputs truly *random*. The shortest way to do that is to
>call the constructor with the empty string as sole argument, instead
>of no argument at all : new Random('') instead of new Random().
To be pedantic, new Random(0) is shorter and should serve!
Johannes Baagoe
>> The problem arises because the vast majority of PRNGs generate
>> integers, not fractions between 0 (included) and 1 (excluded). And
>> the ones most suitable for ECMAScript produce 32-bit integers
Dr J R Stockton :
> I disagree strongly. The ones most commonly used may be 32-bit;
> but they are NOT suitable.
Why not? I am talking about the number of bits they produce at a time,
not their internal state which is always larger in the case of good
PRNGs, and often *much* larger.
> There is no difficulty in programming 64-bit Lehmer, and 64-bit code
> using the kiss32 approach, on any modern machine; it just takes a
> little more work.
Quite, but why would one bother when some of the most suitable
operations - shifts, XORs, etc - happen to operate on 32 bits
in ECMAScript, and several 32-bit well-researched PRNGS which
are straightforward to code pass all known tests with flying
colours, whereas even the best LCG fails them miserably,
and *must* fail them, for well-known theoretical reasons ?
(http://www.pnas.org/content/61/1/25.full.pdf)
> VastRand, in <js-randm.htm>, does exact 64-bit Lehmer in JavaScript
> in only a few lines of my code; it would be easier in ASM or Pascal
> (or, I presume, on C/C++) on a 32-bit machine, especially if the
> flexibility were omitted.
Yes, I must confess that I haven't understood the code, not even to
the point of figuring out what the multiplier may be.
> 64-bit Lehmer, sagaciously converted to 53 bits, may not be the
> best solution of its order of complexity; but it is surely better
> than what the inferior browsers use for Math.random, when using
> Knuth-approved constants.
Knuth recommends C. E. Haynes's 6364136223846793005, I know of no other
proposal. *Nobody* does 2^64 LCGs, there is simply no point. It is
like investing lots of efforts to build a bigger and better Zeppelin.
>> Let a and b be two "random" unsigned 32-bit integers obtained by
>> some suitable method.
> If they are obtained by successive calls of the same 32-bit method
> using one 32-bit state, the second call adds no real randomness.
What do you mean by "real randomness" ? If the generator produces
successive numbers that are not correlated in any meaningful way,
as it should (and LCGs fail to do), what else would be needed ?
> One must have sufficient state bits;
Quite so, and 64 is probably not enough. The simplest generator I
*know* passes L'Ecuyers' BigCrunch battery of tests is his own MRG32k3a
which has a state of 192 bits. Marsaglia's KISS32, which I *suspect*
passes BigCruch as well (it passes Crunch, I haven't yet had the time
to test BigCrunch which is rather lengthy) has somewhat less than 127.
> and if they are in different generators the generators should have
> co-prime lengths
That is indeed an important consideration for combined generators,
which are possibly the simplest way to make good ones.
> (except maybe if they are truly independently seeded).
That seems to me to be a completely different issue, am I missing
something ?
--
Johannes
Johannes Baagoe
[Repeating the same sequence of "random" numbers for tests]
>> In that case, they should call the constructor with the same
>> arguments, like new Random('foo', 'bar') or simply new Random('').
Dr J R Stockton :
> Indeed; but it is the values of the arguments that matters, not the
> written form; 'new Date()' is not the same for long. I suggest that
> the examples shown should include
> r = new Random("Any arbitrary fixed string will give a fixed
> sequence")
OK.
> and the text should say that the order of the arguments matters.
OK, but it only matters if one wants repeatability. In the more usual
case where that is exactly what one wants of avoid, it doesn't.
> Also : if you instead have a single argument which is an array of
> pseudo-arguments, that at worst adds two characters [] to each call,
> and it enables the initialisation to be handled as a single entity.
> var arr = ["Trondheim", "Boulogne", "Cockfosters", "Spaghetti"]
> var r1 = new Random(arr) var r2 = new Random(arr)
Well, since ECMASCript provides a standard means (the "arguments"
pseudo-Array) of handling any number of arguments, I think I shall
stick with it. It saves the trouble of explaining and enforcing
a particular number and type of seeds.
> Browser JavaScript cannot generate unique GUIDs without input by the
> user (AIUI, it can open a window showing a site that shows fresh
> random numbers, but it cannot see those numbers; it would have to
> ask for copy'n'paste).
I'm not sure I understand what you mean, but my claim is that the user
*can* provide enough entropy without ever noticing it.
> ISTM that we are mingling two * two = four distinct questions :
> the combinations of
> Generating random IEEE Doubles Generating GUIDs
It is easy enough to generate something that looks like RFC 4122
Version 4 UUIDs even with Math.random :
uuid = function() {
/* Version 4 (truly-random or pseudo-random) UUID
Ex: 796483d9-f657-41c0-b4c2-9e0774d244fc
^
always 8, 9, a or b
means "Leach-Salz variant, rfc4122"
^
always 4
means "random or pseudo-random version"
Cf. http://www.faqs.org/rfcs/rfc4122.html */
function randomUInt32() {
return Math.floor(Math.pow(2, 32) * Math.random());
}
function normalHex(number) {
number >>>= 0;
var literal = number.toString(16);
while (literal.length < 8) {
literal = '0' + literal;
}
return literal;
}
var id = (normalHex(randomUInt32())
+ normalHex(randomUInt32()
& 0xffff0fff | 0x00004000) // type 4
+ normalHex(randomUInt32()
& 0x3fffffff | 0x80000000) // rfc 4122
+ normalHex(randomUInt32()));
return id.replace(/(.{8})(.{4})(.{4})(.{4})(.{12})/,
"$1-$2-$3-$4-$5");
}
The trouble is that using the standard Math.random, there is no
guarantee at all that the resulting ID is indeed U, not to mention
UU or GU.
On the other hand, using instead a Random object which is constructed
in the manner I suggested and further reSeeded in an event handler
that is attached, say, to mousemove and keypress events on the <body>,
chances are quite good that the ID is indeed, Universally Unique.
> Doing those with ECMA 262-3 script Considering how ECMA 262-N could
> be better
ECMA 262-N may or not be better, and it will surely be implemented in
widespread browsers some day, but just now, I need to have a way of
making reasonably sure unique identifiers. Not necessarily RFC 4122
UUIDs, but something with at least 120 bits of true randomness that
is actually reflected in the state of the generator.
> A scripted GUID generator has only time as a source of randomness;
User action is another one - even if the user is not aware of it.
> and if other system information is used then there is a security
> leak, even if only that an external attacker who can read the GUIDs
> may be able to tell that two GUIDs probably came from the same system.
I fail to see how that could be done in my scenario.
> So I think it would be better not to consider implementing GUIDs in
> browser JavaScript - Windows Script Host scripting is another matter,
> since that can search the whole computer for entropy sources -
Never heard of it ;)
> or to do that separately from considering what Math.random should
> be or could be substituted by.
Well, if an object can make sufficiently "random" numbers to make
UUIDs, it can surely also make random numbers to play with, can't it ?
--
Johannes
Johannes Baagoe
> One can presumably generate entropy by timing the intervals between
> keystrokes, after requesting the user to copy-type a text in mixed Welsh
> and Finnish while playing the Overture to Tannhauser on one speaker and
> some Stockhausen on the other, for distraction.
I think that won't be necessary.
http://baagoe.com/en/ES/testEvents.html
--
Johannes
Dr J R Stockton
ws.com>, Sat, 27 Jun 2009 23:37:48, Johannes Baagoe <baa...@baagoe.com>
posted:
>Johannes Baagoe :
>
>>> The problem arises because the vast majority of PRNGs generate
>>> integers, not fractions between 0 (included) and 1 (excluded). And
>>> the ones most suitable for ECMAScript produce 32-bit integers
>
>Dr J R Stockton :
>
>> I disagree strongly. The ones most commonly used may be 32-bit;
>> but they are NOT suitable.
>
>Why not? I am talking about the number of bits they produce at a time,
>not their internal state which is always larger in the case of good
>PRNGs, and often *much* larger.
OK; but it seems silly nowadays to have RNGs with many more states and
to get only 32-bit values.
>> There is no difficulty in programming 64-bit Lehmer, and 64-bit code
>> using the kiss32 approach, on any modern machine; it just takes a
>> little more work.
>
>Quite, but why would one bother when some of the most suitable
>operations - shifts, XORs, etc - happen to operate on 32 bits
>in ECMAScript, and several 32-bit well-researched PRNGS which
>are straightforward to code pass all known tests with flying
>colours, whereas even the best LCG fails them miserably,
>and *must* fail them, for well-known theoretical reasons ?
>(http://www.pnas.org/content/61/1/25.full.pdf)
You are still concentrating on systems suitable for generating GUIDs,
and possibly for crypto work. I am interested in getting an adequate
Math.random, preferably native to browsers, with the sort of performance
that a Double should give - equivalent to a fixed exponent, 53 random
mantissa bits, and a cycle length of at least 2^53, with a cycle length
over 2^64 being overkill.
An attempt to over-improve on Math.random by something that looks too
complicated may be self-defeating.
To get a non-native version, one must code in JavaScript, where logical
operations on over 32 bits are cumbersome. But one hopes that the
JavaScript engine is not written entirely in JavaScript. IIRC, the 8086
language has 16-bit shifts with carry, so that a 64-bit shift by 1
requires just 4 ops; and the 386 language may have 32-bit shifts; and
modern machines should be better than that.
>> VastRand, in <js-randm.htm>, does exact 64-bit Lehmer in JavaScript
>> in only a few lines of my code; it would be easier in ASM or Pascal
>> (or, I presume, on C/C++) on a 32-bit machine, especially if the
>> flexibility were omitted.
>
>Yes, I must confess that I haven't understood the code, not even to
>the point of figuring out what the multiplier may be.
Well, it comes from the control marked "Mult", which has a name of Mult,
and is read into Obj.Mult. The default value is from Knuth, as in your
next paragraph.
>> 64-bit Lehmer, sagaciously converted to 53 bits, may not be the
>> best solution of its order of complexity; but it is surely better
>> than what the inferior browsers use for Math.random, when using
>> Knuth-approved constants.
>
>Knuth recommends C. E. Haynes's 6364136223846793005, I know of no other
>proposal. *Nobody* does 2^64 LCGs, there is simply no point. It is
>like investing lots of efforts to build a bigger and better Zeppelin.
>
>>> Let a and b be two "random" unsigned 32-bit integers obtained by
>>> some suitable method.
>
>> If they are obtained by successive calls of the same 32-bit method
>> using one 32-bit state, the second call adds no real randomness.
>
>What do you mean by "real randomness" ? If the generator produces
>successive numbers that are not correlated in any meaningful way,
>as it should (and LCGs fail to do), what else would be needed ?
With a known algorithm, a 32-bit state and a cycle length of 2^32, the
result of the second call is knowable once the result of the first is
known.
>> One must have sufficient state bits;
>
>Quite so, and 64 is probably not enough. The simplest generator I
>*know* passes L'Ecuyers' BigCrunch battery of tests is his own MRG32k3a
>which has a state of 192 bits. Marsaglia's KISS32, which I *suspect*
>passes BigCruch as well (it passes Crunch, I haven't yet had the time
>to test BigCrunch which is rather lengthy) has somewhat less than 127.
You are, of course, aiming for something much better than Math.random
needs, provided that Math.random is not used for crypto or GUIDs.
In any case, Math.random cannot be truly suitable for those, since it
gives a Double and those will want integers or strings.
>> and if they are in different generators the generators should have
>> co-prime lengths
>
>That is indeed an important consideration for combined generators,
>which are possibly the simplest way to make good ones.
>
>> (except maybe if they are truly independently seeded).
>
>That seems to me to be a completely different issue, am I missing
>something ?
I thought that I saw a *possible* loophole to the co-prime requirement;
perhaps you know that it's not an actual loophole.
Dr J R Stockton
ws.com>, Sun, 28 Jun 2009 01:06:37, Johannes Baagoe <baa...@baagoe.com>
posted:
>Dr J R Stockton :
>> and the text should say that the order of the arguments matters.
>
>OK, but it only matters if one wants repeatability. In the more usual
>case where that is exactly what one wants of avoid, it doesn't.
Better wording would be like "the results depend on the order of the
arguments".
>> Also : if you instead have a single argument which is an array of
>> pseudo-arguments, that at worst adds two characters [] to each call,
>> and it enables the initialisation to be handled as a single entity.
>
>> var arr = ["Trondheim", "Boulogne", "Cockfosters", "Spaghetti"]
>> var r1 = new Random(arr) var r2 = new Random(arr)
>
>Well, since ECMASCript provides a standard means (the "arguments"
>pseudo-Array) of handling any number of arguments, I think I shall
>stick with it. It saves the trouble of explaining and enforcing
>a particular number and type of seeds.
That pseudo-Array is accessible within the routine; not outside it.
Above, r1 & r2 (insert missing semi-colon) hold seed-sets which can
conveniently be re-used, as may be required in testing.
>> Browser JavaScript cannot generate unique GUIDs without input by the
>> user (AIUI, it can open a window showing a site that shows fresh
>> random numbers, but it cannot see those numbers; it would have to
>> ask for copy'n'paste).
>
>I'm not sure I understand what you mean, but my claim is that the user
>*can* provide enough entropy without ever noticing it.
Agreed : the input can be unconscious (and not reproducible) or
conscious (in which case it may be bad, but can be reproduced).
>> and if other system information is used then there is a security
>> leak, even if only that an external attacker who can read the GUIDs
>> may be able to tell that two GUIDs probably came from the same system.
>
>I fail to see how that could be done in my scenario.
The worst kind of security leaks are those which are hardest to see.
ISTR that, during WWII, Enigma operators could often be recognised by
their Morse keying habits, which leaks information about troop
movements; and different operators would have different habits of
setting up their encoders sub-optimally, which helped the decoding
effort. Or something like that. The paper I originally cited shows
that identifying that two independent sessions are likely to be from the
same person can be of interest to the naughty.
>> So I think it would be better not to consider implementing GUIDs in
>> browser JavaScript - Windows Script Host scripting is another matter,
>> since that can search the whole computer for entropy sources -
>
>Never heard of it ;)
EXMAScript in Internet Explorer on the PC is implemented by an engine
quite distinct from MS IE itself. The same engine is used by WSH to run
what MS call JScript, using a different DOM. WSH can also run VBScript,
a sort of Visual Basic, in that DOM - and that is much more common and
used for systems programming. That description is substantially, but
not necessarily pedantically, correct. To see a newsgroup for it,
<http://groups.google.com/group/microsoft.public.scripting.vbscript/topi
cs>.
>> or to do that separately from considering what Math.random should
>> be or could be substituted by.
>
>Well, if an object can make sufficiently "random" numbers to make
>UUIDs, it can surely also make random numbers to play with, can't it ?
Undoubtedly. But if it is perceived as large and complicated, it may be
ignored.
Perhaps it would be well to use a Subject line "Math.random" only for
discussing the generation of random Numbers of sufficient quality for
most purposes, and one perhaps of "Generating GUIDs" for GUIDs.
My <js-randm.htm> now includes Rand64 which is VastCalc reduced in
flexibility to just implement
X = ((X * A) + C) modulo M
A = 0x5851F42D4C957F2D ; C = 1 ; M = 2^64
with modulo being done by using 64-bit arithmetic.
Johannes Baagoe
> Better wording would be like "the results depend on the order of the
> arguments".
Doesn't it go without saying ? The order of arguments is usually
significant - V-E Day is new Date(1945, 4, 8), not new Date(1945, 8, 4).
>>> Also : if you instead have a single argument which is an array of
>>> pseudo-arguments, that at worst adds two characters [] to each call,
>>> and it enables the initialisation to be handled as a single entity.
>>> var arr = ["Trondheim", "Boulogne", "Cockfosters", "Spaghetti"]
>>> var r1 = new Random(arr)
>>> var r2 = new Random(arr)
>> Well, since ECMASCript provides a standard means (the "arguments"
>> pseudo-Array) of handling any number of arguments, I think I shall
>> stick with it. It saves the trouble of explaining and enforcing a
>> particular number and type of seeds.
> That pseudo-Array is accessible within the routine; not outside it.
> Above, r1 & r2 (insert missing semi-colon) hold seed-sets which can
> conveniently be re-used, as may be required in testing.
You can use an array if you want, it works nicely :
js> var arr = ["Trondheim", "Boulogne", "Cockfosters", "Spaghetti"]
js> var r1 = new Random(arr)
js> var r2 = new Random(arr)
js> r1.random()
0.9478282313588788
js> r2.random()
0.9478282313588788
js> r1.random()
0.8453338182326062
js> r2.random()
0.8453338182326062
Since arr is neither a Date nor an Event, it is simply concatenated to the
empty String that constitutes the initial seed after an implicit conversion
by toString.
It is even portable across platforms :
15.4.4.2 Array.prototype.toString ( )
The result of calling this function is the same as if the built-in join
method were invoked for this object with no argument.
15.4.4.5 Array.prototype.join (separator)
The elements of the array are converted to strings, and these strings are
then concatenated, separated by occurrences of the separator. If no
separator is provided, a single comma is used as the separator.
So, it is exactly equivalent to
var r1 = new Random("Trondheim,Boulogne,Cockfosters,Spaghetti");
>> my claim is that the user *can* provide enough entropy without
>> ever noticing it.
> Agreed : the input can be unconscious (and not reproducible) or
> conscious (in which case it may be bad, but can be reproduced).
Hardly. It would require the user to turn back the date on the
computer, load the same web page at the same moment with respect to the
altered date, and reproduce exactly the same mouse and key events at the
same milliseconds up to the moment the UUID is generated. It cannot
be done by accident, which is what I am protecting against.
My Random objects are *not* supposed to ensure security in environments
that could justify TEMPEST techniques in order to capture and replay
events. That is a completely different game, which requite completely
different procedures.
>>> and if other system information is used then there is a security
>>> leak, even if only that an external attacker who can read the
>>> GUIDs may be able to tell that two GUIDs probably came from the
>>> same system.
>> I fail to see how that could be done in my scenario.
> The worst kind of security leaks are those which are hardest to see.
> ISTR that, during WWII, Enigma operators could often be recognised
> by their Morse keying habits, which leaks information about troop
> movements; [...]
There is no way one can reconstruct such information from UUIDs using my
Random objects in the recommended manner. On the other hand, as your
cited article points out, there *is* a marginal possibility that one
may extract some rather less valuable information from "random" strings
created by using Math.random.
>> Well, if an object can make sufficiently "random" numbers to make
>> UUIDs, it can surely also make random numbers to play with, can't
>> it ?
> Undoubtedly. But if it is perceived as large and complicated,
> it may be ignored.
I think it will, anyway, but mostly because it will be perceived as
pedantic nitpicking with no real issue. If one doesn't like the
existing Math.random, one may always write one's own, and replace
it by the simple line Math.random = mySuperiorRandomFunction;
The major browsers already provide 53 bits resolution which is more
than needed in the usual case where one multiplies by a smallish
integer and applies Math.floor. Their developers may possibly be
persuaded to use algorithms with more state and longer periods
than 32-bit LCGs by pointing out that such algorithms are not much
more complicated to implement, and that there is a consensus among
academics that they are better. Maybe one recently graduated fresh
addition to the team will insist on using what he wrote his thesis about.
But I rather think they won't care, perhaps with some justification.
> Perhaps it would be well to use a Subject line "Math.random" only
> for discussing the generation of random Numbers of sufficient quality
> for most purposes, and one perhaps of "Generating GUIDs" for GUIDs.
That sounds sensible, but which "most purposes" do you think of ?
For funny visual effects and virtual dice rolling, even the flawed
current implementations are quite adequate. They are not for serious
Monte-Carlo simulations, but nobody wants to do that in ECMAScript,
it is way too slow. The main *real* problem I see is that with their
insufficient state, obsolete algorithms and guessable seed, they
pose a (small) security risk when misused to make supposedly unique
strings or identifiers.
> My <js-randm.htm> now includes Rand64 which is VastCalc reduced in
> flexibility to just implement
>
> X = ((X * A) + C) modulo M
> A = 0x5851F42D4C957F2D ; C = 1 ; M = 2^64
>
> with modulo being done by using 64-bit arithmetic.
I admire the programming feat, but I still don't see what useful purpose
it serves. Apart from /l'art pour l'art/, which may be justification
enough :)
The latest version of Random is here : http://baagoe.com/en/ES/Random.js
--
Johannes
Johannes Baagoe
> it seems silly nowadays to have RNGs with many more states and to
> get only 32-bit values.
Again, the number of bits the generator outputs at a time has nothing
to do with the complexity of its state, the length of its period or
its general quality. Hardware LFSRs output just one bit a time, which
doesn't prevent them from having quite long periods and reasonable
statistical "randomness".
> You are still concentrating on systems suitable for generating GUIDs,
> and possibly for crypto work.
Not for cryptography, there are already plenty of usable libraries
for that.
But for UUIDs, yes, because I have the need, because it appears that
others have the need and resort naively to Math.random which cannot
possibly meet it, and because the challenge of constructing a sensible
entropy-gathering mechanism within the limitations of browser security
and at most a few hundred lines of ECMASCript code is fun.
Besides, it is also addresses the main *real* problem I see with
Math.random. People use it to make separator strings in POST request
over unencrypted http. They shouldn't. They should use a better
generator which much more state, and they should seed it with something
much less predictable than one single call to current time. That is
more easily said than done. I aim to make it easier to do.
> I am interested in getting an adequate Math.random, preferably native
> to browsers, with the sort of performance that a Double should give -
> equivalent to a fixed exponent, 53 random mantissa bits,
You already have that on Gecko, Spidermonkey et al., and I am told
it is even the case in IE.
> and a cycle length of at least 2^53, with a cycle length over 2^64
> being overkill.
Not if you want independence over successive outputs of various
lengths. If you use a PRNG to simulate typewriting monkeys and it
only has a cycle length of 2^64, chances are that some even rather
short letter sequences will *never* come out, and others be grossly
overrepresented, because the numbers are simply not "random" enough,
their succession present systematic biases. As an extreme case, with
full Lehmer including the LSBs, you will never get two successive
odd numbers, nor two even ones.
It doesn't matter if you are just playing games. It matters very
much if you are simulating the sorts of successive incidents that may
happen on an aircraft or a nuclear plant. But then, one hardly does
that kind of things in browsers, except as grossly simplified toys
for educational purposes. Or even in ECMAScript outside browsers -
it is inherently a slow language.
It might also matter, though, if your script generates 32 hexadecimal
digits that look like a UUID and is supposed to be a UUID. Because
if your generator has a systematic bias in its successive outputs,
it is not true at all that 122 of the supposed UUID's bits are random,
as the design of UUIDs assumes them to be. The true number may be 64
or less, which makes accidental collisions much more likely. If every
person on Earth were to generate such a "UUID", chances are that two
of them would share the same. How worrying that is depends on what
it is used for, but it is exactly what UUIDs were supposed to prevent.
> An attempt to over-improve on Math.random by something that looks
> too complicated may be self-defeating.
With all due respect, I am not sure your VastRand looks simple,
and I can't see what it improves.
>> What do you mean by "real randomness" ? If the generator produces
>> successive numbers that are not correlated in any meaningful way,
>> as it should (and LCGs fail to do), what else would be needed ?
> With a known algorithm, a 32-bit state and a cycle length of 2^32,
> the result of the second call is knowable once the result of the
> first is known.
That would make it unusable for cryptography, not necessarily for
simulations. The second number might be knowable, but still not be
correlated to the first, or indeed any previous, in any mathematically
significant sense. As an extreme example, the algorithm could be a
lookup in a known, massive table of completely random 32-bit numbers.
It just requires 16 gigabytes of read-only memory...
On the other hand, if that massive table were *not* publicly known,
you could have full knowledge of the state (the 32-bit counter that
serves as an index in the table), all the previous outputs provided
there haven't yet been 2^32 of them, and still lack the slightest
clue as to what the next will be. This is the basis of the strongest
crypto system of all, the Vernam cipher or one-time pad.
You appear to assume that all PRNGs work like Lehmer's algorithm :
each number is a simple function of the previous number, and nothing
else. That is not at all the case for stronger generators. They
have a lot more state than they output at each step, and each output
depends on all that state, which is updated in other ways than what is
exposed by the output. It is not only a requirement for cryptography,
but also for good statistical properties of the output.
> You are, of course, aiming for something much better than Math.random
> needs, provided that Math.random is not used for crypto or GUIDs.
I also aim for better statistical behaviour, which can be achieved
without the entropy mechanisms necessary for UUIDs. But I am not sure
it is really important in the typical uses of ECMAScript.
> In any case, Math.random cannot be truly suitable for those, since
> it gives a Double and those will want integers or strings.
It is quite easy to make random integers or strings from random fractions
in [0..1), that is the main point of such fractions.
--
Johannes
Dr J R Stockton
ws.com>, Mon, 29 Jun 2009 08:25:07, Johannes Baagoe <baa...@baagoe.com>
posted:
>Dr J R Stockton :
>
>> it seems silly nowadays to have RNGs with many more states and to
>> get only 32-bit values.
>
>Again, the number of bits the generator outputs at a time has nothing
>to do with the complexity of its state, the length of its period or
>its general quality.
The number of bits delivered at once is independent of the generator
mechanism. It seems incongruous, though, to make a mechanism that good
but to deliver the results only in chunks smaller than are likely to be
wanted.
> Hardware LFSRs output just one bit a time, which
>doesn't prevent them from having quite long periods and reasonable
>statistical "randomness".
I have to hand a printed copy of an October 1960 paper by PHR
Scholefield, with whom I later briefly worked, on LFSR theory. His
application required a serial data stream with a period of about 2.5
seconds; I don't recall the bit rate. AFAIR, pseudo-randomness was not
a requirement as such; but the bit stream needed to have one of the
properties of a pseudo-random stream.
>You already have that on Gecko, Spidermonkey et al., and I am told
>it is even the case in IE.
I, and I suspect many others, do not know which browsers use which
engines - presumably Wikipedia does. IMHO, it should, for common
browsers, be in the FAQ. Math.random in IE seems to be good (giving all
values less than 1.0 of N*2^-53), but cosmetically imperfect (Giving
other values too).
>> An attempt to over-improve on Math.random by something that looks
>> too complicated may be self-defeating.
>
>With all due respect, I am not sure your VastRand looks simple,
>and I can't see what it improves.
VastRand has the extra complexity of handling all Lehmer-type
expressions, and of coaxing 53 bits into a Double, and of using
JavaScript. Rand64 could be implemented in ASM or C in 16, 32, or 64
bit machines, and would then look a lot simpler.
>> In any case, Math.random cannot be truly suitable for those, since
>> it gives a Double and those will want integers or strings.
>
>It is quite easy to make random integers or strings from random fractions
>in [0..1), that is the main point of such fractions.
It's not difficult; Math.random is a sufficient primitive from which
other forms can be obtained. But the same underlying engine, whatever
it may be, could also drive a String.random(length[, type]).
Dr J R Stockton
ws.com>, Sun, 28 Jun 2009 23:42:12, Johannes Baagoe <baa...@baagoe.com>
posted:
>Dr J R Stockton :
>
>> Better wording would be like "the results depend on the order of the
>> arguments".
>
>Doesn't it go without saying ? The order of arguments is usually
>significant - V-E Day is new Date(1945, 4, 8), not new Date(1945, 8, 4).
But this is a rather peculiar routine, in that one gets a good result
for the arguments in any order - it's just not the same good result.
There seems to be some risk of a user memorising a set of arguments but
failing to remember their order.
>>> my claim is that the user *can* provide enough entropy without
>>> ever noticing it.
>
>> Agreed : the input can be unconscious (and not reproducible) or
>> conscious (in which case it may be bad, but can be reproduced).
>
>Hardly. It would require the user to turn back the date on the
>computer, load the same web page at the same moment with respect to the
>altered date, and reproduce exactly the same mouse and key events at the
>same milliseconds up to the moment the UUID is generated. It cannot
>be done by accident, which is what I am protecting against.
We are interpreting "conscious" differently. To me, normal computer
user is conscious of the sequence of keys pressed, but not of their
exact rhythm; a pianist is different.
>My Random objects are *not* supposed to ensure security in environments
>that could justify TEMPEST techniques in order to capture and replay
>events. That is a completely different game, which requite completely
>different procedures.
"Not for TEMPEST" could go in the comment.
>The major browsers already provide 53 bits resolution which is more
>than needed in the usual case where one multiplies by a smallish
>integer and applies Math.floor. Their developers may possibly be
>persuaded to use algorithms with more state and longer periods
>than 32-bit LCGs by pointing out that such algorithms are not much
>more complicated to implement, and that there is a consensus among
>academics that they are better. Maybe one recently graduated fresh
>addition to the team will insist on using what he wrote his thesis about.
>But I rather think they won't care, perhaps with some justification.
>
>> Perhaps it would be well to use a Subject line "Math.random" only
>> for discussing the generation of random Numbers of sufficient quality
>> for most purposes, and one perhaps of "Generating GUIDs" for GUIDs.
>
>That sounds sensible, but which "most purposes" do you think of ?
All requiring substantially less quality than GUIDS, maybe; and down to
the lowest level of need, would fit under that Subject; though not
necessarily in the present thread.
>For funny visual effects and virtual dice rolling, even the flawed
>current implementations are quite adequate. They are not for serious
>Monte-Carlo simulations, but nobody wants to do that in ECMAScript,
>it is way too slow.
OTOH, ECMAscript is a way of publishing to anyone with a script-enabled
browser a Monte-Carlo engine to be given a user-defined function (I do
likewise with a Date-of-Easter testing engine); and one can run many
more ECMAscript statements in an evening on a current PC than the number
of Fortran statements that my friends used to run in an evening on a
University mainframe (IIRC, 32 k of 24-bit RAM) when emulating
universes.
For research-grade Monte Carlo, I can agree that something better than a
random which cycles in an obscure order through all values less than 1.0
of N*2^-53 ill be needed. But that quality is what might reasonably be
expected from the ECMA spec of Math.random and should be adequate to
support teaching-grade Monte Carlo exercises, whereas what some current
browsers give is a million times worse.
> The main *real* problem I see is that with their
>insufficient state, obsolete algorithms and guessable seed, they
>pose a (small) security risk when misused to make supposedly unique
>strings or identifiers.
And I have not previously seen that problem, because AFAIR you are the
first person who I have read referring to using browser JavaScript for
GUID generation.