Exactly how is a pseudorandom number generator a security risk?

Question

I was recently reading about Diceware, which is essentially a list of words from which several can be picked to form a long passphrase. The website stresses that these words should be picked randomly by throwing physical casino dice, rather than an electronic random number generator:

You can purchase a set of five casino-grade dice online from Amazon.com or Ebay.com for about $16, but they are overkill for this purpose. Do not use a computer program or electronic dice generator.

I've heard this before: electronics are not able to generate truly random numbers, but only pseudorandom numbers. As far as I understand from Wikipedia, they essentially take an input (like the current time in milliseconds), do some calculations with it to arrive at a bunch of digits, which should finally resemble a random number. If you run the same calculation again with the same input, it should return the same result.

It seems this pseudorandomness is not good enough for encryption, but it is not clear to me why that should be the case. Let's say I wrote a small script that does what was described above (e.g. current time in milliseconds, takes the square root and takes the digit before the decimal point if it's 1-6) to simulate a dice throw. This is a (bad) pseudorandom number generator, but how exactly does this help me to guess the passphrase I create with this method?

Answer 1

The recommendation on the Diceware site is based on the assumption that the user is a non technical person. A dice has a very simple construction, and it's pretty obvious to any person how a dice works. It is much easier for a non technical person to verify that a dice throw will produce a random result, than for them to verify how an electronic PRNG computes a random number. Even for the smartest of technical people, it takes years of study of very specialised form of discrete mathematics to be properly qualified to evaluate the mathematics of a CSPRNG.

The other main problem with electronic PRNG is that most of the popular PRNGs are designed for speed, not for security purpose; a cryptographically secure PRNG is much slower than normal PRNG. They're also quite fickle, it's fairly easy to use a CSPRNG to produce random looking numbers that turns out to barely contains any randomness (examples: Debian's OpenSSL fiasco). A physical dice a lot easier to use correctly than a CSPRNG. It is much easier to teach non-technical user to use physical dice correctly, than it is to teach an experienced programmer to write code that uses CSPRNG correctly or to teach seasoned system administrator to setup a system with the proper environment to run a CSPRNG code.

With that said, in modern system, it is possible to write an pseudo random number generator that's suitable for pass phrase generation purpose. As long as you're aware of the twenty thousand or so caveats and precautions, it can be just as secure as physical dice. Its fickleness and opaqueness though, makes it much easier to recommend a dice to non technical users and most technical users.

Let's say I wrote a small script that ... current time in milliseconds, takes the square root and takes the digit before the decimal point if it's 1-6) to simulate a dice throw. ... how exactly does this help me to guess the passphrase I create with this method?

If you seed your PRNG using the current date time in milliseconds and the attacker knows or guesses that you generated the passphrase sometime around 2018, then this reduces the range of possible passphrases significantly. Instead of having to search 7666^6 = 77.5 bits of entropy for a 6-words passphrase, knowing just the year that the passphrase was generated allows the attacker to only need to search 31536000000 possible passphrases (the number of milliseconds in a year), which is equivalent to 34.9 bits of entropy (a modern computer can brute force this in a few hours, or minutes with GPU).

Answer 2

When Diceware was first proposed more than twenty years ago, many of the computers that people used did not have easy access to Cryptographically Secure PRNGs. And, as noted in other answers, most people are not in a position to determine whether or not the PRNG they are using is cryptographically secure.

A Cryptographically Secure PRNG is, indeed, cryptographically secure. And so using a CSPRNG is perfectly fine for generating diceware like passwords. However, before rolling your own generator, there are other things to worry about, such as modulo bias. If you are curious, take a look at the wordlist generator used by 1Password (for which I work).

Don't fear the "pseudo"

A lot of people get scared away by the "pseudo" in "PRNG", but that is perfectly fine when you also have the "CS" for "cryptographically secure". Let me give a rough pair of definitions to help understand the difference between a CSPRNG and a True RNG.

With a True RNG, which outputs a stream of bits, if you are given all but one of the N bits, for any N > 1, from bit zero through bit N, there is no algorithm that can give you a better than fifty percent chance of guessing that one bit you were not given.

For a CSPRNG the definition is the same, with the following changes:

• There is a (very large) upper limit to N (the number of bits you get).

• The "no algorithm" is replaced with "no probabilistic polynomial time (PPT) algorithm"

• The fifty percent becomes "really, really close to 50% but not exactly 50%." (Note that this is about your ability to guess given the N - 1 bits and your PPT algorithm.

Those are the same sorts of things that are built into other cryptographic security notions. When we say that an encryption scheme is secure we mean that there is no PPT that even on very large input or trials (but there is some limit) gives a a better than almost exactly a 50% chance of guessing a bit of the secret.

Again, this is a rough definition. A complete definition requires some more machinery in defining things like the limits on N, the time given to the PPT, and the "almost" of "almost exactly".

So a CSPRNG (as long as it really is cryptographically secure) is secure in the same way that other parts of your cryptographic should be.

Good seeds and bad seeds

Assuming that you have a CSPRNG, the difficulty is generating the key or "seed" for it. But most operating systems today have good solutions for this. (They tend to frequently reseed the underlying CSPRNG with truly random data. The reason that they don't just use the truly random data is that it is hard to get a lot of such bits quickly enough for applications that need a lot of randomness, so because the truly random bits are more expensive, they are used to just seed the CSPRNG.)

The do not

essentially take an input (like the current time in milliseconds), do some calculations with it to arrive at a bunch of digits, which should finally resemble a random number.

But you are correct that badly seeded CSPRNGs have been known to cause major security problems.

A good system won't use the current time, but may use time jitter as one of several sources of true randomness. Many systems today use specially designed components of chips that are built to produce random static. Other physical measurements used. Once the system decides that it has enough of this sort of data to munge and smooth out to get an appropriate amount of true randomness is will also blend this in with the secret state of the CSPRNG to create a new seed.

This helps illustrate why true RNGs are "expensive" in that they can't produce very large amounts of random data quickly. But they can produce enough to frequently reseed a CSPRNG, and so on modern systems, we do have access to RNGs that are safe to use cryptographically.

How can PRNGs be a risk?

With the whole "pseudo" question out of the way, I can answer the main question. There are two ways that things can go wrong cryptographically with a PRNG. One is that it is not cryptographically secure. In such cases it is possible for a polynomial time algorithm given reasonable output a meaningful advantage at guessing bits of output. The second way is for a CSPRNG to be badly seeded.

Bad PRNG

In the case of a bad PRNG (not cryptographically secure), if the attacker knows enough output (say it appears in non-secret nonces, initialization vectors, and other output) then the attacker can gain a meaningful advantage at guessing the secret output.

This can lead to reducing the search space for generated keys to a small enough size that it is practical to do so. Indeed, for some PRNGs knowing a small chuck of output can give you complete information about what the generator produced before and after that particular chunk of output.

Bad seed

In other cases, the CSPRNG may indeed be cryptographically secure, but badly seeded. If the seed is chosen from a small, somewhat predictable range, such as seeding with the time or seeding with a 32 bit value, then the attacker only has to search through possible seeds to recreate the state of the CSPRNG.

In either case, you can end up with the same secret being generated too many times. And typically use of an insecure PRNG is accompanied by use of a weak seed, so the attacker will have two things to use.

Answer 3

A real-world example of the hazard was that a weakness in the PRNG used by PGP resulted in a lot of duplicate "random" primes, resulting in a lot of duplicate private keys. Bad guys, instead of having to search the nearly infinite set of 100 digit primes, only need search the much smaller set of primes produced by the PRNG.