The search for truly random numbers in the kernel [LWN.net]

Fortuna

Posted Sep 19, 2013 14:04 UTC (Thu) by cesarb (subscriber, #6266) [Link]

Seconded. One interesting feature of Fortuna is that it does not need any entropy estimation.

Fortuna has two parts. The generator is simply AES (or another good block cipher) in counter mode, with the key being the state. When you request random bytes, it generates the requested bytes plus a new key (rotating the state).

The accumulator has 32 pools. Incoming entropy is uniformly distributed between the pools. Each pool is used for seeding half as often as the previous pool, so the first pool is used every reseed, the second pool is used every other reseed, the third pool is used every four reseeds, and so on. A reseed is done every time the generator is called (before calling the generator), if the first pool has received more than a fixed number of bytes, and at most once every 0.1 second.

With this design, at least one of the pools will have received enough entropy when it comes its turn to be used to reseed the generator. You do not have to know which one, so there is no need to estimate entropy. The state for the generator is the counter and the key, and the state for the accumulator is a rolling hash for each pool (which summarizes its contents) plus the size of the first pool and the last reseed time.

For more information, see http://th.informatik.uni-mannheim.de/people/lucks/papers/... and https://en.wikipedia.org/wiki/Fortuna_%28PRNG%29.

I believe the current Linux PRNG was originally derived from the one used by PGP, with modifications accumulating over time. Fortuna (and its predecessor Yarrow) is a more modern design.

Fortuna

Posted Sep 19, 2013 17:26 UTC (Thu) by kleptog (subscriber, #1183) [Link]

Well, Fortuna is designed to be a secure pseudo-random number generator. If that's what you want then /dev/urandom is fine. What we are talking is true random output, which you can't simply generate large amounts of without external input.

We could just drop /dev/random altogether and symlink it to /dev/urandom. Which is what using Fortuna would amount to.

Fortuna

Posted Sep 19, 2013 20:56 UTC (Thu) by cesarb (subscriber, #6266) [Link]

> Well, Fortuna is designed to be a secure pseudo-random number generator. If that's what you want then /dev/urandom is fine. What we are talking is true random output, which you can't simply generate large amounts of without external input.

Both /dev/random and /dev/urandom are secure pseudo-random number generators, and both are seeded with external entropy in the same way. The only difference between both is that /dev/random blocks if the entropy estimate is too low, while /dev/urandom does not.

You could use Fortuna for /dev/random too, you would just need to add some sort of entropy estimator, to keep compatibility with userspace which expects it to block arbitrarily. Since most users (even cryptographic libraries) seem to use /dev/urandom, any problems with this entropy estimator would not affect them.

And for users of /dev/random, you would gain the advantage that the quality of the random numbers would not be affected by bugs on the entropy estimator.

Yes, an overestimation would that mean more numbers would be generated from the same amount of entropy. But Fortuna (and Yarrow) is designed so that, as long as the generator has more than a minimum amount of good quality entropy to start with (256 bits IIRC), and the state is not compromised, the output is secure even without reseeding (if the state can be compromised from the output, AES is broken and you have bigger problems). After the initial seeding, the reseeding is there only to recover if the generator state is compromised; see the presentation for more details.

Fortuna

Posted Sep 24, 2013 21:29 UTC (Tue) by joern (subscriber, #22392) [Link]

While in principle I like the fortuna design, I am wondering what problem you are trying to solve. Both fortuna and the current linux design are prng, both use (or can use) real entropy to seed their pools and to stir them up once in a while. Both should give random numbers that are impossible to predict, assuming the attacker can do almost anything except dump the entropy pool itself or control every bit of input to the pool.

One of the two might have a more pleasing design. But as long as both get the job done equally well, why would you want to do a replacement? You can easily introduce subtle bugs and, without a strong upside, I would like to avoid that possibility.