mercredi 15 mars 2017

Generating truly unique UUIDs in JavaScript and AS3 - PRNGs and underlying algorimths

I'm working on a system that generates around 2 billion unique UUIDs a day. The UUIDs are generated using JavaScript \ Flash (AS3) on the client.

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.

I did some reading and I learned that the pseudo-random generation (PRNG) algorithm most browsers, and specifically chrome, implement is flawed. Chromium and Node.js use the V8 javaScript engine, which implements an algorithm called MWC1616.

In theory, UUIDs generated using a good PRNG should have a 2132 probability for collision, but with MWC1616, under some very realistic scenarios, this probability is around 1:30000.

To solve the problem, I considered the following options:

  1. Generate the IDs on the server (using Go)
  2. Generate a stronger ID on the client, by hashing some info like IP, UA, timestamp, etc. with the UUID.
  3. Replacing Math.random() with a better random generator.

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.

The good news are that on newer browsers, there is the getRandomValues api. Unfortunately, I need to support older browsers.

So my questions are:

  1. What is a good and reliable JavaScript polyfill for

crypto.getRandomValues()

(that doesn't use Math.random internally)?

  1. Does AS3 Math.random() use the browser's Math.random()? Does it implement the same algorithm itself?

  2. 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.S. I highly recommend the article I mentioned. I was aware of the issues with Math.random() for many years, but this article truly made it clear to me for good.

Aucun commentaire:

Enregistrer un commentaire