5
$\begingroup$

How much more entropy gives a Hardware Random Number Generator or True Random Number Generator compared to a Pseudo Random Number Generator?

I know it depends on which TRNG is used, but I'm thinking in general. Does a TRNG generally provide more security than a PRNG?

$\endgroup$
3
  • 2
    $\begingroup$ Entropy does not equal security. A PRNG is deterministic given the seed data, it doesn't contain any entropy by itself. So the answer to the first question is: all the entropy in the TRNG. The second question is much harder to answer. It probably depends on how the RNG is being used. $\endgroup$
    – Maarten Bodewes
    Jul 10 '15 at 23:12
  • 1
    $\begingroup$ Sorry, I forgot to mention that, I was thinking of random numbers used in encryption. Isn't random numbers the holy grale in cryptography? Of course prime numbers are importen too, but prime numbers need also to be random. And if you can weakened the entropy in RNG, and create the random numbers that is more predictable, then the security of the encryption is also weakened? EDIT: I know some algorithms depends less on random numbers, and other more. But again, I speaking in general. $\endgroup$ Jul 10 '15 at 23:37
  • 2
    $\begingroup$ True random number generators sometimes generate bits with fractional entropy, or at random intervals, which then need to be "conditioned" by a PRNG of some kind. Intel RDRAND for example uses AES CBC-MAC mode to condition the entropy before sending it to another PRNG for output $\endgroup$ Jul 11 '15 at 0:40
4
$\begingroup$

Entropy as defined in information theory and cryptography is a difficult concept. One of the most common fallacies is that a piece of data has or "contains" entropy by itself. People who misunderstand this talk about bit streams having entropy, or measuring entropy of a piece of data. Or measuring entropy of a RNG.

To measure entropy you need a data source, plus a model. You compare the predictions given by the model (which are usually a-priori probabilities of certain results) with results from the data source (actual values received, and the probability of getting that result that the model provided before you looked) in order to assess the entropy generated by the data source with respect to the model*. What that means is the value you get for entropy varies depending on how you construct your model.

When considering security of a system, you can look for an "attack" model that tries to reduce the entropy of the system it measures by predicting its results. A successful attack model has a low measure of entropy against its target system.

Generally when looking at attacking cryptographic RNG systems, we look for the best possible model, and declare that the source being attacked has X entropy under that model. This sometimes gets conflated into saying a source (or password) has so many bits of entropy.

With that view, there is a sharp divide between good quality PRNGs and TRNGs. Namely, if your model of the PRNG is accurate and includes the correct seed then a PRNG has effectively zero entropy. But without the seed, and assuming a good quality PRNG, then we don't know of any practical models that can differentiate between a PRNG and a TRNG (also assuming the latter is properly whitened). That is, all known models fed with output from either a PRNG with unknown seed or TRNG will measure the same entropy (with statistical variation within expected bounds) Theoretical models can differentiate, because you could demonstrate a finite state by running e.g. $2^{256}$ iterations and seeing repetition.

This is partly self-defining. If a practical model was found that could separate a PRNG used for cryptography from a TRNG, and that demonstrated by showing a lower measure of entropy, then the PRNG would likely be abandoned for cryptographic use.

Does a TRNG generally provide more security than a PRNG?

In a theoretical model where you could make enough observations to figure out some of the state of a PRNG, then a TRNG that was essentially the same PRNG plus regular re-seeding from an unpredictable source would have higher entropy against that model.

The caveat is having an unpredictable source. TRNG sources are measurements of physical processes which have been chosen to be very difficult to predict (or for thermal noise or quantum sources, where the best theories to date model them as inherently random). The assertions about the source being unpredictable could turn out wrong. Or a more likely problem is that either the source or measurement process could be tampered with or intercepted.

So a short answer, with caveats, could be "Yes, a typical TRNG design could be considered more secure than its own PRNG component, because successful attacks against it would involve more work."

However, that is not the same as saying "This PRNG supplies less entropy than this TRNG" - without a qualifying model, the statement is meaningless.


* It is sort of possible to estimate entropy contained in a piece of data, but this is not as well defined, and is usually based on some assumption such as comparison with a simple model of a TRNG, compressibility etc. It is unwise to use these kinds of estimates when dealing with more formal definitions of randomness.

$\endgroup$
4
  • $\begingroup$ Neil has a great answer there! I would add that if you're not rolling your own system from scratch then it is almost certain that regardless of your entropy source it is still passing through some sort of PRNG or similar algorithm. $\endgroup$
    – gobbly
    Jul 23 '15 at 2:14
  • $\begingroup$ "meaningless" : Irrespective of opinions on the practicality of one time pads, a vastly meaningful distinction from an information theory perspective is that a TRNG can create a one time pad, whilst a PRNG can't. $\endgroup$
    – Paul Uszak
    Jan 18 at 13:46
  • $\begingroup$ An important thing that's missing from this answer is that a (crypto) PRNG is indistinguishable from a TRNG as long as there is a single instance of it. If the PRNG can be cloned (e.g. multiple devices seeded with the same value, or a cloned virtuam machine), this can be recognized easily and is a practical, major attack vector. $\endgroup$ Feb 8 at 13:03
  • $\begingroup$ @Gilles'SO-stopbeingevil' - I'm not sure why this answer has got attention recently, but I have changed my focus over the last year and not able to keep up with the good suggestions by crypto experts. I've made this a community wiki answer so commenters can be free to adjust as they see fit $\endgroup$ Feb 8 at 17:12
0
$\begingroup$

How much more entropy gives[sic] a Hardware Random Number Generator or True Random Number Generator compared to a Pseudo Random Number Generator?

Infinitely more.

A PRNG is a soft construct that features a 'state'. A memory if you will. The state is iterated and mathematically regurgitated to produce what is (mostly) computationally indistinguishable from truly random output. The Mersenne Twister (not cryptographic but a world class PRNG) has a huge state of $ 4.315424797388162648055235516337919839053935043226711505165... \times 10^{6001} $possibilities. That's 6002 digits.

Yet.

We can predict it's entire output with only ~620 numbers, and it all fits into (example) Apache Commons Math 6.8 MB of storage. Therefore it's Kolmogorov complexity (K) cannot exceed 6.8 MB.

The 'state' of a TRNG is physical matter. And if you've picked the right matter, it's state is undefined due to quantum indeterminacy and things like stochastic atomic orbitals and the uncertainty principle. Therefore it can't be defined without actually including the physical matter. And even then, universal quantum principles mean that it can't be replicated. It's really really random.

A school grade Arduino Uno samples (by default) at ~10,000 samples/s. In 11 minutes we can absorb the entirely of the Mersenne Twister/Apache Commons Math state. We can't hope to do that with a physical TRNG.

And so, with a little reductio ad absurdum:-

K(PRNG) ~ 0 whilst K(TRNG) ~ infinite.

I know it depends on which TRNG is used, but I'm thinking in general. Does a TRNG generally provide more security than a PRNG?

No. Maarten's comment to you addresses this well. Entropy ≠ security. There are nuances and implementation issues that mean it can all fall apart notwithstanding the amount of entropy. Remember that all digital randomness comes from programming code. Mess up the code, mess up the encryption → Firing squad.

$\endgroup$
0
$\begingroup$

Theoretically a TRNG provides more security, since its not deterministic and it cannot be predicted.

But provided a PRNG is implemented correctly the repetition period is very large e.g. $>2^{128}$. Unless you have a cryptographic application that uses the full iteration length the PRNG is believed to be equally secure against attacks if they are based on computationally difficult problems. For example, the security of Fortuna is based on AES (which is assumed to be secure). Or Blum-Blum-Shub (BBS) is based on the quadratic residues problem. As long as the underlying components remain secure and implemented correctly there should not be any practical reason to believe that a PRNG is less secure.

Some (reasonable) community suggestions:

  1. Tempering with the device or implementation: Generally, I believe that software implementations are easier to review than hardware.
  2. BBS is is generally considered to be more of academic interest as a learning example and not used in practice (not necessarily for security reasons).
$\endgroup$
10
  • $\begingroup$ I was thinking of the documents realesed by the whistleblowers past years about government surveillances, and how they actively has tried to weaken the randomness of the PRNG's to create they more predictable. In this case the security of the encryption is weaken, and it's easier to crack the encryption, not only for governments but for everyone who has knowledge about how the PRNG is made less predictable. $\endgroup$ Jul 11 '15 at 11:05
  • 1
    $\begingroup$ @BufferOverflow The same kind of trick could of course be used for a TRNG. Do you know if the TRNG in Intel chips can be trusted? It's not using Dual ECC but how are you going to prove the source trustworthy? $\endgroup$
    – Maarten Bodewes
    Jul 23 '15 at 14:31
  • $\begingroup$ Also for most people the implementation of the PRNG can be reviewed more easily than a hardware TRNG. For example the BBS: While it might not be easy to proove the unpredictability of the PRNG it can be coded very easily. The point of trust is that the complexity assumption (quadratic residues problem) is hard. $\endgroup$
    – Fleeep
    Jul 23 '15 at 14:43
  • $\begingroup$ I would champion otherwise. A diode and a hammer are pretty simple. Also consider the physical implementation of PRNGs (NIST 'Deterministic Random Bit Generator') in 11 layer silicon (i7). Audit that. $\endgroup$
    – Paul Uszak
    Jan 18 at 16:31
  • $\begingroup$ @Fleeep BBS is a toy CSPRNG. It is not intended to be used in practice. $\endgroup$
    – forest
    Feb 7 at 22:16

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.