2
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ As a side-note: 128 bits is cutting it a bit low, especially if you don't have any measures to prevent multi-target attacks. I'd recommend going with 256 bits. $\endgroup$ – CodesInChaos Oct 25 '16 at 7:10
  • $\begingroup$ So even with the above increased and now hugely exorbitant requirements(!) you could generate the 256 bits in a little less than 0.9ns. $\endgroup$ – Paul Uszak Oct 25 '16 at 21:50
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I now realize that I have said the same thing as you with a lot more words... $\endgroup$ – fgrieu Oct 25 '16 at 10:54
  • $\begingroup$ @otus I think some gambling houses just use one of those cheapo USB stick TRNGs shoved into a Windows 95 desktop. I saw a certificate. I don't know whether it's a seed for a PRNG or used natively. I don't think that there is a legal requirement for true random numbers in gambling. 300 Gb/s seems high for Blackjack, even at the weekend. $\endgroup$ – Paul Uszak Dec 3 '16 at 13:34
  • $\begingroup$ @PaulUszak, I doubt anyone needs 300Gbps for gambling. That would require something like a billion concurrent players with most games' state being so small. But they do use more than just a cheapo USB, at least at some sites. And the latency issue may be a concern, if they don't want the entropy to sit in a cache. $\endgroup$ – otus Dec 3 '16 at 13:51
  • $\begingroup$ (Also, gambling sites need to appear very trustworthy, so a very over-engineered solution may be good for marketing reasons.) $\endgroup$ – otus Dec 3 '16 at 13:53
  • $\begingroup$ Per packet nonce generation in SSL network concentrators in data centers constitute the highest bandwidth demand for secure random numbers in use today. $\endgroup$ – David Johnston Aug 30 '18 at 6:31
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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:

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.

$\endgroup$
  • 3
    $\begingroup$ That part of the citation is deeply in error: "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 immediatelyrenders such generators as useless for the simulation of the distribution of the H-test." Fact is, output of a good PRNG is undiscernable from output of a good TRNG, thus if a good TRNG is suitable for X, then a good PRNG is suitable for X. $\endgroup$ – fgrieu Oct 26 '16 at 6:48
  • $\begingroup$ @fgrieu I think there might be philosophical and scientific reasons that mean a PRNG is not equivalent to a TRNG. It might be true for pulsars, I don't know I'm not a spaceman, but it's certain for working on Bell's quantum theorem for non locality testing. It's on the main NIST randomness beacon page. Clearly there's a difference as a PRNG can't make a OTP either. $\endgroup$ – Paul Uszak Aug 30 '18 at 9:13
0
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

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