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?
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:
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")
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).
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").
Now, you take the number I sent you and do the exact same operation with it. So that's: Ba mod p .
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.
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:
Image is in the public domain
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.
- Alice and Bob agree on a prime number,
p, and a base,
g, in advance. For our example, let's assume that
- Alice chooses a secret integer
awhose value is 6 and computes
A = g^a mod p. In this example, A has the value of 8.
- 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.
- Alice sends
Ato Bob and Bob sends
- To obtain the shared secret, Alice computes
s = B^a mod p. In this example, Alice obtains the value of
- To obtain the shared secret, Bob computes
s = A^b mod p. In this example, Bob obtains the value of
The algorithm is secure because the values of
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.
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.
Bob receives the box, puts a second padlock that only he has the key to on it, and ships it back to Alice.
Alice removes her lock and ships the box to Bob a second time.
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.
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:
- exchange the key by physically meeting and sharing the keys.
- 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.
Diffie-Hellman makes use of a mathematical function with the following properties:
- It is EASY to compute
- It is HARD to invert
- It is EASY to calculate
- It is EASY to calculate
- It is HARD to calculate
How DH scheme works
- 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.
- 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.
- Alice computes
f[B]. Bob computes
- Mallory, who is Eavesdropping, has only
f[B], and so it is HARD for her to calculate
- 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.
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.
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
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.
Anyone "listening in" on the conversation would only "hear" the numbers which were exchanged in the middle:
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 (
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.
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.
Goal of Diffie–Hellman: secretly share a number between two parties over an open channel.
First recall from school these exponentiation rules:
(2³)⁴=(2⁴)³=4096. The idea is that if Alice sends
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:
- Alice and Bob agree on a number
xthat can be known to anyone, let's say
- Alice generates
- Bob generates number
- Alice calculates
16³=4096and Bob calculates
So both Alice & Bob know 4096, but no one else knows
b so can't calculate xᵃᵇ.
In reality calculating logarithms is not that complicated. But it becomes complicated once modular arithmetic is included.
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-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-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
In the first steps of the
DH Key Exchange,
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-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-B now have.
Diffie and Hellman have been awarded the
Turing Award in 2015 for this invention.
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.