Diffie-Hellman

The Diffie-Hellman key agreement protocol (also called Diffie-Hellman key exchange, or just Diffie-Hellman, D-H or DH) is a technique of cryptography that allows two parties without any initial shared secret to create one in a manner immune to eavesdropping. Once they have done this, they can communicate privately by using that shared secret as a cryptographic key for a block cipher or a stream cipher, or as the basis for a further key exchange.

The Diffie-Hellman method is based on the discrete logarithm problem and is secure unless someone finds an efficient solution to that problem. It can use any of several variants of discrete log; common variants are over a field modulo a large prime (1536 bits for one heavily used group in IPsec) or a field defined by an elliptic curve.

Conventionally, the two communicating parties are A and B or Alice and Bob.

Given a prime p and generator g (see discrete logarithm), Alice:

   * generates a random number a
   * calculates A = g^a modulo p
   * sends A to Bob

Meanwhile Bob:

   * generates a random number b
   * calculates B = g^b modulo p
   * sends B to Alice

Now Alice and Bob can both calculate the shared secret s = g^(ab). Alice knows a and B, so she calculates s = B^a. Bob knows A and b so he calculates s = A^b.

An eavesdropper will know p and g since these are made public, and can intercept A and B but, short of solving the discrete log problem, these do not let him or her discover the secret s.

Attacks

If the attacker either subverts one of the computers involved or finds an efficient solution to the discrete logarithm problem, then all bets are off — the Diffie-Hellman protocol canot be secure under those conditions. Discrete log is a well-studied problem and no efficient solution has been published; it is possible that none exists. On the other hand, no proof that an efficient solution does not exist has been published either. It is at least conceivable that an efficient method will be published next week, or even that that some intelligence agency has one already and are keeping it secret.

If either Alice or Bob uses a weak random number generator, or uses a good pseudo-random generator but does not provide it with a good truly random seed, then the protocol can be subverted. The attacker can make guesses at a or b; a correct guess breaks the system. If the random number generator is sufficiently weak, or uses a weak seed, then the number of guesses required for this attack may not be prohibitive. An early version of Netscape SSL was broken because of poor seeding practices . However with large p, a good generator, and a good seed this attack is wildly impractical.

With the exceptions mentioned above, the protocol is secure against all passive attacks.

Authentication required

However, the protocol itself is not at all resistant to an active attack, in particular a man-in-the-middle attack. If a third party can impersonate Bob to Alice and vice versa, then no useful secret can be created. Authentication of the participants is a prerequisite for safe Diffie-Hellman key exchange. Without authentication, neither Alice nor Bob know who they are talking to; they may think they are talking to each other, but actually both be talking to the man in the middle.

There are several ways to do the required authentication. For example, in Internet Key Exchange (IKE), authentication can be done with a shared secret or with any of several public key techniques. In Transport Layer Security (TLS), it is done by exchange of X.509 Certificates.

RFC 5386 and RFC 5387 propose Better than nothing security or BTNS, basically IPsec done without authentication. Setting up and managing a secure authentication infrastructure is not a trivial task and unauthenticated encryption does at least protect against all passive eavesdropping.