# Unpredictability vs randomness

I'm experimenting with creating an entropy source for an environment where I have no hardware available and the language is very high level (executed in a virtual machine). I know it's not a good idea but I don't have /dev/random or CryptoAPI and the only possible sources are things like http://random.org but they need a network connection and is discouraged.

I have tried to execute a tight loop and get entropy from the elapsed times which, because of the CPU scheduling and other processes activities, has some variance. This source of entropy is of very poor quality but it seems unpredictable as long as someone has not access to the physical machine where the generator is running. Nevertheless, if I run the "ent" tool through the values I get it shows that they are strongly correlated and not truly random.

If I then iterate Von Neumann unbiasing between 2-4 times, until the point the resulting data passes the chi square test of "ent" (BTW: this process always converges), it seems that I get truly looking random numbers.

My question is: would this random numbers be unpredictable because their source is unpredictable or am I masking possible errors and fooling myself? What would happen if I used this numbers to seed a PRNG based on AES in CTR mode with a key and IV?

-
Since this is a crypto board, I answered the question from a crypto perspective. But from a practical security standpoint, I suspect your time might be better spent trying to find richer sources of entropy. (Also, and I suspect you are aware of this but just want to make sure, Van Neumann unbiasing only unbiases bits that are independent --- unlikely to be the case here.) –  Seth Mar 6 at 1:04
@Seth Thanks for the replies. I suspect (like you) that the bits are not independent, but then, why does iterating Von Neumann always converge to a random sequence after a small amount of iterations? Isn't it extracting the entropy in the samples? –  izaera Mar 6 at 7:10
It apparently converges to something that passes a Chi Square test. Is every distribution that passes that test a uniform distribution? I doubt it. For example, consider the distribution created by choosing a random K and outputting K|AES(K, 0)|AES(K, 1), where | is concatenation. It's trivial to distinguish these outputs for random (since you're given K), but highly unlikely that a standard statistical test, such as Chi Square, will be able to do so. See the second paragraph of my answer. –  Seth Mar 6 at 20:57

## 1 Answer

The process of turning inputs that are hard to predict (formally, inputs that have some min-entropy) into bit strings that are cryptographically uniformly random is called entropy extraction. So there's your search term if you want to learn more theory.

The problem. The fact that your outputs produce values that can pass a given statistical test (or even a suite of standard tests) is a bit encouraging, but far from a guarantee. The tests in question know nothing about your entropy source or extraction function, but presumably an attacker will. Therefore an attacker may be able to exploit some non-uniformly random characteristic of the output that would go unnoticed by the test.

I have no idea how likely this is in your particular setting. But if you want to place your system on a more solid theoretical foundation, you need to use a proper entropy extractor.

The easy way out. Before continuing, I should say that in practice, a lot of people would simply take the output of the entropy source, hash it (using SHA-256 for example), and use the result to seed an AES-CTR PRNG.

PRNG Seed = SHA-256(Entropy)


Despite the fact that hash functions aren't really designed to take this kind of abuse (they are not random oracles!), so far this approach hasn't led to any practical attacks --- at least, that I know of. This might be good enough for you as long as you harvest enough entropy to make a brute-force attack infeasible.

If you're particularly paranoid and want to be a good cryptographer, read on.

The "Right" Solution. In order to construct an entropy extractor, first you need access to a random seed. Which seems a bit circular, but, crucially, the extractor seed does not need to be secret and it does not need to change. (In contrast, the PRNG seed most definitely does). So you could generate one elsewhere and send it over. The only restriction on the extractor seed is that it needs to be generated in a way that's independent of your entropy source, and you need to assume that an attacker can't influence the entropy source based on his knowledge of the extractor seed.

Now that you have a seed in hand, the question is how much effort you're willing to expend on implementation. You can use the seed as a key for HMAC-SHA256, and you'd probably be fine (see Randomness Extraction and Key Derivation Using the CBC, Cascade, and HMAC Modes by Dodis, et al.):

PRNG seed = HMAC-SHA256(Extractor Seed, Entropy)


If you want to be a bit more paranoid, find code that implements a polynomial hash over a finite field (this could probably be taken SSL's GCM code), use the entropy to encode the coefficients of a polynomial, and evaluate the polynomial at the value encoded by the extractor seed. (See, e.g., Leftover Hash Lemma, Revisited by Barak, et al.)

PRNG Seed = PolyHash(Extractor Seed, Entropy)


Regardless of which of these two approaches you take, in order to get a strong degree of security you'll need around 160 bits of min-entropy to generate a 128 bit PRNG seed (i.e., an attacker should not be able to predict your entropy with probability more than $2^{-160}$). Note that since there are likely redundancies in your entropy source, the strings you get from it may need to be considerably longer.

-
The phrase "randomness extraction" is better and also used, such as in this answer's key derivation link. $\:$ Also, one could potentially implement a strong extractor that is not a polynomial hash. $\hspace{1.42 in}$ –  Ricky Demer Mar 6 at 1:29
Looking at "the easy way", I cannot find very fundamental differences between the Von Neumann approach and the hash. Both are non invertible functions (in the sense that they are mapping a bigger input to a smaller output) and thus you would need to test the inputs to know the possible outputs. If then, you know that the input space is restricted you can make a "table of possible outputs" to speed up the search. Given that I'm harvesting entropy from execution times (a normal distribution) it shouldn't be difficult in either case. –  izaera Mar 6 at 7:21
Regarding the "right solution", if I use, say, an HMAC and a non-secret key. How does that differ from the hash approach? I mean, what prevents the attacker from (again) making a table of most probable outputs? What makes it better than a pure hash? In the end, it seems that I always get to the same point: I need a very good entropy source. But then, if the source is so good, why not using it directly to key an AES-CTR for PRNG? (note: I know I'm not being very orthodox, but I want to clarify the intuitions first before going into the maths). –  izaera Mar 6 at 7:27
How about the fact that your "source of entropy is of very poor quality but it seems unpredictable as long as ..."? $\:$ If the problem is insufficient entropy, rather than getting randomness from a large amount of entropy, then you should use a password-based key derivation function. $\;\;\;$ –  Ricky Demer Mar 6 at 18:15
@izaera Any (deterministic) extractor algorithm can be attacked by a brute-force adversary. The only ways around this are to either gather more entropy or, as Ricky suggests, using a PBKDF to slow down a brute-force attack. The goal of the extractor isn't to resist brute-force attacks, the goal is to generate outputs that are (statistically close to) uniformly random from outputs that are merely unpredictable (have high min-entropy). AES was designed to be used with a uniformly random key; using a key that's merely unpredictable puts you on shaky ground. –  Seth Mar 6 at 19:50