294

Can someone explain what the Diffie-Hellman Key Exchange algorithm in plain English? I have read that Twitter has implemented this technology which allows two parties to exchange encrypted messages on top of a non-secured channel. How does that work?

Xander
  • 35,616
  • 27
  • 114
  • 141

11 Answers11

400

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 a prime number p and a number g which is coprime to p-1 and tell these numbers to you. (FYI: p for "Prime", g for "Generator")

  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.

FYI: DH Parameters
The numbers from step 1 (p and g) are the "Diffie-Hellman Parameters." You usually compute these well ahead of time since it takes a while. These aren't secret, so they tend to be reused. For a long time many servers all just used the same values for p and g, and not particularly good ones, leading to a bit of a kerfuffle (which got named Logjam) that might be fun to read about if you're interested.

tylerl
  • 82,665
  • 26
  • 149
  • 230
  • 13
    DH is public key/asymmetric *crypto* but not *encryption*. – CodesInChaos Nov 24 '13 at 12:15
  • 23
    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
  • 14
    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 04:40
  • 29
    @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 05:57
  • But assuming this an insecure network, can't i just find the root of 'A' and therefore 'a'. and voila! sorry for my amateur question but i have to learn :p – Mero55 May 25 '16 at 12:41
  • 3
    @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 07 '16 at 02:42
  • Brilliantly explained ! Thanks a lot for the clear answer :D. – Shivam Aggarwal Nov 27 '16 at 15:45
  • why is this the building block of asymmetric crypto? if the keys discovered and used either side are the same are these not symmetric keys ? – whytheq Apr 23 '17 at 13:47
  • Why does $g$ need to be prime? For example, if $g\neq2$ works then $p-g$ also works (and is even so not prime). Surely stipulating that $g$ is prime cuts down on your options...(and hence makes the key "easier" to guess). – user1729 Sep 12 '17 at 09:15
  • thank you very very much for this clear explanation of DH :) – Fernando Gabrieli Oct 05 '17 at 15:42
  • For reasons of security the prime numbers **a** and **b** should both be reasonably *high* numbers and have some distance to each other. – Socrates Dec 06 '17 at 19:18
  • 2
    @whytheq yes, after the DH procedure both parties get the same secret key. This key can then be (and typically is) used to encrypt messages using a symmetric algorithm. Since asymmetric encryption is much slower than symmetric, this is often done. Moreover, DH is said to be the building block of asymmetric crypto because it is very similar to RSA (which has been developed later) and a full-fledged encryption algorithm can be derived from DH. – A. Darwin Apr 20 '18 at 16:37
  • what happens if someone use our secret key to fool us about his identity. If someone knows that secret he can use it to hide his identity – user3070752 Jun 09 '18 at 06:35
  • @tylerl You could just *note* that **g** and **p** have additional properties. E.g., "I come up with two prime numbers (that have some additional properties that we won't get into) **g** and **p** and tell you what they are." – jpmc26 Sep 12 '18 at 16:10
  • @tylerl I'm not sure this is the correct use of Perfect Forward Secrecy(PFS). From your answer, it is inferred that PFS comes with DH key exchange however this should not be the case. For example ECDH and ECDHE are both derevied from DH but only the latter one has PFS because of generating ephemeral key in each session. – Makif Nov 19 '18 at 04:27
  • @Makif DH is what makes PFS possible, but ECDH (not ephemeral) stores and re-uses keys, which sorta defeats the purpose if PFS is your objective. – tylerl Nov 21 '18 at 03:15
  • I think a less confusing way to state the equation is that "(g^a)^b = g^ab" and "(g^b)^a = g^ba", all done in modulo p. That way there's less "mod" all over the place. – forest Jul 08 '19 at 01:23
  • Do the values of P and G change or are they just constants? – Matthew Tranmer Oct 31 '21 at 23:16
  • 1
    @matthewtranmer a little of both. Added a small update explaining. – tylerl Nov 01 '21 at 15:56
  • Note the problem with Logjam is specifically that the group was too small, not that it was shared. Using a correctly-generated large-enough shared group is safe and is _one_ approach recommended in the paper. The other problem is that a _maliciously_ generated group (with g^x confined to a small subgroup) is not safe at all. If you want to communicate with somebody other than yoiurself, it's safe for you to use your own parameters but not theirs, and safe for them to use their own parameters but not yours, so you can't communicate at all. ... – dave_thompson_085 Nov 02 '21 at 03:30
  • ... As a result TLS recently changed _to_ standardized/shared groups (that are reliably chosen and large enough), optional in TLS1.2 and below (rfc7919) and mandatory in TLS1.3 (rfc8446). These use the same scheme (with different details) as IPsec/IKEv2 always and SSH _usually_; SSH allows both standard 'Oakley' groups and user-chosen groups. – dave_thompson_085 Nov 02 '21 at 03:33
158

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

Tobi Nary
  • 14,352
  • 8
  • 44
  • 58
Duncan Jones
  • 1,647
  • 1
  • 10
  • 14
  • 5
    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
  • 2
    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. – Tim Oct 22 '16 at 02: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 https://en.wikipedia.org/wiki/Discrete_logarithm. – sovemp Mar 28 '17 at 17:15
  • That is very clever and easy way to make other understand the fundamentals. – Mubashar Dec 17 '18 at 05:37
  • And either Bob or Alice starts it off by publically sending the common paint to the other? – LightCC Jan 17 '19 at 20:44
  • @LightCC The common paint is usually standardized, so they both know in advance what the other is using. There's no need for them to send it. In DH, this common color is called the "generator", or _g_, and is usually the number 2 or 5. The "+" operation in real DH is exponentiation modulo a public prime _p_ (which may or may not be known beforehand instead of being exchanged, depending on implementation). That is what mixing the paint refers to. Undoing this modular exponentiation is hard and that's what makes DH secure. – forest Jul 08 '19 at 01:26
  • @forest So, the fact that the world may know what the "common paint" is, still keeps them from figuring out what the individual secret paint is? Or if you implement it that way, do you need to pick random secret paint colors each time? My assumption is that if you keep the common and the secret paint colors constant all the time, it becomes hackable (through a determined, long-term effort), and that randomly varying one (or both) and reestablishing sessions occasionally, will resolve that issue. – LightCC Jul 09 '19 at 03:36
  • @LightCC The common paint doesn't need to be changed and there's no security issue with keeping it the same. The analogy involves mixing, but in reality, it's modular exponentiation. It computes "g^x mod p", where _g_ is the common paint, _x_ is the secret paint, and _p_ is a prime number that's necessary to make the mixing operation irreversible. Although it _is_ true that using the same _p_ over and over can _potentially_ result in the system being breakable after a determined, long-time effort. The [weakdh site](https://weakdh.org/) explains more. – forest Jul 09 '19 at 05:47
  • In cryptography, sometimes what's intuitive isn't necessarily correct. Take the Rabin cryptosystem for example, which encrypts with a message _m_ by computing "m^2 mod pq" for secret primes _p_ and _q_. That number 2 is a constant and never changes, and yet the Rabin system has been _proven_ to be as hard as integer factorization. You are right that the secret paint needs to be changed often though. For standard "ephemeral" DH (usually called DHE in TLS suites), it changes for every single key exchange. – forest Jul 09 '19 at 05:55
40

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.

Ronald
  • 103
  • 3
  • 18
    It's nice, but you could've also quoted that it's from [Wikipedia](https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange#Cryptographic_explanation). – Waffle's Crazy Peanut May 04 '15 at 02:50
35

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.

Dan Is Fiddling By Firelight
  • 1,382
  • 10
  • 14
  • 8
    Now this is what I call a plain English explanation. love you man. –  Nov 24 '13 at 16:31
  • 65
    While plain English, this doesn't describe Diffie-Hellman. It describes the [Three-pass protocol](http://en.wikipedia.org/wiki/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
  • 17
    It's not a matter of "a lot of accuracy". The locked box analogy doesn't resemble Diffie Hellman at all. – Tim Oct 22 '16 at 02:58
  • This at least show it is possible. Initially some people think than shared key over observable channel cannot be created in principle. – h22 Nov 22 '17 at 07:14
  • @NanbanJim It does not represent Diffie Hellman at all, it just shows some another method, of exchanging secret. – Suraj Jain Mar 19 '18 at 04:02
  • 2
    DH does not exchange secrets as this does, it generates them, but it's a fun read – sivann Aug 30 '18 at 13:02
  • Thanks! this is a very good and sensible analogy! (though not explaining DHE) – MewX Oct 26 '18 at 02:22
  • if you could not visualize this simple explanation in your head without reading it a second time (I did), here's a video from an awesome Royal Institution public science lecture series explaining it https://youtu.be/U62S8SchxX4?t=85 you can clearly count the three passes @CodesInChaos mentioned. – Wis May 06 '20 at 13:58
26

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.

aiao
  • 409
  • 5
  • 7
  • 5
    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
11

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.

Eddie
  • 751
  • 1
  • 6
  • 21
6

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.

Matthew
  • 27,263
  • 7
  • 89
  • 101
Lucas Kauffman
  • 54,229
  • 17
  • 113
  • 196
  • It lacks explanation, I wish you could explain a little bit more... –  Nov 24 '13 at 02:11
  • 11
    You wanted an english explanation without math. – Lucas Kauffman Nov 24 '13 at 08: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
2

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.

securityOrange
  • 921
  • 5
  • 12
0

Goal of Diffie–Hellman: secretly share a number between two parties over an open channel.

First recall from school these exponentiation rules: (xᵃ)ᵇ=xᵃᵇ=xᵇᵃ e.g. (2³)⁴=(2⁴)³=4096. The idea is that if Alice sends x and xᵃ to Bob then neither Bob nor anyone else can calculate a. It's easy to say what 2³ is, but given 8 it's hard to say which power 2 has to be brought to to get 8. So it boils down to:

  1. Alice and Bob agree on a number x that can be known to anyone, let's say 2
  2. Alice generates a=3 and sends 2³=8 to Bob
  3. Bob generates number b=4 and sends 2⁴=16 to Alice
  4. Alice calculates 16³=4096 and Bob calculates 8⁴=4096

So both Alice & Bob know 4096, but no one else knows a and b so can't calculate xᵃᵇ.

In reality calculating logarithms is not that complicated. But it becomes complicated once modular arithmetic is included.

Stanislav Bashkyrtsev
  • 191
  • 6
0

In plain English without using any math expression like in the above answers, the Diffie-Hellman Key Exchange is an invention by Diffie and Hellman.

The invention is about a way for two persons to agree on the same number. This common agreed upon number will then be used for whatever purposes the two persons wished. For example, after following the DH Key Exchange steps, the end result is that both persons now arrive on the same number. None of the two persons has control over what this common number will be. The DH Key Exchange invention only guarantees that both persons will arrive to a common number. An example usage once this common number is achieved is to forward the letters of the alphabet using this number. For example, if the common number is 5, then the letter A becomes F, the letter B becomes G and so on when sending a message. The other person receiving the message will then backward each letter of the message to read it.

Person-A and person-B could not just talk loudly in order to agree on a common number because a third person-C will hear it. If person-C knows the agreed number, then he can read the secret message too. The DH Key Exchange always requires that there is always a third person-C that can listen to the messages between person-A and person-B and this three-persons scenario is the whole purpose of the invention on how to make person-C unable to read the secret encoded messages between person-A and person-B.

In the first steps of the DH Key Exchange, person-A and person-B will send some numbers back and forth and at this early phase person-C can read these first messages. In the second phase, person-A and person-B will be sending encrypted messages that person-C can no longer read. Despite the fact that person-C can hear the initial messages during the first steps, person-C cannot arrive to the agreed number that person-A and person-B now have.

Diffie and Hellman have been awarded the Turing Award in 2015 for this invention.

daparic
  • 200
  • 1
  • 5
0

I wrote this once as a concept of a talk that I never gave. It demonstrates some real cryptography using a level of math that everyone can do after high school.

Since it's written as a talk, this is Diffie-Hellman in plain English!

Hey you! Let's setup an encrypted channel. I'll send you my key and you send me yours, and then we can talk privately.

What did you say? Everyone can hear us? Yes, that is no problem!

We can use Diffie-Hellman. Just think of a random number and raise 5 to the power of that random number. Divide the result by 23 and take the remainder. Give that to me. The original random number, you should keep secret, the other numbers are all public knowledge.

Your remainder is 8? Okay. My remainder is 10. Now raise my remainder to the power of your secret random number again, and divide by 23 again, and take the remainder. Same thing, easy peasy. I'll do the same thing with your number and my secret random number.

You got the result? Great, me too! I know you got 6, just like me, and yet nobody else in this room could have computed that. They could have tried every possible combination until finding the random numbers that match what they heard (8 from your side and 10 from mine), but there is no way to compute this more efficiently than by trying all possibilities. We could have used the result, 6, as password. Nobody would have known the password we use, despite hearing the exchange. But it's a very weak password. Next time, we should choose bigger numbers and use a calculator to create a longer and stronger password.

Note that this worked because we can see each other. I know it's not someone else talking when you tell me your number is 8 because I can see your lips move. On the internet, someone could setup attacks against this by pretending to be the other side and giving us fake numbers. How we prevent these attacks is a topic for another day.

Luc
  • 32,378
  • 8
  • 75
  • 137