"Diffie-Hellman Key Exchange" in plain English
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?
I found this video useful in understanding - https://www.youtube.com/watch?v=YEBfamv-_do
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 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.
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`.
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 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.
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 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.
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 ?
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).
For reasons of security the prime numbers **a** and **b** should both be reasonably *high* numbers and have some distance to each other.
@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.
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
@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."
@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 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.