7
$\begingroup$

To give a little background I'm currently implementing a crypto library in JavaScript.

I have started porting across Linux's random number generator because its both publicly scrutinized, it is open-source, and is extremely well documented. After browsing around other implementations before settling on Linux's RNG, most of the other implementations like the Mersenne Twister and other PRNGs all use single byte seed values as their single source of entropy and to add more entropy you simply XOR the seed value with your "stream of entropy". Linux's RNG however uses a pool of entropy which consists of, as it sounds, a larger array of "seed" values in which all are considered to have a high amount of entropy. To add entropy, you simply XOR the entropy into the pool and mix it around with a few polynomials and hash it all to hide the internal state.

What I want to know is what are the benefits of using an entropy pool over a single byte seed value? It also sparks the question, considering Linux's RNG is used almost globally across the entire kernel and by every application requiring random data, is the "seed" or entropy source dependent on its use case? If only one application will be using the RNG at a time, is a single byte seed just as secure as a larger pool of entropy? Is the only reason Linux uses an entropy pool is to not give away any hints on internal seed state if other applications pull random data from it?

I guess what I'm trying to ask is what are the benefits of using a single byte seed value over an entropy pool, and is an entropy pool relevant for single user RNGs where only a single, trusted user uses the RNG?

Improve this question
$\endgroup$
6
  • $\begingroup$ Your first paragraph is a bit fuzzy. If you need a cryptographically secure pseudo random number generator, it is because you need cryptographically secure pseudo random numbers, and whatever that reason might be, it is cryptographic by definition. If not, you might need a PRNG, but not necessarily a CSPRNG, and should probably ask elsewhere. $\endgroup$
    – Henrick Hellström
    Dec 30, 2013 at 3:16
  • $\begingroup$ @HenrickHellström The difference between a CSPRNG and a PRNG is simply that one can be predicted and one cannot. I may want to make a poker game where I do not wish to have the randomness predicted so a CSPRNG would be ideal. $\endgroup$
    – jduncanator
    Dec 30, 2013 at 4:44
  • 1
    $\begingroup$ There is window.crypto.getRandomBytes. You may already have looked at this and decided not to use it (incompatibility), etc., but for anyone reading the post not aware, that's an honest-to-goodness built-in CSPRNG implemented by newer browsers. Also, there is the SJCL which has Fortuna already implemented. None of this affects the validity of your question, but I wanted to give already-built solutions. $\endgroup$
    – Reid
    Dec 30, 2013 at 4:50
  • 1
    $\begingroup$ Instead of implementing Linux's RNG in JavaScript, I would implement one of CTR_DRBG, Hash_DRBG or HMAC_DRBG from NIST Special Publication 800-90A. These fulfill requirements of CSPRNG, unlike e.g. Mersenne Twister, which you shall avoid in cryptographic uses. One great aspect of NIST's RNG's is that they provide test vectors to ensure implementation is correct. A RNG like Linux's but in JS will be significantly different impl than Linux's and it does not have any test vectors anywhere making it hard to ensure correctness. $\endgroup$
    – user4982
    Dec 30, 2013 at 14:44
  • 2
    $\begingroup$ You normally use both: a pool, to throw incoming events into, mix, and generate output from, and a seed, which is initially thrown into the pool (or just a dump of the initial pool, as in the MirBSD kernel). $\endgroup$
    – mirabilos
    Jan 6, 2014 at 23:49

2 Answers 2

Reset to default
3
$\begingroup$

What I want to know is what are the benefits of using an entropy pool over a single byte seed value?

There are no benefits of an entropy pool. It's a necessity. If anything, it's a strong indicator of a poor true random number generator (TRNG) and hints at the construction actually being a de facto pseudo random number generator (PRNG), which I believe /dev/random to be.

The golden rule of any TRNG is that H(in) >= H(out) where H is entropy. The following diagram illustrates the Linux random number generator's entropy pool.

entropy

As the input events are totally irregular and of indeterminate frequency, H(in) cannot be calculated. You can easily wait >60 seconds for a single random output byte to become available. You mention that the Linux implementation is well documented. Not for this point. There is no quantitative assessment of input entropy that I can find in the literature. The best is the report at the bottom, but that still accepts the developers' assessment of 1 bit of entropy/event. It might well be far lower but as stated, irregular events cannot be given a rate. No one has undertaken an accurate entropy measure of the jiffy events themselves. δ3s are not valid units of entropy. Ergo the golden rule is not proven.

Thus the entropy pool acts as an accumulator and low pass filter to smooth the jiffies. You will have had to implement this for yourself in your Javascript port. Re iteratively hashing the pool is very much akin to the re permutations of a sponge construct during the squeeze phase, and thus another parallel with a PRNG.

TRNG are all about real entropy and it's accummulation. Any port of /dev/random will have to address the capture of entropy from a machine, and as Javascript is more highly abstracted than the kernel, it will be harder. But a pool will be unavoidable. You cannot easily re seed a generator's state byte by byte and bit by bit as irregular entropy events are detected. Whether you implement a direct copy of /dev/random or some NIST CSPRNG, you'll need the pool to cheat. It's got nothing to do with the number of concurrent applications. You're confusing the entropy pool with a connection pool.

This question may be a trifle stale, but the answer is still relevant today for anyone developing a true random number generator.

Ref. François Goichon, Cédric Lauradoux, Guillaume Salagnac, Thibaut Vuillemin. Entropy transfers in the Linux Random Number Generator. [Research Report] RR-8060, 2012, pp.26.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nice answer. Worth pointing out that this inequality, ${H(out)}\leq{H(in)}$ is known as the Data Processing Inequality. Intuitively, a deterministic data process can only destroy information. $\endgroup$
    – conchild
    Oct 2, 2020 at 17:22
0
$\begingroup$

In the comment above, I take it that Paul Uszak, must be referring to a CSPRNG, and not a TRNG (realized with hardware in relation to real chaos from the non-computer-world)... TRNGs can be used as great supplements and will make any [CS]PRNG work even better though.

User Space Entropy manipulation, i.e. manipulating entropy from the application layer should generally be avoided. Stick to Kernel Space Entropy, which also has the advantage of being much better at protecting the memory space around the Entropy pool. In addition, you avoid to make human errors when manipulating the pool of entropy.

As Paul Uszak writes above, Seed is in place of the initially "empty" entropy-pool, and used only at boot time (when we talk Kernel Space entropy, as used by e.g. /dev/[u/a]random)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.