10
$\begingroup$

Is it possible to feed a neural network, the output from a random number generator and expect it learn the hashing/generator function. So that it can predict what will be the next generated number? Does something like this already exist? If research is already done on this or something related to (predict pseudo random numbers) can anyone point me to the right resources. Any additional comments or advice would also be helpful.

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

$\endgroup$
  • 2
    $\begingroup$ Your idea might work for a poor implementation of a RNG but other methods would be better. The next number of a proper RNG is, umm, random. $\endgroup$ – Bob Salita Aug 21 '17 at 15:31
  • $\begingroup$ Very interesting question. (I too sometimes wonder about the predictability of pseudo-random number generation over extremely long cycles.) Welcome to AI! $\endgroup$ – DukeZhou Aug 21 '17 at 16:37
  • $\begingroup$ @BobSalita Sorry for the confusion. But I have mentioned its pseudo-random. And we know computers cant produce truly random numbers. Just many variables to predict. I am not trying to predict the next possible number as the first step. My first goal is to analyse and see if there is any common pattern given a window size. The next step would be to predict the next number using that pattern. Source: softwareengineering.stackexchange.com/questions/124233/… $\endgroup$ – AshTyson Aug 22 '17 at 5:25
11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Wow thanks for the explanation behind this. I am trying to analyse the pattern and predict the next bit and it is not a perfect RNG, but somewhat solid PRNG. But it is not state of the art either. I think with a little computational power and proper implementation I cnould predict it with 60-70% if not more. If possible, can you point any resources where I can read more about this. I am not from a research background and more of a developer. $\endgroup$ – AshTyson Aug 22 '17 at 4:41
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ This is not learning to predict the random sequence -- it is learning to echo it. Concretely, the training samples, X, consists of 5 random integers, and the output, y, is the 4th integer of the 5. For example, if X = [15, 33, 44, 30, 3], y = 30. The LSTM is learning to echo the 4th sample. $\endgroup$ – Chris Hiszpanski Mar 14 at 9:42
  • $\begingroup$ Yes, good point. I still find it to be a very interesting practical example of LSTM usage. If you know how to learn something like Mersenne Twister from seed only given as an input, please post it here as I'd be really interested to see. Seems possible with enough samples, but I might be completely wrong. $\endgroup$ – isp-zax Mar 17 at 18:49
1
$\begingroup$

If a psuedo random number generator is throwing out numbers then in the analysis of these numbers you will be able to determine the algorithm that produced them because the numbers ain't random they are determined by that algorithm and are not chance. If the world is made up of physical laws that are able to be understood and replicated than the apparent randomness we observe in events is down to those physical laws. and the psuedo generator is no longer, and is actual randomness which which from its definition is indeterminable,and presents a paradox. How can rules create randomness by definition surely our apparent perception of the randomness of events we observe is an allusion and is actually a certainty which we are not unable to predict. If there are absolute fundamental laws of nature these laws create order out of the observed chaos and then the randomness and its reference is false and without any proper truthful meaning.

$\endgroup$
  • 1
    $\begingroup$ True. Quite philosophical though. Expected somewhat of a technical answer. Thanks anyway :) $\endgroup$ – AshTyson Sep 1 '17 at 10:37
  • $\begingroup$ @Sammy no worries mate :) $\endgroup$ – Bobs Sep 1 '17 at 16:50
  • $\begingroup$ @Sammy just felt we need to understand the philosophy of things because I think it allows us to see our limitations. Hope it was of some help anyway :) $\endgroup$ – Bobs Sep 1 '17 at 17:01
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You've just demonstrated to me a conception in my own mind between quantity and its communication being a method of determining a pattern i knew i was'nt far of from my intuition :) $\endgroup$ – Bobs Sep 29 '18 at 16:59
  • $\begingroup$ But it still begs an inseparable question of randomness being a "product" disconected from rationality when we attempt to describe it from a function of the language we use which is derived from a humility in retaining the evolutionary process and it percieved method of maintaining human sanity lol. $\endgroup$ – Bobs Sep 29 '18 at 17:09
  • $\begingroup$ Is randomness or its perception a disjunction between reality and human perception and because of its disjointness only a residue of sentient perception decides each and everyone's picture we all observe and adds up to communicable randomness because of intellectual disjointness in humans concentric factor in conceptual distribution. $\endgroup$ – Bobs Sep 29 '18 at 17:25
  • $\begingroup$ How can you ever analyse something without a basis to begin your analysis from if your trying to analyze randomness then surely it is from a basis of certainty ego enteric lol $\endgroup$ – Bobs Oct 6 '18 at 0:23
  • $\begingroup$ Pseudo randomness is a property of plastic people masquerading as real down to earth qualities that they have a superfluous disregard for and an unholy or human preocupation with. Determination leads to faith and a certainty of occupation and wholesome communication of the product of a good life not withstanding the problems of a balance of hardship. $\endgroup$ – Bobs Oct 13 '18 at 20:39

protected by Community Oct 18 '18 at 21:38

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.