Solving the key exchange problem

The solution to last week's key exchange puzzle can teach you something about how cryptographic key exchange works.

In last week's article, The key exchange puzzle, I shared a problem with a known solution with you. The solution to this puzzle demonstrates the Diffie-Hellman key exchange protocol. Click the link to the key exchange puzzle to see the original puzzle if you haven't already, and come back when you're done, so you won't have the fun spoiled for you.

The Solution

The answer is actually rather simple, but non-obvious:

  1. Put your secret message in a box, and lock it. Keep the key, and send the box to me.
  2. When I receive the box, I'll put my own lock on the box as well, and keep the key for it, then send the box back to you.
  3. When you get the box back with two locks on it, you use your key to unlock your lock and take it off, then send the box back to me.
  4. I can now unlock my lock on the box with my key, and there are no longer any locks on the box. I now have access to the secret message inside.

The Point

Diffie-Hellman key exchange uses this protocol not to send messages, but to send keys. If you send a copy of a key you have to me using this protocol, then anything you send me forever after that is secured with a lock that key unlocks will be unlockable by me. Thus, we have a secure means of sending keys to each other that can then be used to keep opening later boxes, as long as the later boxes are all locked with locks that can be opened using the same key. With each message you send, you can send another key that will allow me to open the box carrying your next message.

This secure protocol for exchanging keys for use with symmetric key ciphers — where encryption and decryption are performed with the same key, so that two communicating parties need to have copies of the same key to send each other encrypted messages — is known as Diffie-Hellman key exchange because it was developed in 1976 by Whitfield Diffie and Martin Hellman. As it turns out, it was independently developed even earlier by Malcolm J. Williamson for use by the British signals intelligence agency, GCHQ. Williamson's invention of this protocol didn't do the rest of us any good, though, because it was classified, necessitating the reinvention of the wheel by Diffie and Hellman.

Going back to the symmetric key cipher again for a moment, once you have sent me a copy of a key you have, you can then send me a box locked with the lock that key fits. When it arrives, I can of course open it — but, because it is my own copy of the key, and you still have your own copy of the key, I can then use the same lock to send a message back to you, knowing you'll be able to open it with your copy of the key. The analogy to digital encryption breaks down here, however, because with a symmetric digital cipher the key is used not only to open a "lock", but to create it in the first place.

The Problem

Unfortunately, this is vulnerable to a man-in-the-middle, or MITM, attack. Still using the box-and-lock metaphor, an MITM attack is what happens when some malicious third party is intercepting the boxes. That person could intercept the first box you send to me, add a lock of his own, then send it back to you. When you see your box come back with an extra lock on it, you might assume it reached me and that I sent it back with that extra lock.

If you unlocked your lock and sent the box back, so that it got intercepted again, the man in the middle could then unlock his own lock and see what's inside. To make it a true "man-in-the-middle" attack, the man in the middle could then forge a message from you to me, and send it to me, with the contents conforming to what you sent in the first place. In the end, then, you would have given a key to your next lock to the man in the middle, and I would have a key for the next lock belonging to the main in the middle. Neither of us would have any idea our locked communication channel had been compromised. The same problem exists for cryptographic key exchange protocols that do not have any out-of-band verification built into them.

Avoiding the Man in the Middle

The term "out-of-band" refers to something that takes place outside the normal communication channel. Such information can be used to verify that the original communication channel has not been compromised.

Another approach to key exchange is that of public key cryptography. Rather than create a symmetric key cipher and find a way to securely exchange keys, then figure out a way to use out-of-band verification to ensure there wasn't a man in the middle compromising the entire process, public key cryptography involves creating a cipher where two keys operate on the same encrypted data. One is used to encrypt, and the other to decrypt, resulting in an asymmetric key cipher.

At this point, no secure key exchange is needed. All you need to do is keep the key you use to decrypt messages secret, and publish, for all the world to see, the key used to encrypt messages meant for your eyes alone. Then, anyone at all can encrypt a message that only you will be able to decrypt. To send a message to someone else, you use that person's publicly published encryption key (the public key), and that person is then the only person in the world that can decrypt the message because that person will be the only one to possess a copy of the required decryption key (the private key). Each person, then, has his or her own private decryption key, and a public encryption key that is shared with anyone else who wants it.

If the cipher being used allows encryption and decryption roles to be reversed, so that a private key can be used to encrypt something that only the public key associated with it could decrypt, an encryption step can be performed by the sender using his or her own private key and effectively "sign" the message with an unforgeable digital signature that can be verified by using the public key.

This explanation of how public key encryption works is the basis for OpenPGP, one of the most popular and secure private communication protocols in the world.

In terms of the key exchange puzzle, a public key cipher would be akin to publishing the specifications for a lock that only you can open because only you have the key. Anyone could then put together that lock and use it to send secure messages to you. I leave trying to fit the analogy of cryptographic signatures into the key exchange puzzle as an exercise for the reader.

Combining the Two

Public key encryption itself can actually act as out-of-band verification for a symmetric cipher key exchange. If, for some reason, you find yourself needing to exchange keys for a symmetric key cipher — and public key encryption simply isn't suitable to the uses to which you play to put the symmetric key cipher — an initial Diffie-Hellman key exchange can be protected from MITM attacks by use of a separate public key cipher.

To do this, you would digitally sign the message sent to the me with the encryption key enclosed using your public key so I can verify it using your public key. Then, you would encrypt the whole thing — digital signature included — using my public key, so only I could decrypt it.

If you do not have a compelling reason to use a symmetric key cipher, however, it is probably easier to just use public key cryptography instead.

A Broken Solution

An alternate solution has been suggested to variants of the key exchange puzzle in the past. In this alternate solution, you would send me an empty box, locked with one of your locks — or maybe just send the lock. A key for a different one of your locks could then be attached to the lock by passing the lock's hasp through a hole in the key before it is locked.

Then, after enough time has passed that the lock with the key attached has arrived in my hands, you could send another box with a secret message inside, locked using a lock that is unlocked by the key you previously sent.

There is at least one glaring security hole in this key exchange protocol, however — possibly two, depending on your assumptions. The problem is that keys can be copied. Before the first lock (with the key attached) ever reaches me, some unscrupulous postal worker could easily have pressed the key into putty and used the impression to make a new key, or could have just taken the whole lock with the key attached down to Home Depot to get a copy of the key made, then passed the lock on to me with neither you nor me knowing there's now a copy of the key out there. This would even render out-of-band verification useless, which is why a private encryption key must never be exposed to the public the way it would be if it were a physical key attached to the outside of a locked package. It is, in fact, even easier to copy an exposed digital encryption key than a physical padlock key.

Who Won?

More than one person essentially came up with the Diffie-Hellman key exchange protocol in discussion following last week's article about the key exchange puzzle. The first correct response — not strictly the Diffie-Hellman protocol itself, but encompassing the core principles of it — was posted by richard.moore4 only a few hours after the article appeared. Congratulations, richard.moore4.


Chad Perrin is an IT consultant, developer, and freelance professional writer. He holds both Microsoft and CompTIA certifications and is a graduate of two IT industry trade schools.

Editor's Picks