Stretching a random seed to maximize entropy

Question

I'm using a random number generator that requires me to pass it a big (several kilobytes) pool of random data for initialization.

I've gathered entropy from various system metrics (free memory, system clock, mac address .etc) and generated a 64-bit seed value which I need to "stretch" over the big memory pool.

Whats the best way to spread this small amount of entropy over the big pool? I've considered something like encrypting a null (0x00) buffer with a stream cipher using the seed as the key. Is that a safe approach?

Answer 1

What you ask for is a RNG to produce some output which another RNG will use as seed. This looks quite overly complex...

The point of the seed is to be unknown to the attacker: the seed data should be such that "trying out" possible seed values should not match the actual seed except with negligible probability. With a 64-bit seed, even if the seed is "perfect" (chosen totally randomly and uniformly among the $2^{64}$ possible seed values), an attacker trying possible seed value still has a $2^{-64}$ probability of finding the correct seed at each try, and that's a bit high for comfort. We usually prefer attack probabilities of $2^{-128}$ or less. Regardless of how you generate your 64-bit seed, how you then expand that 64-bit seed into whatever ISAAC requires, and whether ISAAC is good or not, your security will never be higher than that provided by a 64-bit seed.

How ISAAC is supposed to be seeded (with what, under which properties) is not clear; the ISAAC author himself says:

I provided no official seeding routine because I didn't feel competent to give one. Seeding a random number generator is essentially the same problem as encrypting the seed with a block cipher. ISAAC should be initialized with the encryption of the seed by some secure cipher. I've provided a seeding routine in my implementations, which nobody has broken so far, but I have less faith in that initialization routine than I have in ISAAC.

Come to think of it, this is a bit scary comment. Are you sure you want to trust the security of a system, a part of which being deemed by the author himself as being not trustworthy ?

And more generally, ISAAC was designed at a time where the competition was RC4, a generator with known biases, and not that fast. Science has improved since. See the eSTREAM project: this is the result of a kind of open competition, where cryptographers proposed new stream cipher designs, and tried to break the proposed designs. The resulting "portfolio" consists in the designs which resisted cryptanalysis, and offer good performance. The good thing about these stream ciphers is that they work with keys of reasonable size, with no underspecified part as the seeding in ISAAC. For instance, consider Sosemanuk: it accepts a key of 1 to 256 bits, and a 128-bit IV, and produces pseudo-random bytes at an reasonably high speed (it should be competitive with ISAAC, possibly even a tad faster).

This would lead to the following design:

• Accumulate your source entropy in a buffer. It does not really matter how you encode each metric, as long as you do not lose information.
• Hash the whole buffer with a secure hash function, preferably SHA-256. This results in a 256-bit value.
• Use the 256-bit value as key for Sosemanuk (the IV can be 0). Produce random bytes. Enjoy.
• (Alternatively, use the Sosemanuk output as seed for ISAAC, if you really need, for administrative reasons, to use ISAAC. But the under-specification of the seeding process could trigger weaknesses, so I would not recommend it at all.)

Note that entropy gathering is a subtle thing. MAC address and system clock, for instance, are really bad entropy sources because they can be observed by attackers: the system clock is close to the current time, which (by definition) is public data, and the machine will write its MAC address on every ethernet frame it emits. Entropy is good only insofar as it is unknown to the attacker. The good thing about SHA-256 is that it does not matter if some of your entropy is bad, as long as there is also some good entropy somewhere in your buffer. Still, you are warmly encouraged to use as entropy sources the services specifically offered by the operating system to that effect (it is called CryptGenRandom() on Windows, /dev/urandom on Unix-like systems and MacOS X): since the OS directly manages the hardware, it is in ideal position to gather entropy from hardware sources.

Answer 2

There is no good way to stretch your 64-bit seed value without some secret material. Anything deterministic you do is bound to be vulnerable to enumeration of all 64-bit seed values. The least wrong option is to use a purposely slow derivation function designed for passwords, e.g. Scrypt.

With some $Secret$ material assumed hidden from an adversary, you have more options. The basic idea is to mix $Seed$ with $Secret$ into an expanded $Seed'$ using a random-like function. The simple $Seed'=SHA_{256}(Secret||Seed)$ will do, other Key Derivation Function can be used, including Scrypt. Issues are that you must protect the confidentiality of $Secret$; further, if it remains constant, identical 64-bit $Seed$ will generate the same $Seed'$.

Next steps are to store and vary $Secret$ from one execution to another; pretty soon we are reinventing a full-blown implementation of a cryptographically secure random source, such a Yarrow.

Answer 3

It is not safe in light of the recent cavity-compression attacks against key stretching (see Secure Applications of Low-Entropy Keys, J. Kelsey, B. Schneier, C. Hall, and D. Wagner (1997))

Answer 4

Correct me if I am wrong in the following claim and deduction. 1. You are trying to generate a large amount of random data that you need in a random number generator (which should be precisely pseudo-random number generator because if you know a construction of a random number generator from a small seed that you are already breaking some theoretical known result based on a very plausible complexity theoretic assumption!) 2. You are trying to do this with the help of small entropy.

Now lets see both these steps. One possible way to do the second step is assuming that you have access to a small number of truly random bits (say $d$). Now from the entropy that you have can be seen as being the entropy of a distribution, say $\mathcal{X}$ with a min-entropy the size of your seed which for brevity I say $k$. Now the task that you are trying to achieve is actually extracting randomness from the arbitrary distribution $\mathcal{X}$. There has been known lower bound results which says that you will always lose some entropy if you are concerned with getting randomness which passes any statistical test. Precisely, the work is by Jaikumar and Ta-Shma (Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators ) which says that you will lose about $2 \log (1/\varepsilon)$ entropy if you want the statistical test to pass by at most $\varepsilon$ probability. This said, you can see that the second step is impossible to do because you always lose some entropy even if you have an access to $d$ truly random bits.

I hope this clears and settles the matter for you. Let me know if you have doubt on any of the points or I have missed something that you wanted to ask explicitly.