Fortuna: paranoid random number generator

Everyone knows that the best random number generator is a device that digitizes the output from a very sensitive microphone standing on the sunny beach of the sea somewhere in the wild beaches of Bali.

If you do not have such a device, then I ask for cat.

So, you always need good random data. To generate encryption keys, salts, passwords, it does not matter. It is important their quality.

Suppose you have a good cryptographically PRNG that you once initialized with some large number ( seed ) and have not changed since.
If an evil FSB hacker somehow finds out this number, then he will be able to restore the entire sequence, and this is not at all good.
')
Therefore, it is logical periodically to re-initialize this PRNG with a new, good, random number.
It turns out that in order to generate good random numbers, we need good random numbers. The circle is closed.

Noise

Or, more strictly speaking, the source of entropy. Of course, ideally, it should be of a physical nature, but in the software execution environment, they are also sufficient. Not so good, of course, but nonetheless.
Roughly speaking, any time-varying data can be a source of noise. For example:

• Incoming / outgoing requests \ messages
• OS status (free memory \ CPU load)
• current mouse coordinates
• various counters
• current screen shot

The more of these sources, the better. One by one, they can provide fairly scarce data, but their combinations provide a good stream of more or less unpredictable data that we need.

If you are limited in sources of entropy, here is a recipe for you to pick it up almost from scratch :

1. We start a separate stream, in which in an infinite loop we increment the integer variable
2. Once a millisecond we look from another stream on its last bit and save (without interfering with its increment)
3. After 1 sec you have ~ 1000 bits of entropy of good quality.

You can vary the number of bits that you take from this variable every millisecond. The quality of entropy will be inversely proportional to the number of bits taken, but then its generation rate will be higher in the number of bits.
Also, you can wait more than 1 ms, then the influence of side processes on this last bit to be taken will be even greater, and accordingly, the quality of its “randomness” will improve.

The disadvantages of this generator are obvious:

• Very low generation rate.
• Full load of one of the processor cores at run time

But he is well suited for the role of "seed" for faster comrades in the shop.

Fortune

So, we have some number of sources of entropy, what to do with them?

Continuously feed them GPSN

This PRNG is called a continuously-seeded pseudo-random number generator. and Fortuna, by the authorship of Comrades Schneier and Ferguson, is a remarkable representative of such a generator.

It consists of two levels.

1. Entropy pools
2. Internal generator

The first 32 pieces, they represent nothing more than 32 hashes (any, of your choice), into which the entropy is formed according to the principle of a carousel. During the collection period, these hashes are not finalized (that is, they do not calculate the final value), thus accumulating random data in the process.

To make it easier to imagine, for the time being, these 32 hashes seem to hash large large, near-by-large files and do not do hash . Selected bold is important, further will be an explanation

That is, you received a new message / request, you gave it to Fortune, she asked Pool No. 1 to process it.
Generated several bytes by the generator described above, also there, she already gave them to the second.
And so on.

Since these are hashes, all incoming data is not accumulated in memory, but changes their internal state, i.e. memory is not wasted.

And so, we have 32 fattened pools, what next?

First, a little about

Inner Mongolia Inner Generator

It is a block cipher (AES, for example) and a counter (a number the size of an AES block, increasing by 1 every time someone asks for new data). That is, the task of the counter is simply to have different data encrypted each time .
No matter what, they are still encrypted with a random key.
This generator is actually the one that gives out random data, which is obtained by encrypting the counter with a random key.
At the same time, every time when we ask him for another piece of random data, it generates a little more than necessary, and using the excess as a new encryption key for himself.

Ie, for example, we asked the generator 100 bytes, it generated 116, gave us 100, and 16 (128 bits) used as a new encryption key for the block cipher.

In this case, the counter is not reset, and each of its next value is encrypted with different keys.

In the mix

Where does the very first encryption key value for the generator come from and how does the pool system work?

Initially, the internal generator is initialized with external data, like all ordinary generators. There is no magic here.

But when the number of bytes processed by the pool (hash) at number 1 exceeds a certain threshold (64 bytes), the most beautiful part of the algorithm begins.

Fortuna scores such triggers. This counter is called Reseed Count and means "How many times have we changed the encryption key of the internal generator?"

The current Reseed count depends on the set of pools that will participate in generating a new encryption key.

Since we have 32 pools, the “degree of their involvement” depends on the extent to which the two of them got Reseed count.

The first pool is used every time.
The second - if the remainder of the division of the Reseed count by 2 is zero
the third - if the remainder of the division of the Reseed count by 4 is zero
etc

That is, the higher the pool number, the less often it is used and accumulates entropy longer. The 32nd pool will only give up its own after 2 ^ 32 reseed operations.

Reseed

So, it's time to change the encryption key of the internal generator.
We finally finalize the hashes of those pools that participate in the current Reseed. We get an array of bytes the size of the number of participating pools * the number of bytes of the hash.
And we give it to the internal generator.
The generator takes all those Baitics, and the current encryption key (which, as we remember, changes every time after data generation) mixes in the same place, also hashes everything and this hash is used as a new encryption key for itself.

Everything.

What the hell is all this?

The pool system makes Fortune self-healing . If at first good data came to your pools, and then bad data began to arrive, then another reseed with a pool in which entropy from good data remained would restore the balance of forces in the universe.

Also, it can be noted that the previous information, on which the generation of random data depends (the same entropy) is not lost. With each reseed, new keys are mixed in to the current, and not replace it.

Additionally

The authors of Fortuna recommend generating a couple of kilobytes of random data every few minutes and saving them to disk so that the next time you start the application, you don’t know where the initial entropy is, but immediately download Fortune with good data.

That's all, thank you for your attention.

PS There are a lot of realizations, for example, in Zhave, the beloved BouncyCastle is used:
searchcode.com/codesearch/raw/16881031