2

When I look at most RNG's (random number generators), I see a disclaimer that looks similar to this:

Caution: Mersenne Twister is basically for Monte-Carlo simulations - it is not cryptographically secure "as is".

  1. What are the requirements for a (pseudo-) RNG to be 'cryptographically secure'? What tests/logic is used to decide that a RNG is secure for this purpose or not?

  2. What are the general differences between secure and non-secure RNGs? Are secure RNGs usually just far more complex/include larger seeds and more manipulation of data? Is it ever possible to make a non-secure RNG secure by adding a series results obtained from it or using a result as a seed to produce new results that are 'more random'?

  3. What is the problem with using non-secure RNGs for cryptography? I have no doubt that the cryptography would be much easier to break, but how is this actually done? Does the cracker somehow recognize a pattern in the data that is characters of a certain RNG and use this to help 'remove' the randomness from the clear-text?

NOTE: Please leave a comment if you think this question should be broken up; I know the different parts are related, but if they are complex enough to merit more specific treatment I will gladly separate them across multiple posts. :D

Gordon Gustafson
  • 121
  • 4

1 Answers1

2

I've written elsewhere about how we vet the security of a cryptographic primitive -- everything I wrote there applies equally to vetting the security of a cryptographically secure PRNG.

The difference between secure and non-secure PRNGs is that the secure ones are, well, secure. You could start by reading up on the definition of security for a cryptographic-strength PRNG. Starting with a non-secure PRNG and then trying to add extra complexity is not likely to be an effective way to end up with a secure PRNG.

The problem with using a non-cryptographic PRNG for cryptography is that you end up with with a system that is insecure. See, e.g., the example of early implementations of SSL in Netscape Navigator, which turned out to be breakable because they used a non-cryptographic PRNG in a place where they needed a cryptographic-strength PRNG.

In the future, I suggest asking these questions on Crypto.SE, and splitting them up into multiple parts. Or, better yet, take a look at a good cryptography textbook -- all of this should be covered there.

Community
  • 1
D.W.
  • 98,420
  • 30
  • 267
  • 572
  • 4
    I'd also add that the basic requirement is that you cannot create a predictor function, i.e. you cannot create a function such that `P(f(G(s)|1..n) = G(s)|n+1) > 0.5 + epsilon` where `f` is your predictor, `G` is your RNG and `s` is the seed without `f` knowing `s`. – Polynomial Apr 21 '12 at 15:12
  • 2
    @Polynomial or in general you cannot predict the next output bit with better than 0.5 probability in polynomial time even when knowing an arbitrary number of past output bits (wordy version) – Thomas Apr 22 '12 at 01:04
  • 1
    As long as you quantify "better than 0.5" as "0.5 plus some non-negligable value", then that's correct. I'd also go as far as saying that you don't need to qualify it as polynomial time - a break is anything with a lower time complexity than a bruteforce, which includes some NP solutions (e.g. `n log(n)`) – Polynomial Apr 22 '12 at 11:02