Fixing JavaScript's Broken Random Number Generator (hackaday.com) 136
szczys writes: It is surprising to learn how broken the JavaScript Random Number Generator has been for the past six years. The problem is compounded by the fact that Node.js uses the same broken Math.random() module. Learning about why this is broken is interesting, but perhaps even more interesting is how the bad code got there in the first place. It seems that a forum thread from way back in 1999 shared two versions of the code. If you read to the end of the thread you got the working version, if you didn't make it that far (perhaps the case with JavaScript devs) you got the bad version of the code whose fix is just now being rolled out.
Obligatory XKCD (Score:5, Informative)
https://xkcd.com/221/ [xkcd.com]
Re:Obligatory XKCD (Score:5, Funny)
Re: (Score:2)
he's a fucking cartoonist; who cares what he thinks? enjoy the fucking cartoons
Re: (Score:1)
Re: both comic authors, a famous quote, "Who would have thought creative types had mental issues?"
Javascript? lol! (Score:4, Insightful)
Is there anything about Javascript that isn't shitty and broken? Can we please just take this language behind the barn, shoot it and move on with our lives?
Re:Javascript? lol! (Score:5, Insightful)
Re: (Score:1)
You say that like it's a bad thing.
Re: (Score:2)
It's support for functional programming?
Re: (Score:1)
And how many of the Javascript monkeys actually understand functional programming? A handful?
Re: (Score:1)
Well, if your only requirement for functional programming is that functions are objects, why not Ruby?
Generally when I think of functional programming, I think of currying and lazy evaluation. Ruby and Javascript both have neither, but at least Ruby gives you a sane type system and sane scoping rules for anonymous functions. I haven't learned Python yet, but I understand it's in a similar place.
Well, I should qualify that. I had a hacking session with the person who taught me how to do Javascript correct
Re: (Score:2)
Re: (Score:1)
HTML5 basically IS Javascript, ya fuckin' dummy. The only thing that's going to replace Javascript is a newer version of Javascript i.e. ECMA6. Javascript, like C++, will just keep getting updated, and so stay relevant forever while the Perls and Rubys will come and Go.
Re: (Score:3)
A point of information:
Adobe is killing the Flash brand, but ActionScript lives on. So Flash is not really being killed.
Re: (Score:2)
Re: (Score:1)
Amen! It's okay as a light-duty "glue" language, but it's now being used for OS-like features with huge underlying libraries. It's not meant as a systems language. It's outdone Emacs in the over-doing-it department: A tinker-er's paradise, but not practical in the staff churn of everybody business.
And it has a lousy OOP and inheritance model, forcing one to use annoying and unnatural anonymous functions all over the place.
The browser stack is
Re: (Score:1)
The impressive thing is that you can control the keyboard backlight of a gaming PC with only 20 lines of Javascript. But you need to install about 20 Megabytes of device driver code, USB programming, G++ and Python.
Re: Javascript? lol! (Score:3)
That's like saying, "It's amazing that I can control the ceiling fan in my living room with a $2 light switch, all I had to do was spend $300k building the house first."
Re: (Score:2)
In my line work, the coder maintenance effort is usually more of a factor than client-side-browser speed/memory, or even server side for that matter. Whether (good) OOP is inherently more resource intensive than anonymous function prototypes remains to be solidly proven. It may depend on coding style.
As far "simpler to parse", if that were the main factor, we'd all be using Lisp. Being human-friendly and being machine-friendly are not necessarily the same thing. Machines are generally cheaper than humans (code maintainers) such that economics often favors being human-friendly over machine-friendly (speed/memory). What I personally like is another matter; I'm paid to make my employer's org more efficient. (The database is usually the bottleneck, not the application, I would note.)
In short, I question how you are weighing the factors being compared. I agree that different niches emphasize different factors, but in general an application language (or usage) should favor humans over machines when you look at the total economics involved. Unfortunately, JavaScript is often being used for application development AND systems software (OS-like services and low-level libraries). One-language-fits-all is a tall order, and probably in impossible order if we want to optimize the language design for its actual usage patterns.
I shared this same opinion, but have found protipical inheritance (accompanied with static typing ala closure compiler) to be quite nice. In fact, it has made me more aware of how/when OOP constructs can provid actual value above a more functional approach (hint: it's not as often as you may think)
Re: (Score:2)
Do you have some realistic examples?
Also, approach-ability by "random" developers sometimes trumps something that's more flexible but requires more experience or a learning curve. Staff changes such that we often have to target "middle brow" abstractions.
Sure, since you asked... I find that functional programming is better for processing "data," while OOP is better for processing/handling "events." I also think there is a line that can be crossed where functional programming simply becomes a clever form of obfuscation, but overall, there is a lot of value in simple, repeatable, and easy to use constructs, which may be composed together to express the "idea" behind the code in fewer lines. I would say that readability and maintainability ranks #1 in my book
Re: (Score:1)
Underscorejs seems to be reinventing SQL with dots: rows = dataSource.join(...).select(...).where(...).orderby(...);
Re:Javascript? lol! (Score:5, Insightful)
We are using JavaScript for performance critical code and I can confirm that it is the most buggiest, immature technology by far that I have ever seen in my 30 years old carrier. Every second month there is a new browser version for each browser, each with a different set of new critical bugs. We even find JIT compiler bugs regularly!
I simply do not understand why they do not take the free, open source, mature, very fast Java virtual machine, and let the browsers run Java bytecode directly, and let software engineers chose any programming language which best suits their task.
Re: (Score:2)
That's kinda what asm.js is. You can use any language you like as long as it compiles down to asm.js, which is stable, well debugged and fast (in theory at least).
Java is a bit heavy for web apps, and the security model isn't really suitable. Plus, asm.js is much more open and less likely to attract lawsuits.
Re: (Score:2)
We tested asm.js a year ago, it is not particularly fast even within the JavaScript universe (i.e. it was much slower than other JavaScript solutions we have found). And of course browser variants/versions (even small versions!) seriously differ - but that would not be a showstopper, as that can be said about anything in JavaScipt.
Of course they can slowly fix everything in JavaScript, make it more performant, and eventually reach the current level of the Java virtual machine - in about 10-15 years. This
Re: (Score:2)
We are using JavaScript for performance critical code and I can confirm that it is the most buggiest, immature technology by far that I have ever seen in my 30 years old carrier. Every second month there is a new browser version for each browser, each with a different set of new critical bugs. We even find JIT compiler bugs regularly!
I simply do not understand why they do not take the free, open source, mature, very fast Java virtual machine, and let the browsers run Java bytecode directly, and let software engineers chose any programming language which best suits their task.
Not to come across sounding like "you're doing it wrong," but I found I had a fairly similar experience when I needed to produce some solid javascript (rather intensive real-time media/graphics in mobile web). It wasn't until I realized I was trying to hammer a screw (applying my knowledge of c/c++/Java/C# to my JavaScript code) that my experiences turned around. In short, a relatively small amount of your code should be exposed to browser specific bugs, to the point where most of it can be tested without a
Re:Javascript? lol! [server-bound] (Score:1)
The more of an application you do server-side, in a language of your choosing, the less you have to depend on browser JavaScript (and other browser issues). But, it takes experience to do that well. One cannot think in "desktop mode" anymore, and toss much of their desktop UI design experience. It's bummer, but it's what the Web Stack forces on us if we want to avoid JavaScript and client-versioning headaches.
Re:Javascript? lol! (Score:5, Insightful)
What is the difference between bytecode and obfuscated or simply just complex JavaScript? Do you verify all or even 1% of JavaScript your browser runs? Bytecode can be disassembled into its source language if it is not obfuscated. But JavaScript can be obfuscated as well. Not to mention automatically generated JavaScript, cross compiled from another language. I do not see a difference. Why do you want to verify either bytecode or JavaScript? Bytecode runners wouldn't have more permissions then the JavaScript just in time compilers already have. We rely on the sandboxing in both cases.
Re: (Score:2)
Is there anything about Javascript that isn't shitty and broken? Can we please just take this language behind the barn, shoot it and move on with our lives?
As terrible as the language called "Javascript" may be, this isn't an example of that. It's an example of a poor implementation of one standard library function in one implementation of the language. It seems the problem was fairly easily fixed. Javascript code doesn't need to be changed to use the better PRNG so it would be very foolish to abandon Javascript just because of the past poor PRNG.
Wait, what? (Score:5, Insightful)
What? Does the ECMA spec dictate the exact implementation of the RNG? If not, then it's not JavaScript that's broken, but the implementation(s) in question. Calling it "JavaScript's Broken RNG" is nonsense unless the language spec mandated or mandates a broken RNG.
Re:Wait, what? (Score:5, Informative)
Blame slashdot. TFA's made it pretty clear it's the V8 engine that had been broken for six years.
Re: (Score:2, Informative)
TFA isn't that good either though. It spends the first half of the page with patronising pedantry about how numbers cannot be random, which is a waste of time since ‘random’ can mean ‘randomly chosen’. Here, I'll have a go at summarising the situation.
V8's random number generator is pretty bad. It's a thing called MWC1616, which basically means it's two multiply with carry random number generators, of whose outputs the lower 16-bits are concatenated to form a single 32-bit number. MW
Re:Wait, what? (Score:5, Insightful)
Yeah, seems rather convenient that the part in the Hackaday title and in the article that mentions that this was in Google's V8 engine was left out.
Plus I couldn't help but laugh at the comment to the commit that put in this shitty PRNG:
This is great, I had talked to Ivan once about it before. It's good that we avoid system random for a few reasons, including thread safety / lock holding / etc.
I know nothing of the implementation though, I would have gone with mersenne twister since it is what everyone else uses (python, ruby, etc)
Sounds like some real quality code reviewing there, bub. *golf clap*
Re: (Score:1)
Re: (Score:2)
Yeah, might as well have had no code review at all.
Re:Wait, what? (Score:5, Interesting)
Well at least knowing that the guy who wrote this shitty PRNG is a designer of Google's Dart gives you one more reason to avoid it the plague.
Re: (Score:3)
Actually, you just embarrassed yourself. The function spec says that the numbers produced don't have to be cryptographically secure, so his implementation is absolutely fine. It produces pseudo random numbers quickly. If you want secure the docs say use something else.
This fix is more like fixing the stupidity of programmers who, like you, didn't RTFM and used this function for security related tasks.
Re: (Score:2)
Teah I'm so embarrassed because some guy wrote a shit PRNG. Oh how will I ever live with myself. /s
Re: (Score:3)
to assign per-session tokens to users. They thought they were fine, because the chances of a collision were vanishingly small if the PRNG was doing its job.
How stupid do you have to be to use any value as a "unique" token without verifying that it is not currently in use? Even truly random numbers will still have the rare collision. In other words, "vanishingly small" != unique.
Re: (Score:2)
Yeah, seems one would have chosen a UUID generator not a PRNG.
Re: (Score:2)
Sadly this is industry standard practice. For example, Microsoft GUIDs are used extensively and are just randomly generated numbers. At least they are usually 64+ bits, but some are still 32 bit.
The problem is that it works and collisions are so rare they don't become a cost for the developers. The fix would require creating infrastructure to hand out GUIDs, and it's always hard to justify spending time and money developing a secure system to do that (GUIDs must not be predictable) when there is no visible
Re: (Score:3)
GUIDs are 128 bits, of which 122 bits may be either pseudo random or made up using such input as MAC address and time.
Re: (Score:2)
There are plenty of reasons why you might not verify a particular token is in use. For instance, we have a system which is highly distributed for which checking token uniqueness would be very costly (both to implement and at runtime). It uses version 4 UUIDs as an identifier (122 bit random), which is about 5.3x10^36 possible combinations.
You'd have to generate one of these every millisecond for tens of millions of years to even get to even a 50% chance of picking the same random UUID twice, given a good RN
Re: (Score:2)
An additional benefit is that is a token that was generated in the area served by 'A' suddenly appears in an area served by 'B', you may want to code in c
Obviously (Score:3)
What did you expect from some random coder?
Re: (Score:2)
No random coder. A guy employed by Google and now working on Dart. One can only hope that he hasn't touched anything else related to PRNGs, cryptography, etc. since he wrote this broken code 7 years ago.
Re:Obviously (Score:5, Interesting)
He was using node.js (which using V8 Javascript engine)
And he was using it for some security related function (in this case generating id's of sessions).
Maybe he should have been using a cryptographically strong pseudo-random generator:
https://nodejs.org/api/crypto.... [nodejs.org]
Why did they need to 'fix' V8 Math.random () function which everyone knows is not meant for such things ? It even says so in for example the Mozilla documentation (the organisation that created Javascript in the first place):
"Note: Math.random() does not provide cryptographically secure random numbers. Do not use them for anything related to security."
https://developer.mozilla.org/... [mozilla.org]
This makes no sense to me.
Re: (Score:2)
You're confusing two different people from the article. The person who checked-in the broken PRNG code was a Google employee named Kasper Lund. The person who found the bug when they were using the class to generate session ids was Mike Malone.
Re: (Score:2)
And to clarify, my original post was about the Google employee who broke V8's random number generator.
Re: (Score:2)
One can only hope that he hasn't touched anything else related to PRNGs, cryptography, etc. since he wrote this broken code 7 years ago.
I'm not sure why you mentioned "cryptography, etc.", since Math.random() should never be used for cryptography or other security purposes. It's entirely reasonable to believe that if it were supposed to be used for those purposes that the Google engineer would have picked something known to be good for those purposes.
V8 == the only JavaScript engine? (Score:5, Insightful)
Because JavaScript doesn't specify the RNG implementation details, and V8 is the only engine mentioned ass affected in the article ...
Obligatory v.Neumann: SIN ! (Score:3)
That said, even JvN understood the usefulness of pseudo random numbers for things like Monte Carlo simulations. I believe he favored Linear Congurential Generators (Knuth liked 69069 as a multiplicand on a 32-bit word).
Re:It was noticed at least 3 years ago, possibly m (Score:5, Informative)
The article doesn't claim it's new information. The article is about the fact that Google has finally fixed it and the backstory behind the broken code.
And StackOverflow didn't even exist! (Score:2)
Oh yeah? (Score:4, Funny)
Well if you don't like RNG you should try WHM, BML or THF.
More code audits needed? (Score:3)
So now that we know it's Kasper Lund who broke this within the V8 engine, is someone going to do a code audit of all checkins he's done within the Dart SDK to make sure he hasn't broken anything related to PRNGs and cryptography?
Re:More code audits needed? (Score:4, Funny)
What would be the point of wasting time fixing something that nobody uses?
Re: (Score:2)
The spec [ecma-international.org] only says "approximately uniform". The code generated approximately uniform numbers, for some value of approximate, so it wasn't broken per se.
Re: (Score:3)
Sure, it's only broken when actually used.
Re: (Score:2)
No, only broken when used out of specification. RNGs have a lot of uses, not all of them related to cryptography. Generators suited for cryptography could be extremely unsuitable for other uses. Take for example the ISO-C random function. It is specified for reproducibility. There is even a non-mandatory recommendation to because they saw a use for a generator that behaved the same way on a variety of systems, for example when implementing sprite behavior in games.
If you implement cryptography and uses a RNG that isn't specified for it then it is your code that is broken. It's like using a CRC designed for sequential data when communicating over a framed protocol like RS485. It isn't the one implementing the CRC that is to blame, it is the one who applied it incorrectly.
..Quoting AC rated at 0 as the only reasonable response to this thread.. (Try 2 haha, oops)
Happened, not designed. (Score:4, Insightful)
Re: (Score:1)
You are confusing PHP with Javascript.
JS has a very powerful and sane subset.
PHP does not.
Re: (Score:2)
You are confusing PHP with Javascript.
I am aware of both PHP and JavaScript. I said nothing about PHP. My opinion about Javascript is my opinion about Javascript, not PHP. I do not confuse the two.
.
JavaScript happened, it was not designed.
The damned librals everywhere! (Score:2)
We should carve out an exception for the sincerely held religious beliefs to serve or
That's why JS is untyped then... (Score:2)
That's why JS is untyped, it adds much needed randomness.
Seeds are important. (Score:2)
Since seed values are important, why not just use the comments in slashdot - some of them are REALLY random.
Or use the latest presidential campaign statements - can't get much more random than that (for some definitions of random).
Fixing *Google's* random number generator (Score:2)
This is fixing Google's random number generator; Firefox, Safari and MS Edge (if not old IE versions) have never had this issue, it is specific to Google's JS implementation.
Random functions... (Score:4, Informative)
The mighty Knuth (Score:1)
Re: (Score:2)
Every browser since IE10 has had secure RNG (Score:4, Informative)
See this table for support: http://caniuse.com/#feat=getra... [caniuse.com]
It's great that they're finally improving Math.random(), but node.js should've had crypto.getRandomValues() from the start.
Ignorance is bliss (Score:1)
Given there is no way to seed math.random assumptions about collisions are meritless and storage of random identifiers in databases serves no useful purpose other than causing needless index fragmentation.
In short TFA while having a point about quality of a specific implementation of math.random() is bitching about things that could still be failures even if math.random() represented an ideal PRNG.
Also hardware random number generators are what you get for free when you sleep through your 101 class on noise
Doesn't this just affect Chrome? (Score:1)
Seems like this should just affect Chrome / Chromium and anything derived from those, as it's an implementation issue in the V8 JavaScript interpreter. (V8 is the name for the engine in Chrome.)
That is, it's not a JavaScript / ECMAScript bug in the standard (as implied by the headline), but rather a bug in one company's implementation.
Compare/contrast with the comically bad PRNG enshrined in the C standard itself:
static unsigned long int next = 1; // RAND_MAX assumed to be 32767
int rand(void)
{
next = n
Why didn't they optimize the new generator? (Score:2)
The new 128-bit generator is shown as this piece of code, using a pair of 64-bit state variables:
uint64_t state0 = 1;
uint64_t state1 = 2;
uint64_t xorshift128plus() {
uint64_t s1 = state0;
uint64_t s0 = state1;
state0 = s0;
s1 ^= s1 > 17;
s1 ^= s0;
s1 ^= s0 >> 26;
state1 = s1;
}
The absolute minimum latency of that code is 8 clock cycles, assuming that the two initial loads happen at the same time and tha
Re: (Score:2)
Are we really still in an era where we care about counting individual clock cycles, outside of an embedded context?
Huh? (Score:2)
I thought it was axiomatic that the inbuilt default PRNG was good for writing scissors/paper/stone when doing programming 101 but not for anything more serious.
In any language.