Random numbers are not random

How to create a random number generator in JS and predict Math.random()

Have you ever wondered how Math.random() works? What is a random number and how does it work? And imagine the question in a job interview — write your random number generator in a couple lines of code. And so, what is it, randomness and is it possible to predict it.

Pseudorandom number generator and random number generator
In order to get something random, we need a source of entropy, a source of some chaos that we will use to generate randomness.

This source is used to accumulate entropy and then to get from it an initial value (seed), which is needed by random number generators (RNG) to generate random numbers.

A Pseudo-Random Number Generator uses a single initial value, hence its pseudo-randomness, while a Random Number Generator always generates a random number with a high-quality random value in the beginning, which is taken from different entropy sources.

Entropy is a measure of disorder. Information entropy is a measure of the uncertainty or unpredictability of information.

It turns out that to create a pseudo-random sequence, we need an algorithm that will generate some sequence based on a certain formula. But such a sequence would be predictable. Nevertheless, let’s imagine how we could write our own random number generator if we didn’t have Math.random()

The PRNG has some algorithm which can be reproduced.
RNG is the obtaining of numbers entirely from some noise, the possibility to calculate which tends to zero. At the same time there are certain algorithms in the RNG to equalize the distribution.

Create your own PRNG algorithm

Pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers whose elements are almost independent of each other and obey a given distribution (usually uniform).

We can take a sequence of some numbers and take the modulus of a number from them. The simplest example that comes to mind is this. We need to think about which sequence to take and the modulus of what. If we just go from 0 to N and modulo 2, we get a generator of 1 and 0:

This function generates for us the sequence 01010101010101… and we can’t even call it a pseudo-random sequence. For the generator to be random, it must pass the test for the next bit. But we do not have such a task. Nevertheless, even without any tests we can predict the next sequence, so this algorithm is not suitable head-on, but we are in the right direction.

What if we take some known, but non-linear sequence, for example, the number of PI. And as a value for the modulus we will take something else instead of 2. You can even think about changing the modulus value. The sequence of digits in the number Pi is considered random. The generator can work using Pi numbers starting from some unknown point. An example of such an algorithm, with a sequence based on PI and with a changeable modulus:

But in JS the number of PI can be output only up to 48 digits and no more. Therefore, it is still easy to predict such a sequence and each run of such a generator will always give the same numbers. But our generator already started to display numbers from 0 to 9. By the way, this is the distribution of numbers at 10,000 iterations:

0: 394
1: 2026
2: 304
3: 845
4: 806
5: 1738
6: 950
7: 935
8: 736
9: 1267

The distribution is very uneven, but we will get a number generator from 0 to 9.

We can take not the number Pi, but time in the numeric representation and consider this number as a sequence of digits, and in order not to repeat the sequence every time, we will read it from the end. So our PRNG algorithm will look like this:

This is like a pseudorandom number generator. And the same Math.random() is a PRNG, which we’ll talk about later. In this case the first number is different every time.

Actually on these simple examples you can understand how more complex random generators work. There are even ready algorithms. For example, let’s look at one of them, the Linear Congruent PRNG.

Linear Congruent PRNG

Linear Congruent PRNG is a common method for generating pseudo-random numbers. It is not cryptographically strong. This method consists in calculating the terms of a linear recurrent sequence modulo some natural number m, given by the following formula:

where a(multiplier), c(addend), m(mask) are some integer coefficients. The resulting sequence depends on the choice of starting number — i.e. seed. Different values of seed result in different random number sequences. An example of implementation of such an algorithm in JavaScript:

Many programming languages use LCPRNG (but not that algorithm(!)).

As stated above, such a sequence can be predicted. So why do we need PRNG? If we’re talking about security, then PRNG is a problem. If we are talking about other tasks, these properties can be a plus. For example for different special effects and animations you may need to call random very often. And this is where value distribution and performance are important! Securus algorithms can not boast about the speed of execution.

Another property is reproducibility. Some implementations allow you to set seed, and this is very useful if the sequence must be repeated. Repeatability is needed in tests, for example. And there are many other things for which you don’t need a safe RNG.

How Math.random() works

The Math.random() method returns a floating-point pseudo-random number from the range , that is, from 0 (inclusive) to 1 (but not including 1), which can then be scaled to the desired range. The implementation itself selects the initial seed for the random number generation algorithm; it cannot be selected or reset by the user.

How the Math.random() algorithm works is an interesting question. Until recently, namely before 49 Chrome, the MWC1616 algorithm was used:

It is this algorithm that generates for us a sequence of pseudorandom numbers between 0 and 1.

Predicting Math.random()

There is a challenge:

What should I put in place of questions for the function to return true? It seems impossible. But, it is possible if you have looked in the spec and seen the V8 PRNG algorithm.

This code worked 70% of the time for Chrome < 49 and Node.js < 5.

What’s going on here? The point is that the algorithm can be predicted. To make it clearer, you can generate a picture of random pixels. The website

https://bl.ocks.org/mmalone/bf59aa2e44c44dde78ac

there is such a generator. This is what happened when the browser had the MWC1616 algorithm:

Do you see these uniformities on the left slide? The image shows a problem with the distribution of the values. In the picture on the left you can see that the values are heavily clustered in places, and in places large fragments drop out. As a consequence, the numbers can be predicted.

It turns out that we can reverse Math.random() and predict what number was guessed based on what we get at this point in time. To do this, we get two values via Math.random(). Then we calculate the internal state from these values. With internal state we can predict the next values of Math.random() without changing the internal state. Let’s change the code so that previous value will be returned instead of next value. Actually all this is described in the code-solution for the random4-problem. But then the algorithm was changed (see spec for details). It can be broken as soon as we will have normal JS working with 64 bit numbers. But that will be another story.

The new algorithm looks like this:

It will still be calculable and predictable. But so far we don’t have “long math” in JS. You can try to do it with TypedArray or use special libraries. Maybe one day someone will write a predictor again. Maybe it will be you, reader. Who knows ;)

Сrypto Random Values

The Math.random() method does not provide cryptographically robust random numbers. Don’t use it for anything related to security. Use the Web Crypto API instead and the more accurate window.crypto.getRandomValues() method.

An example of generating a random number:

But unlike the Math.random() PRNG, this method is very resource intensive. The point is that this generator uses system calls in the OS to access entropy sources (mac address, CPU, temperature, etc…).