# Usage and limitations of sponge functions for PRNG

This HRNG uses SHA3 as a sponge function (in its device driver) to inflate ots raw source output to many MByte/s. They compare this output rate to the output of other HRNG which don't use a sponge function. I'm wondering if this comparison is fair and brings me to the question to which extend a sponge function should be used to inflate RNG. The goal should be to get entropy suitable for cryptographic operations (e.g. key generation).

Edit: In other words, if a sponge function could be used to inflate 300 kByte/s to 500 MByte/s without reducing the entropy, why--talking Linux--to use /dev/random in favour of /dev/urandom at all?

• I’m not seeing any thing there which criticizes the whitening algorithms method used by other TRNG. The criticism seems to bethat having any whitening on the TRNG device makes them more difficult to audit. This has nothing to do with the use of SHA-3, so can you clarify your question? Or at least point exactly to the statements you think are controversial? – rmalayter Jul 9 '18 at 10:35
• Note that the sponge function has been used for extending the output of the hash by the authors itself, explicitly even in implementing the SHAKE functions, which are eXtendable Output Functions (XOFs). So that it is used for a RNG makes a lot of sense and was to be expected. – Maarten Bodewes Jul 9 '18 at 13:03
• @rmalayter I added a link to the comparison table. It's not about criticising other's whitening algorithm and it's not about transparency. It is about comparing apples with oranges. – jans Jul 9 '18 at 14:03
• @MaartenBodewes I clarified my question. Please have a look. – jans Jul 9 '18 at 14:12
• Huh. I wonder what makes a \$35 dollar hardware cost deserve a green box and what makes something \$5 dollars more worthy of a red box. I wonder why 300kbit/s is green and 350 Kbit/s is red. Why is how fast a software RNG runs on the host CPU at all relevant? The advertised RNG outsources whitening to the host CPU. That speed is not a function of the hardware for sale. It's going to vary greatly based on the specs of your own (several hundred dollar) desktop computer. Why is free not in a green box? What miracle made the entire top row boxes all green? – Future Security Jul 9 '18 at 22:00

The only reason to use /dev/random is to wait until the system has loaded entropy. If you have waited once, it is generally safe to use /dev/urandom. It has nothing whatsoever to do with speed of output. There is no reason to ever read more than a single byte from /dev/random in an application. Writing a benchmark that measures time to read long outputs from /dev/random is incompetence bordering on dishonesty. Writing an application like GnuPG that reads more than a single byte from /dev/random is incompetence bordering on malpractice. The only excuse is that the historical documentation of /dev/random was also incompetence bordering on voodoo.

In general, to be secure, any random number generator must have at least a minimum amount of entropy—say, 256 bits—after which point you can safely draw arbitrarily long outputs using whatever pseudorandom number generator you like. There are perfectly good stream-cipher-based PRNGs. There are perfectly good sponge-based PRNGs. It doesn't make much of a difference to security which one you choose as long as it provides an adequate security level.

There's no reason that the PRNG has to be on the same hardware IC as the entropy source. Indeed, it is better if you can scrutinize the raw output of the entropy source to confirm that it has the biases it is predicted to have before you wire it up to a PRNG. If the IC just stores a secret key $k$ and a count $c = 0, 1, 2, \dots$ of the number of requests made to it, and returns $\operatorname{AES-256}_k(c)$, you will have no way to distinguish that from a true entropy source. Of course, an adversary selling you these devices might write an elaborate simulator for the physical system it is advertised to have, but that won't be replicated if you fabricate your own instance of a free hardware design.

• If someone can access getrandom they should use it instead of /dev/random or /dev/urandom. Let the value of "flags" be zero. If the flag GRND_RANDOM is not set then it will use the same source as urandom. When GRND_NONBLOCK is also not set then it will wait until /dev/urandom has enough entropy to be used safely. This makes the one use case of /dev/random unnecessary. – Future Security Jul 9 '18 at 21:14
• I know that I've championed AES RNGs, but isn't it possible to distinguish an AES-RNG after so many (lots & lots of) bits? Too many to worry about? – Paul Uszak Jul 10 '18 at 0:10
• @PaulUszak Suppose your device can generate one 128-bit block every nanosecond, which is about 14 Gbit/sec of output. A birthday attack on AES-CTR at that rate would take approximately half a millennium. – Squeamish Ossifrage Jul 10 '18 at 1:37

I'd say the comparison table is not a fair one, as it compares the Infinite Noise generator's throughput when feeding bits into a CSPRNG (Keccak) running on the host workstation and then running that CSPRNG as fast as the workstation allows. Other devices in the table achieve ~10 Mbit/sec speeds, but all of those devices in the table which had enough design documentation published on the web seem to advertise their throughput based on whitened output, but not on output expanded via a seeded CSPRNG on the host.

All of this is “much ado about nothing” however. A single 256-bit seed and a fast-key-erasure CSPRNG is all one should ever want in the real world. Don't create a persistent channel for attacker-controlled input. Or just use /dev/urandom.

• Upvote for fast-key-erasure CSPRNG, which I wasn't aware of. – jans Jul 10 '18 at 19:00

The usage of sponge functions for random number generators, or indeed other cryptographic processing algorithms is governed by the following golden rule of true random number generation:-

$$entropy_{in} > length_{out}$$

This is why entropy measurement is fundamental to all good TRNGs. It governs the overall architecture of the system, and is best illustrated by considering the cases of satisfying the golden rule, and not.

A. When $entropy_{in} > length_{out}$

In this case you have a TRNG that is unbreakable from an information perspective. Since less information is output by the TRNG than is generated internally, it is impossible to invert the output algorithm and obtain the raw input entropy which you might ostensibly call the seed. The consequence is that no cryptographic algorithms are necessary. Any of the typical entropy extraction techniques like simple matrix multiplication will do. /dev/random and the Quantis TRNG are good examples of this case. They both output less entropy than is harvested, although the latter device explicitly enumerates this ratio as $768/1024^{ths}$. This obviously limits the output of the device to less than the raw entropy generation rate. As harvesting of entropy inside a PC is very slow with an inconsistent and indeterminate rate, /dev/random is tricky to use and will often pause whilst more entropy is harvested. This blocking is it's attempt at satisfying the golden rule.

As OneRNG uses CRC16 for whitening, it probably fulfils the golden rule better than the others in your list. It's uncommon to get a raw entropy rate in any published TRNG.

B. When $length_{out} > entropy_{in}$

This is essentially a classic pseudo random number generator, as the input entropy remains constant for a long time, acting as a seed. Since enough information is produced by the output algorithm to theoretically invert it and obtain the seed, cryptographic primitives have to be used in an attempt to thwart attackers. This just makes inversion difficult, but not impossible from a mathematical perspective. /dev/urandom and Intel's RDRAND are good examples of this case. Output rate can be whatever bytes the CPU can compute given a seed.

The Infinite Noise TRNG falls squarely into this B category. You could even successfully argue that as such, it's not a real TRNG. Thus the comparison is not fair. What actual primitive is used is kinda irrelevant, and your example of SHA-3 is as good as any. Just ensure that it's not already broken cryptographically.

So the use /need of a cryptographic primitive is governed by the golden rule equation. Consider the difference as between the security properties of a one time pad and a general stream cipher, or a malt whiskey and a blend.

• Security is not guaranteed by lower entropy on the output generated by the device than the physical process has. Example: Let $X$ be a sample of some random physical process like a Geiger counter or an avalanche diode. Define $f(x)=0$ as the generator. No matter how large $E[f(X)]$ is, as long as it is positive, the entropy out is less than the entropy in: $E[f(X)]=0<E[X]$. So case (A) is false. Moreover, it is impossible for the output of a deterministic function of a random variable input to have higher entropy than the input in the first place: $E[f(X)]\leq E[X]$. So case (B) is nonsense. – Squeamish Ossifrage Jul 10 '18 at 2:05
• For (A), I demonstrated an example where entropy in (i.e., entropy of the internal physical process) exceeds entropy out (i.e., entropy of the combined physical-process-on-IC-with-USB-interface), and it is completely insecure because the entropy out is zero and the output is 100% predictable: it is always zero. So your conclusion that case (A) is ‘unbreakable’ is false. If that's not the conclusion you meant to say, you'll have to say something else. – Squeamish Ossifrage Jul 10 '18 at 14:17
• If you're not familiar with the definition of entropy, I suggest you avoid using the term or study the definition. There's a simple formula, but you have to understand how it fits into the conceptual framework of probabilistic models: it is a property of a state of uncertain knowledge represented by a probability distribution on possible outcomes. No single outcome has entropy. You may find it helpful to read an introduction like the first few chapters of Jaynes's Probability Theory: The Logic of Science or of McKay's Information Theory, Inference, and Learning Algorithms. – Squeamish Ossifrage Jul 10 '18 at 14:25
• If you're referring to min-entropy vs. Shannon entropy, yes, there are different notions whose definitions and place in the conceptual framework of probabilistic modeling are well-understood inside and outside cryptography. They are both types of Rényi entropy, and they coincide on uniform distributions, but min-entropy is more useful in cryptography. But your post, and your long history on this site, suggests that you haven't grasped any concept of entropy. The downvotes are not a conspiracy but reflect this consistent misunderstanding, which is why I recommend introductory texts. – Squeamish Ossifrage Jul 10 '18 at 15:32
• @PaulUszak No one qualified to talk about entropy and modern cryptography would conclude from this post that you understand what Shannon entropy is. Which is one reason why you got downvotes. – Future Security Jul 10 '18 at 17:32