Reply
Tue 14 Oct, 2008 12:06 pm
I saw this logic puzzle today, and enjoyed thinking about possible solutions. I don't believe there is a 'perfect' solution, but it's fun to try to come up with interesting ways to solve it, and how those solutions fail. Maybe someone here will find a perfect solution, who knows!
The problem
Alice needs to send an object to her boyfriend Bob without nosy Eve knowing what it is. Alice has a box that, when locked, is impenetrable, a number of locks that are unpickable, and a number of corresponding keys that are copyable. Bob has nothing.
How should Alice send the secure object to Bob, given the following?
* Alice and Bob can send packages to each other through courier; however, these packages can be intercepted by Eve.
* If Bob ever gets the object, glorious things will happen. Ideally, this is what we want.
* If Eve steals the package with the box, it's okay, so long as she can't open it.
* If Eve manages to open the box, dire things happen, especially if Alice and Bob don't know that she opened it.
* Alice and Bob can talk via cell phone, but Eve can spoof the caller id, and can fake voices. However, she cannot reroute calls. Essentially this means that if Alice calls Bob, Alice can be sure that she is talking to Bob, but Bob cannot be sure it wasn't actually Eve that called him.
* Eve can also send packages
* Anything not otherwise stated above (within reason) is considered insecure
Obviously Eve could steal every package, and the problem is unsolvable. Therefore I would like to assume that while Eve can steal any given package, it is assumed that eventually she won't. Also assume that Alice has an unlimited number of boxes, locks, objects, etc.
To start things off, I'll provide a wrong solution:
Alice sends locked box containing object. Then she calls Bob to confirm he has received it. She may need to send multiple locked boxes (if Eve steals them) but eventually one will go through and Bob will say he received the box. Then, Alice sends the key to open it (as many as it takes to get to Bob). Because Alice verified Bob had the box before sending the key, it ensures the key will be useless to Eve. Eve will never have the box and key at the same time.
So this is incorrect, but why? And what do you change to make it better?
@Nick Ashley,
I'm going to guess that this solution isn't good enough because Eve can intercept the package, send Bob a different package, and then wait to intercept the key.
Isn't this more or less the network packet problem?
@Nick Ashley,
Bob may be lying when he says he recieved a box because he thinks he might be talking to Eve.
I think the box part can be solved by Alice calling Bob, and asking him to call her back in X number of minutes, and tell him to use a password when he calls back, one that will change each time.
So Alice knows it was Bob she talked to, and she knows it's Bob who called back, because he uses the non repeating password.
When Bob calls back, Alice tells him she is going to send him a key, and tells him another password to verify he got it.
When Bob recevies the key, he calls Alice and tells her to call back in a certain number of minutes, and to use a non repeating password he gives her.
Alice calls back and gives the password, so Alice and Bob both know they are talking to each other.....Then Bob can give the password verifying he received the key.
@Nick Ashley,
Can you nest boxes? Can you have two simultaneous calls?
Alice calls Bob (Eve cannot re-route the call, so Alice knows she's talking to Bob).
Bob then calls Alice on a different line. (Bob knows that he's talking to Alice, for the same reason.)
Bob and Alice now have a secure communications link.
Alice lockboxes the object. Places it and a secret message in another lockbox.
Bob receives the lockbox.
Alice ships the key to the outer lockbox.
Bob opens the box and reads the secret message.
If the secret message is correct, Alice ships him the key to the inner box.
@chai2,
chai2 wrote:I think the box part can be solved by Alice calling Bob, and asking him to call her back in X number of minutes, and tell him to use a password when he calls back, one that will change each time.
Eve can eavesdrop. She'll know the password as well.
@DrewDad,
I like mine better because it's got secret passwords and junk.
@FreeDuck,
Yep. Or, when Eve gets the package, she could call Alice and say "This is Bob. I got the package, send the key now."
It has many similarities to network packets, yes. However there are some key differences. A computer can keep a copy of the packet, while still sending it to the destination. However Eve can't completely copy a box. (and this is a hint. She can copy a box itself, but if she can't open it, there is no way for her to replicate what is inside of it).
Can Eve eavesdrop? I wasn't sure.
@DrewDad,
Actually, two simultaneous calls aren't needed.
1. Lockbox object.
2. Place 1st lockbox with secret message in second lockbox.
3. Send lockbox to Bob.
4. Call Bob, verify that he received lockbox.
5. Ship key to outer lockbox to Bob.
6. Call Bob, verify secret message.
7. Ship key to inner lockbox.
8. Rejoice.
Alice puts the key in a box and sends that package. When Bob gets the box he calls Alice and says "got the box". Alice calls Bob and says "did you get the box"? If he says yes, then she sends the key to that box. Repeat the ping (Bob: I got it, Alice: did you get it). If that was successful, and as long as Bob could actually open the box with the key in it, send the package. The only key that Eve can copy is the key to the box that holds the key. If she spoofed the first box, Bob would know because his key wouldn't open it. Then they would try again until Bob got a valid key, at which time Alice sends the package.
@FreeDuck,
Eve and Bob must not discuss this plan ahead of time, though.
Eve could intercept the first package, and replace it with her own
if the contents can be spoofed.
Intercept the key, replace it with her own.
Intercept the second box, and horrible things happen.
@Nick Ashley,
Nick Ashley wrote:Alice sends locked box containing object. Then she calls Bob to confirm he has received it. She may need to send multiple locked boxes (if Eve steals them) but eventually one will go through and Bob will say he received the box. Then, Alice sends the key to open it (as many as it takes to get to Bob). Because Alice verified Bob had the box before sending the key, it ensures the key will be useless to Eve. Eve will never have the box and key at the same time.
So this is incorrect, but why? And what do you change to make it better?
Well, Eve could intercept the box and send another (empty) one to
Bob. When Alice calls Bob to find out if he's gotten the box, he'll affirm
to have received the box. Then Alice sends the key to Bob - Eve intercepts
and can open the real box.
So, I'd suggest this way: Alice sends the key plus password to Bob first.
Once he's gotten the key, he calls Alice, asks for the password and if correct,
will affirm having received the key. Then Alice will send a few empty boxes to see if Eve intercepts, and eventually sends the right box for Bob to open up.
@DrewDad,
This is a great solution. However, I don't think its necessarily without it's flaws. The only thing that allows it to work is your innovative way to create a secure communications link. Assuming they can only use one line, this wouldn't work.
But assuming they each have 2 cell phones, what would happen in the following scenario?
Alice sends first box. Eve keeps it. Since Bob never receves it, Alice sends second box. When Eve gets the second box, she sends a fake box to Bob. Alice then sends the key to the second box. Eve intercepts it, and opens the box to reveal the inner box, and message. She puts a fake inner box and a real message in a new locked box, and sends the box to Bob. Bob assumes the box he had was the first box, which was just slow to arrive. The second box he has must be correct. The next day, Eve sends bob a key to open her fake box. Bob notices it doesn't unlock his first box, but it unlocks the second. He reads the password to Alice, which is the correct password for box 2. Therefore, Alice sends the key for Box 2's inner box, because she thinks Bob has received that package. However, Eve actually has box 2's inner box. When the key comes, she opens it and collects her prize.
@CalamityJane,
Eve can intercept, copy the key, then send it on.
Each following box is then intercepted, opened, inspected, relocked and sent on its way.
@Nick Ashley,
That only works if Alice and Bob do not coordinate which key to use.
Alice: Use the key I sent you on the first box.
Bob: It doesn't work
Alice: Our box has been spoofed. Discard that key; we will try again.
@DrewDad,
Oh! I thought Eve could only intercept the box not the key.
OK, combining Freeduck's solution with mine:
1. Package a key and secret message together in a lockbox. Label the lockbox. Ship it to Bob.
2. Call Bob, verify receipt of 1st box.
3. Send key to Bob.
4. Call Bob, have him open the labeled box (and only the labeled box). Have him read the secret message.
5. Seal delightful object in second box that can be opened by the key in step one. Ship it to Bob.
6. Rejoice.
(This has the added benefit of not requiring nested boxes.)
@DrewDad,
Hm, okay I have another scenario.
1. Alice sends a box with a key in it to Bob. Does he not receive the box then
they know that Eve has intercepted the box and Alice keeps resending the
box with key inside until Bob receives it.
2. Once Bob has the box, Alice sends the key to open the box. Eve can copy
the key, it doesn't matter. When Bob receives the key, he can open the box
and find another key inside.
3. Alice sends the box where Eve could have copied the key - the box contains unimportant stuff. Then she sends the box where Bob has the key already, Eve could intercept but cannot open the box. Alice re-sends the box until Bob receives it and he's got the key already to open.
Stumble It!
Tweet This
Bookmark on Delicious
Share on Facebook
Share on MySpace