Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 



Forgot your password?
typodupeerror
Check out the new SourceForge HTML5 internet speed test! No Flash necessary and runs on all devices. ×
Bug Math Open Source Programming

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.
This discussion has been archived. No new comments can be posted.

Fixing JavaScript's Broken Random Number Generator

Comments Filter:
  • Obligatory XKCD (Score:5, Informative)

    by psergiu ( 67614 ) on Monday December 28, 2015 @03:49PM (#51197117)
  • Javascript? lol! (Score:4, Insightful)

    by Anonymous Coward on Monday December 28, 2015 @03:53PM (#51197145)

    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?

    • by ickleberry ( 864871 ) <web@pineapple.vg> on Monday December 28, 2015 @03:59PM (#51197191) Homepage
      We could but all the startup hipsters would be so disappointed
      • by Anonymous Coward

        You say that like it's a bad thing.

    • by hey! ( 33014 )

      It's support for functional programming?

      • And how many of the Javascript monkeys actually understand functional programming? A handful?

      • 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

    • Its install base?
    • by Anonymous Coward

      Is there anything about Javascript that isn't sh*tty and broken?

      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

      • by Anonymous Coward

        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.

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

    • by dshk ( 838175 ) on Monday December 28, 2015 @06:31PM (#51198235)

      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.

      • by AmiMoJo ( 196126 )

        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.

        • by dshk ( 838175 )

          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

      • 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

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

    • by Jonner ( 189691 )

      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)

    by tibit ( 1762298 ) on Monday December 28, 2015 @04:00PM (#51197205)

    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)

      by Anonymous Coward on Monday December 28, 2015 @04:06PM (#51197249)

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

      • Re: (Score:2, Informative)

        by Anonymous Coward

        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)

      by Lunix Nutcase ( 1092239 ) on Monday December 28, 2015 @04:10PM (#51197273)

      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*

      • by Anonymous Coward
        That's just tragic. The reviewer is familiar enough with PRNGs to mention the mersenne twister, but blindly accepted a goofy PRNG implementation. Even smart people are lazy and stupid some of the time.
    • 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.

      • Yeah, seems one would have chosen a UUID generator not a PRNG.

      • by AmiMoJo ( 196126 )

        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

        • by fnj ( 64210 )

          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.

      • by Alioth ( 221270 )

        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

        • The solution to that is very simple - whichever system is called upon to generate the token is the one that throws out any token that doesn't meet additional rules. If it's system A, throw out every token that begins with a '1'. If it's system B, 'throw out any token that begins with a '2'. This way you also know which system to check to verify the token.

          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

  • by penguinoid ( 724646 ) on Monday December 28, 2015 @04:05PM (#51197239) Homepage Journal

    What did you expect from some random coder?

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

        by Lennie ( 16154 ) on Monday December 28, 2015 @04:23PM (#51197363)

        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.

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

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

  • by BitZtream ( 692029 ) on Monday December 28, 2015 @04:09PM (#51197271)

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

  • by redelm ( 54142 ) on Monday December 28, 2015 @04:13PM (#51197297) Homepage

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

  • 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

  • Oh yeah? (Score:4, Funny)

    by U2xhc2hkb3QgU3Vja3M ( 4212163 ) on Monday December 28, 2015 @04:19PM (#51197335)

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

  • by Lunix Nutcase ( 1092239 ) on Monday December 28, 2015 @04:26PM (#51197375)

    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?

    • by U2xhc2hkb3QgU3Vja3M ( 4212163 ) on Monday December 28, 2015 @04:37PM (#51197463)

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

    • by dfsmith ( 960400 )

      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.

      • Sure, it's only broken when actually used.

  • by QuietLagoon ( 813062 ) on Monday December 28, 2015 @04:31PM (#51197425)
    JavaScript was not designed by any regular use of that word. JavaScript happened.
    • by Anonymous Coward

      You are confusing PHP with Javascript.

      JS has a very powerful and sane subset.

      PHP does not.

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

  • Why can't they leave at least one bastion of free enterprise and perfect competition? Why should they come in ask for equal representation of every 32 bit patterns? These numbers should know that in America every one gets equal opportunity not equal outcomes. It is a tough world out there and you have 32 bits and the other number has 32 bits. Fight your way and get represented as often as you can or fall by the way side.

    We should carve out an exception for the sincerely held religious beliefs to serve or

  • That's why JS is untyped, it adds much needed randomness.

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

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

    by Kazoo the Clown ( 644526 ) on Monday December 28, 2015 @07:11PM (#51198413)
    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.
    • Knuth covers this definitively in Volume 2 of "The Art of Computer Programming". I think I first read it in 1979 so it certainly used to be covered in teaching, maybe that's all been lost in the later generations. Now get off my lawn.
      • It's not clear Knuth was used all that much even back then, and I wonder if it's been in use at all in the last 20 years or so.
  • by Scorpinox ( 479613 ) on Monday December 28, 2015 @07:34PM (#51198511)

    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.

  • by Anonymous Coward

    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

  • 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;
    int rand(void) // RAND_MAX assumed to be 32767
    {
    next = n

  • 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

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

When it is not necessary to make a decision, it is necessary not to make a decision.

Working...