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)?
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 two prime numbers g and p and tell you what they are.
- 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.
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.
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
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.