How random is the value $ZZ$ in the DH protocol?
This question was triggered by this somewhat naïve implementation in I2P shown by Sergei at Stackoverflow. Obviously $ZZ$ is distinguishable from a random oracle, as the first byte will be lower or equal to the highest byte of $p$, if $p$ is encoded using the same $I2O$ (integer-to-octetstring) function.
Is there a mathematical function that shows how much "entropy" there is in the first (highest order) $x$ bytes taken out of $ZZ$?
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.
