# What is the use of REAL random number generators in cryptography?

I understand the use of pseudo-random number generators. I am not getting mixed up between these and "real" random number generators.

However, I don't understand for what a real random number generator is used. If it is not deterministic, how can it be used in an algorithm?

-
You need a real random number generators to seed the pseudo-random number generator. Additionally, most true random number generators require post-processing of the random output, which is often done using pseudo-random generators. –  j.p. Sep 20 '11 at 12:01
@jug Yup, entropy sources may even have a particular bias to bits valued 0 or 1. Normally you need at least a whitening technique to get something looking like a random number. Feeding that as a seed into a PRNG is certainly helping to get the right quality. Be careful not to confuse a source of entropy with a secure random number generator. –  owlstead Mar 20 '12 at 23:58

For some types of algorithms (or protocols) we only need non-guessable (by the attacker) bits/numbers, not reproducible non-guessable ones (like from a deterministic PRNG).

In this cases, "real" random numbers are in theory (i.e. from an information-theoretic point of view, not a cryptographic one) better, since they can't be guessed (or even influenced) by an attacker, even if she could break our PRNG.

Some cases that I can now think of, where we don't need deterministic random numbers:

• key generation (both symmetric and asymmetric)
• initialization vectors for block cipher modes of operation (these are usually sent with the message, so the same plaintext will not result in recognizable ciphertext for the next message)
• random padding in asymmetric encryption (for example OAEP)
• salts for password storage (these are stored with the hash)
• challenges in zero knowledge proofs (sent to the partner)
• random values used in digital signatures (the k in DSA)
• one time pads (OTP) (Here, for the security proof, we actually need "real" random numbers.)
• chaffing and winnowing

In practice, pseudo-random bits are cheaper and just as secure for real-world attackers (e.g. with resources limited by our earth mass and universe lifetime), as long as the PRNG is not broken and has enough entropy input to start with.

(If the attacker can control the seemingly random input to the "true random" generator, this would be even worse than a good PRNG.)

Often for these uses we use a combination of a cryptographically secure (deterministic) PRNG and an entropy pool, which gets filled (and re-filled) by random bits gathered by the OS. This would be a non-deterministic PRNG.

-
So basically the use for a REAL random number generator is for creating random bits, to reduce entropy, because humans cannot think of data that is truly random –  liamzebedee Sep 20 '11 at 5:43

Many of the uses of a True RNG fall into the general category of generation, without persistent storage, of a value that is different with high probability from any value determined otherwise.

A value that is different with high probability from any value determined otherwise is very useful in cryptographic protocols. For example, under classic CBC encryption with multiple messages enciphered with the same key, an IV needs to be distinct from a previous IV (which is necessary to conceal a possible repeat of the plaintext), and distinct from the XOR of the first block of plaintext with any value that has or will ever enter the input of the block cipher (which is necessary to ensure confidentiality of that first block of plaintext under the assumption that all other plaintext is known).

"Without persistent storage" requirement rules out a Pseudo RNG, and greatly simplify things: in the case of PRNG, persistent storage needs to be made confidential and/or integrity-protected, which is plain impossible on a regular PC under the basic "maid boots USB stick" security threat. Sometime there is just no persistent storage (boot from CD-ROM), or it is a bit slow.

Another reason to use a True RNG is protection of the implementation of a cryptographic algorithm from side-channel attacks, a process often called "masking". For example, protection against DPA of the crypto-engines used in Smart Cards uses random data for that purpose. Using a Pseudo RNG here would create a chicken-and-egg problem (since secure PRNGs use cryptographic algorithms); while this might be solvable, it is simply easier and much faster to use a TRNG.

-