Diffie-Hellman Key Exchange: How to Share a Secret
ฝัง
- เผยแพร่เมื่อ 26 พ.ค. 2024
- How can two computers share a piece of secret information without anyone else knowing? Diffie-Hellman key exchange is one of the core algorithms in cryptography for solving this problem. In this video, we build an intuition for how the algorithm works and why it's secure.
***
Spanning Tree is an educational video series about computer science and mathematics. See more at spanningtree.me
To be notified when a new video is released, sign up for the Spanning Tree mailing list at spanningtree.substack.com/
You can support the Spanning Tree channel at ko-fi.com/spanningtree
Spanning Tree is created by Brian Yu. brianyu.me/
Email me at brian@spanningtree.me to suggest a future topic.
![[UNCUT] ฝันรักห้วงนิทรา | EP.8 (4/4)](http://i.ytimg.com/vi/RDYJYiDwsj0/mqdefault.jpg)
My favourite thing about this channel is that they take seemingly complex algorithms and break it down so that it’s easy to understand!
💯
And with cute renditions of the code at that!
The problem with DH on its own is that there is no way to verify the calculated public parameters. So an attacker can sit in the middle and perform the handshake with both parties, generate a secret key and maintain the session. The attack decrypts the data from party A, is able to look at it and store it, then encrypt it to party B and vice versa. It does need to be an active attack, because otherwise there would be no way to retrieve the secret key. So you still need PKI for making sure that the public parameters you receive are from the correct party.
Is there a way to counter this?
@@M_1024 Yes. You use certificates on the server side, so you have a means to send the public parameters to the server and back safely. This uses asymmetric encryption, which is a lot slower, so it's only used for the handshake. And if the server later got hacked and the RSA keys are compromised, you still cannot decrypt sessions, because DH achieves perfect forward secrecy. The signing is only neccesary to combat an active attack and verifying the public parameters, otherwise DH is perfect.
The other part of security: authentication!
@@NibbyBanana This only works if you can be sure that some communication is with the right person.
For example lets say that Alice tries to verify that Bob is really Bob. If she Has Bobs public verification key, she can do this, but first she has to get that key, which in practice is easy, but in theory could be impossible
@@M_1024 Yes, that's the entire point of the certificates, and why you'd need PKI. To make sure the public paramters are from the right person.
Wow, this is the second time you have dropped a video with a theme I'm currently learning for an exam in a few days.
Good luck!!
I learned about the DH key exchange back in University and even got the test questions correct without ever really understanding it. This video was fabulous - because NOW I understand. Insanely well done!
Been wondering this for 15 years
This concept has been explained to me several times in classroom settings, but this video is the first time it actually made sense to me.
I recommend Khan Academy's series on it as well
a more efficient algorithm to find x^p:
the main idea is that a^b * a^b = a^(2 * b) so you can double the exponent in 1 operation instead of increasing it by one. the code of the function would look something like this:
function pow(x, p)
if (p == 1) return x
if (p is even) { int y = pow(x, p / 2); return y * y; }
if (p is odd) return x * pow(x, p -1)
and you can just take the mod on every step
Diffie-Hellman is one of those problems where you could naively swear that it's impossible to solve. And yet!
Yeah, the trick is to notice that the problem isn't to find an irreversible operation, that is impossible (when you know the operation and the result nothing can prevent you from, in the worst case, trying every number as input until you find one that gives you the same result), you can make reversing it prohibitively expensive, and that is all you actually need making the problem not as impossible as you initially frame it.
As is typical, actually understanding a problem is the hard part of solving a problem.
@@kevinscales Did you read this in a fortune cookie? I mean, you could always define "understanding" in such a way for this sentence to be true but then it's not really a useful statement, is it?
Understanding a^n + b^n = c^n is not all that difficult. Understanding it deeply enough to solve it clearly is. So the word "understanding" is doing _a lot_ of heavy lifting here.
I think one thing you forgot to mention is why both would get the same key when raising it to their secret number.
Operation by person with secret number c
= (A^b mod M)^c --- (A^b mod M is what he received from other person)
= (A^b)^c mod M --- (property of modular arithmetic) -> 1
= (A^bc) mod M --- (exponent property)
= (A^c)^b mod M --- (multiplication is associative)
= (A^c mod M) ^ b --- same as eq. 1
= The operation that person with secret number b would do
This implies both of them end up with the same output which is the key
There is a flaw in this as attacker can become a mediator between two communicating parties.
Intercepts communication
Creates shared key k1 with A and k2 with B
Both A and B think they are communicating well but a mediator attacker sits in middle and reads and manipulates messages xD
@@mufaddaldiwan8555 Thanks for going over a basic version of the proof for why both parties get the same result.
Diffie Helman gives you secrecy but not authentication . We use other means to add authentication to the chain.
That red robot looks scary.
Gotta stay alert. Red Guy out there lurkin'.
@@k-vn-7 cross-hairs on him
There's another method I like that has a great analogy, but requires a type of cryptography that you can _swap the steps of and still get the same result_ (think A XOR B XOR C == A XOR C XOR B). The analogy is, Alice comes up with a secret, puts it in a box with Padlock A (only she has A's key) and mails it to Bob, who _puts his own Padlock B on it_ and mails it back (the contents are now "double encrypted"). Alice now unlocks Padlock A so the box only has Padlock B on it, and mails it back again to Bob, who unlocks his own padlock and retrieves the secret, that they then share for regular communication. They never unlocked each other's locks, and the box was never in flight without at least one lock on it.
The fact that I didn’t turn on all notifications for this channel is mind-blowing
Great vid as always!
I got into cryptography because of your video about AES!
I think a video about Shamir's Secret Sharing could be interesting too.
Wow, straightforward and clear explanation! Thank you for this video!
Thank you for the amazing educational content and adorable animations! it helps me as a student studying computer science in university I find your videos a nice and small research video on topics that I don't always encounter in the syllabus so thank you for everything :)
You are an absolute nerd.
And that's **exactly** why I keep watching your videos.
Keep up the fantastic work.
Thanks for sharing !! Those animations makes so easy to understand the algorithm
What a great cryptography lesson! Thank you!
Well explained, great video!
Best explanation of DH that I've ever seen
Omg, it was this simple! Computerphile did a very poor job in this concept. I love your videos and those cute robots man, you know your stuff really well
I need to disagree with this:
1. The Water Color video is just for the non math person: th-cam.com/video/NmM9HA2MQGI/w-d-xo.html
2. The Math behind explains deeper and why exponentiation is safe: th-cam.com/video/Yjrfm_oRO0w/w-d-xo.html
While this video is a mix between, but completely fails to explain why exponentiation is safe, if the communicating parties used the exponentiation iteratively as shown in this video, brute forcing it would be as hard as encrypting it. While multiplying previous powers gives a great benefit to efficiency, reducing your cost to from linear to logarithmic, assuming you know your target exponent.
And if you assume the person watching this video knows how exponentiation can be sped up, there would be no need to watch this video in the first place, cause that's literally everything going on.
@@JariNesteloh thanks, I totally missed the second video you mentioned
Great video! Second only to Khan Academy's explanation - they did a really good job on their series. But I'd recommend either one to someone interested in cryptography, security, and that stuff.
I have an exam on this topic tomorrow and you uploaded this today. Right time ! lucid explanation thanks
Liar.
That red guy is a masterpiece!!!
It's very concise and you learn a lot in a short time, and if you want to learn the source code, it'll be easier!
This is explained so well!
One of the best explanation
Just when I needed it! I’m working on understanding AES-GCM encryption and ECDH key exchange for an internship
Or.... or.... you could read the fing man.
@@Katchi_ huh??
This is a great explanation! I wish I had this when I was taking my cryptography class last year
This protocol is used in SSH, a widely used cryptographic software. However you are susceptible to MITM at first generation. This is why checking the public key is important.
Thank you, that was easy to follow !
worth mentioning that in more modern cryptography the same idea is used on elliptic curves, but the cool thing is this is a pretty black box approach, the higher level key agreement protocol doesn't care about the underlying mathematical structure used so long as it's an Abelian group where reversing the group operation is hard and it turns out that defining an addition operation on the solutions to elliptic curve equations gives a very good tradeoff between efficiency and (presumed) hardness.
Great job!
its always fun to watch ur explaination
Found your channel from this video. You just earned a sub. Great content.
Well explained, thanks a lot
Great video, thanks!
I just discovered your channel! Amazing video! 10/10
But what would happen if red guy:
1. Generated his own secret and modular exponent.
2. Intercepted or stopped green's modular exponent from reaching blue.
3. Sent his own modular exponent to blue, pretending it is from green.
Wouldn't he be able to read blue's messages now?
I feel like this would also be a good moment to make a video about the euler phi function since it massively simplifies such calculations
Huh, I knew and studied this, technically, but this made it less "black magic" where the math was concerned. Thanks!
great video!
thank you, I have been implementing d-h exchange when communicating with telegram server but this video gave me a much better understanding than reading code or text, I guess I am a visual learner
Oh hey, this amazing channel that I love uploaded! :D
Really, thank you so much!
Best explanation out there
Brilliant! thanks for such good video
Keep up the good work, loved it ❤
You are the best!
Amazing video
Wow! First time I saw the beauty in Maths
One reason for wanting to do this instead of Asymmetric key cryptography is that Symmetric tends to be much more efficient for encription and decription. If you want ALL traffic to be encrypted, it better have a low overhead over sending plaintext.
Thanks!
good material
thanks it was helpful
Good explanation gets a like.
I like your content, please make more
this video is so good
Cool vid :)
Great video!
I'm subscribing to your channel
Best explanation out there! Came here after watching several videos on the matter. This was the best by far. Thanks!
Small nitpick near the end. TL;DR: You don't have to use primitive roots for your base.
It is not sufficient to choose any prime number modulus, as an attacker can use something called the Pohlig-Hellman algorithm if one less than the prime only has small prime factors.
Bad prime example: 306557831 is a prime, but 306557831 - 1 = 306557830 = 2 * 5 * 53 * 67 * 89 * 97, and this makes it weak.
Good prime example: 489678227 is a prime, and 489678227 - 1 = 489678226 = 2 * 244839113, and this makes it strong. In fact, these primes are called safe primes.
Now suppose you've chosen the safe prime modulus in the example. If you avoid a base of 1, 0, or -1, you're guaranteed to go through at least 244839113 values, so pretty much any base works. Pohlig-Hellman makes sure having 489678226 values doesn't make it harder, so there's no need to find a primitive root.
You touched on the discrete log problem, so compression functions and their special case of one way hashing next please!
Diffie-Hellman relies on the same principle (modular exponentiation) that RSA uses to allow asymmetric encryption. Incredible inventions if you think about it
iirc they're often used together -- key exchange versus encryption
It ain't much, but it's my way of saying thanks for your work
brian yu is a genius😊😅
Thanks for making the explanation so simple. Would you make another vid that explians how quantum computing can break this? And any solution post-quantum?
I love video like this, can you do block cipher mode of operation (especially XTS), RSA, ECC and Lattice cryptography?
Dustin Hoffman seems to be not only a good actor but a pretty smart guy too.
Brian!!!!
All of this just to say good morning!? I'd go back to bed at that point
Sick
This is way too well explained, thank you!
This is a great video. This topic is so important yet I haven't found to many great simple to understand resources. Thanks a lot and keep uploading! :)
I assume there are some more or less clever ways to find the primitive root modulo n on each ones side? Or is it just trying until it is "good enough"?
Can you talk abount quantum key distribution in next videos? Something like bb84, there are a lot of cool things to show in that algorithm.
Might be a bit simplistic but would like to request a video on hole punching (networking). Maybe if combined with some other networking concept it could be a bit more viable. Thank you
Is this method better and/or more common than using asymmetric encryption to establish a symmetric key?
Keep it up. Animations help a lot!
Good video, but it still doesnt solve the question you asked in the old video "How to Send a Secret Message" about MITM
Yes. You need to have some way to secure/verify part of at least one communication -- this could be done with public/private keys which are trusted and setup out of band. The good part is you can then continue the conversation with encryption
Is this a follow up to the three pass protocol video?
Nice video. Think you can greatly improve audio with some sound deadening 😁
It might be more interesting to do this in the real world without mod functions, as in actually exchange a physical key
what is this timing i have a test on this in a few days
clearly this means you win
Hi Brian, it’d be nice if you could make videos about important algorithms like Bellman-Ford, Floyd Warshall, BFS, DFS, Prim etc.
Right... because there are no books on the subject...
Why (if at all) is this preferable to asymmetric encryption?
❤❤
I wonder if there's a symmetric key cryptography algorithm which is unconditionally secure.
Dumb question, since there seems to be a preference for a "good" base and modulus, doesn't that also mean someone building a sort of rainbow table just has to compute all the combinations of the "good" pairings?
that's why the exponent should be massive
The problem is that the numbers involved are MASSIVE.
Such a table wouldn't fit into the entire universe even if you managed to compute it.
( the base almost always is 3 )
how is diffie hellman different from sending over a public key?
I thought I recognized that lisp. You really fell off since cs50, bro. Good for you.
Ooh!
❤
Why not just look for prime numbers when attacking?
How do you know which computer is Diffie and which computer is Hellman?
Oh yeah, new crytography vid explained visually, lets watch it 😎
Subscribing because the robots are cute 😂
why could you not for example use a bitwise AND or XOR instead of the +? since their order does not matter and they aren't reversible
Nice thinking, but that dosen't work.
AND would result in a key, that is mostly zeroes, making it useless, since it dosen't properly scramble your communication.
XOR is easily reversible (just run it again, similar to +) so it's no good either.
Can somebody explain ecc?
🥰
PLs make more simple algorithms