7
$\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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Dec 4, 2016 at 15:55
  • $\begingroup$ Pretty old question, but decided to say this so that any future people can see this. It depends on how you hash the data. If you take all the files, concatenate them, and then hash it with SHA-256, you'll get 256 bits of entropy. Also, it depends on the hash's output size. If we have some hash function SHA, and you're feeding it more entropy than it's output size, the bits of entropy entropy will be the output size. (For SHA-256 = 256 bits, etc.) This only applies if you're feeding the hash function more entropy than it's output size. $\endgroup$
    – 09182736471890
    Commented Nov 25, 2019 at 19:05
  • $\begingroup$ I think the section you quote is in error. If you have a random function $f: A \rightarrow B$ where $|B| = n$ and $|A| = mn$, it's easy to show that we expect around $1/e^m$ points in $|B|$ not to be in the image of $f$. I think the author saw $k$, $2k$ and thought $m = 2$, but actually $|B| = 2^k$, $|A| = 2^{2k}$, $m = 2^k$. $\endgroup$
    – Paul Crowley
    Commented May 10, 2020 at 16:50
  • $\begingroup$ Almost exactly ten years later, a new version of the paper has been uploaded to ePrint to correct this section eprint.iacr.org/2010/264 $\endgroup$
    – Paul Crowley
    Commented May 11, 2020 at 2:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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