3 ms·

Funny to see this coming up again after all these years. I was the person who reported this issue to the Chromium team, 3 years before that blog posts. They mar

Funny to see this coming up again after all these years. I was the person who reported this issue to the Chromium team, 3 years before that blog posts. They marked it as won't fix, multiple times (other people reported it too), before they fixed it. Safari, Firefox, and IE were all already using more robust PRNGs for Math.random() that did not exhibit this issue. https://stackoverflow.com/questions/9550796/why-is-google-chromes-math-random-number-generator-not-that-random https://stackoverflow.com/questions/9550796/why-is-google-ch... https://issues.chromium.org/issues/40404440 https://issues.chromium.org/issues/40404440 I came across it because of some tests I had for a statistics library I was working on. There was a test that created an array with 100k random values that shouldn't have had any collisions, but I consistently got multiple collisions, only in Chrome.

magicalist 2y ago
Pretty sure it was [1] that finally got them moving (old hacker news discussion here[2]). Not to take away from your bug report, but there were a bunch :) The main issues were that the spec allows engines to pick their own implementation (including only having 2^32 possible values) and there were benchmarks like sunspider where overfitting encouraged the implementation to be as fast as possible. That was a lot less of an excuse for the RNG they used in 2012-2015 compared to when it was added in 2007 or 2008, but by then there was a decent argument that developers should go to crypto.getRandomValues() if they wanted actual random values, which probably stalled action longer than it should have. > Safari, Firefox, and IE were all already using more robust PRNGs for Math.random This wasn't true at the time. I actually don't remember what Safari was doing in 2012 so I won't say that one for sure, but Firefox and IE were both using garbage RNGs as well, they were probably just generating across the full (or at least more of the) (0, 1] double range so didn't produce the collisions you saw in your testing. [1] https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d https://medium.com/@betable/tifu-by-using-math-random-f1c308... [2] https://news.ycombinator.com/item?id=10598065 https://news.ycombinator.com/item?id=10598065
- pseudosavant 2y ago
  Safari, Firefox, and IE all had no trouble producing 100k random values without a collision. Chrome couldn't do it without at least two collisions. Chrome's `Math.random()` performance/speed was not measurably better despite, but it could only produce 2^32 random values despite IEEE-754 FP supporting up to 2^53. That is how I found this bug, because only Chrome used low enough entropy. Which is definitely worse. My recollection of that time working on that stats library was that Chrome took many shortcuts to max out things like SunSpider. There were other Chrome specific workarounds I had to implement to address what I considered bugs, but they were definitely in lightly defined areas like `Math.random()`. I couldn't find the original bug I file, but the discussion on it specifically noted that they could just copy the Firefox one (which was noted to be an improvement over Chrome's) but they decided on Won't Fix until someone more important than me drew attention to it. It was trivially fixed within a week once that happened.
  - hashseed 2y ago
    Hi. I'm the V8 engineer who implemented the fix and wrote the blog post. The reason the initial bug report [0] was marked as WAI but the Medium blog post got a lot more traction is very simple and much more human. When the initial issue was filed to the chromium bug tracker, it was routed to Chrome's security team. From a security perspective, Math.random() provides no guarantees about cryptographic safety, so naturally it was marked as WAI – nobody from the V8 team actually saw this issue. One of the suggestions "3. Make crypto.random(size)" was acted upon though, and so crypto.getRandomValues() was introduced in Chrome 11, about 10 months after the issue report. In terms of specifying and introducing new Web APIs, this was incredibly fast. After the Medium blog post was published, someone filed an issue directly to the V8 project. It did not question the spec compliance, but pointed out that the PRNG quality could be better. That nerd-sniped me into researching this topic and after reading a few papers, I implemented the fix with xorshift128+. I'm thankful that my team lead allowed me to set aside some time to work on this even though it was not on our project roadmap. Performance regressions that could affect our benchmark performance was of course part of the consideration, but there were many options to avoid a performance regression. In V8, crossing the boundary between machine code compiled from JS to C++ runtime builtins is fairly expensive. I could have either ported xorshift128+ to assembly so that this boundary crossing was not necessary, or I could have amortized the boundary crossing cost by buffering multiple random values. I chose the latter because porting to assembly is error prone and I would have to do this for each platform. There are better options in V8 nowadays, by expressing the algorithm in an intermediate representation, but back then that was not available. [0] https://g-issues.chromium.org/issues/40404440 https://g-issues.chromium.org/issues/40404440 [1] https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getRandomValues https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getR... [2] https://g-issues.chromium.org/issues/40643979 https://g-issues.chromium.org/issues/40643979

magicalist 2y ago

Pretty sure it was [1] that finally got them moving (old hacker news discussion here[2]). Not to take away from your bug report, but there were a bunch :) The main issues were that the spec allows engines to pick their own implementation (including only having 2^32 possible values) and there were benchmarks like sunspider where overfitting encouraged the implementation to be as fast as possible. That was a lot less of an excuse for the RNG they used in 2012-2015 compared to when it was added in 2007 or 2008, but by then there was a decent argument that developers should go to crypto.getRandomValues() if they wanted actual random values, which probably stalled action longer than it should have. > Safari, Firefox, and IE were all already using more robust PRNGs for Math.random This wasn't true at the time. I actually don't remember what Safari was doing in 2012 so I won't say that one for sure, but Firefox and IE were both using garbage RNGs as well, they were probably just generating across the full (or at least more of the) (0, 1] double range so didn't produce the collisions you saw in your testing. [1] https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d https://medium.com/@betable/tifu-by-using-math-random-f1c308... [2] https://news.ycombinator.com/item?id=10598065 https://news.ycombinator.com/item?id=10598065

pseudosavant 2y ago
Safari, Firefox, and IE all had no trouble producing 100k random values without a collision. Chrome couldn't do it without at least two collisions. Chrome's `Math.random()` performance/speed was not measurably better despite, but it could only produce 2^32 random values despite IEEE-754 FP supporting up to 2^53. That is how I found this bug, because only Chrome used low enough entropy. Which is definitely worse. My recollection of that time working on that stats library was that Chrome took many shortcuts to max out things like SunSpider. There were other Chrome specific workarounds I had to implement to address what I considered bugs, but they were definitely in lightly defined areas like `Math.random()`. I couldn't find the original bug I file, but the discussion on it specifically noted that they could just copy the Firefox one (which was noted to be an improvement over Chrome's) but they decided on Won't Fix until someone more important than me drew attention to it. It was trivially fixed within a week once that happened.
- hashseed 2y ago
  Hi. I'm the V8 engineer who implemented the fix and wrote the blog post. The reason the initial bug report [0] was marked as WAI but the Medium blog post got a lot more traction is very simple and much more human. When the initial issue was filed to the chromium bug tracker, it was routed to Chrome's security team. From a security perspective, Math.random() provides no guarantees about cryptographic safety, so naturally it was marked as WAI – nobody from the V8 team actually saw this issue. One of the suggestions "3. Make crypto.random(size)" was acted upon though, and so crypto.getRandomValues() was introduced in Chrome 11, about 10 months after the issue report. In terms of specifying and introducing new Web APIs, this was incredibly fast. After the Medium blog post was published, someone filed an issue directly to the V8 project. It did not question the spec compliance, but pointed out that the PRNG quality could be better. That nerd-sniped me into researching this topic and after reading a few papers, I implemented the fix with xorshift128+. I'm thankful that my team lead allowed me to set aside some time to work on this even though it was not on our project roadmap. Performance regressions that could affect our benchmark performance was of course part of the consideration, but there were many options to avoid a performance regression. In V8, crossing the boundary between machine code compiled from JS to C++ runtime builtins is fairly expensive. I could have either ported xorshift128+ to assembly so that this boundary crossing was not necessary, or I could have amortized the boundary crossing cost by buffering multiple random values. I chose the latter because porting to assembly is error prone and I would have to do this for each platform. There are better options in V8 nowadays, by expressing the algorithm in an intermediate representation, but back then that was not available. [0] https://g-issues.chromium.org/issues/40404440 https://g-issues.chromium.org/issues/40404440 [1] https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getRandomValues https://developer.mozilla.org/en-US/docs/Web/API/Crypto/getR... [2] https://g-issues.chromium.org/issues/40643979 https://g-issues.chromium.org/issues/40643979