title: Generating truly unique UUIDs in JavaScript and AS3 - PRNGs and underlying algorimths
body: <p>I'm working on a system that generates around <em>2 billion</em> unique UUIDs a day. The UUIDs are generated using JavaScript \ Flash (AS3) on the client.</p>
  
  <p>We recently noticed that our UUIDs are no where near unique. We have around 20% (!) of daily duplicates, most of which (relative to traffic volume) are coming from chrome.</p>
  
  <p>I did <a href="https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d#.almzgm8l5" rel="nofollow noreferrer">some reading</a> <a href="http://devoluk.com/google-chrome-math-random-issue.html" rel="nofollow noreferrer">and learned</a> <a href="https://v8project.blogspot.co.il/2015/12/theres-mathrandom-and-then-theres.html" rel="nofollow noreferrer">that the pseudo-random</a> generation (PRNG) algorithm implementation on most browsers, and specifically chrome, is flawed. Chromium and Node.js use the V8 javaScript engine, which implements an algorithm called MWC1616.</p>
  
  <p>In theory, UUIDs generated using a good PRNG should have a <a href="https://stackoverflow.com/a/39776/372086">2<sup>132</sup> probability</a> for collision, but with MWC1616, under some very realistic scenarios, this probability is around 1:30000.</p>
  
  <p>To solve the problem, I considered the following options:</p>
  
  <ol>
  <li>Generate the IDs on the server (using Go)</li>
  <li>Generate a stronger ID on the client, by hashing some info like IP, UA, timestamp, etc. with the UUID.</li>
  <li>Replacing Math.random() with a better random generator.</li>
  </ol>
  
  <p>Since I prefer to keep things on the client and I don't want to re-invent the wheel and modify the UUID creation logic, I want to stick with option 3.</p>
  
  <p>The good news are that on newer browsers, there is the <a href="https://developer.mozilla.org/en-US/docs/Web/API/RandomSource/getRandomValues" rel="nofollow noreferrer">getRandomValues</a> api. Unfortunately, I need to support older browsers.</p>
  
  <p>So my questions are:</p>
  
  <ol>
  <li>What is a good and reliable JavaScript polyfill for </li>
  </ol>
  
  <blockquote>
    <p>crypto.getRandomValues()</p>
  </blockquote>
  
  <p>(that doesn't use Math.random internally)?</p>
  
  <ol start="2">
  <li><p>Does AS3 Math.random() use the browser's Math.random()? Does it implement the same algorithm itself?</p></li>
  <li><p>Does flash.crypto.generateRandomBytes() use Math.random()? Does it use crypto.getRandomValues()? If not, which algorithm does it implement and will it be a good solution for the same issue in AS3? If not, which AS3 crypto library would you recommend?</p></li>
  </ol>
  
  <p>P.S. I highly recommend the articles I mentioned <a href="https://medium.com/@betable/tifu-by-using-math-random-f1c308c4fd9d#.almzgm8l5" rel="nofollow noreferrer">-1-</a> <a href="http://devoluk.com/google-chrome-math-random-issue.html" rel="nofollow noreferrer">-2-</a> <a href="https://v8project.blogspot.co.il/2015/12/theres-mathrandom-and-then-theres.html" rel="nofollow noreferrer">-3-</a>. I was aware of the issues with Math.random() for many years, but this article truly made it clear to me for good.</p>