0

So, to start DH, the two parties need to agree upon a prime number and Generator, correct? How do they do do that without someone listening in?

Where does the loop end/start?

Also, Does it matter if a Man in the middle finds out the prime number and generator combo?

2

The Prime number and the Generator are not sensitive or secret. Meaning, the two parties can share them over an unsecured medium with no risk.

This article covers how the exchange works, and provides a number calculation example where two parties attain the same shared secret, which is unattainable if you had all the numbers that were shared over the unsecured medium.

Here is the illustration in that article:

Diffie Hellman Key Exchange - Practical Networking .net

The shared secret "3" can only be attained if you have either of the Private Keys (5 or 4). The values shared over the internet (13, 6, 2, 9) can not be reliably combined in such a way as to extract the shared secret (3).

And this Q&A over at the Cryptography Stack Exchange provides more explinations of how it works:

https://security.stackexchange.com/questions/45963/diffie-hellman-key-exchange-in-plain-english


Edit: As Ricky Beam pointed out in the comments, the numbers above used in the illustration are intentionally small and simple to show you the math of the DH exchange.

This is addressed in the aforementioned article, but for the sake of simplicity I'll quote the relevant section below.

Remember, any key is susceptible to brute force. In large part, the goal of Cryptography is to use numbers and calculations so large that attempting to brute force a particular key would take an unreasonable amount of time (1,000's and 10,000's of years).

DH Numbers

In our example, we used a Prime number of 13. Since this Prime number is also is used as the Modulus for each calculation, the entire key space for the resulting Shared Secret can only ever be 0-12. The bigger this number, the more difficult a time an attacker will have in brute forcing your shared secret.

Obviously, we were using very small numbers above to help keep the math relatively simple. True DH exchanges are doing math on numbers which are vastly larger. There are three typical sizes to the numbers in Diffie-Hellman:

  • DH Group 1 768 bits
  • DH Group 2 1024 bits
  • DH Group 5 1536 bits

The bit-size is a reference to the Prime number. This directly equates to the entire key space of the resulting Shared Secret. To give you an idea of just how large this key space is:

  • In order to fully write out a 768 bit number, you would need 232 decimal digits.
  • In order to fully write out a 1024 bit number, you would need 309 decimal digits.
  • In order to fully write out a 1536 bit number, you would need 463 decimal digits.

(Note, this article was written in 2015. At the current moment (2020), the key sizes above are considered too small)

| improve this answer | |
  • 1
    Love the Alice and Bob characters! ;-) – Zac67 Jun 20 at 16:37
  • 1
    @Zac67 ;) I think it made the illustration more appealing to look at than just the text "Alice" and "Bob". =) – Eddie Jun 20 at 17:34
  • It should also be said, these uber-simplified, single digit examples of DH can be brute-forced in milliseconds. Much of the security of DH comes from the size of the numbers, and the resultant complexity of the calculation. (which is also why MD5 and SHA1 have fallen out of favor.) – Ricky Beam Jun 21 at 0:12
  • @ricky beam it was very helpful for me to start thinking about it with that in mind - before I think I was thinking any number (I missed the part about one of them needing to be a prime number - but that's on me :) ) and thus couldn't understand how it could be secure. – nicotinefull Jun 21 at 19:14
  • Just to show my point, this example can be broken with a bash commandline: for a in $(seq 0 9); do echo "(G^$a) MOD P >>> " $[6**${a}%13]; done In this case the private key can be found, however, what you want is the set of possible private keys that generate the same possible shared secret. (P is larger than the key space, so there are no repeats.) – Ricky Beam Jun 22 at 7:30
0

I suggest you visit the Cryptography section of Stack Exchange. Your question is on-topic there.

You can answer part of your question by reading the Wikipedia page on Diffie-Hellman Key Exchange. Generally, Internet protocols rely on selecting among pre-agreed constants. You can find information about that in the specifications for the particular protocol of interest, for example, IPSEC RFCs.

| improve this answer | |

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.