2
$\begingroup$

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...

Extractor 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.

$\endgroup$
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Randomness_extractor $\;$ $\endgroup$ – user12859 Aug 28 '15 at 4:16
  • 3
    $\begingroup$ Can you edit the question to explain why you have rejected hashes and what requirements you want a solution to have? That would help provide useful answers to your question. Right now the question reads to me like "I know of [a good solution to my problem], but I am rejecting it for unstated reasons". I don't know how to answer that kind of question without knowing what your reasons are. $\endgroup$ – D.W. Aug 28 '15 at 5:48
  • 2
    $\begingroup$ In response to your edit, note that what you're doing is by no means a true random number generator. If the generator of the files is an unpredictable physical process, then it is a TRNG, and your program is a conditioner for this TRNG. $\endgroup$ – Gilles 'SO- stop being evil' Aug 29 '15 at 11:56
  • 2
    $\begingroup$ Are you trying to learn about these things, or are you trying to build a productive system? In the latter case, the obligatory advice is: don't! $\endgroup$ – Raphael Sep 7 '15 at 23:06
  • 2
    $\begingroup$ @PaulUszak Don't, because you are more than likely to mess up and harm whatever your larger system is. See e.g. Knuth in TAoCP. Use what your favorite library offers -- which is based on decades of r&d -- and even then, be very careful that it meets your requirements. $\endgroup$ – Raphael Sep 8 '15 at 7:09
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A very nice answer. Also related, is the Leftover Hash Lemma showing that a pretty good extractor can be obtained by hashing. $\endgroup$ – Ran G. Aug 28 '15 at 20:26
  • $\begingroup$ I'm hoping to use this as a true random number generator, so I'm not looking at AESesque pseudo output. As mentioned, pragmatism is not a concern here, If anything, I'm trying to avoid the mono culture approach. $\endgroup$ – Paul Uszak Aug 29 '15 at 1:58
  • $\begingroup$ @DW Surely using AES on it's own cannot by definition be a true random number generator, only a pseudo one. $\endgroup$ – Paul Uszak Sep 7 '15 at 22:29
  • 1
    $\begingroup$ @PaulUszak, yes, of course, that's why I mentioned in my answer that it's a "cryptographic-quality pseudorandom generator". Perhaps you missed that part? That said... I would be remiss if I failed to mention that most people who think they want a true random generator actually would do better with a well-vetted crypto-quality pseudorandom generator. If you really want to get into the guts of this, you might want to start by reading the cryptographic literature on this subject. You might also want to read security.stackexchange.com/q/3936/971. $\endgroup$ – D.W. Sep 7 '15 at 23:39
  • $\begingroup$ @D.W. No, I reallyreally want a true random number generator, not a pseudo random one. Can you technically undermine my algorithm? Can you show me numbers? $\endgroup$ – Paul Uszak Sep 8 '15 at 0:33
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @d-w Yeh, sorry about re-purposing the question somewhat. It was the only way to generate a decent answer to it. Just to correct some errors in your answer; from the top:- 1.There's a long history of well-intentioned, smart people trying to design their own true random number generator, and succeeded. Research true random number generators in the market place. 2.The output of the compression function will be exactly 26KB every time using some sort of byte folding. 3.Any 7 bit/byte entropy source is easily compressible irrespective of parity as that's the definition of compression. $\endgroup$ – Paul Uszak Sep 10 '15 at 0:13
  • $\begingroup$ 4.The probability distribution of the compressor's output is irrelevant as it's xored with random numbers. The fundamental nature of the xor operator is to preserve randomness. 5. The definition of a working pseudorandom generator is that it does produce uniformly distributed random numbers. 6. My spec states that the PRNG's seed is determined from all of the entropy's bits. $\endgroup$ – Paul Uszak Sep 10 '15 at 0:17
  • $\begingroup$ 7. Most fundamentally, the difference between a pseudo random generator and a true one is that all the output of the pseudo is predictable. It's just clever code. My entropy is quantum based and no one (including myself) can predict it's content. All I know is that it''ll have 7 bits / byte entropy. Every bit output will be dependant on all of the bits input. I 'll know when it's working correctly because it will pass randomness tests. I also have a very strong belief that it will work because my construction is essentially that used in most cryptographic hashes anyway. $\endgroup$ – Paul Uszak Sep 10 '15 at 0:27
  • 1
    $\begingroup$ @PaulUszak, thanks for the replies. However, I don't agree that my answer has any errors, and I think some of your statements are incorrect. For instance, I justified my statement about compressibility by giving an example distribution that a standard compression algorithm is unlikely to be able to compress at all. I could rebut some of the points you made, but rather than prolong the conversation, I'll just say that I stand by my position and advice in my answer, and I guess you can decide to ignore it or continue to disagree. :-) Cheers! $\endgroup$ – D.W. Sep 10 '15 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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