The Basics of Crypto 10: Key Exchange Systems

Cryptography is great once you and the person you intend to exchange messages with have agreed upon a shared secret which you can use to encrypt your messages however what do you do prior to that? This is where Key agreement systems come in such as Diffie-Hellman and other systems (although the others are mostly never used in real systems) come into play. In the long distant past before we invented modern methods of exchanging cryptographic keys securely over the internet people were required to do some very archaic things when setting up a secure key exchange like going to meet in person... Isn't it great how times have moved on!

Diffie-Hellman

Might as well start with the most popular of the bunch. This system requires each party to choose a private number and then compute a public number based on that private number. Normally this public number would be the private number with a few operations built on top of it. The magic here is that the system works by ensuring the public value combined with either private value is the same allowing the two parties to establish a shared secret key. It is important to remember that the private numbers chosen can not just be any old number, they must be primes and they must also be very large, there is an equation ensuring they are large enough which is covered by most Diffie-Hellman implementations including in OpenSSL. There are multiple forms of Diffie-Hellman including those that support message signing to prevent man in the middle attacks and eavesdroppers.</span>

An image (stolen from Wikipedia) demonstrating the key exchange using paint as an example can be seen below and more information can be found here:

If an eavesdropper captures the whole exchange, they would only know the common color (blue) and the first mixed colors (dark blue and brown), but it would be incredibly difficult for the eavesdropper to determine the common secret color (light purple), when using large numbers instead of colors, this action is computationally expensive, so expensive it can be considered impossible for modern computers to achieve in a useful period of time (as in before the sun dies).

Authenticated Key Agreement (AKA)

Mobile phones using 3G and 4G authenticate with the carrier using a method similar to SSL Pinning whereby the carrier has a list of secret keys and the sim cards they shipped with and then sends two values to the sim card, one of which is a value encrypted with the secret key to be used as the key for the current communication and the other is received by the sim, hashed using the secret key and returned from the sim to the carrier. This then ensures both the carrier and the sim have a shared secret that can be used for encrypting further messages.

There are other key exchange mechanisms other than the two mentioned above, one of which is even more secure than Diffie-Hellman with signing (more information here) however they are used very rarely at present.