Entropy Requirements for Encryption

Question

Quality of RNGs is an important issue.

As a very basic question I would like to understand, how "poor" entropy of a RNG can help an attacker to find out the whole secret.

In my naive view, even is a RNG (e.g. of 128 Bit) is not perfect in terms of entropy, but deviates, lets say ~0.1 % from the perfect value 128, so that it has only Entropy 127, how can an attacker find the key? Guessing the remaining 127 Bits would also be an infeasible task - ??? So what can he practically do?

I would also appreciate a good source for reading.

thanks ;-)

Answer 1

For example, assume an RNG spits 128-bit values $X$ that are all-zero with odds $p=1/120$, and otherwise independent and evenly distributed among the other values. The 128-bit values spit by this RNG contain $H(X)=-p\log_2(p)-(1-p)\log_2\big((1-p)/(2^{128}-1)\big)>127$ bits of entropy.

Yet, if repeatedly the same secret is XOR-ed with this RNG forming 128-bit ciphertext blocks, the secret can be recovered, with overwhelming odds, as the first value that repeats; and there are better than even odds that this occurs with a mere 250 ciphertexts.

---

Another example would be a 128-bit RNG where each bit is independent with odds $p=9/20$ to be one, for $H(X)=-128\big(p\log_2(p)+(1-p)\log_2(1-p)\big)>127$ bits of entropy.

With the same hypothesis as in the first example, the secret can be recovered by keeping the most frequent bit value for each rank. Few hundred ciphertexts are enough to recover the secret with fair odds.

Note: the generator of the second example is still safe to generate AES-128 keys; while the first is disastrous; which illustrates that entropy is not the only thing that matters for a RNG.

Answer 2

The relationship between difficulty of guessing/predicting an unknown random variable $X$ and entropy (or entropies) is quite a delicate one, and depends on the assumptions about the attack scenario. In particular, the direct use of Shannon entropy can give misleading results.

It was shown by John Pliam (see preprint ) that if $X$ is a discrete random variable with $M$ points in its support $H(X)$ can be close to its maximum value $\log M$ while the probability of an optimal guessor discovering the actual value of $X$ in $k$ sequential questions is much less than $2^{H(X)}=M.$

Moreover, not only the expected number of guesses, but arbitary moments of the number of guesses can be related to Renyi entropies of various order. Renyi entropies are a family of entropies $H_{\alpha}(X)$ with parameter $\alpha \in [0,1)\cup(1,\infty)$ which satisfy $$\lim_{\alpha \rightarrow 1}H_{\alpha}(X)=H(X),$$where $H(X)$ is the Shannon entropy of $X.$

One result on the expectation is that the expected number of guesses to determine a random variable $X$ (for the optimal guessing sequence) is upperbounded by

$$2^{H_{1/2}(X)-1}$$

where $H_{1/2}(X)$ denotes the Renyi entropy of order $\alpha=1/2$ and is also called guessing entropy. Moreover, it is lowerbounded by (for all guessing sequences)

$$\frac{2^{H_{1/2}(X)}}{1 + \log M } \approx 2^{H_{1/2}(X)} / H_{max}(X)$$

where $H_{max}(X)$ is the maximum entropy $\log M$ in either the Renyi or the Shannon case. Papers by J L Massey, Arikan, Boztas and others have followed this train of thought.