How large should the prime $p$ and generator $g$ values be in a Diffie-Hellman handshake if the messages are encrypted.

If the key that encrypted the Diffie-Hellman messages becomes compromised, then does that compromise the key generated using Diffie-Hellman?

  • 2
    $\begingroup$ Messages being encrypted doesn't make a difference. Just use a standard group designed for diffie-hellman. $\endgroup$ Mar 18 '13 at 8:03
  • 1
    $\begingroup$ You should also ask yourself what you're using DH for, if you already have a shared key? Forward secrecy? $\endgroup$ Mar 18 '13 at 8:03
  • $\begingroup$ Forward secrecy is one reason, but also it is commonly used in password protocols as well, where the key is the password. $\endgroup$
    – jaye1234
    Mar 18 '13 at 8:20

How large should $p$ be if the Diffie-Hellman exchange is encrypted? Well, that rather depends on:

  • How much do you trust the encryption key not to be recovered?

  • Why are you doing a Diffie-Hellman in the first place?

If you can trust that the encryption key will never be recovered by anyone other than the sender and the receiver, then it doesn't really matter how large of a Diffie-Hellman modulus you use. On the other hand, you don't need to do Diffie-Hellman at all, you could have one side pick a random value, and send that, encrypted by the key that we trust.

However, if you can't assume that the encryption key may not be compromised, then it would appear that you would have the same requirements on the DH parameters that we have on unencrypted exchanges; which (with the current hardware and DLOG algorithms) is that $p$ be at least 1024 bits, and that $g$ has an order that's a prime at least 256 bits long.

BTW: you asked about the size of $g$; its actual size isn't important. What's important is its order, that is, the smallest $x>0$ for which $g^x = 1 \bmod p$. This order $x$ should be a large prime value. Small values of $g$ can achieve this; in particular, if $(p-1)/2$ is also prime and $p = 7 \bmod 8$, then $g=2$ will always have a large prime order (and, in fact, in such a modulus, you can show that if someone can solve the computational DH problem with $g=2$, then they can solve it in that modulus for any value of $g$ with a polynomial number of queries).

Lastly, you mentioned that you were doing this for a password protocol. If so, I would strongly urge you not to encrypt the DH value with a password-derived key, but instead use a protocol with PAKE properties (such as SRP or EKE. One of the properties is that someone who passively watches the protocol messages can't learn anything about what password might be used. In contrast, if you just encrypt a DH exchange with the password as the key, what someone might try is to decrypt your messages with his guess at a password, and see if the message makes sense. Even if you don't include any protocol bits in the encrypted message for him to check, what he might try is to see if the decrypted DH value is within the group that you're using to do DH (and if it's not, he has just learned that his guess at a password is not it, and can be removed from his list). The existing PAKE protocols avoid that sort of possibility. In EKE, they actually do encrypt the DH value with a password derived key; they are just careful not to leak any information about the password when they do it.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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