0
$\begingroup$

I try to understand diffie hellmann and I wonder why an attacker just can't make her own secret key and go along with the ride?

She'd be ending up with just the same shared key.

Let the private keys be: $$sk_A = 14, sk_B=12, sk_E=8$$

Let's assume the base is $g=2$ and the prime is $p=17$.

Alice would have a public key of $pk_A=13$ ($g^{sk_A} \bmod p = 2^{14} \bmod 17 = 13$) and publish it and Bob would have a public key of $pk_B=16$ ($g^{sk_B}\bmod p = 2^{12} \bmod 17 = 16$). Eavesdropper would end up with $pk_E=1$ ($g^{sk_E}\bmod p = 2^{8} \bmod 17 = 1$).

Now Alice can take the public key of Bob to arrive at the shared secret ($pk_B^{sk_A}\bmod p = 16^{14} \bmod 17 = 1$) and Bob can do so as well.

But can't the eavesdropper not always do the same procedure with her private key? In other words won't $g^{sk_E} \bmod p$ always lead to the same shared key?

(I updated the numbers so that prime is bigger than the exponents).

$\endgroup$
  • $\begingroup$ I tried to make the math more readable. Feel free to roll back the edit if you feel that they are not true to your intent. Your numbers are unfortunately chosen. Clearly it cannot be the case that $g^{sk_E}\bmod p$ will always be the same as the shared key of Alice and Bob. How would that even work for a randmly chosen key? But you are on to something that Eve can make up her own private key and act as a (wo)man-in-the-middle. This is why plain DH is insecure and the messages need to be authenticated. $\endgroup$ – Maeher Feb 2 '18 at 10:08
  • $\begingroup$ And $2$ is not a generator of $\mathbb{Z}_{17}^*$. $\endgroup$ – Maeher Feb 2 '18 at 10:12
  • $\begingroup$ My point is, that at the end of the day the exponent is the only secret part. Isn't any exponent here resulting in the same shared secret? It's not obvious to me why not ... Eavesdropper has the same information as alice has - the public key of bob. (And what does this generator thing mean?) $\endgroup$ – shredding Feb 2 '18 at 12:44
3
$\begingroup$

Eve does not have the same information. It's only with you poor choice of numbers did you get the phenomena where the number you chose for Eve happens to match. In general this doesn't happen, and with careful choice of parameters and large numbers the chance for this happening is negligible.

You chose an unsafe prime $17=2^4+1$ rather than a safe prime of the form $p=2*q+1$ when q is also prime. You then chose $g=2$ which only spans a group of size 8. $2^8=1\space mod\space 17$ rather than for instance g=3 which can produce the full range.

For Alice and Bob it is guaranteed: $(g^{P_a})^{P_b}=(g^{P_b})^{P_a} = g^{P_aP_b}$ Since Alice and Bob aren't using Eve's public key, she can't calculate the shared key with them. In the vast majority of cases she will end up with a different number.

In your example the shared key came out 1, and many guesses by Eve work (but not all). Because the public key for Alice and Bob came out with low rank (2 and 4). Using a large safe prime and a generator will make this highly unlikely.

It is considered very difficult to calculate $g^{ab}$ from $g^a$ and $g^b$ without knowing either a or b. Eve guessing a random key isn't likely to help. For random $e$ in almost all cases $g^{ae}\ne g^{ab}$

$\endgroup$
  • $\begingroup$ Where can i find out more about safe and unsafe primes and what do you mean by full range for 3 vs 2 for g? I thought g must not be relative prime to the private keys. $\endgroup$ – shredding Feb 2 '18 at 19:47
  • $\begingroup$ 3 is a generator of $Z^*_17$ while 2 is not. Using 3 gives all possible values. I always start my search for knowledge in Wikipedia, but searching this site will work as well in this case. $\endgroup$ – Meir Maor Feb 2 '18 at 19:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.