6
$\begingroup$

It is common to use cryptographic hash functions to extract randomness from entropy sources. One of the quantitative criteria for this is that if 2n bits of entropy are put through a hash, n bits of uniformly distributed random numbers can be extracted.

Why is this? Where do the other n bits of entropy go? Perhaps naively, but if we adopt a water analogy, why can we only get 1 litre of water entropy out of a store that we've put 2 litres into? Is it possible to explain this without complex algebra? It seems counter intuitive that we can't get all the entropy out that was put into the hash function.

The scenario that vexes me is what if we chained hash functions for the hell of it. One cryptographic hash feeding the next. If we start at the top of the pile and input 16 bits of entropy, the available entropy would half passing through each hash. After passing through 5 hash functions, there would be <1 bit of entropy left. I can't fathom how that could be.

I can't find the original reference to n 2n, but there are many instances of this formula scattered throughout the literature. BUT. I have a counter example where this is not the case. The Quantis TRNG manages to output 75% of available entropy via matrix multiplication. And I think that I've seen this technique used in other TRNGs. It's simple compression of the raw entropy stream. Both hash functions and matrix multiplication is essentially similar, so what's going on?

$\endgroup$
4
$\begingroup$

I'm sure that somebody can give a better answer, but I can at least point the HKDF paper as containing some references that you might want to chase. See, e.g., Section 2, "Statistical and Computational Extractors," p. 5:

Efficient constructions of generic (hence randomized) statistical extractors exist such as those built on the basis of universal hash functions [15]. However, in spite of their simplicity, combinatorial and algebraic constructions present significant limitations for their practical use in generic KDF applications. For example, statistical extractors require a significant difference (called the gap) between the min-entropy $m$ of the source and the required number $m'$ of extracted bits (in particular, no statistical extractor can achieve a statistical distance, on arbitrary sources, better than $2^{−{m−m'\over 2}}$ [60, 63]). That is, one can use statistical extractors (with its provable properties) only when the min-entropy of the source is significantly higher than the length of output.

See also Section 5, "Random Oracles as Computational Extractors," pp. 11-12:

We note that random functions do not make by themselves good statistical extractors (here the key to the extractor is the description of the function itself). For example, if $\chi$ is the uniform distribution over $\{0, 1\}^{2k}$ (thus having min-entropy $2k$) and we choose a random function $f$ from $2k$ to $k$ bits, we expect $1/e^2$ of the points in $\{0, 1\}^k$ not to be in the image of $f$ (i.e., they are assigned probability 0 regardless of the sample from $\chi$), thus inducing an output distribution that is statistically far from uniform. Furthermore, the lower bounds on min-entropy gap from [60] mentioned in Section 2 apply to random functions as well.

So the short answer is: because of established theorems about randomness extractors.

$\endgroup$
  • $\begingroup$ Are you able to enumerate this gap? I have 11 KByte files with about 79 Kbits of entropy each. How much entropy could I expect to get through a hash based extractor then? $\endgroup$ – Paul Uszak Dec 4 '16 at 15:55

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.