Entropy of two concatenated random values

Question

In this Intel blog posting, the author claims:

The amount of work required to brute-force predict a random value that has n bits of entropy is $O(2^n)$. If you concatenate two values together, the entropy required to brute force the result becomes only $2^n + 2^n = 2^{n+1}$. By combining two n-bit random values, each with n bits of entropy, in this manner you get a random number with effectively only one additional bit of entropy.

Is this correct? My intuition suggests it would be $2n$ bits of entropy. But on the other hand, the two values are independent, so I can kind of see why it might be $n+1$ bits. Can anyone explain this?

Answer 1

Even in context, much of what is written in the blog post makes no sense. E.g., it says:

While it can be argued that the DRNG is in reality just splitting a 128-bit value into two pieces and handing them to you one piece at a time, from a theoretical viewpoint this does not matter. While the original value had 128 bits of entropy, the end result is that you are handed two 64-bit numbers one at a time, each of which only has 64 bits of entropy. Because they come from a pseudorandom number generator, the entropy is additive when the values are concatenated, and the resulting 128-bit number has only 65 bits of entropy.

This is just wrong. If you have a 128-bit string that's truly uniform (i.e., has 128 bits of entropy) and split it in half then concatenate the halves, you clearly still have the original string and thus 128 bits of entropy. The rest of the post is a similar muddle, so I wouldn't give it much credence.

Entropy of independent random strings is indeed additive, but not in the way the post says. Concatenating independent strings having entropy $n$, $m$ yields a string of entropy $n+m$, full stop.

Note however that the strings need to be truly independent to reach this conclusion. Strings generated as outputs of a deterministic RNG algorithm will not be truly independent, and in fact their concatenation will not have any more true entropy than that of the seed provided to the RNG (and may even have less).

I don't know whether the outputs of these Intel instructions can be considered independent or not, but either way this aspect of the blog post is incorrect.

Answer 2

Their numbers are off and the explanation confusing, but they do have a point.

The algorithms used for RDRAND/RDSEED instructions are described in the software implementation guide (pdf). What it amounts to is that for RDRAND, some hardware entropy is conditioned and used as a 256-bit seed for AES CTR_DRBG (from SP 800-90A).

The same 256-bit seed is used to create up to 1022 64-bit random values, if called quickly enough. Since up to 65408 bits are generated from a 256-bit seed, you can't concatenate them for arbitrary entropy.

Specifically, if you created a 512-bit value, it could "only" have about 256 bits of entropy. Do the math considering the 64-bit splitting and I think you'll end up with 257 bits in total: it's either one of the at most $2^{256}$ 512-bit values the AES CTR_DRBG can generate, or else it is the middle 512-bits of a 640-bit value. In that sense concatenating two 256-bit numbers adds a single bit of entropy.

When you consider combining two 64-bit numbers, however, that logic does not apply. There is no brute-force attack that will let you narrow it down to fewer than $2^{128}$ possible values. The DRBG would have to have a state smaller than 128-bits for there to be an attack, and that would no longer be cryptographically secure.

In comparison, RDSEED always returns independent numbers with entropy from the hardware RNG. That means they can be concatenated to arbitrary length numbers with full entropy.

---

The rationale for using cryptographic mixing is also wrong. If the inputs to the HMAC or AES combiners have only $n$ bits of entropy, then the output can't have any more either. The only way it would help is if some of the inputs (e.g. a longer term key) came from independently seeded instances of the DRBG.

Answer 3

It would appear that, in this case, your intuition is correct, and the Intel guy is wrong.

When you concatenate two random values, the entropy contained in the concatination depends not only one the entropy of those two sources, but whether they are correlated.

If they are entirely uncorrelated, that is, if the probability distribution of one of the random variables is independent on the value of the other random variable, then the entropy of the concatenation is the sum of the entropies of the two sources.

In this specific case, the two adjacent values are effectively uncorrelated; according to the Intel article, two adjacent outputs are either the lower and upper 64 bits of SP800-90 DRBG output, or the lower 64 bits of one DRBG output and the upper 64 bits of the next output. That specific DRBG is believed to have much more than 128 bits of entropy; this concatination is effectively just glueing the original sequence back together.