1

More or less out of curiosity, what defines a random number generator to be cryptographically secure? Would testing for non-cryptographically secure and cryptographically secure generator different?

Related post here: How to test a random generator

Community
  • 1
  • 1
tll
  • 377
  • 1
  • 3
  • 12
  • Take a look at http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Requirements – AJMansfield Apr 11 '13 at 23:51
  • does this helps you? http://stackoverflow.com/a/2450098/702353 – Matías Cánepa Apr 11 '13 at 23:51
  • 1) As far as "what constitutes a 'Cryptographically Secure Pseudo Random Number Generator' (CSPRNG)?", Wikipedia has a good list of criteria: http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator. 2) As far as "How to test", you might consider Chi-square: http://en.wikibooks.org/wiki/Algorithm_Implementation/Pseudorandom_Numbers/Chi-Square_Test – paulsm4 Apr 11 '13 at 23:54
  • Short answer: You can't. That's why they fail so often. – CodesInChaos Apr 12 '13 at 12:59

2 Answers2

4

Testing a general-purpose random number generator for quality typically involves running various statistical tests which show that its results are not biased in certain ways. NIST has a set of tests that they use for this, detailed at: http://csrc.nist.gov/groups/ST/toolkit/rng/index.html

Showing that a random number generator is cryptographically secure is not a matter of testing at all — it's a matter of proof. This typically comes down to showing that, to predict the future (or guess the past) output of the RNG from a sample of its output (and, in some cases, even when controlling part of its input), one would have to defeat a cryptographic hash, cipher or other problem that is generally regarded as intractible. This is a fundamentally human-driven process; it cannot be performed mechanically.

  • I take issue with your end point "it can not be performed mechanically". There are a number of ways to show reduction mechanically, just because these mechanisms tend to require a PhD who knows the mechanization doesn't mean they don't exist. I would agree, however, to what I would bet is your response - the fact that it requires such an expert means the bar is too high for the mechanization to be meaningful. – Thomas M. DuBuisson Apr 13 '13 at 20:50
  • @duskwuff Thank you for your response. I have looked mostly into statistical tests but not much into the cryptographical tests. It makes sense that this process cannot be performed mechanically which makes testing for it essentially meaningless. – tll Apr 13 '13 at 22:08
  • Consider a program which generates "random numbers" by encrypting sequential numbers with a known key. This should pass all statistical tests, but is not actually random at all — if you know the key, you can decrypt one of the numbers and predict everything. Without the key, though, there's no way to even detect that this is what's happening, so no standard test can show that it's insecure. –  Apr 15 '13 at 20:28
  • I read through this article on statistical testing for RNG (http://www.johndcook.com/Beautiful_Testing_ch10.pdf) before posting this question, so I thought it would be interesting to know more as I have not done much work in cryptography to have a sufficient understanding. – tll Apr 16 '13 at 22:33
  • @tll Sorry to take up this old question, but I have come across the same situation where I need to evaluate the randomness of an RNG. I have read through the chapter you provide, but I am wondering what to do, if the tests described by John Cook don't give a decisive result. Any idea where to go beyond this chapter 10? – martin_wun Jun 26 '19 at 10:54
0

1) As far as "what constitutes a 'Cryptographically Secure Pseudo Random Number Generator' (CSPRNG)?", Wikipedia has a good list of criteria:

http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.

2) As far as "How to test", you might consider Chi-square:

http://en.wikibooks.org/wiki/Algorithm_Implementation/Pseudorandom_Numbers/Chi-Square_Test

paulsm4
  • 114,292
  • 17
  • 138
  • 190
  • 2
    Chi-square test cannot prove that a random number generator is cryptographically secure. All it can do is show that the RNG is not subject to certain types of biases — but this is not even sufficient to show that it's a good PRNG, let alone that it's secure! –  Apr 12 '13 at 00:02