Security

The key exchange puzzle: Test your cryptographic skills

Test your cryptographic skills by solving a puzzle. This one points out the principle that concerns the secure key exchange.

Let's do something different today. Let's learn about cryptography by trying to solve a puzzle.

The Puzzle

You and I need to communicate via the National Postal Service. What you want to communicate is secret, so you don't want a postal worker or some random schmoe who finds your mail in the mailbox or a package on your stoop to be able to open it up and read what's inside, and you know from experience that any time you send something in the mail without securing it, it either gets read or (if it's not just text) stolen. We must live in a country with a really corrupt postal service, I guess -- kind of like the Internet.

We each have access to an arbitrary number of indestructible boxes, and an arbitrary number of indestructable key locks. Each box can have as many locks on it as you like. Unfortunately, each lock has only one key, and only the person who possesses the lock has the key. We can send things to each other in locked boxes, but of course the recipient doesn't have the key to the lock because the sender has it. Sending the key unsecured will get it stolen or, worse, copied. We also have no way to meet each other in person to exchange keys securely (and if we did, we could just skip the postal service altogether, anyway).

How can we arrange, with these resources, to communicate securely with each other?

The Point

The point of this puzzle is to demonstrate a principle of cryptography known, among other terms, by the name "secure key exchange". This particular puzzle is especially relevant to Diffie-Hellman key exchange. If you can figure this one out, you either have run across something like the problem in this puzzle before or probably have a mind suited to developing secure cryptographic algorithms.

Can you figure out the solution?

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.

45 comments
apotheon
apotheon

Check out Solving the key exchange problem to compare your solution with the canonical solution -- and to learn some more about key exchange protocols.

msr
msr

A 3 pass protocol can solve this. Secret is locked with lock1 and sent across. Receiver puts on lock2 and sends back to sender. Sender removes his lock1 and passes back to receiver. Receiver opens the box by removing Lock2 with key2 that he holds

melias
melias

I am going to assume you cannot or will not make copies of the keys. Other parties will of course try to do so. Tom sends Tammy a locked box secured by lock A. In it is unlocked lock B and key C. After Tammy has the box, he sends Tammy key A. Tammy opens lock A using key A, then disposes of both. She replies back to Tom, locking the box w/lock B, keeps key C. Tom gets the box, unlocks using key B. Replies back using lock C to lock the box, and puts lock B in the box. Tom will now always lock his boxes using lock B. Tammy will lock her boxes using lock C. Tom keeps key B on him, Tammy keeps key C. Each will put the other lock in the box unlocked when replying. If the key HAS to stay with the lock, then just include the key in the box with the matching lock. Edited to fix incorrect placement of lock vs key.

The 'G-Man.'
The 'G-Man.'

Send unsecured open box Send unsecure key copy (both seperate) Send origional unsecure box back Now secure box with original key after inserting item Send box back Open box with copy key Box destroyed Key now invalid Begin again.

taitos7
taitos7

i've an complex solution suppose mail has 2 locks the sender put the one lock on mail and let the other place free the reciver couldn't open the mail beacuse he isn't have a key so he put another lock on mail and resend it back the sender open the his own lock on mail and resend it ** no one could know the mail unless the sender and reciver another solution public key and private key

jck
jck

dual-key encryption. You have your own key, kind of like a safe-deposit except both aren't required to open it. One key opens for the sender, one for the recipient. Both have unique keys independent of one another, and both people still have access to them. Plus if one key is unrecoverable, the other person can come over with their key and open it for the recipient. QED

CharlieSpencer
CharlieSpencer

1) I send you a box locked with Lock A. Inside the box is Key B. Since the postal crooks couldn't open the box, Key B is secure. If you didn't get it at all, I'll repeat with a different pair of non-matching locks and keys (Lock B and Key C, Lock C and Key D, etc). 2) Eventually you'll send a message acknowledging receipt of a box and a specific lock. Let's say you receive Lock F and Key G. 3) I then send you Key F. I don't care if Key F gets copied, since you have the only lock it fits. If you don't get the key, start over with the next Lock 'x' / Key 'x+1' / Key 'n' until successful. 4) Let's say you eventually have a box with Lock N containing Key O, and then Key N arrives in a separate shipment. Use Key N to open Lock N and remove Key O. Send me a message saying you've got the key and I'll send you X-Men #137 in a box locked with Lock O. Any good? I liked this better than Tammy's, although I could feel a couple of brain cells die in the process.

apotheon
apotheon

I'll share the solution next week, and discuss some relevant concepts of security. Hopefully someone will answer it in comments before then. I expect someone might answer it today, actually.

apotheon
apotheon

Yep, that's basically the Diffie-Hellman key exchange algorithm.

apotheon
apotheon

Why shouldn't they both have copies of the same key? . . . and how do you get keys for one lock to both people, starting with the conditions I presented in the puzzle?

Neon Samurai
Neon Samurai

You send me an open lock for which you have the key. We confirm that you sent the lock that I recieved. I send you the item in a box sealed with your lock. You open your lock with the key allowing you to retrieve the item. This assumes the lock can be identified without duplication and a key can not be made based on the lock. I think I'm also missing something to do with multiple locks. I have to give this more thought and resist the urge to go reread how deffie-helman exchange actually works.

apotheon
apotheon

Your solution relies on the ability to: 1. authenticate the box and lock 2. authenticate the message saying the box and lock were received Since I never stipulated a means of authentication, your solution is based on unwarranted assumptions. Sorry. What if I get a copy of a box with lock B, and think it's the real thing, so I send you a message saying I got it? Then the key you send gets intercepted en route to me and is used to open the real box. What if I don't get any box at all, and the person who intercepted the box with lock B sends you a message meant to appear to be from me, saying that I received the box? Once again, when you send the key, it will get intercepted and used to unlock the box. Your solution is, I'm afraid, vulnerable to at least two types of MITM attack.

apotheon
apotheon

Did I miss a puzzle somewhere?

keith29@usa.net
keith29@usa.net

I came up with the idea of including an unlocked lock in the lockbox with each message,so: Bob sends Alice unlocked lock A,(he keeps the key). Alice puts unlocked lock B in the lockbox, with any desired message, locks the box with lock A, and sends it to Bob. Bob can now unlock the lockbox with the key for lock A, etc. Of course, this looks like public key cryptography. Oh well, just a few years too late.

unhappyuser
unhappyuser

I send you a locked box with a key and lock inside it. I have a copy of that key (locks come with a set of two). I then send you the key to the first lock. After you unlock the box you then discard the first lock-key set so, if it's copied, it doesn't matter. You then send me the locked box (that I sent you) with a lock and key in it (you have a copy of that key). This goes on until one of goes insane, since the supplt is unlimited. EMD

hburke
hburke

Mail me a lock. I'll lock my box with it and return it to you. You already have the key.

phelmima
phelmima

have one person sent a box that is not locked to the another person, then that person insert their locked box and key into the unlocked box then closed the box and locks it

jck
jck

you're thinking padlocks. my bad. i was thinking secured boxes with installed keyed locks. they can actually be keyed to 2 different keys, but I would think it would be more secure to have a lock mechanism with two different key releases so each key was exclusive to one person yet lets either person open their own lock to the same container. i read wrong...and just used a different lock.

CharlieSpencer
CharlieSpencer

Not my area of expertise. Enlightening, none the less. Thanks for a few minutes of mental exercise.

unhappyuser
unhappyuser

What if the postal guy locks the lock?

dschlesak
dschlesak

How are you going to lock the box when there is only one key and the person who sent you the lock has it?

apotheon
apotheon

I'm glad you got some enjoyment out of it. Mental exercise is good for you -- and yours was a good effort -- plus, anything from which one learns has an upside.

apotheon
apotheon

I didn't even know this had been accomplished. Thanks for the link.

lastchip
lastchip

My box has a space for two locks. I enter my message to you, lock the box and send it to you. You then place your lock on the box and send it back to me. I now remove my lock and send it back to you. You can now remove your lock and read the contents. The reverse is also true.

Neon Samurai
Neon Samurai

She can open Lock1 attached to the box though not Lock2 added by Bob.

CharlieSpencer
CharlieSpencer

Regarding the point you raised about my solution: how does Andrea know the box she initially received back came from Billy? How does she know her package wasn't intercepted and someone else sent her package back with a false Lock 2 added to her Lock 1?

NetMan1958
NetMan1958

(1) Andrea makes a copy of the key for lock3 (2) Andrea sends lock 3 and one of it's keys in a box locked with lock 1 (3) Billy adds lock 2 and sends it back (4) Andrea removes lock 1 and sends it back (5) Now both Andrea and Billy have a key for lock 3 so Billy sends the next message in a box locked with lock 3. (6) They continue to use lock 3 for all further exchanges.

NetMan1958
NetMan1958

(1) Andrea sends a box locked with lock 1 that contains the key for lock 3. (2) Billy adds lock 2 to the box and sends it back to Andrea. (3) Andrea removes lock 1 and sends it back to Billy. (4) Billy unlocks the box, takes the key for lock 3 and makes a copy of it. (5) Billy outs the original key for lock 3 back in the box, locks it with lock 2 and sends it back to Andrea. (6) Andrea adds lock 1 to the box and sends it back to Billy. (7) Billy removes lock 2 and sends it back to Andrea (8) Now they both have a key for lock 3 and continue to use lock 3 for all further exchanges.

Neon Samurai
Neon Samurai

I made the mistake or reading the comments before thinking more on it myself but having read the spoiler... Billy does not have to open lock1 or the box. A.Lock1 -> B.Lock1 "Here is Lock3 but you can't open it yet" A.Lock12 B.Lock2 "I accept that removed my Lock1" A.Lock3 B.Lock4 "here is a secret response and a Lock5"

Lodai
Lodai

Billy doesn't have the key to open Lock 1, however if Andrea sent the box with Lock 1 unlocked instead of locked, then it would work fine. We can't make assumptions that Billy can open Lock 1.... Edit: After re-reading, I mis-interpreted the solution. My mistake. Never try to solve anything without having had your first cup of coffee....sheesh

richard.moore4
richard.moore4

Now I remember why I used locks instead of keys. At the end of that last exchange, if Billy had received a key, Billy could now open the next message that Andrea sent, which will geive him the key to the next message after that... but he can't send a message until he gets his own key to Andrea. By sending keys you need two secure exchanges. By sending locks, you only need one. That's why locks occurred to me first. Of course, you could send a key AND a lock the first time, and switch to keys after the next message, but for the simple proof, that's unneccessarily complicated. And besides, indestructable boxes are probably heavy enough that the weight of an extra lock won't make that much difference :P Good night!

richard.moore4
richard.moore4

If you send a key, then if one exchange is compromised, any exchange further down the line is potentially compromised, as each time, the people could just open the lock with the copy of the last key and copy the key as it comes by. I suppose that if you send a lock, then a similar interception is possible, but it's a lot harder (especially if the locks have serial numbers). The interceptor would have to replace the lock in the package with his own lock and send it on. Still, if the interceptor missed one interception, in either case the data becomes inaccessible to the interceptor, but in the lock case, the tampering becomes evident. I guess what I'm saying is: you have to anticipate that no system is bulletproof. Attackers will penetrate it; you have to make it so that one compromised message does not compromise the whole system. Or am I overthinking things and breaking how this equates to encryption? (By the way, this isn't why I originally did it that way; this is just me rationalizing. The locks were just how I visualized it)

santeewelding
santeewelding

Came back in reversal of the temporal to do it.

apotheon
apotheon

Your solution is basically the Diffie-Hellman solution, but there's an unnecessary extra step involved for getting the first message across -- since you used the initial secure exchange just to send the means to send a message securely, when you could have (also) sent the first message at that point. Also . . . instead of sending an unlocked lock in the initial exchange, you should have sent a key. Locks weigh more, and thus require more postage. Good job getting the initial exchange algorithm down, though.

apotheon
apotheon

I added a spoiler warning.

santeewelding
santeewelding

You're going existential on us. _______________ Hey! I guessed right! I posted this before I saw your answer! Although, spoilsport, you could have simply posted the eighth.

apotheon
apotheon

Actually, I just found it unnecessarily obscure -- not mysterious at all. Now that I've seen a link to the thing, though, I actually see eight differences between the pictures.

CharlieSpencer
CharlieSpencer

Mine puts all the work on one person. By splitting it like you did, you reach a solution much faster.

richard.moore4
richard.moore4

Let's call the people Andrea and Billy. Let's say that Andrea has all odd-numbered locks and Billy has all even-numbered locks. Andrea sends a box locked with Lock 1 to Billy with an unlocked Lock 3 in it. Billy then sends that box back to Andrea, now locked with both Locks 1 and 2. Andrea removes lock 1 and sends the box back to Billy, which he can now open, as it only has lock 2 on it. Billy unlocks the box and removes lock 3. Now Billy has a lock which only Andrea can open. So Billy sends a message to Andrea, includes Lock 4, unlocked, in that box, and locks it with Lock 3. Andrea reads the secure message, writes a reply, puts the reply and Lock 5, unlocked, in the box and locks it with lock 4, and sends it back to Billy. And so on. I'd hate to see the postal bill on all of these packages being sent through the mail...

Editor's Picks