Slashdot Mirror

← Back to Stories (view on slashdot.org)

Fixing JavaScript's Broken Random Number Generator (hackaday.com)

Posted by samzenpus on from the the-fix-is-in dept.

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.

28 of 136 comments (clear)

  1. Obligatory XKCD by psergiu · · Score: 4, Informative

    https://xkcd.com/221/

    --
    1% APY, No fees, Online Bank https://captl1.co/2uIErYq Don't let your $$$ sit in a no-interest acct.
    1. Re:Obligatory XKCD by antimatter_16 · · Score: 5, Funny

      Or dilbert. http://dilbert.com/strip/2001-...

  2. Javascript? lol! by Anonymous Coward · · 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?

    1. Re:Javascript? lol! by ickleberry · · Score: 4, Insightful

      We could but all the startup hipsters would be so disappointed

    2. Re:Javascript? lol! by dshk · · Score: 4, 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.

    3. Re: Javascript? lol! by radiumsoup · · Score: 2

      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."

    4. Re: Javascript? lol! by MachineShedFred · · Score: 2

      A point of information:

      Adobe is killing the Flash brand, but ActionScript lives on. So Flash is not really being killed.

      --
      Slashdot still doesnâ(TM)t support Unicode after it was added to the HTML standard in 1997.
    5. Re:Javascript? lol! by dshk · · Score: 4, 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.

  3. Wait, what? by tibit · · 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.

    --
    A successful API design takes a mixture of software design and pedagogy.
    1. Re:Wait, what? by Anonymous Coward · · Score: 5, Informative

      Blame slashdot. TFA's made it pretty clear it's the V8 engine that had been broken for six years.

    2. Re:Wait, what? by Lunix+Nutcase · · 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*

    3. Re:Wait, what? by Lunix+Nutcase · · Score: 4, 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.

    4. Re:Wait, what? by BarbaraHudson · · Score: 2
      The situation in example given in the article could have been avoided entirely if it had been done right:

      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.

      --
      "Transparent" is a shit show that trades on every stereotype going. A man in drag is NOT a transsexual.
    5. Re:Wait, what? by Anonymous Coward · · 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. MWC generators aren't particularly good; they're related to linear congruential generators. But sticking two together could improve the cycle length, as long as the cycles are different. But due to the fact that MWC1616 sticks two 16-bits numbers together, the most significant bits just have the short cycle length. That's a problem, because in many random number applications the most significant bits tend to be more... eh... significant. Examples include the use of multiply-and-floor to roll dice (d = floor(rnd * 6)) or when the number gets used straight-up in physical simulations. So the effective cycle of MWC1616 is pretty short.

      There's an interesting lesson here, by the way, as the original author of the algorithm could have known about this problem if he had thought his method of combining the generators through, but ‘the algorithm passed all tests’ so it was good. I too often see code that passes unit-tests but that's nevertheless deeply flawed, so please, people, if you've only got time to either write unit tests or think, then please, please think - it's more important. Later, the author did think about it, and did realise his mistake and published a different version, but the original got published in various places, including on Wikipedia. And hey, it's on Wikipedia, and it has a cited source, so it must be good, right?

      The fact that MWC1616 was an odd choice was picked up during code review. The reviewer noted the odd choice saying ‘I would have gone with mersenne twister’ but the algorithm wasn't changed or investigated. The warning was raised, but not acted upon. Another important lesson: if you have code review, use the results, otherwise it's pointless busywork.

      So, did the V8 random number generator get replaced by the Mersenne twister? No, they opted to use XorShift128+, presumably because it's slightly faster and uses a lot less memory, while still passing common randomness tests. But I have my reservations about this decision. The Mersenne twister is fast enough, well-understood, hard to misuse and has a long cycle-length. XorShift is by the same author as MWC1616 and relatively unknown, so there's (in my view) a bigger chance that it contains some bigger as-yet undiscovered hidden flaw.

    6. Re:Wait, what? by AmiMoJo · · Score: 2

      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.

      --
      const int one = 65536; (Silvermoon, Texture.cs)
      SJW, n: "Someone I don't like, and by the way I'm a fuckwit" - AC
    7. Re:Wait, what? by fnj · · Score: 2

      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.

      GUIDs are 128 bits, of which 122 bits may be either pseudo random or made up using such input as MAC address and time.

  4. Obviously by penguinoid · · Score: 2

    What did you expect from some random coder?

    --
    Don't waste your vote! Vote for whoever you want, unless you live in a swing state it won't matter anyways
    1. Re:Obviously by Lennie · · 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....

      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/...

      This makes no sense to me.

      --
      New things are always on the horizon
  5. V8 == the only JavaScript engine? by BitZtream · · Score: 4, Insightful

    Because JavaScript doesn't specify the RNG implementation details, and V8 is the only engine mentioned ass affected in the article ...

    --
    Persistent Volume manager for Kubernetes - https://github.com/dwimsey/openshift-pvmanager
  6. Obligatory v.Neumann: SIN ! by redelm · · Score: 2

    "Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number - there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method." John von Neumann

    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).

  7. Re:It was noticed at least 3 years ago, possibly m by Lunix+Nutcase · · Score: 4, 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.

  8. Oh yeah? by U2xhc2hkb3QgU3Vja3M · · Score: 3, Funny

    Well if you don't like RNG you should try WHM, BML or THF.

  9. More code audits needed? by Lunix+Nutcase · · Score: 2

    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?

    1. Re:More code audits needed? by U2xhc2hkb3QgU3Vja3M · · Score: 3, Funny

      What would be the point of wasting time fixing something that nobody uses?

    2. Re:More code audits needed? by Lunix+Nutcase · · Score: 2

      Sure, it's only broken when actually used.

  10. Happened, not designed. by QuietLagoon · · Score: 3, Insightful

    JavaScript was not designed by any regular use of that word. JavaScript happened.

  11. Random functions... by Kazoo+the+Clown · · Score: 3, Informative

    I've seen some pretty bad "random number" generators in my time. In one case, it was implemented by a pointer that would walk through the processes memory space and use whatever it found as-is. And another where the coder clearly thought that if you multiply something by enough made up crap and take the remainder, you get randomness. An understanding of random numbers in computing is not something the classrooms ever cover as far as I can tell.

  12. Every browser since IE10 has had secure RNG by Scorpinox · · Score: 3, Informative

    See this table for support: http://caniuse.com/#feat=getra...

    It's great that they're finally improving Math.random(), but node.js should've had crypto.getRandomValues() from the start.