7
$\begingroup$

Cryptographic applications use deterministic algorithm for random number generation that are not statistically random but they appears to be random.

Why do cryptographic applications use PRNGa instead of TRNGa?

$\endgroup$
10
$\begingroup$

Expanding small shared secrets

In many cryptographic systems, it's necessary for the two honest parties to have a shared secret between them such that:

  1. The attacker cannot easily guess it.
  2. It's large enough to protect a large volume of data.

For example, the one-time pad tells us that if two parties have a shared secret at least as large as the message, that is sufficient to communicate the message confidentially.

But the fatal problem then is, how do the parties manage to establish such large shared secrets? And the practical solution is to:

  1. Establish a small shared secret instead of a large one—say, 128 random bits—as the key.
  2. Use a secure, deterministic PRNG to expand the key into a long, pseudorandom bit stream that's guaranteed to be the same on both sides.

This is for example how stream ciphers work.

Engineering challenges of TRNGs

How do you build a true random number generator so that it's:

  1. Correct: Is the output actually random? I.e., no bit of the output must be predictable from any other. How do you prove this? There are physical processes that science says are truly random, but does your machine introduce some predictable measurement errors into the system, and does your TRNG reliably remove these?
  2. Reliable: Doesn't fail often, and when it does you can tell it did.
  3. Auditable: The users can actually verify for themselves that it is correct and reliable.
  4. Performant: Produces random bits at a sufficiently fast rate.
  5. Efficient: Doesn't use lots of power.
  6. Affordable: Doesn't cost a lot of money.

It's not easy at all! Cryptographically secure PRNGs are better in nearly all categories. Their only downside is that by definition they cannot truly random—but given a slow TRNG to provide seeds for the secure PRNG, that's a theoretical, not a practical downside.

Some of the techniques used in true RNGs are actually quite educational about the value of PRNGs. For example, one common technique in TRNGs is to XOR the TRNG's output with that of a PRNG. The reason for this is that way if the TRNG's true random components fail silently or are just not correct, the pseudorandom data mixed into the output can serve as a backup to keep the security level above a certain baseline.

That's an example of using a PRNG to address the engineering challenges of building a TRNG.

Cost effectiveness

The cheapest secure solution for most applications is to use a slow source of true random data to periodically seed a secure PRNG. By allowing that source of true randomness to be very slow (produce random bits at a low rate), it makes all the engineering challenges easier. By using noise from peripherals that the computer already has (e.g., keyboard, mouse and network timings), it reduces the cost even more, and makes it easier for third parties to audit than a custom, proprietary device would.

The resulting system is not truly random, but it just needs to be good enough, not theoretically perfect.

$\endgroup$
  • 3
    $\begingroup$ I think this is a great answer (especially the middle part), but I'm not sure that I like the fact that a stream cipher and a PRNG are tossed together. There are different considerations to be made between a stream cipher and a DRBG. The later has e.g. interfaces for reseeding etc. I think the question, by comparing TRNG and a PRNG is mainly focused on that. The uses of a shared secret are in that case inconsequential to the answer and targets a different use case. My point here is made explicit by the fact that e.g. NIST has different standards for DRBG's and ciphers. $\endgroup$ – Maarten Bodewes Jan 9 '17 at 15:22
  • $\begingroup$ @MaartenBodewes: I agree that the distinction between "stream cipher" and "DRBG" is precise and practical. But: (a) I routinely see a lot of vague talk about "CSPRNGs" that doesn't make that principled distinction; so (b) I don't read the question as narrowly as you do, because I assume much of the audience won't read it as a narrow DRBG vs. TRNG question; and (c) I think going into the terminology and interfaces issue at length would have been a big digression. $\endgroup$ – Luis Casillas Jan 9 '17 at 21:32
  • $\begingroup$ That's ok. Lets just leave my comment here for those that do want to know that there is a distinction =) $\endgroup$ – Maarten Bodewes Jan 9 '17 at 21:34
3
$\begingroup$

Computers are simply incapable of generating true randomness because they are designed to be very accurate binary machines. Seeing as most cryptographic functions are implemented on computers they must settle for PRNG's

A Cryptographicaly secure PRNG has additional requirements that make it difficult for an attacker to guess the output if they know the seed, however they are all PRNG based. Examples of this might be to include mouse movement or key press timings in to the equation.

Random.org for example provides random numbers drawn from a variety of sources but if you use such an external source you then have to worry about the security of transporting numbers. Or you could start looking at hardware devices like this quantum device. This WIKI page goes over the hardware solutions in more depth.

You are correct to be worried about this because secure random number generation is at the heart of all modern crypto. If I could workout the random number you selected for a DH key exchange then TLS is broken.

$\endgroup$
  • $\begingroup$ You can but generally it's related to cost. Silicon is cheap, and compared to what we spin on sapphire wafers, anything on Si is very slow. You can get a TRNG on silicon a few dozen ways by putting a radio isotope down. I've had Si32 deposited for this reason, but you'll never find this on any x86. $\endgroup$ – b degnan Jan 8 '17 at 21:12
  • $\begingroup$ Yes. Hardware solutions are available but I doubt many consumers are going to want decaying radioactive materials in their CPU's (despite the fact they exist in your smoke detectors) $\endgroup$ – dave.zap Jan 9 '17 at 1:33
  • $\begingroup$ if they only knew :) $\endgroup$ – b degnan Jan 9 '17 at 2:49
1
$\begingroup$

There are many reasons for using a Computationally Secure PRNG. One of the most important reasons is probably that - as long as it is well seeded and if the state is well protected - a CSPRNG is very reliable.

One of the things that catches most people by surprise is the very high resistance against cycles (repeats of the internal state) of CSPRNG's.

A PRNG (or, to use another name, a DRBG) is very likely:

  • not dependent on the OS;
  • not dependent on specialized hardware;
  • much faster;
  • thread safe (again, depending on the implementation);
  • non-blocking;

As already indicated you still need a source of entropy. It's very beneficial for this to be an on-chip TRNG with user available instructions, as you don't want to rely on other peripherals. For instance, if you have a VM or a headless device with SSD and high performance network card, you may not have too many reliable entropy sources.

However, once you have enough entropy - preferably from different sources - there is nothing wrong with using this to seed a PRNG. That way you can combine the security of all the entropy sources (and then remove most of the reliance on them).


Of course the reliability is not counting constructions such as the Dual-ECC generator that has likely been compromised by the NSA. Then again, how do you know that your hardware device is not compromised? The issue of compromise is also much less likely for hash based schemes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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