# How random is the shared secret in the Diffie Hellman key agreement

Being triggered by this horrible implementation in I2P shown by Sergei at Stackoverflow, I would like to know how random the value ZZ in the DH protocol is. Obviously it is distinguishable from a Random Oracle, as the first byte will be lower than the highest byte of p (if p was to be encoded using the same integer-to-octet or I2O function).

Is there a mathematical function that shows how much "entropy" would be in an X number of bytes taken out of ZZ?

-
I would be very happy if anyone wants to extend my answer on stackoverflow or post a better one, of course - I'll certainly make sure that the answer here is converged into my answer on stackoverflow. –  owlstead Jul 24 at 23:47
I'm pretty sure that taking the 32 least significant bytes doesn't lead to noticeable entropy loss. Not sure about about the MSB. –  CodesInChaos Jul 25 at 7:37
@CodesInChaos there is certainly entropy loss in the first byte, and because the implementer forgot to left-pad and left a spurious 00 bytes for many values, I'm pretty sure that that is loss of entropy too. But I don't know about the MSB bits that at least look random. I'm pretty sure you cannot just perform size of secret * (relative key strength / size of prime) though (that would be too easy). –  owlstead Jul 25 at 14:54

The shared secret generated by the Diffie–Hellman key exchange is a random element of the subgroup of the multiplicative group modulo $p$ generated by $g$.

In particular, for $g$ and $p$ chosen as specified in RFC 2631 section 2.2, i.e. so that $p = jq+1$, where $q$ and $p$ are both prime, $j$ is a small number (often 2, making $p$ as safe prime) and $g$ generates the order $q$ subgroup modulo $p$, this subgroup contains $q$ elements and the shared secret therefore (assuming that the private keys are appropriately generated, of course) has $\log_2 q$ bits of entropy.

The recommended way to extract this entropy into a useful form is to hash the shared secret or, better yet, feed it into a key derivation function like HKDF (RFC 5869). What you're asking is how bad is it if we simply take the first (or last) 256 bits of the binary encoding of the shared secret and use them as an AES-256 key?

My answer, a bit surprisingly, would be "not too bad." We may not get quite 256 bits of entropy out of the secret that way, but we ought to get at least 247 bits or so (assuming that the secret is long enough to have that many bits in the first place, of course), which is still plenty enough for any practical purposes.

Specifically, let's assume that $p$ is a safe prime (i.e. $j=2$), and that the secret is padded to the minimum number of bytes needed to encode $p$, as specified in RFC 2631. Thus, the padded secret will be a bitstring with $n = 8 \cdot \lceil (\log_2 (p+1)) /8 \rceil \le \log_2 p + 8$ bits, and will contain $$m = \log_2 q = \log_2((p-1)/2) = \log_2(p-1)-1 \approx \log_2 p - 1$$ bits of entropy. When we truncate the secret to 256 bits, we throw away some of this entropy, but at most only as many bits as we remove from the length. Thus, the truncated secret will contain at least $m - (n - 256) = 256 - (n - m) \ge 256 - 9 = 247$ bits of entropy.

Now, in the code you refer to, the secret is apparently not padded to a fixed number of bytes, but rather has leading zero bytes removed. However, at least assuming that $q \gg 2^{256}$, this still should not make much difference. (In fact, in some cases it might even slightly increase the entropy left after truncation.)

To see why, let $k = 8 \cdot \lceil (\log_2(z+1))/8 \rceil$ be the number of bits needed to encode the secret $z$. First, we'll observe that ${\rm Pr}[k < 256] = {\rm Pr}[z < 2^{256}] \le 2^{256} / q = 2^{256-\log_2 q}$. For, say, $q > 2^{336}$, this probability is negligible (less than $2^{-80}$). Thus, for large enough $q$, we may safely assume $k \ge 256$.

Now, for each possible length $k$, the secret $z$ lies in the interval $2^{k-8} \le z < 2^k$. Using the same argument as above, we may show that, for any given $k$, $z$ must have at least $k - 9$ bits of entropy, and that truncating it to 256 bits must leave at least $256 - 9 = 247$ bits of entropy. Since we'll have at least 247 bits of entropy regardless of $k$ (except in negligible cases), we'll have at least 247 bits of entropy overall.

(For $j > 2$, the constant $9$ above becomes $8 + \log_2 j$ instead, but that makes little difference unless $j$ is huge, which it normally shouldn't be.)

All that said, none of the above should be taken as an argument against using a proper KDF to convert Diffie–Hellman secrets into key material. You definitely should do that, if only because a) the standards say so, b) it's still more secure and c) it provides other benefits such as salting. Still, it does appear that simply using the raw truncated D–H shared secret as an encryption key may not be quite as bad as one might assume just based on reading the RFCs.

-
I'll accept this as it is hard to get a better answer than this. Note that the implementation also leaves the first 00 byte if the number is the same size as the prime (in bits) so the result may be 129 bytes instead of 128 for a 1024 bit key. I think I can calculate the -average - loss of entropy for that myself. –  owlstead Jul 26 at 10:07