Diffie-Hellman

	Main Article	Discussion	Related Articles  [?]	Bibliography  [?]	External Links  [?]	Citable Version  [?]
	This editable Main Article is under development and subject to a disclaimer. [edit intro]

The Diffie-Hellman key agreement protocol (also called Diffie-Hellman key exchange, or just Diffie-Hellman, D-H or DH) ^[1] 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 = ga modulo p
   * sends A to Bob

Meanwhile Bob:

   * generates a random number b
   * calculates B = gb 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 can intercept A and B. We assume he will know p and g; by Kerckhoffs' Principle he may know everything about the system except the current keys, a and b. However, short of solving the discrete log problem, this does not let him discover the secret S.

Passive attacks[edit]

If the attacker finds an efficient solution to the discrete logarithm problem, then all bets are off — the Diffie-Hellman protocol is secure only if discrete log is intractable. Discrete log is a well-studied problem and no efficient solution has been published; it seems likely 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 some intelligence agency has one already and is keeping it secret.

There are pitfalls in the choice of the prime and generator ^[2]; poor choices make the discrete log problem much simpler.

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 ^[3]. 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.

Active attacks[edit]

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), ^[4] authentication can be done with a shared secret or with any of several public key techniques. In Transport Layer Security (TLS), ^[5]it is done by exchange of X.509 Certificates. How to do it securely when the only authentication available is a password short and simple enough for humans to remember is an active area of current research.

Better than nothing security, or BTNS, is basically IPsec done without authentication ^[6], ^[7]. Setting up and managing a secure authentication infrastructure is not a trivial task and unauthenticated encryption does at least protect against all passive eavesdropping.

There are variants of a man-in-the-middle attack which involve the attacker choosing specific values for a and b that help him break the system^[2]

References[edit]