Diffie-Hellman

The Diffie-Hellman key agreement protocol (also called Diffie-Hellman key exchange, or just Diffie-Hellman, D-H or DH) 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.

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 cannot exist has been published either. It is at least conceivable that some intelligence agency has such a method 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.

However, the protocol is not at all resistant to active attacks, in particular man-in-the-middle attacks. Conventionally, the two communicating parties are A and B or Alice and Bob. 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. 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.