Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

First of all, I don't recommend doing this. This was something I created when I didn't know better and didn't have a solution available to me.

Long ago I created my own entropy gather for a cryptography project. I used a window and had the user type with the keyboard while moving and clicking the mouse. I kept the milliseconds of the timestamp on each message, as well as the X, Y of the mouse and the values of the keystrokes.

Basically in designing the method I examined the messages and only kept the values that changed significantly (unpredictably) from message to message. For example the date, hour and minute of the message was discarded since all the messages were collected on at close to the same time.

I then created an algorithm to "stir" the pool. This just used the built in simple random number generator to shuffle the values around a user defined number of times. After the fact I wondered if this was a good idea or not.

After that I would extract numbers from the pool (removing them not to be used again) each time I needed a random value as a seed. I would warn the user if the pool got to small and allow them to add more entropy. I would stir the pool before each use and after gathering.

I know that today there are cryptographically secure random number generators built into most operating systems and development libraries, so I would discourage anyone from rolling their own solution today, but I am curious if the methodology I described was effective and if there was anything I did or didn't do that could improve it.

share|improve this question
1  
Your basic method is sound and still used today. Gather entropy. Mix it. Extract randomness. Mix again. Rinse, wash, repeat. –  David Schwartz Jan 10 '12 at 22:55
add comment

2 Answers

up vote 7 down vote accepted

You should not remove any part of the pool, or do some more-or-less random selection out of it. Instead, just hash the whole thing with SHA-256. This will get you all the entropy there is to get out of the data, up to 256 bits, which is more than enough.

Once you got 256 bits of entropy, i.e. you accumulated physical measures which should amount, together, to at least that many bits of entropy, and then you hashed all of it, into a single 256-bit value, then you can use that 256-bit value in a good PRNG, which will produce as many random bits that you could wish for (i.e. bits computationally indistinguishable from true alea, which is the best you can practically hope for or actually need).

Now that's exactly what is happening behind /dev/urandom, CryptGenRandom(), java.util.SecureRandom, or whatever name your OS gives to its strong random number generator.

share|improve this answer
    
So you are saying collect the whole message (including parts that are always the same), don't bother stirring it, and then use a SHA-256 hash to retrieve a value to use as a seed? How often should the pool be flushed or new entropy be gathered? –  Jim McKeeth Jan 10 '12 at 21:37
2  
@JimMcKeeth: never ! A 256-bit random seed is good enough until the end of times -- the end of your times, that is, including your grandchildren's grandchildren. That's what computational indistinguishability is about: 300 years of computation with all the world's computers are not enough to get it through. In practice, a PRNG needs a new seed upon boot and until next time the machine is shut off. –  Thomas Pornin Jan 10 '12 at 22:05
3  
New entropy should be gathered whenever you have it. Why not? (You can grab timestamps on operations, for example.) But generally, you shouldn't produce a single byte of output until you have enough input to produce cryptographically-strong random numbers forever. –  David Schwartz Jan 10 '12 at 22:56
    
@DavidSchwartz: that's exactly how /dev/urandom works on FreeBSD: it blocks until a big enough seed has been obtained, and then never after. Linux's /dev/urandom is broken in that respect (it will accept to output data before having obtained enough bytes) but Linux distributions fix that by recording at each boot a random seed in a file, which will be used upon next boot. As for gathering additional entropy afterwards, it does not harm, as long as it is cheap (not gathering extra entropy being always, by definition, the cheapest option). –  Thomas Pornin Jan 11 '12 at 13:09
1  
I found eprint.iacr.org/2006/086.pdf which explains how linux does it. In particular I was curious about how to estimate how much entropy you have at any one time. –  kasterma Jan 14 '12 at 18:33
show 1 more comment

The high level architecture is alright. You implement a sponge-like structure that absorbes randomness from any source, and when you need randomness back, you squeeze it out. (Note: there actually is something called a cryptographic sponge, used in some new hash functions, which I am not referring to although it is related).

There are a few improvements you can make. You don't need filter for entropy first. If you update the random pool with a well-designed update function, you can update with any source. If the source isn't actually random, it won't make the pool any less random. But if it is random, then the pool randomness will increase. Similarly, an update should touch every bit of the pool negating the need to stir it.

These are just high-level points, the real details are in the exact primitives you use and how you use them. A very nice model for an entropy pool is given in the paper “A model and Architecture for Pseudo-Random Generation and Applications to /dev/random” (PDF). It is relatively simple yet provably secure.

It uses a PRG and an extractor. An extractor is sort of like a hash, often mis-implemented as a hash, but could be a block cipher in CBC-MAC mode, for example, with a non-secret but randomly-generated key. Importantly, it can take an arbitrary-sized input and reduce it down to a fixed-size (m bits in this case). If the input has at least 2m-bits of min-entropy over the whole string, it will condense it to m bits that are indistinguishable from a truly random m bits.

Call the pool $p_i$ at time $i$ and say you want to add newly harvested randomness $r$. The function is:

$p_{i+1}=\mathsf{PRG}(p_i \oplus \mathsf{Ext}(r))$

In this case the PRG is taking m-bits and returning m-bits (its not actually expanding the size). Now to get a random value $x$ out of the pool, you do:

$\langle x,p_{i+1} \rangle=\mathsf{PRG}(p_i)$

In this case the PRG is taking m bits and returning 2m bits. The first m bits are used as your value $x$ and the second m bits are the new value for the pool.

share|improve this answer
    
What do you mean by "mis-implemented as a hash"? Doesn't a good hash function work fine as an extractor? –  Paŭlo Ebermann Jul 11 '12 at 12:09
    
Hash functions cannot be shown to be good extractors. There is a theory-practice gap on this point, but given that there are very simple constructions that can be shown to be good extractors, one should use them. See Section 1 of this paper: iacr.org/archive/crypto2004/31520493/clean.pdf –  PulpSpy Jul 11 '12 at 13:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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