16
$\begingroup$

I understand the output of a TRNG is almost impossible to reproduce, such a flipping a coin 100 times to produce a 100-bit sequence. However, it is also my understanding that a CSPRNG produces an unpredictable output.

  1. If they are both non-deterministic are they not the same? Are they not both producing unpredictable outputs?
  2. Do we not use both TRNG and CSPRNG to produce sessions keys?
  3. Can we (do we?) use TRNG to produce CSPRNG?
$\endgroup$
  • 3
    $\begingroup$ This When is an RNG a CSPRNG, a CSRNG, or a TRNG? may help. $\endgroup$ – kelalaka Oct 29 '18 at 8:29
  • $\begingroup$ Possible duplicate of When is an RNG a CSPRNG, a CSRNG, or a TRNG? (I merely refrained from close-voting since the linked Q is one that was asked by me in 2017.) $\endgroup$ – e-sushi Nov 2 '18 at 1:29
  • $\begingroup$ @e-sushi I think there are notable difference between our questions. However, having now read yours and the answers to it I better understand the whole idea of random generators. $\endgroup$ – Red Book 1 Nov 2 '18 at 13:53
  • 1
    $\begingroup$ @RedBook1 In the end, that’s what counts. ;) $\endgroup$ – e-sushi Nov 3 '18 at 6:03
27
$\begingroup$

A True Random Number Generator uses a physical phenomenon not known to be fully deterministic as origin of the discrete values (bits or integer numbers) that it outputs. That phenomenon can for example be a dice throw, thermal noise, disintegration of a radioactive substance… What detects this phenomenon can be followed by a conditioning stage to turn the output into an (at least, near) ideal sequence of random bits. The conditioning is often an integral part of the TRNG.

The archetypal conditioning stage is the Von Neumann debiaser: it groups the values at its input (such as dice values, binary output of a clocked comparator, count of clock cycles between events…) into pairs, and outputs 0, nothing, or 1, depending on if the first element in the pair is less, equal or more than the second. If the input was consisting of independent values, the output (if any) would be independent random bits with 50% probability for 0 and for 1; that is, truly uniform independent random bits (hereafter: ideal randomness).

Unless otherwise stated, a TRNG can be imperfect to some degree: it is to be expected that a statistical test distinguishes its output from ideal randomness.


A Cryptographically Secure Pseudo Random Number Generator is a deterministic (hence the pseudo) computational method to turn an input (typically short or low-throughput, and explicit unless otherwise stated) into a (typically arbitrarily long or/and high-throughput) sequence of bits that are indistinguishable from ideal randomness, with cryptographic certainty, for a computationally bounded adversary not knowing the input, assumed secret and not reused.

In a cryptographic context, a CSPRNG can be abbreviated PRNG or PRG. But in other contexts, not all PRNGs are cryptographically secure. The Mersenne Twister is an example of PRNG that is not cryptographically secure.

A Cryptographically Secure Random Number Generator (not Pseudo) is a random generator with no explicit input, and which output is indistinguishable from ideal randomness, with cryptographic certainty, for a computationally bounded adversary assumed able to attack multiple instances of the CSRNG and obtain multiple output sequences (the adversary can use one CSRNG to attack another; restart the CSRNG, in some attack model s/he can attempt to exploit side channels, inject faults in the calculations made, or/and shutdown power at any time).

The archetypal deterministic CSRNG is built from a CSPRNG and a random secret seed that is not reused (perhaps, with help of permanent memory surviving a power cycle). That is essentially the only way to build a CSRNG without some form of TRNG.

The archetypal non-deterministic CSRNG is built from a CSPRNG, and a TRNG which output is used as input of the CSPRNG at start of each sequence (including power-up). The idea is that the cryptographic strength of the CSRNG comes mainly from the CSPRNG, and the unpredictability across multiple sequences and instances comes from the TRNG.

Note: there are more complex constructions, where the TRNG's output influences the CSRNG continuously, so that hopefully, security will eventually be recovered after a compromise of the CSPRNG state. A Unix /dev/urandom typically uses this strategy.

A TRNG can be a CSRNG. Any CSRNG must include a TRNG, or must have made use of one as the origin of some secret value at an initialization stage (otherwise, knowledge of the CSRNG structure would allow to predict its output).


It is notoriously difficult to make a good non-deterministic CSRNG even by applying the above principle and using a good CSPRNG. One reason is that in practice, TRNGs often fail, spontaneously or under adversarial influence (for example, an adversary can reduce thermal noise by putting the device in cold condition using evaporation of some liquefied gas, or remotely feed controlled events to a sensor of disintegration). If that goes undetected, the output of the TRNG can become highly predictable, and knowledge of the PRNG will allow to predict its output. Thus a practical non-deterministic CSRNG must test its TRNG, and somewhat prevent any output when it does not operate properly.

On the other hand, a deterministic CSRNG must permanently keep its state secret. Due to the possibility of side channels attacks that's difficult when the adversary has physical access, and it turns out that methods to guard against side-channel attacks require random numbers in vast quantity! Also, there is understandable prevention against fully deterministic RNGs. This adds up to make fully deterministic CSRNGs a rarity in modern high-security cryptographic designs.


Summary of terminology:

  • A TRNG is not deterministic. Unless otherwise stated, that's its only defining characteristic.
  • A CSPRNG is deterministic, has an explicit input (unless otheriwse stated), and, with cryptographic certainty, its output is indistinguishable from ideal randomness by a computationally bounded adversary if its input is random, secret, and not reused.
  • A CSRNG has no explicit input, at least appears not deterministic, and its output is computationally indistinguishable from ideal randomness by a computationally bounded adversary. It can be deterministic, or not. In the former case, it's a CSPRNG with a random secret key that is not reused. In the later case, it includes (or perhaps is) a TRNG.
  • In a cryptographic context, PRNG or just PRG is synonymous with CSPRNG, and RNG might be synonymous with CSRNG (especially when using a RNG in another construct, rather than discussing its properties). But in non-cryptographic contexts, don't assume any security property from the acronym PRNG: in many programming languages, the default implementation is not cryptographically secure.

If they (TRNG and CSPRNG) are both non-deterministic are they not the same? Are they not both producing unpredictable outputs?

A CSPRNG is deterministic, and never is a TRNG; and vice versa.

Do we not use both TRNG and CSPRNG to produce sessions keys?

Often we use a CSPRNG initialized with a shared secret and some other element (like a nonce) to initialize session keys, so that the session keys needs not be transmitted secretly.

If we use the output of a CSRNG or TRNG as a session key, we need to encipher the value produced on one side to transfer it to the other side, which has no way to produce the same session key independently. Further, it we use a TRNG directly, we must use one that is close enough to a CSRNG that the key can't be guessed (that's an issue for short keys).

Another practice is to use a CSRNG or TRNG (often, one on each side) as input to an asymmetric key exchange protocol (like Diffie-Hellman) to produce a shared secret session key.

Can we (do we?) use TRNG to produce CSPRNG?

No. But we often use a TRNG and a CSPRNG to produce a CSRNG.

$\endgroup$
  • 1
    $\begingroup$ Aren't there lots of PRNGs that completely insecure in the crypto sense? I'm not sure if grouping CSPRNGs and PRNGs together is a good idea even in summary. $\endgroup$ – ilkkachu Oct 29 '18 at 13:43
  • 2
    $\begingroup$ I'm beginning to realise that the true challenge in TRNG design is entropy measurement. And that still seems to be an open question. $\endgroup$ – Paul Uszak Oct 29 '18 at 15:45
  • 4
    $\begingroup$ @Paul Uszak: per my definition, an entropy source needs not have an output consisting of bits or discrete values / needs not be a Random Number Generator; when a TRNG output must be discrete. For example a radioactive source (even together with the gizmo that makes an electric pulse when there's a decay) is an entropy source, but not a TRNG, because it does not output bits; sample the output of said gizmo with a clock, and you have a TRNG (with terminaly biased and dependent bits). Same for a reverse-biased (zener) diode, which is an entropy source but by itself does not deliver bits. $\endgroup$ – fgrieu Oct 29 '18 at 16:53
  • 1
    $\begingroup$ @PaulUszak The true challenge is nothing more than reliability, requiring some designs to even use redundant but identical noise sources and checking for correlations indicative of failure. Approximate entropy measurement itself is so easy that there are standards for it, so it is not an open question anywhere other than in your mind. Note that such measurements are designed to check for statistical failures, not to actually quantify entropy (this seems to be something you frequently misunderstand). $\endgroup$ – forest Oct 29 '18 at 22:30
  • 2
    $\begingroup$ @PaulUszak I believe it is described in the SP 800-90B document as an example debiaser. And yes, they are necessarily awfully simple (just as Von Neumann extraction is so simple), otherwise it would be a whitener, not a debiaser, and would invalidate any randomness tests done on it. It works as a debiasier because it is a very simple (if not the most simple) compression technique. $\endgroup$ – forest Oct 30 '18 at 0:12
2
$\begingroup$

They both appear random, but:-

  1. A TRNG is a physical device that produces a non deterministic output. You have to be able to hold a TRNG in your hand.

  2. A CSPRNG is a mathematical algorithm that always produces an identical output given the same initial state. It's deterministic.

$\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.