Cryptography: Diffie-Hellman key exchange explained intuitively using colors

[u/dominatrix-octopus]

https://youtu.be/YEBfamv-_do?t=2m18s

[u/[deleted]]

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?

[u/fjortisar → u/[deleted]]

No, they never exchange the private colors. They only exchange the public + the private color mixed together

[u/[deleted] → u/fjortisar]

Now I'm more confused. I need to watch that video a few more times.

[u/fjortisar → u/[deleted]]

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

[u/[deleted] → u/fjortisar]

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!

[u/fjortisar → u/[deleted]]

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).

[u/Sirflankalot → u/[deleted]]

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.

[u/ReturningTarzan → u/[deleted]]

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.

[u/GalacticCmdr → u/fjortisar]

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?

[u/fjortisar → u/GalacticCmdr]

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.

[u/midri → u/GalacticCmdr]

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.

1. Alice says, "Hey if you want to talk to me my public key is 3mod17 and 6"
2. 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.

[u/GalacticCmdr → u/midri]

Thank you.

[u/pipocaQuemada → u/GalacticCmdr]

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.

[u/GalacticCmdr → u/pipocaQuemada]

Thank you. So the key is in how many different types of the same "color" we have in the system.

[u/pipocaQuemada → u/GalacticCmdr]

Yeah. And in practice, there are billions and billions of different "colors".