Can a neural network be used to predict the next pseudo random number?

Question

Is it possible to feed a neural network the output from a random number generator and expect it learn the hashing (or generator) function, so that it can predict what will be the next generated pseudo-random number?

Does something like this already exist? If research is already done on this or something related (to the prediction of pseudo-random numbers), can anyone point me to the right resources?

Currently, I am looking at this library and its related links. https://github.com/Vict0rSch/deep_learning/tree/master/keras/recurrent

Answer 1

If we are talking about a perfect RNG, the answer is a clear no. It is impossible to predict a truly random number, otherwise it wouldn't be truly random.

When we talk about pseudo RNG, things change a little. Depending on the quality of the PRNG, the problem ranges from easy to almost impossible. A very weak PRNG like the one XKCD published could of course be easily predicted by a neural network with little training. But in the real world things look different.

The neural network could be trained to find certain patterns in the history of random numbers generated by a PRNG to predict the next bit. The stronger the PRNG gets, the more input neurons are required, assuming you are using one neuron for each bit of prior randomness generated by the PRNG. The less predictable the PRNG gets, the more data will be required to find some kind of pattern. For strong PRNGs this is not feasable.

On a positive note, it is helpful that you can generate an arbitrary amount of training patterns for the neural network, assuming that you have control over the PRNG and can produce as many random numbers as you want.

Because modern PRNGs are a key component for cryptography, extensive research has been conducted to verify that they are "random enough" to withstand such prediction attacks. Therefore I am pretty sure that it is not possible with currently available computational resources to build a neural network to successfully attack a PRNG that's considered secure for cryptography.

It is also worth noting that it is not necessary to exactly predict the output of a PRNG to break cryptography - it might be enough to predict the next bit with a certainty of a little more than 50% to weaken an implementation significantly. So if you are able to build a neural network that predicts the next bit of a PRNG (considered secure for cryptography) with a 55% success rate, you'll probably make the security news headlines for quite a while.

Answer 2

Old question, but I thought it's worth one practical answer. I happened to stumble upon it right after looking at a guide of how to build such neural network, demonstrating echo of python's randint as an example. Here is the final code without detailed explanation, still quite simple and useful in case the link goes offline:

from random import randint
from numpy import array
from numpy import argmax
from pandas import concat
from pandas import DataFrame
from keras.models import Sequential
from keras.layers import LSTM
from keras.layers import Dense

# generate a sequence of random numbers in [0, 99]
def generate_sequence(length=25):
    return [randint(0, 99) for _ in range(length)]

# one hot encode sequence
def one_hot_encode(sequence, n_unique=100):
    encoding = list()
    for value in sequence:
        vector = [0 for _ in range(n_unique)]
        vector[value] = 1
        encoding.append(vector)
    return array(encoding)

# decode a one hot encoded string
def one_hot_decode(encoded_seq):
    return [argmax(vector) for vector in encoded_seq]

# generate data for the lstm
def generate_data():
    # generate sequence
    sequence = generate_sequence()
    # one hot encode
    encoded = one_hot_encode(sequence)
    # create lag inputs
    df = DataFrame(encoded)
    df = concat([df.shift(4), df.shift(3), df.shift(2), df.shift(1), df], axis=1)
    # remove non-viable rows
    values = df.values
    values = values[5:,:]
    # convert to 3d for input
    X = values.reshape(len(values), 5, 100)
    # drop last value from y
    y = encoded[4:-1,:]
    return X, y

# define model
model = Sequential()
model.add(LSTM(50, batch_input_shape=(5, 5, 100), stateful=True))
model.add(Dense(100, activation='softmax'))
model.compile(loss='categorical_crossentropy', optimizer='adam', metrics=['acc'])
# fit model
for i in range(2000):
    X, y = generate_data()
    model.fit(X, y, epochs=1, batch_size=5, verbose=2, shuffle=False)
    model.reset_states()
# evaluate model on new data
X, y = generate_data()
yhat = model.predict(X, batch_size=5)
print('Expected:  %s' % one_hot_decode(y))
print('Predicted: %s' % one_hot_decode(yhat))

I've just tried and it indeed works quite well! Took just a couple of minutes on my old slow netbook. Here's my very own output, different from the link above and you can see match isn't perfect, so I suppose exit criteria is a bit too permissive:

...
 - 0s - loss: 0.2545 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.1845 - acc: 1.0000
Epoch 1/1
 - 0s - loss: 0.3113 - acc: 0.9500
Expected:  [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 79, 45, 95, 92, 32, 33]
Predicted: [14, 37, 0, 65, 30, 7, 11, 6, 16, 19, 68, 4, 25, 2, 95, 45, 95, 92, 32, 33]

Answer 3

Being a complete newbie in machine learning, I did this experiment (using Scikit-learn ):

• Generated a large number (N) of pseudo-random extractions, using python random.choices function to select N numbers out of 90.

• Trained a MLP classifier with training data composed as follow:

  • ith sample : X <- lotteryResults[i:i+100], Y <- lotteryResults[i]

  In practice, I aimed to a function that given N numbers, coud predict the next one.

• Asked the trained classificator to predict the remaining numbers.

Results:

• of course, the classificator obtained a winning score comparable with the one of random guessing or of other techniques not based on neural networks (I compared results with several classifiers available in scikit-learn libraries )

• however, if I generate the pseudo-random lottery extractions with a specific distribution function, then the numbers predicted by the neural network are roughly generated with the same distribution curve ( if you plot the occurrences of the random numbers and of the neural network predictions, you can see that that the two have the same trend, even if in the predicytions curve there are many spikes. So maybe the neural network is able to learn about pseudo-random number distributions ?

• If I reduce the size of the training set under a certain limit, I see that the classifier starts to predict always the same few numbers, which are among the most frequent in the pseudo-random generation. Strangely enough ( or maybe not ) this behaviour seem to slightly increase the winning score.

Answer 4

Adding to what Demento said, the extent of randomness in the Random Number Generation Algorithm is the key issue. Following are some designs that can make the RNG weak:
Concealed Sequences
Suppose this is the previous few sequences of characters generated: (Just an example, for the practical use larger range, is used)

lwjVJA
Ls3Ajg
xpKr+A
XleXYg
9hyCzA
jeFuNg
JaZZoA

Initially, you can't observe any pattern in the generations but changing them to Base64 encoding and then to hex, we get the following:

9708D524
2ECDC08E
C692ABF8
5E579762
F61C82CC
8DE16E36
25A659A0

Now if we subtract each number form the previous one, we get this:

FF97C4EB6A
97C4EB6A
FF97C4EB6A
97C4EB6A
FF97C4EB6A
FF97C4EB6A

This indicates that the algorithm just adds 0x97C4EB6A to the previous value, truncates the result to a 32-bit number, and Base64-encodes the data.
The above is a basic example. Today's ML algorithms and systems are capable enough to learn and predict more complex patterns.

Time Dependency
Some RNG algorithms use time as the major input for generating random numbers, especially the ones created by developers themselves to be used within their application.

Whenever weak RNG algorithms is implemented that appear to be stochastic, they can be extrapolated forwards or backwards with perfect accuracy in case sufficient dataset is available.