Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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:
The answers in this thread all assume that the PRNG and TRNG are separate entities. The book Cryptography Engineering: Design Principles and Practical Applications by Bruce Schneier, Niels Ferguson, and Tadayoshi Kohno provides an answer to this question.
In summary, a PRNG with a TRNG as a source of entropy is a more robust solution than a TRNG due to the single point of failure. A PRNG can take entropy from any number of sources; the addition of sources reduces the likelihood of all entropy sources being controlled in an attack.
