The Diffie-Hellman Key Exchange Process

The Diffie-Hellman algorithm, introduced by Whitfield Diffie and Martin Hellman in 1976, was the first system to utilize "public-key" or "asymmetric" cryptographic keys. ( Evidence shows that Comm-Electronics Security Group (an arm of the U.K. government) may have invented the concept of asymmetric key 6 years before D-H. The CESG papers were classified for 20 years, but Diffie-Hellman figured it out on their own without the information in those papers.) These systems overcome the difficulties of "private-key" or "symmetric" key systems because key management is much easier. In a symmetric key system, both sides of the communication must have identical keys. Securely exchanging those keys has always been an enormous issue. As one example, the National Security Agency has an entire fleet of it's own planes manned by armed couriers to shuttle around the approximately fifteen tons of paper based symmetric key used by the United States Government every year. Businesses simply do not want to mess with that. Asymmetric key systems alleviate that issue because they use two keys - one called the "private key" that the user keeps secret and one called the "public key" that can be shared with the world. Unfortunately, the advantages of asymmetric key systems are overshadowed by speed - they are extremely slow for any sort of bulk encryption. Today, it is typical practice to use a symmetric system to encrypt the data and an asymmetric system to encrypt the symmetric keys. That is precisely what Diffie-Hellman is capable of doing - and does do when used for key exchange as described here.
Diffie-Hellman is not an encryption mechanism as we normally think of them in that we do not typically use it to encrypt data. Instead, it is a method to securely exchange the keys that encrypt data. Diffie-Hellman accomplishes this secure exchange by creating a "shared secret" (sometimes called a "key encryption key") between two devices. The shared secret then encrypts the symmetric key (or "data encryption key" i.e. DES, Triple DES, CAST, IDEA, Blowfish, etc.) for secure transmittal.The protocol has two system parameters p and g. They are both public and may be used by all the users in a system. Parameter p is a prime number and parameter g (usually called a generator) is an integer less than p, with the following property: for every number n between 1 and p - 1 inclusive, there is a power k of g such that n = gk mod p. Suppose Alice and Bob want to talk across an insecure medium. First they must agree on a shared secret key which they get by both picking two large prime numbers, n and g, where (n-1)/2 is also a prime and certian conditions apply to g. These numbers may be public, so either one of them can just pick n and g and tell the other openly. Now Alice picks a large (say 512-bit) number, x, and keeps it secret. Bob also does the same and keeps his number y secret. These numbers are called their private keys. Alice will initiate the key exchange protocol by sending Bob a message containing ( n, g, gx mod n ) as shown in fig 1. Bob responds by sending Alice a message containing gy mod n . Now Alice takes the number Bob sent her and raises it to the xth power to get (gy mod n )x. Bob performs a similar operation to get ( gx mod n )y . By the laws of modular arithmetic, both calculations yield gxy mod n. Now Alice and Bob are sharing a secret key g xy mod n.

Example of the Diffie-Hellman :
Lets assume that there is an intruder called Trudy that is trying to listen in on Alice's and Bob's conversation. Trudy has already seen Alice and Bob's first two messages where they exchanged public keys with there private keys encryped in them, and have agreed on a shared secret key, so Trudy knows g and n. If she could compute x and y she could figure out the secret key. But beacuse she only knows gx mod n, she cant find the value of x. There is no known practical algorithm for computing discrete logarithms modulo for very large prime numbers. To make this example more concrete, we will use the values of n = 47 and g = 3. Alice picks x = 8 and Bob picks y = 10 (These numbers are completely unrealistic and are only being used to prove a point). Both of these numbers (x and y) are kept secret. Alice's message to Bob is (47,3,28) because 38 mod 47 is 28. Bob's message to Alice is (17). Alice computes 178mod 47, which is 4. Bob computes 2810mod 47, which is 4. Alice and Bob have independently determined the secret key is now 4. Trudy has to solve the equation 3xmod 47 = 28, which can be done with exhaustive search for small numbers like this, but not when all the numbers are hunderds of bits long.

Problems with the Diffie-Hellman Key Exchange :
Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. In this attack, an opponent Trudy intercepts Alice's public value and sends her own public value to Bob. When Bob transmits his public value, Trudy substitutes it with her own and sends it to Alice. Trudy and Alice thus agree on one shared key and Trudy and Bob agree on another shared key. After this exchange, Trudy simply decrypts any messages sent out by Alice or Bob, and then reads and possibly modifies them before re-encrypting with the appropriate key and transmitting them to the other party. This vulnerability is present because Diffie-Hellman key exchange does not authenticate the participants. Possible solutions include the use of digital signatures and other protocol variants.
Simple version of Diffe-Hellman :
  1. Alice chooses a random value x.
  2. Alice sends gx mod n to Bob.
  3. Bob chooses a random value y
  4. Bob sends gy mod n to Bob.
  5. Alice computes gxy mod n as (gxmod n)y mod n<

  6. Bob computes gxy mod n as (gymod n)x mod n

 

Why do we care about Diffie-Hellmen

           Simply stated, if you are involved in any sort of Virtual Private Network (VPN), you are probably using Diffie-Hellman, even if you didn't realize it. If that VPN is operating on the IPSec standard, then Diffie-Hellman is certainly in use. To follow the standards trail for key management in IPSec, we begin with the overall framework called Internet Security Association and Key Management Protocol (ISAKMP; see RFC 2408). Within that framework is the Internet Key Exchange (IKE) protocol (see RFC 2401). IKE relies on yet another protocol known as OAKLEY and it uses Diffie-Hellman as described in RFC 2412. It is an admittedly long trail to follow, but the result is that Diffie-Hellman is, indeed, a part of the IPSec standard.


(Figure 1) Diffie-Hellman Key Exchange

Here are a few links to some sites of interest.

Diffie-Hellman

PGP

RSA

DES

MD5