Answers.Body: <p>If we are talking about a perfect RNG, the answer is a clear <strong>no</strong>. It is impossible to predict a truly random number, otherwise it wouldn't be truly random.</p>
  
  <p>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 <a href="https://xkcd.com/221/" rel="noreferrer">XKCD</a> published could of course be easily predicted by a neural network with little training. But in the real world things look different.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-22T04:41:52.303Z
Answers.Text: 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.
Answers.UserDisplayName: AshTyson
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-08-21T21:09:40.843Z
Answers.LastActivityDate: 2017-08-21T21:09:40.843Z
Answers.UserDisplayName: Demento
Answers.Body: <p>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 <a href="https://machinelearningmastery.com/learn-echo-random-integers-long-short-term-memory-recurrent-neural-networks/" rel="noreferrer">example</a>. Here is the final code without detailed explanation, still quite simple and useful in case the link goes offline:</p>
  
  <pre><code>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))
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>...
   - 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]
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-14T09:42:00.303Z
Answers.Text: 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.
Answers.UserDisplayName: thinkski
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-17T18:49:29.747Z
Answers.Text: 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.
Answers.UserDisplayName: isp-zax
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-09T04:51:09.103Z
Answers.LastActivityDate: 2018-09-09T04:51:09.103Z
Answers.UserDisplayName: isp-zax
Answers.Body: <p>Being a  complete newbie in machine learning, I did this experiment (using Scikit-learn ):</p>
  
  <ul>
  <li><p>Generated a large number (N) of pseudo-random extractions, using python random.choices function to select N numbers out of 90.</p></li>
  <li><p>Trained a MLP classifier with training data composed as follow:</p>
  
  <ul>
  <li>ith sample : X &lt;- lotteryResults[i:i+100], Y &lt;- lotteryResults[i]</li>
  </ul>
  
  <p>In practice, I aimed to a function that given N numbers, coud predict the next one.</p></li>
  <li><p>Asked the trained classificator to predict the remaining numbers.</p></li>
  </ul>
  
  <p>Results: </p>
  
  <ul>
  <li><p>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 )</p></li>
  <li><p>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 ?</p></li>
  <li><p>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.</p></li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-22T14:56:28.880Z
Answers.LastActivityDate: 2017-12-22T14:56:28.880Z
Answers.UserDisplayName: Francesco Bochicchio
Answers.Body: <p>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:<br>
  <strong>Concealed Sequences</strong><br>
  Suppose this is the previous few sequences of characters generated: (Just an example, for the practical use larger range, is used)<br></p>
  
  <pre><code>lwjVJA
  Ls3Ajg
  xpKr+A
  XleXYg
  9hyCzA
  jeFuNg
  JaZZoA
  </code></pre>
  
  <p>Initially, you can't observe any pattern in the generations but changing them to Base64 encoding and then to hex, we get the following:<br></p>
  
  <pre><code>9708D524
  2ECDC08E
  C692ABF8
  5E579762
  F61C82CC
  8DE16E36
  25A659A0
  </code></pre>
  
  <p>Now if we subtract each number form the previous one, we get this:<br></p>
  
  <pre><code>FF97C4EB6A
  97C4EB6A
  FF97C4EB6A
  97C4EB6A
  FF97C4EB6A
  FF97C4EB6A
  </code></pre>
  
  <p>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.<br>
  The above is a basic example. Today's ML algorithms and systems are capable enough to learn and predict more complex patterns.<br><br>
  <strong>Time Dependency</strong><br>
  Some RNG algorithms use time as the <em>major input</em> for generating random numbers, especially the ones created by developers themselves to be used within their application.<br><br>
  Whenever weak RNG algorithms is implemented that appear to be stochastic, they <strong>can be extrapolated forwards or backwards with perfect accuracy</strong> in case sufficient dataset is available.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-09T08:38:05.427Z
Answers.LastActivityDate: 2018-09-09T08:38:05.427Z
Answers.UserDisplayName: Ugnes
Body: <p>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 <a href="https://softwareengineering.stackexchange.com/q/124233/145653">pseudo-random number</a>? </p>
  
  <p>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? </p>
  
  <p>Currently, I am looking at this library and its related links.
  <a href="https://github.com/Vict0rSch/deep_learning/tree/master/keras/recurrent" rel="noreferrer">https://github.com/Vict0rSch/deep_learning/tree/master/keras/recurrent</a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-11-21T15:19:36.960Z
Comments.Text: See [Can machine learning analyze random number generator?](https://crypto.stackexchange.com/q/24646/25579) at [Cryptography SE](https://crypto.stackexchange.com).
Comments.UserDisplayName: nbro
Tags: <neural-networks><machine-learning><deep-learning><prediction><randomness>
Title: Can a neural network be used to predict the next pseudo random number?
UserDisplayName: AshTyson
ThreadText: # Can a neural network be used to predict the next pseudo random number?
  
  (Asked by: username_0 on 2017-08-21)
  
  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](https://softwareengineering.stackexchange.com/q/124233/145653)?
  
  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>
  
  **Tags:** neural-networks, machine-learning, deep-learning, prediction, randomness
  
  > **Comments:**
  > **username_1**: See [Can machine learning analyze random number generator?](https://crypto.stackexchange.com/q/24646/25579) at [Cryptography SE](https://crypto.stackexchange.com).  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_2 on 2017-08-21. Score: 19
  
  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](https://xkcd.com/221/) 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.
  
  > **Comments:**
  > **username_0**: 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.  
  
  ---
  
  ### Answer by username_3 on 2018-09-09. Score: 5
  
  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](https://machinelearningmastery.com/learn-echo-random-integers-long-short-term-memory-recurrent-neural-networks/). 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]
  
  ```
  
  > **Comments:**
  > **username_4**: 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.  
  > **username_3**: 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.  
  
  ---
  
  ### Answer by username_5 on 2017-12-22. Score: 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 by username_6 on 2018-09-09. Score: 2
  
  Adding to what username_2 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.
  
  
  ---
  
  