Security

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.

About

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.

22 comments
oria001
oria001

I win... Since he did not come forward to clime the prize, I did :) Actually... I know the answer to the puzzle but get lost reading replies... So I did win :) Thanks Chad for the fun way of learning.

jck
jck

One question though, Chad: If I provide a box with a lock openable by either one of two keys, and the keys are both of complexity enough. Doesn't my method work more efficiently than the original, so long as I securely provide both users with their unique, usable key to the box? Someone puts data into my secure box. Locks box with their key. Sends box. Other user opens it with their key. QED Actually, I think my method sounds like a mutation of public key encryption where the public key isn't so public. :^0 But, I'm not sure. I haven't worked in encryption in 11 years. Love the brain teaser/mind moving/techie stuff like this that deals making you go "hmmmm...". Thanks for doing it :)

LocoLobo
LocoLobo

One thing that has me stumped though is the concept of the asymmetric key cipher. If you can encrypt data, why can't you decrypt it? Worse case you build a table by encrypting a small dictionary. Wouldn't you then have the capability to decrypt the encrypted data?

Michael Kassner
Michael Kassner

I have read many explanations and yours is one of the best. Kudos to you sir. Edit: Spelling error.

Sterling chip Camden
Sterling chip Camden

This is a great introduction for anyone seeking to understand either Diffie-Hellman or public key cryptography.

apotheon
apotheon

Learning and fun go together like a horse and carriage -- except, sometimes, when learning from mistakes.

apotheon
apotheon

What you're talking about is having two keys that are identical except for some part of the key that doesn't actually make any difference at all. Even if that's not how they work in a particular given case, there isn't any functional difference from that explanation in terms of your end result. At that point, you may as well just use a symmetric key cipher. I don't really see the point of using two separate keys, each of which does nothing the other doesn't do. . . . unless I misunderstood something you said. Love the brain teaser/mind moving/techie stuff like this that deals making you go "hmmmm...". I'm glad you liked it.

Neon Samurai
Neon Samurai

The math in asymmetric algorithms does not allow the key that encrypts to decrypt so you always have to use the second key to reverse what the first key did. symmetric algorithms mathematically use the same key to encrypt and decrypt based on how those formulas are developed. hash algorithms result in a standard length of characters which can not mathematically be reversed back to generate whatever was processed nor should two different things result in the same hash value. I'm not sure the deep details of the math behind them otherwise I'd be much better paid. ;)

apotheon
apotheon

Please elaborate on the specifics of your question so I'll have a better idea what you're asking.

robo_dev
robo_dev

on Saturday. PKI is pretty simple, once you understand it. :)

apotheon
apotheon

I certainly hope it proves useful.

LocoLobo
LocoLobo

I was trying to figure out a simple math example for the asymmetric functions. But I just don't understand it. Went to wikipedia and looked at their articles on Public-key cryptography and Diffie-Hellman but haven't spent the time required to understand them.

LocoLobo
LocoLobo

Although I don't understand the concept that well which prompted my question. Asymetric Keys - Encryption key (algorithm) encrypts but doesn't decrypt. Decryption Key decrypts an encrypted message but doesn't encrypt. I got that far but can't really come with a simple example mathematically I can understand. But my real question is if you have the public encryption key can't you reverse engineer the process. Encrypt 1000 words one at a time. Study the output. Do the same for phrases. Wouldn't that give you a "code" book? Of course it wouldn't be as efficient as the decryption key, but... I'm asking because I really don't understand it. thanks

apotheon
apotheon

Best o' luck on the exam. By the way, a public key cipher is not the same thing as Public Key Infrastructure. A public key cipher is the sort of thing used in tools like OpenPGP. PKI, meanwhile, is the complete set of systems necessary to manage the issuance, use, and revocation of digital certificates for protocols such as SSL/TLS.

Neon Samurai
Neon Samurai

That's a much more clear description then was in my current casual reading from a week ago. It may also have been my reading so close to the resort bar that helped to complicate it. ;) Either way, I'm due to go back and reread the chapter so it'll be interesting to have this example on hand when I do.

LocoLobo
LocoLobo

Still reading through the other links. My college math classes were back in the 70s.

LocoLobo
LocoLobo

I'm still working through the links. It's been a long time since my last math class.

LocoLobo
LocoLobo

That's what I'm asking. Thanks for the simple example. It helps with understanding the concept.

apotheon
apotheon

It seems you're asking about why one can't figure out how specific words or other small chunks of data look when encrypted, and build a sort of linguistic phrasebook of sorts that can be used to decrypt larger messages. For instance, if you have the words "world", "gray", "super", "hello", and "pedobear" decrypted individually, and know how each of them looks when encrypted, you reason that you should be able to recognize the encrypted message "hello world" by simply attaching the encrypted forms of "hello" and "world" together and comparing. Is that what you're asking about? Assuming it is, that's not the way modern cryptography works. A cipher that worked like that would be trivially broken, by today's standards, using essentially the exact methodology you described. Strong encryption works in an entirely different manner, though. For instance . . . let's use an absurdly simple example. Say you have a cipher that only works on numbers of any length greater than two digits. Your cipher implementation counts to the second digit, and takes note of that digit. If the number you want to encrypt is 121, that means the cipher picks out the number 2. Then, the cipher implementation takes the original number, 121, adds 2 to that digit it plucked out, and applies the resulting number as an exponent, so you get 121 to the power of 4. The end result is 214358881. Now, let's say you want to use that same cipher on the number 1121. The second digit is 1 now, instead of 2. As a result, your cipher implementation raises 1121 to the power of 3, producing the number 1408694561. Notice that, even though 121 is part of the visible form of the number 1121, there is no 214358881 (the "encrypted" form of 121) in 1408694561 (the "encrypted" form of 1121). (By the way, this is absolutely not an example of strong encryption. It's stronger than a simple substitution cipher, where every character has a corresponding "encrypted" character that is swapped in, but that's not saying much. Don't try using this naive cipher of mine for anything that actually requires any security.) So . . . does that answer your question, or have I misunderstood what you're asking?

Michael Kassner
Michael Kassner

One common type of public/private key encryption is RSA encryption. The encryption scheme works like this: 1. A message is converted into cipher text by changing the message into a number N that belongs to a predetermined set of numbers. 2. The number N is raised to a predetermined power (public key) and massaged with modular arithmetic. http://en.wikipedia.org/wiki/Modular_arithmetic 3. The now huge number N is then sent to the receiver. 4. The message is decrypted when the number N is divided by the product of two predetermined prime numbers (private key) and the magic of modular multiplicative inverse. http://en.wikipedia.org/wiki/Modular_multiplicative_inverse You are correct that the public key could lead to finding the private key through two attacks. To prevent confusion, I better mention that the private and public keys are composed of two numbers a modulus (needed for modular arithmetic) and the actual key. One attack is factoring the modulus back to the two prime numbers used to create it. The two prime numbers along with the public key can be used to find the private key. That's why absolutely huge numbers are used, making factoring almost impossible. Your thought of encrypting known text and comparing it to the cipher text would also work originally, because RSA encryption did not have a random component. That was fixed by adding padding: http://en.wikipedia.org/wiki/Padding_%28cryptography%29 RSA encryption then becomes semantically secure: http://en.wikipedia.org/wiki/Semantically_secure It means the attacker will not be able to distinguish two separate encryptions from each other even if the plain text is known. So comparing your results would not work. Edit: Spelling

Neon Samurai
Neon Samurai

What one key does, the other key undoes and neither key can undo it's own work. If I use my private key to encrypt something then anyone can use my public key to decrypt it. The message is not secret because anyone can decrypt it but they can be sure it came from me because only my private key could have encrypted it. My private key can not be used to decrypt that message so even I have to use my public key. If you want the message sent too me to be private. You would use my public key to encrypt it. Only my private key can then decrypt it so my public key being available to anyone doesn't matter. For my private reply back to you, I would then have to use your public key to encrypt the message which only your private key can then decrypt. I can't think of a nifty ascii diagram to display it right now. I may also be repeating what you already know.