How to extract randomness from a file?

Question

I have a generator of files with approximately 7 bits /byte entropy. The files are about 30KB each in length. I'd like to use these as sources of entropy to generate random numbers. Theoretically I should be able to achieve about 26 KB (max) of randomness per file.

This is a hobby and I know about hashes, but they're primarily checksums. I'm looking for more sophisticated methods of extraction designed specifically for that purpose. I'm hoping to use this as a true random number generator.

Supplemental:

Following comments, and in order to solicit non hash based responses, I'm evaluating the following architecture...

It works like this:-

The entropy is the 30KB file

The compressor reduces the entropy to a target size of 26KB

A seed is derived from all of the bytes of the entropy

Some PRNG implementation produces 26KB of pseudo random output

The two outputs are xored together to produce true random numbers

So in summary, a 30KB file of 86% entropy is manipulated into a 26KB file of 100% entropy. Entropy is preserved throughout the extraction process, and all the output is totally dependant on the input. 26KB of full entropy goes in, and 26KB of full entropy comes out.

I suggest that this is a good method to extract entropy from complete files. Or not.

Answer 1

In practice, in about 95% of cases, the correct answer is probably going to be: forget about those files, use /dev/urandom or CryptGenRandom() (or equivalent). They provide very high quality random numbers -- That's what they're designed for. So this is the most pragmatic answer, and it will provide excellent quality randomness.

---

Let's say you can't do that, maybe because it's a headless embedded device with no access to entropy, or you want your random numbers to be a repeatable deterministic function of the files. Then in that case the best answer is likely to be -- guess what? -- hashing. In particular: concatenate all the files, take the SHA256 hash of the concatenation, and then use that as a key for AES-256-CTR; then use AES-256-CTR to generate as much output as you want. This is basically using a cryptographic hash to generate a seed for a cryptographic-quality pseudorandom generator, and it satisfies all your requirements. This is a solid answer, from the perspective of robust engineering and high quality random numbers.

---

OK, let's say you are a theorist. If you are a theorist, you won't like the last answer, because it relies upon cryptographic assumptions that have not been mathematically proven to hold. Pragmatically, you probably shouldn't worry about that -- you rely upon those assumptions every day (e.g., when doing e-commerce or entering your password into a website), and other issues are far more likely to affect you in practice -- but let's say you are a theorist.

From a theoretical perspective, the cryptographic solution is potentially unsatisfying, because it relies upon an unproven assumption, and that is... inelegant. So, it's interesting to ask what can be achieved that will provably work. If that's what you're interested in, you'll want to read about randomness extractors.

If you care about pragmatics, randomness extractors are probably not the best possible solution: extractors need stronger assumptions about the distribution of the data in your files, they are more limited in how much random output they can produce, and they are more fragile. But they do come with provably good properties, and they are mathematically elegant and beautiful.

Answer 2

OK, so the question has changed to "please review my construction for me". Let me try to help with a few principles first, and then some detailed analysis.

Don't roll your own

If you're going to use this for anything serious, don't try to design it yourself. It's too easy to screw up. There's a long history of well-intentioned, smart people trying to design their own true random number generator, and messing up.

And what makes this worse is that if you get something wrong, you'll probably have no way of knowing: your algorithm will output numbers that have a bias, but how will you know? You won't know; your statistical algorithm will just give you bogus results that are slightly wrong, or your crypto algorithm will become insecure in a subtle and non-obvious way, or whatever.

You probably don't actually need true random numbers

In my experience, 99% of people who think they want true random numbers don't actually need true random numbers. I often people look at pseudorandom generators, figure that the "pseudo" is bad, and figure "I want the best, so why would I mess with anything less than the best? obviously I want true not pseudo random numbers".

However that reasoning is flawed. Skepticism about garden-variety pseudorandom generators is healthy. But it's worth knowing that not all pseudorandom generators are created equal.

In particular, cryptographic-quality pseudorandom generators are special. The definition of "cryptographic-quality" is that no feasible adversary can distinguish their output from true random numbers (e.g., it takes exponential time to tell them apart from true random numbers). Thus, if you have a pseudorandom generator that truly is cryptographic-quality, it's every bit as good as true random numbers.

Now this does leave the question of whether a pseudorandom generator that's claimed to be cryptographic-quality, actually is. However, the good news is that there's been a lot of work on this in the crypto literature, and we have constructions that have been studied extensively and are widely believed to meet this requirement.

In contrast, anything you build yourself is not going to have been studied anywhere near as carefully. So, on the one hand we have well-vetted cryptographic pseudorandom generators that have been carefully studied by others. On the other hand we have a scheme you designed yourself that you think/hope outputs true random numbers. Which do you think is more likely to have a catastrophic flaw?

Your scheme doesn't output true random numbers

With all those general principles out of the way, on to your specific scheme that you propose in the question. Unfortunately, your scheme is not guaranteed to output true random numbers.

In particular, let's be clear on what the requirement is. We want the output of your scheme to be uniformly distributed: each bit is a identically and independently distributed random bit, with equal probability of heads and tails. For a $n$-bit output, we want all $2^n$ possible outputs to be equally likely. And we want this to hold for every possible input distribution that has approximately 7 bits of entropy per byte.

Your scheme doesn't have this property. There are input distributions where your scheme falls apart.

For example, suppose that we compress the 30KB input file, and the output of the compressor is 30KB long. Then what are you going to do? Your specification doesn't actually say what to do, but it turns out that there is no good answer. If your answer is "truncate to 26KB, then xor with the output of the pseudorandom generator", that's a bad answer: the output might not be uniformly distributed. If your answer is "well, I'll just generate 30KB of pseudorandom numbers, xor them with the output of the compressor, and output all 30KB", that's a bad answer too: the output isn't uniformly distributed, and quite obviously cannot have more than 26KB of entropy, since no deterministic procedure can ever increase the entropy present in the input.

For instance, here's a simple input distribution you can think of, to hone your intuition. Imagine that each byte is generated using the following process: the low 7 bits are chosen uniformly at random, and the high bit is chosen deterministically as the parity of the previous 8 bytes of input. Then this has 7 bits of entropy per byte. However, no standard compressor is going to compress this stream of data; the output of the compressor will almost surely be about 30KB. Moreover, if you truncate the output of the compressor to 26KB, so the truncated result will probably have only about 23KB of entropy; the amount of entropy in the output of the PRNG is at most its seed length; so the xor of the two will have far less than 26KB of entropy and fails to be uniformly distributed.

Another problem with your scheme is that you haven't specified how the seed for the PRNG is chosen, nor what PRNG you'll use. Analysis of your scheme might depend heavily on these details.

There may well be more problems beyond this, but this is already enough to show that the scheme doesn't meet the requirements.

What should you do instead?

Don't try to generate your own scheme. Re-assess whether you really need true random numbers (odds are you don't). Then, use an existing well-vetted high-quality source of random/pseudorandom numbers, e.g., /dev/urandom or /dev/random or similar.