14
$\begingroup$

I'm studying for random number generators(RNG) and I saw about machine learning a few days ago. So I searched analysis of RNG using machine learning. But I couldn't find such fields. Are there such examples for analysis of RNG using machine learning? No matter some papers of articles.

Improve this question
$\endgroup$
2
  • 4
    $\begingroup$ Are you asking if machine learning could analyze THE OUTPUT of a (P)RNG? Or if machine learning could analyze THE DEFINITION of a PRNG? $\endgroup$
    – fgrieu ♦
    Mar 26, 2015 at 15:50
  • $\begingroup$ Exactly, I meant that target is THE OUTPUT of PRNG. There are many method to determine randomness of output string. So I just wonder if I can predict some of strings using concept of machine learning. $\endgroup$
    – Tylor Yoo
    Mar 27, 2015 at 8:57

4 Answers 4

Reset to default
3
$\begingroup$

The goal of an ideal cryptographically secure pseudo-random number generator (CSPRNG) is to produce a stream of numbers that no machine can distinguish from a truly random stream of numbers. Formally, it's impossible unknown whether it's possible to prove that a CSPRNG is truly random.

That being said, there exists a family of statistical tests that can measure whether a sequence of numbers appears to be uniformly random, and produce a probabilistic analysis as output. I'm not sure if these tests qualify as related to machine learning, but here are some examples:

If you are interested in trying out a CSPRNG, you can use:

  • AES-CTR with a random key acting as the seed.
  • Under Linux, Mac OS X, BSD, /dev/urandom.
  • window.crypto.getRandomValues() in your browser console (Chrome, Firefox).

Note that not all PRNGs are CSPRNGs.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I'm pretty sure those tests are not considered "machine learning". $\endgroup$
    – Maarten Bodewes ♦
    Mar 26, 2015 at 15:49
  • $\begingroup$ Shrug I thought so as well, but hopefully my answer can be somewhat helpful either way. $\endgroup$
    – Nadim Kobeissi
    Mar 26, 2015 at 15:54
  • $\begingroup$ It's good background info, I'm not sure if it qualifies as an answer. AES-CTR is close but not quite a CSPRNG I guess, it does not offer re-seed possibilities for instance. $\endgroup$
    – Maarten Bodewes ♦
    Mar 26, 2015 at 16:10
  • 1
    $\begingroup$ You can transform a block cipher in CTR mode into a RNG using NIST's CTR_DRBG, I'm pretty sure. $\endgroup$
    – pg1989
    Mar 27, 2015 at 2:28
  • 1
    $\begingroup$ Hi, kaepora. Thank you for your answer. Your answer is really helpful to me. $\endgroup$
    – Tylor Yoo
    Mar 27, 2015 at 8:50
3
$\begingroup$

Consider the limitations of such an analysis. It can summarily reject a PRNG as being insufficiently random by demonstrating that the outputs are predictable by a computer program. However, its ability to generate comfort as to the randomness of a PRNG is limited. We have mathematicians going through hoops with months of mathematical analysis to prove that a flaw exists, much less find the flaw outright. Often a "broken" algorithm is shown to break after petabyes of random numbers, which becomes an indication that it will continue to be attacked in less and less time, until any old laptop can break it. Those studying PRNGs would want a little more warning than "a computer program has actually cracked it."

It might be interesting to use such machine learning programs for high performance PRNGs that do not have any cryptographic guarantees. They might be able to help explain to a programmer or artist the limitations of a particular PRNG choice for their particular job, rather than relying on highly abstract measures of unpredictability.

Improve this answer
$\endgroup$
2
$\begingroup$

The NIST test suite for random numbers implements "short-term memory" machine learning algorithms.

It needs to save and categorize all relevant data to be "long-term memory" machine learning.

Paper: http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf

Suite: https://gerhardt.ch/random.php

Improve this answer
$\endgroup$
0
$\begingroup$

You may use binary classification algorithm like decision tree and have two learning data sets one which has the truly random bytes and the other puesudo random bytes. As you might probably know, you have to specify the size of every record say for example 1k.

It is really a good idea.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ This (probably) won't work. There is certainly structure in CSPRNG's that could potentially be exploited, but I don't believe naive classification will be powerful enough to yield a distinguisher for any nontrivial CSPRNG. $\endgroup$
    – Thomas
    Oct 3, 2015 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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