3

I might have missed parts of the technicality when it comes to the initial state of the key exchange. However, If I'm not wrong, if the initial key exchange is done over an insecure channel, how can one be sure that this first encounter is not "wiretapped"?

I've read someone say here that its like having a box, encrypting it with a key, sending the box, forcing the receiver to encrypt it with a key and returning the box. First sender then removes her key and returns the box. But how can one remove your key from something that has been encrypted again by someone else? How do identify what is yours?

Gjert
  • 175
  • 5
  • @SteffenUllrich What confuses me is this, is f[A] and f[B] the same? Is it like A*f[B] = S and B*f[A] = S where S is the same for both? – Gjert Nov 28 '17 at 16:44
  • No, they are not the same. – ewanm89 Nov 28 '17 at 17:02
  • DIffie-Hellman key exchange doesn't care if the channel is being wiretapped. The secret can still be shared without revealing it. If both the parties authenticate each other, the presence of attacker becomes useless. – defalt Nov 28 '17 at 17:03
  • @ewanm89 But how is the secret common if A * f[B] is not the same as B * f[A]? – Gjert Nov 28 '17 at 17:10

1 Answers1

2

The analogy of the sending of the box is not quite accurate in any public/private key algorithm. It is only as good as it is something that would work in the physical world. With that out of the way, lets get to Diffie-Hellman key exchange.

Diffie Hellman does not actually exchange keys, it exchanges some information to generate the keys. However it only exchanges part of this information, the rest is kept by each user. Lets go through it, we'll call our users Alice and Bob ;) :

  1. Alice and Bob agree to use a prime number as a modulo p, and a base which is a primitive modulo root of p which is g. These mathematical properties must hold for the discrete logarithm problem the mathematics is built on to hold.

  2. Alice and Bob each choose an integer they keep to themselves, lets call them a and b, then each of them runs the same calculation on that integer, first they calculate g to the power of the integer modulo p. And they send this to each other.

    ga mod p
    gb mod p

  3. Now here is the clever bit, neither now can find out what the others secret integer is, but if they take what they got from the other one and raise it to their own integer and calculate modulo p of that, they both get the same number S:

    (ga mod p)b mod p = gab mod p
    (gb mod p)a mod p = gba mod p

4) Shared number is now used to derive some encryption key for further information.

Without knowing one of those secret integers an attacker can not generate the same number and therefore the same key. Schors algorithm on a quantum computer can solve the discrete logarithm problem to get back those secret integers from the data that was exchanged, but past that or getting Alice or Bob's machine to send them (in which case you can get them to send the derived key, or the unencrypted messages sent/recieved instead).

However if that information did not actually come from the other party but the attacker themselves then without other checks (this is what SSL/TLS certs are for) the attacker can decrypt, re-encrypt and relay the data on.

ewanm89
  • 2,043
  • 12
  • 15
  • This is great! The entire (ga mod p)b mod p = (gb mod p)a mod p is what I've struggled with understanding! :) Thanks! – Gjert Nov 28 '17 at 17:28
  • 1
    There fixed the formatting, Math in Markdown is hard. – ewanm89 Nov 28 '17 at 17:31
  • This has just been released and has a far better analogy specific to Diffie-Hellman: https://www.youtube.com/watch?v=NmM9HA2MQGI – ewanm89 Dec 15 '17 at 22:48
  • Yeah, I just watched it, but I was curious behind the mathematics of it, however I think I managed to grasp the arithmetics of modulo :) – Gjert Dec 16 '17 at 13:11