Can someone explain to me what Diffie-Hellman Key Exchange is in plain English? I have read in a non-tech news page that Twitter has just implemented this technology which allows two persons to exchange encrypted messages on top of a non-secured channel. How is that (if this is true)?

up vote 318 down vote accepted

Diffie-Hellman is a way of generating a shared secret between two people in such a way that the secret can't be seen by observing the communication. That's an important distinction: You're not sharing information during the key exchange, you're creating a key together.

This is particularly useful because you can use this technique to create an encryption key with someone, and then start encrypting your traffic with that key. And even if the traffic is recorded and later analyzed, there's absolutely no way to figure out what the key was, even though the exchanges that created it may have been visible. This is where perfect forward secrecy comes from. Nobody analyzing the traffic at a later date can break in because the key was never saved, never transmitted, and never made visible anywhere.

The way it works is reasonably simple. A lot of the math is the same as you see in public key crypto in that a trapdoor function is used. And while the discrete logarithm problem is traditionally used (the xy mod p business), the general process can be modified to use elliptic curve cryptography as well.

But even though it uses the same underlying principles as public key cryptography, this is not asymmetric cryptography because nothing is ever encrypted or decrypted during the exchange. It is, however, an essential building-block, and was in fact the base upon which asymmetric crypto was later built.

The basic idea works like this:

  1. I come up with two prime numbers g and p and tell you what they are.
  2. You then pick a secret number (a), but you don't tell anyone. Instead you compute ga mod p and send that result back to me. (We'll call that A since it came from a).
  3. I do the same thing, but we'll call my secret number b and the computed number B. So I compute gb mod p and send you the result (called "B")
  4. Now, you take the number I sent you and do the exact same operation with it. So that's Ba mod p.
  5. I do the same operation with the result you sent me, so: Ab mod p.

The "magic" here is that the answer I get at step 5 is the same number you got at step 4. Now it's not really magic, it's just math, and it comes down to a fancy property of modulo exponents. Specifically:

(ga mod p)b mod p = gab mod p
(gb mod p)a mod p = gba mod p

Which, if you examine closer, means that you'll get the same answer no matter which order you do the exponentiation in. So I do it in one order, and you do it in the other. I never know what secret number you used to get to the result and you never know what number I used, but we still arrive at the same result.

That result, that number we both stumbled upon in step 4 and 5, is our shared secret key. We can use that as our password for AES or Blowfish, or any other algorithm that uses shared secrets. And we can be certain that nobody else, nobody but us, knows the key that we created together.

  • 9
    DH is public key/asymmetric crypto but not encryption. – CodesInChaos Nov 24 '13 at 12:15
  • 16
    I think it's worth mentioning that the reason this is secure is that, unlike normal log(x), the modular log(x) is thought to be hard to compute. Otherwise we could just do log_g(A) and log_g(B) to get a and b. – BlueRaja - Danny Pflughoeft Nov 24 '13 at 19:25
  • 12
    I think you might also want to add that g is not just any prime but a generator (or a primitive root) of p – TheRookierLearner Nov 26 '13 at 4:40
  • 24
    @TheRookierLearner this answer is a simplified explanation of DH; there are quite a few important details omitted for simplicity. This shouldn't be considered an implementation tutorial. – tylerl Nov 26 '13 at 5:57
  • 2
    @Mero55 You're not just finding the root of A, you're finding the roots of A, A+p, A+2p, A+3p, ... until the result is an integer. – kbolino Jul 7 '16 at 2:42

The other answers do an excellent job explaining the maths behind the key exchange. If you'd like a more pictorial representation, nothing beats the excellent paint analogy shown on the Diffie–Hellman key exchange Wikipedia entry:


DH key exchange image

Image is in the public domain

  • 4
    This image is great at explaining what it does. My only problem was "If the attacker knows the common paint and he knows the end mixtures, why can't he figure out the original color?". The answer is of course that it's not the color he needs to know, but the actual original mixture, and as you mentioned, the mixture separation is expensive. The actual mathematics that allows for this would be great to know in brief detail as well. – ffledgling Jul 29 '16 at 13:49
  • 1
    The math has been explained elsewhere but think of it like this: let's say that the "paint mixing function" is f(a,b) = (a+b)%1000. You and me announce "the shared secret is 793". Then I tell you f(my_secret, 793) = 172. What's my secret? Note that f(a, f(b, 793)) == f(b, f(a, 793)). The actual function used by DH is not so simple but all that's important is that information is lost and this commutative property holds. – HasFiveVowels Oct 22 '16 at 2:51
  • 3
    The color example is only illustrative. Obviously, calculating the color mixtures is trivial; the discrete log problem that DH uses is not. See en.wikipedia.org/wiki/Discrete_logarithm. – sovemp Mar 28 '17 at 17:15

Diffie-Hellman is an algorithm used to establish a shared secret between two parties. It is primarily used as a method of exchanging cryptography keys for use in symmetric encryption algorithms like AES.

The algorithm in itself is very simple. Let's assume that Alice wants to establish a shared secret with Bob.

  1. Alice and Bob agree on a prime number, p, and a base, g, in advance. For our example, let's assume that p=23 and g=5.
  2. Alice chooses a secret integer a whose value is 6 and computes A = g^a mod p. In this example, A has the value of 8.
  3. Bob chooses a secret integer b whose value is 15 and computes B = g^b mod p. In this example, B has the value of 19.
  4. Alice sends A to Bob and Bob sends B to Alice.
  5. To obtain the shared secret, Alice computes s = B^a mod p. In this example, Alice obtains the value of s=2
  6. To obtain the shared secret, Bob computes s = A^b mod p. In this example, Bob obtains the value of s=2.

The algorithm is secure because the values of a and b, which are required to derive s are not transmitted across the wire at all.

If you want a simpler plain English explanation of DH that can be readily understood by even non-technical people, there is the double locked box analogy.

  1. Alice puts a secret in a box and locks it with a padlock that she has the only key to open. She then ships the box to Bob.

  2. Bob receives the box, puts a second padlock that only he has the key to on it, and ships it back to Alice.

  3. Alice removes her lock and ships the box to Bob a second time.

  4. Bob removes his lock, opens the box, and has access to the secret that Alice sent him.

Since the box has always had at least one lock on while in transit, Eve never has the opportunity to see what's in side and and steal the secret: In this a cryptographic key that will be used for encrypting the remainder of Alice and Bob's communications.

  • 7
    Now this is what I call a plain English explanation. love you man. – user15119 Nov 24 '13 at 16:31
  • 49
    While plain English, this doesn't describe Diffie-Hellman. It describes the Three-pass protocol which has significantly different properties from DH. For example it requires three passes, whereas DH only requires a single pass. – CodesInChaos Nov 24 '13 at 18:21
  • 1
    I think CodesInChaos is expecting a lot of accuracy from a purposefully simplified analogy. This helped me understand the paint analogy better, which helped me understand the more accurate ones better. (Note the boxes have unlocker-holes too small to get the cookies out of the innermost box. That's what threw me at first.) – Nanban Jim Sep 27 '16 at 22:15
  • 9
    It's not a matter of "a lot of accuracy". The locked box analogy doesn't resemble Diffie Hellman at all. – HasFiveVowels Oct 22 '16 at 2:58
  • 1
    DH does not exchange secrets as this does, it generates them, but it's a fun read – sivann Aug 30 at 13:02

The key exchange problem

A secure connection requires the exchange of keys. But the keys themselves would need to be transfered on a secure connection.

There are two possible solution:

  1. exchange the key by physically meeting and sharing the keys.
  2. Somehow established a shared secret on a public unsecure channel. This is easier said than done, and the first such implementation of this is the Diffie-Hellman Scheme.

Properties

Diffie-Hellman makes use of a mathematical function with the following properties:

  1. It is EASY to compute f[x] (from x)
  2. It is HARD to invert f[x] to get x
  3. It is EASY to calculate S from A and f[B]
  4. It is EASY to calculate S from B and f[A]
  5. It is HARD to calculate S without either A or B (even with f[A] and f[B])

How DH scheme works

  1. Alice comes out with a random number A. She computes f[A], and sends f[A] to Bob. Alice never discloses her A, not even to Bob.
  2. Bob comes out with another random number B. He computes f[B], and sends f[B] to Alice. Bob never discloses his B, not even to Alice.
  3. Alice computes S using A and f[B]. Bob computes S using B and f[A]
  4. Mallory, who is Eavesdropping, has only f[A] and f[B], and so it is HARD for her to calculate S.
  5. Alice and Bob now share a common secret which can be used as (or to come up with) a key to establish a secure connection.

Side note:

The Diffie-Hellman Scheme does not provide authentication of any kind. It only allow 2 anonymous parties to share a common secret. But for all Alice knows, she could be shaking hands with the devil (instead of Bob). This is why we need at least one party to be authenticated.

For example: SSL (https), the webserver is authenticated using PKI (Public Key Infrastructure), and then a secure connection is established (D-H) between the website and the client. Since the website has been authenticated, the client can trust the website, but the website cannot trust the client. It is now safe for the client to provide his own authentication details on the webpage.

  • 2
    I really appreciate the side note here, it answered a nagging question I had but couldn't quite elucidate. – Nanban Jim Sep 27 '16 at 22:17

Diffie-Hellman is a mathematical algorithm to exchange a shared secret between two parties. This shared secret can be used to encrypt messages between these two parties. Note that the Diffie-Hellman algorithm does not provide authentication between these two parties.

  • It lacks explanation, I wish you could explain a little bit more... – user15119 Nov 24 '13 at 2:11
  • 8
    You wanted an english explanation without math. – Lucas Kauffman Nov 24 '13 at 8:56
  • In the case of an HTTPS connection, authentication is handled by the SSL certificate framework. You can be certain (as you can be) that you are communicating with the intended parties through verification and trust. The handshake/negotiation of an SSL connection is expensive in terms of overhead. The DH algorithm allows both parties to securely negotiate a symmetric key for encryption/decryption which is much more efficient. – k1DBLITZ Nov 25 '14 at 15:53

Computerphile's Diffie-Hellman videos are absolutely spectacular when it comes to explanations of this key exchange. Their video "Secret Key Exchange (Diffie-Hellman)" is quite thorough, but their explanation of the math behind DH is the best one I've come across so far in any medium (and certainly better than what I personally could write for you here). Take a watch here.

Securing data as it passes through the internet usually requires protecting it in two ways:

  • Confidentiality -- assuring no one except the intended recipients can read the data
  • Integrity -- assuring no one can modify or tamper the data in transit

Confidentiality is provided using Symmetric Encryption and Integrity is provided using a Message Authentication Code (MAC).

Both Symmetric Encryption and MAC's require that both parties have identical and secret keys (a "key" in this sense being simply a number, converted to binary).

The problem then is How do both parties establish identical and secret keys over the Internet? (or any other insecure medium). This is known as "the key exchange problem".

One of the solutions for this problem is the Diffie-Hellman algorithm.


Diffie-Hellman allows two parties to establish a shared secret over an insecure medium. Or, to put it more simply....

Imagine you and your friend were standing in a crowded room, surrounded by dubious looking people. Assume you and your friend needed to agree upon an identical number, but do not want anyone else in the room to know what number that is. Diffie-Hellman would allow you and your friend to cleverly exchange some numbers, and from those numbers calculate another number which is identical. And even though everyone in the room heard the numbers being exchanged, they have no way to determine the final number you and your friend arrived to.

We can see an example of this occurring in the image below. Alice and Bob will use the Diffie-Hellman key exchange to establish a shared secret.

Diffie-Hellman Key Exchange -- pracnet.net/crypto

Anyone "listening in" on the conversation would only "hear" the numbers which were exchanged in the middle: 13,6,2,9. There is no consistent way to combine these four numbers to attain the final shared secret: 3 without knowing one of either Alice or Bob's Private values (5 or 4) which were never shared.

That is the beauty of Diffie-Hellman.

The numbers used in the example above are small to keep the math simple. In reality, numbers used in modern Diffie-Hellman exchanges are (or ought to be) at minimum 2048 bits long -- which would require approximately 617 digits to write out!!


After finishing the Diffie-Hellman key exchange, both parties now possess an identical value, known only to each party.

This value becomes the "starting point" from which additional keys can be generated.

Earlier, we mentioned Symmetric Encryption and Message Authentication Codes each require a Secret Key. Well, take your DH Shared Secret and combine it with a few other values and now you have the Encryption and MAC keys you need.

The additional benefit is combining values to create keys is easy... It can be done as many times as necessary.

In fact, many security protocols (SSL/TLS, IPsec, etc) generate one set of keys to secure traffic in each direction -- a total of four keys (MAC + Encryption in one direction, MAC + Encryption in the other direction). All four keys generated from the same initial starting value, derived from Diffie-Hellman.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.