4
$\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$
  • 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
  • $\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$ – BufferOverflow 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$ – Richie Frame 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$
  • $\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
-1
$\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 $>2^{256}$. Unless you have a cryptographic application that uses the full iteration length the PRNG is not the weakest spot in the cryptosystem. Taken PRNG like Blum-Blum-Shub or Fortuna the security is based on other cryptographic problems/ applications like quadratic residues (BBS) or AES and SHA-256 (Fortuna). So as long as they remain secure (or hard to compute) there should not be any pracitical reason to believe that a PRNG is less secure.

$\endgroup$
  • $\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$ – BufferOverflow Jul 11 '15 at 11:05
  • $\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

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.