New issue
Advanced search Search tips

Issue 852411 link

Starred by 1 user

Issue metadata

Status: WontFix
Owner: ----
Closed: Jun 2018
Cc:
Components:
EstimatedDays: ----
NextAction: ----
OS: Windows
Pri: 2
Type: Bug



Sign in to add a comment

window.crypto.getRandomValues appears to produce consistent peaks over large counts of generated numbers

Reported by glenat...@gmail.com, Jun 13 2018

Issue description

UserAgent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/66.0.3359.181 Safari/537.36

Steps to reproduce the problem:
As described ( with working code snippet ) in this StackOverflow question: https://stackoverflow.com/questions/50588573/why-does-window-crypto-getrandomvalues-on-chrome-appear-to-return-consistently-g 

What is the expected behavior?
I would expect window.crypto.getRandomValues() to be at least as random as Math.random().

What went wrong?
When window.crypto.getRandomValues is used to retrieve many numbers in a way that I have seen recommended in various places, there are clear and consistent peaks in the output, strongly implying that the numbers generated are less random than someone using this call might be expecting.

Did this work before? N/A 

Does this work in other browsers? No
 The same behaviour shows up in Firefox ( possibly same underlying RNG mechanism ) not submitted a bug yet, the peaks are less noticeable in Edge.

Chrome version: 66.0.3359.181  Channel: stable
OS Version: 10.0
Flash Version: 

I absolutely accept that this could be user error or some quirk of the way the numbers are being retrieved, but I figured it was worth reporting because it seems as though it could be serious if the API was responsible.
 
Labels: Needs-Milestone

Comment 2 by eroman@chromium.org, Jun 14 2018

Cc: davidben@chromium.org
Status: WontFix (was: Unconfirmed)
Thanks for the report.

That snippet of code seems rather problematic, so I wouldn't trust those conclusions.

That said, running tests for the randomness is always good - davidben can you advise on existing tests to use?

On Windows we are using Advapi32!RtlGenRandom to generate that randomness.
Yeah, the sampling method in that code snippet is not at all sound. The "peaks" are entirely out of your code. Rather, you should consider *not* seeing those peaks to be an indication that the distribution has a problem!

You're counting:

numbers[(Math.floor((rnd/255)*count)+1)]++

rnd is uniformly distributed over [0, 256). count here is 50. That is not how you turn a 256-sided die into a 50-sided die. That sampling method, in fact, is biased towards 1, 11, 21, 31, and 41.

Try it:

counts = {}
for i in range(256):
  sample = int((i / 255.0) * 50 + 1)
  counts.setdefault(sample, 0)
  counts[sample] += 1

for k, v in counts.items():
  print "%d shows up %d times" % (k, v)

That outputs:

1 shows up 6 times
2 shows up 5 times
3 shows up 5 times
4 shows up 5 times
5 shows up 5 times
6 shows up 5 times
7 shows up 5 times
8 shows up 5 times
9 shows up 5 times
10 shows up 5 times
11 shows up 6 times
12 shows up 5 times
13 shows up 5 times
14 shows up 5 times
15 shows up 5 times
16 shows up 5 times
17 shows up 5 times
18 shows up 5 times
19 shows up 5 times
20 shows up 5 times
21 shows up 6 times
22 shows up 5 times
23 shows up 5 times
[and so on...]

Comment 4 by glenat...@gmail.com, Jun 18 2018

That makes sense, thank you. I assumed I was doing something stupid but I couldn't tell what it was and I would rather raise a superfluous bug than have something dangerous slip under the radar.
If you need a 50-sided die but can only have power-of-two die, the usual approach is something like:

Pick a random number from 0 to 255. If it is less than 250, divide by 5 (250 = 5 * 50), rounding down. Otherwise, discard the number and try again.

Sign in to add a comment