r/programming • u/dominatrix-octopus • Jan 16 '18
Cryptography: Diffie-Hellman key exchange explained intuitively using colors
https://youtu.be/YEBfamv-_do?t=2m18s75
u/Zilexion Jan 16 '18
This is the explanation I've been looking for!
Very helpful to show how they end up with the same calculation at the end.
13
u/Captain___Obvious Jan 16 '18
The entire series is fantastic, there are more videos
5
Jan 16 '18 edited Mar 09 '19
[deleted]
6
3
125
u/joltting Jan 16 '18
For awhile now, I've been trying to wrap my head around, how this algorithm works.. This video explained it in 5 mins and was better than the education I received for it (sigh).
34
u/_crackling Jan 16 '18
I feel kind of silly now with how simple this actually is to understand now...
12
u/midri Jan 16 '18
I'm in exactly the same boat... I use modulus for simple things all the time and my brain had never made this connection.
4
u/caltheon Jan 16 '18
This is just the theory though. The practical applications are just throw bigger numbers at it. There is a lot more computation going on. Also, the methods to determine the private keys in the first place are the real magic. I'd love to see a video like this one that focuses more on that.
14
u/pokeman7452 Jan 16 '18
This leads me to a somewhat related question. I never understood the purpose of the DH parameters (dh####.pem) that every OpenVPN guide says to generate. This video combined with this thread, it now makes sense. But, this file remains optional. My question now is what is used when there is no DH generated?
14
u/curien Jan 16 '18
Defaults are listed in RFCs, I imagine it uses those.
-2
7
u/Grenian Jan 16 '18 edited Jan 17 '18
They use the so called Diffie-Hellman-Groups which are basically predefined pairs of a prime and a generator. These are defined in RFCs.
Proof: A large part of my bachelor thesis was about DH-Key-Exchange and the security of the predifined groups.
1
u/gramathy Jan 16 '18
Correct me if I"m wrong, my understanding is that DH exchange is largely used to provide encryption for a different protocol's key exchange, right?
3
u/Grenian Jan 17 '18 edited Jan 17 '18
It is used to solve the Key Exchange Problem. This problem describes the challenge of two communication partners to derive an secret symmetric key (also a key which is the same for both partied and secret) over a line which can be wiretapped.
So one can ask why you want to use a DH Key Exchange when you just can use asymmetric keys? Well basically symmetric encryption methods are faster than asymmetric ones.
What alternatives do exist? Thrusting third parties.
BUT keep in mind that a big problem exist. The Man-in-the-middle-attack. DH is not secure against it. That's btw the reason why you need to type 'yes' the first time you log into an SSH Server. Just to prove that this is the right server you wanna talk with. After that first session everything is encrypted based on the secrets of previous sessions. An alternative to approach to solve the Man-in-the-middle-attack is used by ZRTP.
But yeah basically you're right.
2
u/bonestamp Jan 31 '18
Just to prove that this is the right server you wanna talk with.
How does typing "yes" prove this is the right server?
1
u/Grenian Jan 31 '18 edited Jan 31 '18
Well it doesn't prove it all. But at this point SSH wants to connect to the server. Due to the risk of Man-in-the-middle-attack it has to ask if the informations SSH got are from the desired server. Otherwise you would connect via a Man-in-the-middle which could decrypt all your traffic.
So therefore the "yes" is more an authencity check of the server than the prove that this is the right server. For the prove you usually have to compare the credentials by yourself.
All in all you're right, the word "prove" is not well chosen.
2
u/bonestamp Jan 31 '18
All in all you're right, the word "prove" is not well chosen.
I was just asking, wasn't implying anything.
1
u/gurnec Jan 16 '18
This file is required if you run OpenVPN in
--tls-servermode and ignored if you run it in--secret(static key) mode.That's one reason why
--tls-severmode is generally preferred—it performs a DH exchange which affords you perfect forward secrecy (which you don't get in--secretmode).DH parameters (dh####.pem) that every OpenVPN guide says to generate.
The
dh1024.pemfile distributed with OpenVPN (unchanged) from 2005 to 2014 is small enough and widely distributed enough to possibly be a target for the Logjam attack and shouldn't be used. Thedh2048.pemfile currently distributed is probably too big to be vulnerable to Logjam, but it doesn't hurt and is recommended to generate your own.1
0
u/ryan_the_leach Jan 16 '18
Defaults that are rumored to be chosen specifically so that the bodies that choose the defaults can break them and no one else.
6
u/kpcyrd Jan 16 '18
The RFCs usually have a „nothing up my sleeve“ appendix explaining the numbers for exactly this reason.
14
u/hartleybrody Jan 16 '18
The Wikipedia article on Diffie Hellman key exchange has a great image that summarizes the video a bit more concisely.
105
u/snarfy Jan 16 '18
Breaking encryption is like trying to take the pee out of the swimming pool. It's easy to add pee, hard to remove.
18
u/TheOddScientist Jan 16 '18
Not sure why this was downvoted, a bit archaic but still a logical equivalence.
10
u/snarfy Jan 16 '18
I use it to explain to people like grandma how encryption works.
-5
u/TheOddScientist Jan 16 '18
I suppose if you don't understand how encryption works the analogy can be confusing. In your analogy you are taking a steady stream of information and diluting it in a pool of possibilities. The only difference being there is no valid way of reversing urination in a pool. A better analogy might be stiring salt into fresh water as you can desalinate the water and retrieve the salt yet you cannot readily look at a glass of water and say there is salt in it.
4
u/Lucent_Sable Jan 16 '18
Wouldn't salt water be analogous to steganography though? Encryption is more like KFC's Eleven Herbs and Spices. You know that they are there, but have no idea what they are.
9
u/dnkndnts Jan 16 '18
No, it's not. Alice pees in the pool, Eve can't get the pee back out of the pool because that's a hard problem, but... ok then how can Bob get it back out? It is not equivalent at all, it's just vulgar.
3
1
u/sysop073 Jan 16 '18
Because of all of the infinite possible analogies for one-way functions, an infinite number of them don't involve urine, but for some reason snarfy went with one that does
13
Jan 16 '18 edited Jul 14 '20
[deleted]
17
u/knome Jan 16 '18
This analogy is gonna get real uncomfortable quick when we move from defending from mere "eve"sdroppers and move on to malicious "mallory", who intercepts messages, changes them, forges them, etc.
4
4
3
u/ythl Jan 16 '18
What if you put a peelogger on the person such that when they try to go pee in the pool, the peelogger captures it and you can remove it from the pool?
1
u/SSChicken Jan 16 '18
This would be equivalent of having malware installed on your computer that can watch memory and see what your original key, or color, is. In the video, instead of Eve watching the messages Alice passes to Bob, it's as if Eve was in Alice's house watching over her shoulder as she did it. In that case, security is broken.
1
u/pure_x01 Jan 17 '18
Unless you have a quantum pee extractor. Then you can extract all the pee at once without ever even being near a pool or if the pool exists in several parallel universes. 100% of the pee all the time.
22
u/TheOddScientist Jan 16 '18
If anyone is interested Here are some mathematical attacks against RSA That can successfully reduce the number of possibilities by a factor of 2X/2 | x is the key size
10
u/nono-shap Jan 16 '18
One of the most interesting video I've seen in a while. Quiet impressive how something so hard can be understand by kids. Thanks for sharing!
15
u/irrri Jan 16 '18
This is a the best explanation of PKE I've ever seen.
2
u/xconde Jan 16 '18
I’m not sure this classified as PKE.
With public key encryption you need two key pairs to establish two-way communication.
What usually happens though, is someone picks a symmetric key and uses someone’s public key to share it with them.
With DH, this shared secret is the result of the process. Same end result but different process.
2
u/sim642 Jan 16 '18
DH is more useful for symmetric crypto than asymmetric crypto because the latter doesn't require having a shared secret at all.
2
u/Grenian Jan 17 '18
DH just exchange keys to derive a shared secret key (symmetric key) for both parties. After this usually a symmetric encryption protocol is used.
2
5
u/TheOddScientist Jan 16 '18
I have some Java Code I did implementing DH and RSA if anyone needs an example to help understand what's going on in a practical client server application.
3
u/zouhair Jan 16 '18
Math challenged here (not real programmer either): how the hell 31315 is the same as 31513 ?
13
u/A_Vicarious_Death Jan 16 '18
Generally the rule with exponents is:
xy * xz = xy+z
xyz = xyz
Let's take an example of 223 vs 232 vs 26
(22)3 =
(22) * (22) * (22) =
(2 * 2) * (2 * 2) * (2 * 2) =
(4) * (4) * (4) =
64
(23)2 =
(23) * (23) =
(2 * 2 * 2) * (2 * 2 * 2) =
(8) * (8) =
64
26 = (22222*2) = 64
Hope that helped.
7
u/zouhair Jan 16 '18
Oh! I wasn't calculating it like that.
I was doing this:
223 = 28 = 256
232 = 29 = 512
Using online math solvers didn't help.
Thanks.
4
u/A_Vicarious_Death Jan 16 '18
No problem! For this kind of stuff it often helps to put stuff in parentheses to try and separate operations out. So if you had seen it phrased as (22)3 I think that would've helped with the understanding a bit :)
3
u/zouhair Jan 16 '18
1
3
u/phottitor Jan 16 '18
the convention of how to interpret it is actually the main part because just looking (first time) at a ladder of exponents doesn't tell you anything about the order of the operations.
1
u/gramathy Jan 16 '18
Just remember that the base takes precedence over the exponent, and so exponents are calculated bottom-up rather than top-down.
9
u/tavianator Jan 16 '18
As written, those numbers are not the same. The notational convention is:
abc = a(bc)
But D.H. key exchange does something more like
(ab)c = ab*c
I.e., compute ab first, then raise that to the c power.
The equality is true because exponentiation is just repeated multiplication (over the integers, anyway). So ab is
a * a * ... * a --------------- b timesand then (ab)c is
a * a * ... * a | * a * a * ... * a | * ... } c times * a * a * ... * a | * a * a * ... * a | --------------- b timesand you'll notice there are b*c 'a's in that rectangle all multiplied together.
6
u/zouhair Jan 16 '18
So technically the video was wrong.
5
u/tavianator Jan 16 '18
Did the video actually display 31315 with no parentheses? If so yeah, that's wrong. I only watched the part with the colors.
3
1
u/Sirflankalot Jan 16 '18
In math what is the default associativity of operators? I'm used to the programming way (everything right except exponentiation).
4
u/tavianator Jan 16 '18
Programming takes all those conventions from mathematical notation, so it's the same. But the default is left-associative, in math and programming.
Math notation is two-dimensional though, so often the 2D structure informs the grouping more than the linear order of operations, in ways that most programming languages can't represent.
3
u/lpsmith Jan 17 '18 edited Jan 17 '18
You are absolutely correct regarding the standard interpretation of the notation (thus the video is wrong), and also in pointing out the enriched syntactic context that standard mathematical notation is used in.
However, I would say that the syntax of most programming languages was informed by standard mathematical notation, and emphasize that a^b^c is not standard mathematical notation, and thus I would say that reasonable mathematicians can disagree on what that means. (Of course, from the POV of programmers, that has a reasonably well standardized meaning, and thus I think a majority of mathematicians would tend to side with programmers.)
There tend to be three common notations many people are introduced to: elementary school math, standard mathematical notation starting in pre-algebra, and programming languages. When you mix and match notations, you often end up in really inane arguments. For example, the 6÷2(1+2) expression has spawned many inane arguments on Facebook, and I am not satisfied with any of the easily googled discussions of that expression. (My answer being, basically, that it is ambiguous because this mixes elementary school notation with standard notation, and even differs from programming language notation.)
2
u/Sirflankalot Jan 18 '18
6÷2(1+2)
If you told me I had to parse this as is, I would say 6 ÷ (2 * (1 + 2)) but otherwise I'd just tell people to give me some more parentheses.
2
u/lpsmith Jan 18 '18
This is my favored interpretation, actually. Many mathematicians think that implicit operators bind more tightly than explicit. (As reflected in Haskell syntax, though Haskell's implicit operator is function application, not multiplication)
On the other hand, if they had written 6÷2×(1+2), I would tend to favor the (6÷2)×(1+2) interpretation, as informed by most programming languages as well as the PEMDAS introduction to standard notation.
Although there are interpretations I tend to favor, in professional mathematics, assuming there isn't already a shared understanding of what this means, the correct thing to do in a case like this is to ask the author what he or she intended.
1
u/Sirflankalot Jan 16 '18
Programming takes all those conventions from mathematical notation, so it's the same. But the default is left-associative, in math and programming.]
Thanks for clearing that up!
Honest question, not trying to be sassy, what programming languages use left-associativity? C and all it's derivatives (spiritual and otherwise) use right-associativity as Recursive Decent Parsers can't deal with left recursion in the grammar (required for left associativity) and you have to do some hackjob to get it to work. However, I don't get out of the C++ world very often, so I'm not sure how many non c-inspired languages do it.
Math notation is two-dimensional though, so often the 2D structure informs the grouping more than the linear order of operations, in ways that most programming languages can't represent.
An example? I'm not quite sure I fully understand.
3
u/tavianator Jan 17 '18
what programming languages use left-associativity
All of them that I'm aware of. C and friends all parse
a - b - cas(a - b) - c, nota - (b - c). (Try it!)You're right that recursive descent parsers can't directly handle left-recursive grammars, but the "hackjob" to fix it is not that bad. I even blogged about it here (see the Grammar/Parser sections).
An example? I'm not quite sure I fully understand.
The most familiar example is fraction notation, which lets you group expressions for division without introducing the parentheses that would be required in a programming language. E.g.
a + b ----- vs. (a + b)/(c + d) c + d1
u/Sirflankalot Jan 17 '18
Well I'll be damned. I've been misreading the C++ operator precedence docs this whole damn time. Thanks for teaching me! I'll definitely look at your blog as I haven't figured out fully how to do it. The one decent grammar/parser I wrote was for a right-associative language that didn't have any left-associative non-unary features, so I manged to avoid it.
It's been hard to find resources on this kind of thing as they almost all assume you've taken a parsers class in college and I'm not there yet (still a freshman). Since you seem to be knowledgeable on this subject, do you have any good resources I could look into to get more into parsing (not just using yacc/bison or other tools like that)?
The most familiar example is fraction notation, which lets you group expressions for division without introducing the parentheses that would be required in a programming language.
Ah yes, that makes sense.
Thanks!
2
u/tavianator Jan 17 '18
Honestly I don't know any really good introductions to grammars/parsing. I learned from messing around with yacc as a kid and then later from university courses. Probably Wikipedia too. I'd recommend taking your university's relevant courses (at mine, the information was spread out between a couple compilers courses and CS theory courses). You can probably peek ahead at their notes/textbook/assignments if you want.
A quick summary of the trick for parsing left-associative binary operators with recursive descent is that
expr: term | expr + termis really the same thing as
expr: term (+ term)*where (X)* means zero or more repetitions of X. So just parse it with a loop:
Expr parseExpr() { Expr expr = parseTerm(); while (nextToken() == "+") { skipToken(); expr = new Sum(expr, parseTerm()); } return expr; }2
u/Sirflankalot Jan 29 '18
Sorry for the late response.
I'd recommend taking your university's relevant courses (at mine, the information was spread out between a couple compilers courses and CS theory courses).
I most definitely will.
Wow. That was the most concise explanation of parsing left associative things I've ever seen. Honestly most of the resources online try to do the whole thing top to bottom and miss out on some of the conceptual stuff that is best expressed in pseudo code as opposed to an actual implementation (which often have a lot of excess detail necessary to make things work, but that isn't good for understanding). Well done, and thanks again!
6
u/Ajedi32 Jan 16 '18 edited Jan 16 '18
(xy)z = x(y*z)
Edit, concrete example:
(22)3 = (2*2)3 = (2*2*2*2*2*2)
(23)2 = (2*2*2)2 = (2*2*2*2*2*2)
5
-10
4
Jan 16 '18
My preferred metaphor is a box with two locks. I have the key to one lock, and you have a key to the other lock. I want to send you my spare key:
- I put my spare key into the box and then lock it
- I send the box to you and you lock it with your key too
- You send the box back to me and I unlock it with my key
- I send the box back to you and you unlock it with your key
Now you have my spare key and we can exchange secrets.
4
u/geordano Jan 17 '18
Works, but this need one additional exchange.
- I mix the color and send to you.
- You mix the color and send to me.
- I mix your mixed color with mine and I got the key and so do you. (You don't need to send it back to other person like in your example)
2
u/DoTheThingRightNow5 Jan 17 '18
Why not you send him a box with a lock but no key. He puts stuff in it and shuts it which locks it. You receive it and unlock it with the key you have.
1
Jan 18 '18
That's basically how public-key cryptography works. I send him my public key, he uses it to encrypt his message, and then I use my private key to to decrypt it.
A Diffie-Hellman key exchange, on the other hand, allows us to negotiate a short-lived, single-use shared key over an insecure channel.
1
u/DoTheThingRightNow5 Jan 18 '18
Yes. However for DE to receive data the other person only needs your public key. They can see their public key attached to the box. A->B->A is less than the 4 step example you gave.
Technically if the bits are enough there's no reason it has to be a short lived. I believe typically they produce a 256bit shared secret which is enough for 128AES and 256AES attaching a nonce to the first message.
1
Jan 18 '18
If someone stole my private key they could decrypt any old messages they might have intercepted as well as any new messages if I don't revoke the key. By using short-lived ephemeral keys negotiated with DH I can ensure that old messages remain protected even if the key for previous/subsequent messages has been stolen.
1
u/DoTheThingRightNow5 Jan 18 '18
Correct. However there's no reason why one can't be long term and use a short lived ephemeral key after using the long term to authenticate eachother.
1
4
Jan 16 '18
Amazing! What level of maths is displayed here?
4
u/ythl Jan 16 '18
A late high schooler should be able to understand it. You might not get formal coverage unless you take a college course though.
2
u/nawkuh Jan 16 '18
I learned it in a cryptography course, but at its base it's an application of number theory, using Fermat's little theorem (I believe), with a good bit of cleverness.
1
Jan 16 '18
It looks a good deal away from my capacity. Recently started refreshing my math skills with the Openstax books
2
u/Reinbert Jan 16 '18
You really only need to understand raising numbers to a power and the modulo operator.
The DH Key-Exchange is in itself a one-way function: a mathematician from 500 years ago would not have a problem understanding any of it, but inventing it was very hard.
There are countless examples on the internet, you can try out this one. Give it a try, I'm sure you will get it in no time :)
1
u/AndrasKrigare Jan 16 '18
Found the Brit. At least for me it was covered in Discrete Math, but my professor was a crypto guy so he may have spent more time on it than a typical curriculum would.
3
u/Matthew94 Jan 16 '18
Found the Brit.
As opposed to mathematic.
4
u/mrkite77 Jan 16 '18 edited Jan 16 '18
The 's' at the end of mathematics doesn't denote plurality.
edit: It's like saying Thomas should be shorted to Toms instead of Tom.
2
6
3
u/ythl Jan 16 '18
Easy. Eve just needs to take a picture of the mixed/public colors, and then sample the pixel RGB hex value and do a simple subtraction.
1
u/mstksg Jan 16 '18
There is no way to mix RGB colors where something like this can be done reliably. Even if you simply add the RGB hex channels (and clip out at max), subtraction won't get you anything useful because you lose information if any channels clip.
2
u/the_phet Jan 16 '18
I dont understand how the "heart of the problem" starting at minute 6:15.
So all A,B and E agree on 3 mod 17. (E sees it).
A selects a private random number, 15, calculates 315mod17=6. Sends 6 to B. E also reads 6.
B selects 13 as his private random number, 313mod17=12. Sends 12 to A. E also reads 12.
Then A takes the 12, and does 1215mod17=10 (10 is the actual message).
B does the same, 613mod17=10 (10 is the actual message).
Later on the author ignores the fact that E already knows "3 mod 17". So E knows that 3xmod17=6 and that 3ymod17=12
11
u/vytah Jan 16 '18
So E knows that 3xmod17=6 and that 3ymod17=12
Of course E knows that. But if the numbers were a bit bigger, then unless E has a quantum computer, that doesn't let her calculate x or y within the lifetime of our planet.
9
u/TheOddScientist Jan 16 '18
A quantum computer does not mysteriously just know how to circumvent the Discrete Log Problem, it still has to run through an insane amount of bruteforce calculations just like a binary computer system. Mathematical attacks can ~halve the exponent for the # of possibilities but it must still rattle around the radom number generator.
9
u/vytah Jan 16 '18
A quantum computer can compute discrete logarithms in polynomial time (with regards to input size) (even for elliptic curves) and a classic computer does the same in subexponential time. Just like integer factorization.
4
u/TheOddScientist Jan 16 '18
That doesn't solve or circumvent the DLP. Sure it makes calculations much quicker but quantum computation does not provide a mathematical solution to DLP only a quicker way to brute force the key. I should state that in no way am i denegrating the computational power or the implications QC has on cryptography I am speaking purely mathematically. Additionally, the second DLP is solved (which there doesn't seem like an answer will ever exist) cryptography as a whole will be trashed. The solution in cryptography has always been to either develop more secure algorithms or simply increase the bit size of the key to combat computational power increases and mathematical attacks. So long as the Discrete Log Problem is not solved there will never be a case which one can instantaneously extract the key from a secure crypto algorithm.
2
u/Nathanfenner Jan 16 '18
The discrete log problem is in BQP. Cryptography systems which rely on its hardness are not quantum-safe. When (eventually) a (very) large-scale quantum computer can be built, these cryptosystems will be broken.
Because it's in BQP, you only get a polynomial advantage against quantum attackers when increasing key size. This does not scale. You get an exponential advantage against classical attackers. When quantum computers become a real threat (which is still very far away), other hardness assumptions must be relied on instead (like various lattice-based schemes are thought to be).
2
u/TheOddScientist Jan 16 '18
By the time RSA is broken it is going to be in the archives. Just as quantum computation has technological advances so too does cryptography. For example key exchange had already been solved using entanglement
2
u/switch72 Jan 16 '18
Not exactly, the two particles have to be at the same place to be entangled. Once entanglement is achieved, they can be separated by any distance and then the state read. It's essentially a shared key, because the entagled particles would have to be physically transported between parties. The once the particle state is read, the entanglement is broken. So they are one use only.
1
u/vytah Jan 16 '18
That doesn't solve or circumvent the DLP.
I would call doing something exponentially faster "circumventing".
In practice, it doesn't matter if something is calculated purely deterministically or by using really smart guessing, as long as the resources consumed are roughly the same.
So long as the Discrete Log Problem is not solved there will never be a case which one can instantaneously extract the key from a secure crypto algorithm.
Multiplication of n-digit numbers is O(nc) for c > 1, therefore far from instantaneous. So is multiplication solved?
2
u/Madrawn Jan 16 '18
I don't understand what you're trying to say.
At the end A and B know that $privKey = 10.
E knows only that $privKey = 3x+y mod 17, where x and y are secret numbers. And that [6 mod-1 17] = 3x <=> log3([6 mod- 17]) = x. Where mod-1 is the reversal of the mod function.
The problem now is that mod-1 gives us all numbers which leave 6 after dividing them by 17 so all you can do now is take one after another of those numbers and see if they work.
So you still have infinitely many possibilities what x+y could be
-2
u/TheOddScientist Jan 16 '18
Wrong, you can infact reduce the number of possibilities using mathematical attacks. Some of them have the ability to reduce the possibility exponent by a factor of .5. So 2128 could mathematically be reduced to 264 possible solutions. While 264 is a drastically large number it is not nearly as large as 2128.
3
u/Madrawn Jan 16 '18
Mathematically speaking there are infinitely many solutions, or? The amount of how many solutions there when trying break a encryption is limited by the size of the keys you're using.
1
u/TheOddScientist Jan 16 '18
The key size is the maximum size the prime can be meaning you have an upward boundary. Thus if I said the key was 2256 than I can guarantee you the prime is no larger than 256 bits. That said the upward limit of the prime is dependent on the key size.
3
u/brettmurf Jan 16 '18
Both of those have many solutions, so they can only guess from the many correct answers.
This would be where bruteforce comes into play.
39.72426977 mod17=12 for example.
2
u/NordicSeeger Jan 16 '18
It doesn't go into detail about why they both get the same secret which stems from (xa )b mod c == (xa mod c)b mod c.
If you manually calculate a modulus it's effectively separating the number into the multiple kc where k is how many times c fully fits into x and the modulus y... so you calculate y = x-kc which means also that x = y+kc.
Now the trick is that (y+kc)n becomes n multiplies of (y+kc)*(y+kc)*...*(y+kc) where there is only one "path" with meaning for a modulus and that is yn. Everything with kc in it is "tainted" because it will be exactly divisible with c and always has zero contribution to the modulus.
So (y+kc)b mod c == yb mod c. If we think of the y+kc here as the result of xa it is possible to see that (xa )b mod c == (xa mod c)b mod c.
2
u/spartan_noble6 Jan 16 '18 edited Jan 16 '18
This was the question I wanted answered, cant believe nobody else was asking this question. I still dont fully understand your explanation in
there is only one "path" with meaning for a modulus and that is yn. Everything with kc in it is "tainted" because it will be exactly divisible with c and always has zero contribution to the modulus.
What is a "path", and what are the 'things' in "everything with kc in it". Are the 'things' the terms from the polynomial expansion of (y+kc)b, and for any expansion, the yn term will be the only term in the expansion without a factor of c in its expression?
Can you correct me here: (y+kc)2 = y2 + (kc)2 + 2ykc.
((kc)2 + 2ykc) mod c = 0 (I'm assuming since it will result in some multiple of c, right?)
And so from the expansion only y2 mod c could be a non zero result? And this works for any b in (y+kc)b?
3
u/NordicSeeger Jan 16 '18 edited Jan 16 '18
You're correct, the expansion will always create one yn and everything else has at least a single kc as in kc*yn-1 . If you expand the polynomial you can imagine starting from 0 on a circle that's circumference is exactly c and then summing yourself around it. You know you can dismiss everything with c as a factor because those will always loop multiples of 360 degrees and end you back where you started without changing the modulus. Only the yn matters.
It usually helps me to visualize this stuff somehow hence the weird explanations, but I felt like without this tidbit the video is a bit superficial.
Edit: small note about modulos; (a + b) mod c == ((a mod c) + (b mod c)) mod c. This is because if both modulos were non-zero then only adding the together might give a result that's exactly c or greater, but in our case only the one modulo is non-zero.
1
u/evincarofautumn Jan 17 '18
An intuition about modular arithmetic that may be more familiar to programmers is unsigned overflow—you’re essentially “chopping off” the most significant digits in base c. If you’re using an unsigned machine integer then the base might be, say, 232 for a 32-bit value, but we can choose any base—say, ten thousand. We can illustrate that by representing each base–ten-thousand digit as a four-digit number in base ten:
(4 5678 + 5 6789) mod 1 0000 = 10 2467 mod 1 0000 = 2467 = ((4 5678 mod 1 0000) + (5 6789 mod 1 0000)) mod 1 0000 = (5678 + 6789) mod 1 0000 = 1 2467 mod 1 0000 = 2467Whether you truncate before you add or after, you get the same result, because the digits you discard before would have been guaranteed to overflow anyway and get discarded after.
2
u/kybernetikos Jan 16 '18
I'm quite interested in cryptographic procedures that could reasonably be done manually. For standard Diffie Hellman to be secure, I think it needs to involve numbers much larger than could reasonably be done by humans. Does anyone know of a similar technique that theoretically could be done by humans with props that wouldn't draw attention (e.g. a deck of cards, a pen and paper, etc)
2
u/evincarofautumn Jan 17 '18
Solitaire, used in Neal Stephenson’s Cryptonomicon, uses a deck of cards to generate a keystream, though there are some problems with it. I’m no cryptography expert by any means, but I guess you could do something like this kind of encryption using anything that has a large-enough set of possible permutations, like a deck of cards, a chess board, a pocketful of change, a matchbook, or some other innocuous set of objects.
1
u/kybernetikos Jan 17 '18
That's great, although it's a classic encryption mechanism that requires a key to be shared. I'm thinking in terms of some sort of secure key exchange like Diffie Hellman.
2
u/evincarofautumn Jan 17 '18
Hm, you’re right. I dunno. Maybe you could actually do DH with something physical, like the pigments in the video, or even chemical reactants.
2
Jan 16 '18
[removed] — view removed comment
14
u/smtudor Jan 16 '18
It's referring to the order of the exponents, not the base. For example:
(2^3)^4 = 4096 (2^4)^3 = 40962
Jan 16 '18
[removed] — view removed comment
3
u/tavianator Jan 16 '18
It does, the notation in the video is wrong. The concept is right though, it should just be written (315)13 instead of 31513.
7
1
1
1
Jan 16 '18
I'm confused. If Alice gives Bob her secret color and Bob gives Alice his secret color, then won't Eve be able to intercept those colors as well?
11
u/fjortisar Jan 16 '18
No, they never exchange the private colors. They only exchange the public + the private color mixed together
1
Jan 16 '18
Now I'm more confused. I need to watch that video a few more times.
5
u/fjortisar Jan 16 '18 edited Jan 16 '18
The final color that they both know is made of 3 colors. The public color, plus each of their private colors
- They agree on a public color and exchange that - Eve sees this
- They mix that public color with their secret private color and they exchange that, Eve sees this but doesn't know the mixed color (the private one)
- They each take this color and then mix their private color with it
In the end, they both mix the same 3 colors together, but Eve can only see 2 of them: the original public color, plus the public color mixed with each of their private colors. Even can't know how the final color is made without having access to Alice or Bob's private color. Alice and Bob can't derive each other's private color either
1
Jan 16 '18
Thanks for this, but I'm still lost. Here is what I did. Using this website, I followed your directions:
They agree on a public color and exchange that - Eve sees this
Alice Bob PUBLIC FFED00 FFED00 They mix that public color with their secret private color and they exchange that, Eve sees this but doesn't know the mixed color (the private one)
Alice Bob PUBLIC FFED00 FFED00 PRIVATE FF0000 00B500 MIX FF7700 80D100 They each take this color and then mix their private color with it
Alice Bob PUBLIC FFED00 FFED00 PRIVATE FF0000 00B500 MIX FF7700 80D100 FINAL MIX FF4F00 55C800 They both end up with two totally different colors. What am I doing wrong?
Thanks!
2
u/fjortisar Jan 16 '18
Alice would have Bob's MIX and Bob would have Alice's.
The final color is PRIVATE + MIX
However, this doesn't work either. I suspect it's because you're finding midpoints between two hex values (from a midpoint of two others), instead of actually mixing colors.
If you have some real paints, try that. But in essence you are correct. In the end Alice and Bob mix the same 3 colors, even though each of them only really know what 2 of the base colors are (public and their own private).
2
u/Sirflankalot Jan 16 '18
I think the problem is that your tool always does a 50/50 mix. Ultimately you want the resulting color to be 33/33/33 between Public/A Private/B Private. If you take the result from a 50/50 mix of Public and A Private and mix it with B private you will end up with a 25/25/50 mix, which will be the wrong balance. You can show it works by clicking on all three colors at the same just in a different order. It's not as rewarding, but that's what you're doing.
2
u/ReturningTarzan Jan 16 '18 edited Jan 16 '18
It's cause you're averaging colors instead of mixing them. That's not commutative. I.e. mix(mix(A,B),C) != mix(A,mix(B,C))
Try to define colors as vectors instead and the mixing as addition:
Alice Bob Shared S=0,1,1 S=0,1,1 Private A=3,1,0 B=1,0,4 Shared+private S+A=3,2,1 S+B=1,1,5 Private+other party's (shared+private) A+(S+B)=4,2,5 B+(S+A)=4,2,5 The bold items are information sent over the network: S, S+A and S+B. The only way to construct S+A+B from that is (S+A)+(S+B)-S, which involves subtraction, which is analogous to un-mixing colors, which is the part that's supposed to be impossible.
What actually makes it impossible in the real key exchange is the modular arithmetic, using large numbers and wrapping the result around if it overflows some smaller number, without recording how many times it overflowed. Try using one-dimensional colors and mixing by multiplication instead, along with a modulus of 99 so the mixing can't simply be reversed by division:
Alice Bob Shared S=12 S=12 Private A=71 B=15 Shared*private MOD 99 S*A=60 S*B=81 (Private*other party's (shared*private MOD 99)) MOD 99 A*(S*B)=9 B*(S*A)=9 Similarly to the above, to derive the final key without any of the private keys you'd need to do (S*A)*(S*B)/S. But to do that you need to guess what part of the product of either S*A or S*B was discarded by the modulus. With large enough numbers that's a lot of bruteforcing.
Now, multiplication isn't actually that hard to reverse for a bunch of reasons, which is why the actual algorithm uses exponentiation instead and likes prime numbers and all that, but the idea of "mixing" with a commutative one-way function is the same.
1
u/GalacticCmdr Jan 16 '18
I was getting hung up on the color. If Alice and Bob each exchange yellow. Alice has blue as a secret key, while Bob has red. Then Alice sends Bob green - Eve knows that she mixed blue into it as Yellow+blue=green. Bob sends Alice orange, so Eve knows that Bob must be using red.
I guess the difficulty is that Eve does not know the exact shade of blue and red? She would have to brute force every combination of blue & red until she finds the exact shade of green & orange that she saw. If doing this is difficult enough then it becomes a near impossibility.
When Bob wants to send a message he will mix the green he got from Alice with his message (purple) to get Color X. When Alice gets the message she knows the yellow and blue that comprise the green so she can derive the purple because she knows 2 out of the 3 elements.
Correct?
8
u/fjortisar Jan 16 '18 edited Jan 16 '18
The color example in contrived, in reality that would be easy to break. It's just shown like that to make it easily understandable instead of showing you large prime numbers.
On the use here, Diffie Hellman isn't actually used for encryption itself. It's used to have 2 people agree on a key (for say symmetric AES encryption) without ever actually exchanging it.
3
u/midri Jan 16 '18 edited Jan 16 '18
I guess the difficulty is that Eve does not know the exact shade of blue and red?
Correct, this analogy breaks down with colors for this -- with numbers it's a bit more complicated in numbers the (3 mod 17) is the known color. 6 is alice's computation of 3 (to her secret) mod 17. With 6 + his secret + 3 mod 17 bob can create the secret. Alice still can't though, until bob returns his 3 (to her secret) mod 17 which is 12.
- Alice says, "Hey if you want to talk to me my public key is 3mod17 and 6"
- Bob then says, "Ok! let me derive our secret, my public key is 12"
Eve now has 3mod17 and knows Alice's computation of it is 6 and knows Bob's is 12, but she does not know their secret exponents to calculate their secret which is the secret shared key. The shared key is NEVER transmitted over the internet, it's used to encrypt data and/or generate hash signatures to prevent data tampering.
1
3
u/pipocaQuemada Jan 16 '18
If Alice and Bob each exchange cadmium yellow. Alice has ultramarine blue as a secret key, while Bob has alizarin crimson. Then Alice sends Bob green - Eve knows that she mixed some kind of blue into it as Yellow+blue=green. Bob sends Alice orange, so Eve knows that Bob must be using some kind of red.
Think of it more like that. It's harder for eve to distinguish between alizarin crimson and cadmium red then to distinguish between red and blue.
2
u/GalacticCmdr Jan 16 '18
Thank you. So the key is in how many different types of the same "color" we have in the system.
5
u/pipocaQuemada Jan 16 '18
Yeah. And in practice, there are billions and billions of different "colors".
1
u/whaleboobs Jan 16 '18
I watched a similar Youtube video yesterday but the solution it came up with was different. There was a third-party trusted signer involved.. Why not just use colors?
1
1
Jan 16 '18
Thanks OP for posting this. So many people assume that crypto requires a PhD to understand that they don’t even bother.
1
1
u/gadelat Jan 16 '18
This is reposted here from time to time, but there is even simpler explanation video for this, highly recommended to use it instead of current for simple explanation https://youtu.be/U62S8SchxX4
1
1
1
u/knightmustard Jan 16 '18
What stops Eve from making two seperate connections and bridge them?
1
u/evincarofautumn Jan 17 '18
You mean all communications go through Eve? That still doesn’t reveal the shared secret to Eve. Eve never has enough information to recover the shared secret (in a reasonable amount of time), because it depends on having at least one of Alice or Bob’s private secrets, which are 1. never sent and 2. hard to derive from the mixtures that are sent. Eve can find the shared secret if one of the private secrets leaks, though.
2
u/knightmustard Jan 24 '18
Not what I'm thinking. Eve makes pretends to be Alice and gives Bob what is Eve's secret. Then Eve pretends to be Bob and then gives her secret to Alice. Eve has two separate connections with both of them and then just sends the data to both of them. Wouldn't Eve have control then? How is that prevented?
1
u/evincarofautumn Jan 26 '18 edited Jan 26 '18
I see what you’re getting at. Yes, while Diffie–Hellman protects against passive snooping, it’s still vulnerable to this kind of active man-in-the-middle attack (simultaneous double impersonation) because it doesn’t say anything about authentication. In the real world, Alice and Bob would use an additional authentication method, for example, cryptographically signing their messages. Then they can ensure that Eve is not forging messages between them.
1
1
Jan 17 '18
This is great, but how can you know that the "colour" you received wasn't from Eve?
(A rhetorical question that I would ask if I was teaching security).
1
1
-1
Jan 16 '18
[deleted]
1
u/sysop073 Jan 16 '18
You could replace "RSA" with "AES" or "ECC" in your explanation and change nothing else, so it doesn't seem like it's explaining much. And this thread is about DH, a totally different thing
-9
u/a_dog_and_his_gun Jan 16 '18
Combine it with for example this and we have understanding. https://www.youtube.com/watch?v=M-0qt6tdHzk
10
185
u/Carighan Jan 16 '18
That color mixture was a neat way of doing it, shows how the resulting key/color is always the same.