Why do cryptographers need loads of true random numbers?

Question

I've just read an answer to fastest-random-number-generator. The answer is a couple of years old, but mentions a true random number generator capable of running at 300 gigabits per second. It is re-linked here. They might go even faster now. .

One time pads are out of favour. There's no point storing these numbers for reruns as you might as well use a psuedo random number generator. Most pundits on this forum suggest a maximum of 128 bits of true entropy for seeding. So why would cryptographers need so many true random numbers? Or is it just a *issing contest between researchers?

Answer 1

Mostly, you do not actually need a lot of true randomness, as you observed. However there are at least some niche cases where you might want a fast TRNG.

• Stateless implementations cannot use a typical CSPRNG. Something like a hardware token without writable storage, maybe. The intersection with applications that require a lot of speed is pretty small.
• Long term key generation. People tend to want true random numbers when generating long term keys. That is not usually a frequent event, but perhaps something like a federated key store would need to do it often enough.
• Latency. Even if you do not need gigabytes of entropy every second, getting e.g. 256 bits quickly can be important. Although again it is probably rare to need it and not be able to use a cache.

There are probably also use cases where the random numbers are used for non-cryptographic algorithms, but need to be both strong and non-deterministic. Maybe in gambling.

Answer 2

Cryptographers seldom, if ever, actually need true random numbers continuously and by the hundreds of megabit per second (or more), as in what's quoted. They do need random bits/numbers continuously at often much higher rates, and use Pseudo Random Number Generators towards that.

The only actual use that I know of >1 Mbit/s true random bits is to gather, with small latency, a few hundreds of random bits that an adversary can't guess by side channel attack in cryptographic hardware designed to resist such attacks; in such application it is more convenient (uses less silicon), and safer, to generate these bits, than to gather them in a buffer; and since the latency is $t=n/r$ where $n$ is the number of bits wanted and $r$ the bit rate of the source, there is incentive for large rate $r$.

I can also imagine an hypothetical device that needs to be operational a millisecond after power is applied, and uses crypto, which would have need for a fast TRNG for similar reasons.

---

Cryptographers often need values that adversaries can't guess, and for that purpose true random numbers (that it, derived from natural phenomena believed un-modelizable by adversaries) are a must. Uses include

1. key of an algorithm (including generating the keystream of a stream cipher)
2. challenge in a protocol (or nonce generated by a memory-less device)
3. choosing a random element in a set (or clock cycle at which some action takes place)
4. protection against side-channel attacks of a cryptographic device
5. keystream generation in a One Time Pad

In 1/2/3, it is not needed a lot of true random numbers; true entropy of 512 bit (which can be gathered by post-processing say 1024 bits produced by a source with a little bias and cross-correlation between bits) is usually more than enough for each use.

In 4, which occurs in Smart Cards and other cryptographic hardware, there's a need for a significant amount of bits that an adversary can't guess (about proportional to the data manipulated, with a multiplicative factor that varies between implementations); and because we are fighting leakage, the safe thing is to assume that a Pseudo Random Number Generator could be attacked by side channel too, thus it makes sense to use true randomness (with just enough post-processing to remove discernible bias, if any) as the source of the randomness; also, that simplifies the hardware.

In 5, if we did not use true randomness, we would be back to a stream cipher as in 1. Thus, by definition, it is needed as much true random bits as there is data transmitted using the OTP. But fact is, because the pad in the OTP must be securely transmitted, the OTP is extremely inconvenient, and I do not know that anybody is currently using it for significant amount of data; it historically has been used for small amounts of data, and occasionally broken, either because the pad was intercepted, or because there was not enough pad available and a pad was reused.

Answer 3

Looking briefly at the paper in the question that you're linking and reading a bit between the lines, it seems like the primary intended application for the high rates is simulations, not cryptography. Let me make the case.

First, in the introduction they mention simulation ahead of cryptography:

Random number generators (RNGs) are an important primitive widely used in simulation and cryptography.

Second, at the end of section 2.1 they tell us that the outputs of their RNG may be correlated:

A third factor affecting the quality of the RNG is the random source itself. As both periodic and aperiodic electromagnetic noise exists inside a computer system, there may be correlation in the output sequence as the result of coupling of periodic noise from the power supply, clocks, crosstalk, thermal effects and so on. This issue is not addressed in this work.

Third, in the conclusion they caution against prematurely using their RNG for cryptography:

This RNG would be suitable for simulation and cryptographic applications although for the latter, caution should be taken since the design is new, and it may be possible to attack the ASG [alternating step generator] construction given that the ONS [oscillator noise source] is weakly correlated.

And this quote, again, mentions simulation first and cryptography second.

---

I don't know much about simulation applications that might require such a fast RNG, but Googling a bit I did find one such reference:

• Botha, R.C. 2005. "The development of a hardware random number generator for gamma-ray astronomy." M.Sc. Physics Thesis. North-West University, Potchefstroom Campus, South Africa. (PDF here)

Abstract:

Pulsars, as rotating magnetised neutron stars got much attention during the last 40 years since their discovery. Observations revealed them to be gamma-ray emitters with energies continuing up to the sub 100 GeV region. Better observation of this upper energy cut-off region will serve to enhance our theoretical understanding of pulsars and neutron stars.

The H-test has been used the most extensively in the latest periodicity searches, whereas other tests have limited applications and are unsuited for pulsar searches. If the probability distribution of a test statistic is not accurately known, it is possible that, after searching through many trials, a probability for uniformity can be given, which is much smaller than the real value, possibly leading to false detections. The problem with the H-test is that one must obtain the distribution by simulation and cannot do so analytically.

For such simulations, random numbers are needed and are usually obtained by utilising so-called pseudo-random number generators, which are not truly random. This immediately renders such generators as useless for the simulation of the distribution of the H-test. Alternatively there exists hardware random number generators, but such devices, apart from always being slow, are also expensive, large and most still don't exhibit the true random nature required.

This was the motivation behind the development of a hardware random number generator which provides truly random U(0,l) numbers at very high speed and at low cost The development of and results obtained by such a generator are discussed. The device delivered statistically truly random numbers and was already used in a small simulation of the H-test distribution.

---

So it seems like some scientific applications want high quality random numbers at such high rates that conventional RNGs and PRNGs turn out to be a bottleneck. That would seem to be the motivation.

Answer 4

The RdRand instruction in Intel CPUs aims for high performance. This varies with product (E.G. Xeon RdRands are faster than low power SoC RdRands). The high performance is not there to meet a specific cryptographic need. But it is there to meet a specific security need - DoS prevention. We need to ensure that with any number of cores executing RdRand instructions as fast as they can, a core in the same system will still be able to execute RdRand and get a random number every time. This is achieved by making the DRNG faster than the bus to which it attaches so parallel executions on RdRand in multiple cores are serialized at the bus interface and the DRNG is able to service all those requests without underflowing.

Answer 5

Mainly because you need a large and random seed pool for using the more advanced ciphers. as the random numbers are commonly BIG BIG primes + some big random_number. If you have a small entropy pool ( seeding source pool) this is much harder to obtain / retain / confirm true randomness.