Author |
Topic: ghetto encryption 1 (Read 6122 times) |
|
Bob
Guest
|
i've heard something like this before. i was reading it in a book about encryption. the solution (i think) would be:
throw stuff into box, lock it with your lock, mail to friend
have friend add second lock to box, mail back to you
take of your lock, mail to friend
have friend remove lock and get stuff
|
|
 IP Logged |
|
|
|
tyler
Guest
|
just dont think this works with encryption where you scramble the contents then unscramble them in the same order...
|
|
IP Logged |
|
|
|
Ryno
Guest
|
Why not just put the stuff in the box, lock it and send to friend....then afterwards send the key. Who cares if the key gets copied because your friend will be the only one who can access the box!
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
Re: ghetto encryption 1
« Reply #3 on: Jul 26th, 2002, 8:16am » |
 Quote  Modify
|
I think the first solution from Bob is the intended solution, though the question omits the crucial assumption that your friend has a lock of his/her own. Otherwise this problem is not solvable. I guess you could also say that your friend could just send you the lock, and you use that to secure your shipment to him/her.
I think the problem's intent is also that you do not have more than one box available, or else indeed, you can just send the locked box and then the key later. Also something the question should state more clearly.
|
|
IP Logged |
|
|
|
Misha Kruk
Guest
|
I agree with Ryno, put stuff in the box, lock it, then send the key afterwards.
This solution is unexpected and funny. The solution with two locks is correct, but assuming that the other party has a lock is too much. Also this makes it a bit boring, because this is just a classic crypto situation described in every course/book on the subject.
This riddle is nice because it breaks the locked box analogy used by crypto people: you can't store a copy of box and unlock it later when you get the key.
|
|
IP Logged |
|
|
|
jmlyle
Newbie
Gender:
Posts: 31
|
|
Re: ghetto encryption 1
« Reply #5 on: Jul 26th, 2002, 12:44pm » |
Quote Modify
|
I'm pretty sure there is a solution.
The answer about sending the key seperately doesn't work for security. The fact that the key travelled unsecured means that the lock is now compromised, because the key may have been copied (You have to assume that THEY are REALLY out to get you when it comes to security. They can intercept both packages).
It must involve multiple sendings of the box back and forth, usually locked with multiple locks. Eventually, one key has to make it across secured. This probably involves the secure key being in the friend's posession in the locked box one or more times, even though he couldn't get access to it, not having the right keys for the locks.
It seems kind of like the tower of Hanoi problem, possibly....
Still thinking...... 
-- jmlyle
|
|
IP Logged |
|
|
|
jmlyle
Newbie
Gender:
Posts: 31
|
|
Re: ghetto encryption 1
« Reply #6 on: Jul 26th, 2002, 1:09pm » |
Quote Modify
|
Nevermind. It's not possible with just the elements included. The friend has to have his own key and lock which is uncompromised.
I send "valuable object" in box with one lock.
He sends the box back with both my lock and his lock.
I unlock my lock and send it back.
He unlocks his lock and opens the box.
I had been thinking that this was similar to Kerberos, in which the assumption is that nothing can be trusted. But the way that Kerberos gets around it (as I understand it) is not possible here.
Or maybe the locks and keys are quantum material. Then, at least, if the key is looked at en route, it won't work when put in the lock.... 
-- jmlyle
|
|
IP Logged |
|
|
|
Nathan J. Yoder
Guest
|
Quote:| just dont think this works with encryption where you scramble the contents then unscramble them in the same order... |
|
Some forms of encryption allow you to decrypt out of order.
|
|
IP Logged |
|
|
|
Gor
Guest
|
I think the easiest solution (send box first, then key) is the best one. If you assume your friend has a lock anyway, that way would work (he sends box with his lock then key). Also, with the original method, you assume that you can add a lock to a locked box. If the lock is mounted inside the box (much more secure), that would not be possible. Furthermore, if you assume your friend has a lock and that you can lock it without a key (very common), there is a slightly quicker solution: have him send the lock to you, you put stuff into the box, lock it with his lock, send it back.
|
|
IP Logged |
|
|
|
Rhaokarr
Guest
|
Or, assuming your friend has a lock:
You send the locked box to a friend.
Friend receives it, calls and says 'Right-o, I've got the box'
Friend locks the box with his lock as well.
You send the key. If the key is copied in transit, it doesn't matter, because now the box has a second, uncompromised lock.
This solution might also save a touch on postage, since it's likely to be cheaper to post a key than have your friend post the lock.
A second solution, that only requires one padlock:
You lock the box, send it to friend.
Melt down the key.
Friend opens padlock with boltcutters.
Eve, waiting for key to come through, doesn't realise that brute force has been used to open the box.
Of course, if we're talking padlocks (which it seems to be), these aren't too hard to pick, anyway...
|
|
IP Logged |
|
|
|
Ion Rush
Guest
|
I too thought put stuff in, lock it, mail box. after you confirm friend has box, send key.
however, it has been brough up that the key in transit could be copied, making it unsecure.
modified soluton, Through stuff in box. throw second lock and matching key in box. Mail box. After confirmation, mail the key. Assume key has been copied, so open box, remove external lock and dispose of it, then replace the old external lock with the second lock.
|
|
IP Logged |
|
|
|
jmlyle
Newbie
Gender:
Posts: 31
|
|
Re: ghetto encryption 1
« Reply #11 on: Jul 27th, 2002, 5:11am » |
Quote Modify
|
I finally see the beauty of the "send locked box, then send the key" solution.
I was wrapped up in computer communications, like Misha said. I assumed that anything sent through a public medium could be copied, but that's just dim-witted of me.
As a kind of pennence, here is a thought about continued secure communication in this situation:
1> I send the box, locked with Lock1. Inside the box is a "secret thing," Lock2 and Key3.
2> Later. I send Key1 to my friend. He can open the box.
3> He can then send me something in the box, locked with Lock2.
4> I can open it with Key2, which is uncompromised.
5> I can send something back, locked with Lock3, which is uncomprimised.
At this point, we have achieved repeted secured communications. We could continue this for a long time, if I start with a lot of locks and send half of them, and keys for the other half, locked in the first shipment.
That makes me feel better. I wouldn't be suprised if it was possible to have permanent ongoing secure communications, without needing an infinite number of locks, though. Trading locks and keys back and forth in the locked box (but never using Lock1 again). I am too weary to go any further in that direction right now, however....
-- jmlyle
|
|
IP Logged |
|
|
|
Harper
Guest
|
Another variation on "my friend has a lock".
1) Call friend, have her send her open lock.
2) Put stuff in box. To make later transport easier, chuck in a copy of my key. Close with her lock.
|
|
IP Logged |
|
|
|
Misha Kruk
Guest
|
|
Re: ghetto encryption 1
« Reply #13 on: Jul 28th, 2002, 10:08pm » |
Quote Modify
 Remove
|
OK, here is another view of this problem which I find funny:
send n keys (problem doesn't say how many keys and locks you have, so assume we have infinite ammount) to the recipient. Then take one of the n locks you have (truly random, use a good source of entropy) and send the box locked by this lock. Then send your friend a regular letter saying which of the keys she should use.
Yes, the adversary will have all the keys, but we she have time to copy them all? Will she have time to try them all? If we make n sufficiently large, this scheme becomes cryptographically strong 
It's even better than number factorisation for example, because with number factorisation if you are dealing with a government or some rich corporation you may face a lot of computational power, and however many people your adersary hires, they won't try more than one key in five secons!
|
|
IP Logged |
|
|
|
KC1Man
Guest
|
This problem is impossible to solve completely.
Some answers made the assumption that your friend has a lock. So you send the secret (X) to your friend locked with lock A LA().
LA(X) -> Friend.
Your friend then locks the box with lock B and sends it back to you:
LALB(X) -> You
Then you unlock lock A and send it back to your friend.
LB(X) -> Friend.
Your friend unlocks his own lock and gets the secret X.
The problem with this solution (and the "Have your friend send you his own lock beforehand" solution) is that the adversary who "could copy the key en route" could just as easily have added his own lock to the box making you think your friend has sent you the box with the second lock. As soon as you unlock your lock and send it back to your friend, the same adversary could intercept the package and unlock his box.
You have to assume that your adversary has access to the box, otherwise you would not need to worry about locking the box in the first place. Also, you cannot rely on the fact that your friend tells you he has the box because your adversary could send a replica box that is indistinguishable from your box to your friend, causing your friend to tell you that he has received your box (when in fact the adversary has the box which he is about to send back to you with his own lock on it!!!).
The second solution is to send the box first locked with a lock, have your friend tell you he got the box, and then send the key. People have commented that this would work because the box cannot be copied (with the contents) like digital content can. However, the adversary could still hold on to your original box, making an identical replica of it sans secret contents, tricking your friend into believing that he has receive the box. Then when you send your key, the adversary will just open his original box.
Another solution that was kind of nice is the "lock with one lock and send an inifinite number of keys to the friend". Later, tell your friend which key to use. Many problems here.
1. Infinite number of keys weight a lot. I assume you meant a great number of keys which could not be copied easily
2. The puzzle does not say that there is a certain amount of time in which the box has to be delivered. The adversary could copy all your keys (great number of them even, it could take years!!!)
3. Even if your friend was expecting the box in a certain amount of time, and your adversary only had time to copy 10 of the many, many keys, as soon as you tell your friend which key to use, the adversary could intercept that message as well. There is a chance that one of the 10 keys that your adversary has opens the box. If he just copied 10 of the keys, made a replica of the box and the locks, and sent the original keys and the replica of the box to your friend, there is still a chance (small, but real) that he could access the contents. The puzzle states "How can you send the object securely?" which is absolute statement. It does not say "How can you send the object almost securely". However, given a large enough number or keys, this is the best solution, IMHO.
|
|
IP Logged |
|
|
|
Brion
Guest
|
Here's yet another way (and very close variation to a previous answer). This method does not assume your friend has a lock, nor does it require sending an infinite amount of keys.
Assume you have two locks and two keys (more locks and keys work just as well). We'll call them keys A and B (with corresponding locks).
1. Lock key B inside the box with lock A
2. Send the box to your friend
3. Send the key separately to your friend (assume the key is intercepted and copied at this point, but sent on to cover the interception)
4. Your friend unlocks the box and removes key B
5. Your friend sends you back an unlocked, empty box
6. You place your item in the box, and lock it with lock B
7. Send the locked box (B) to your friend
8. Your friend can now open the locked box with key B
While this exposes key A to intruders, it is not used after the initial send, so a copy becomes useless anyway. Alternately, you could send a bunch of keys, have your friend choose one and find the missing key on the unlocked box's return. If an intruder took one of the keys you have evidence of tampering and can try again - but this exposes a lot of keys and is a waste of money. 
Cheers!
Brion
|
|
IP Logged |
|
|
|
mook
Newbie
Gender:
Posts: 15
|
|
Re: ghetto encryption 1
« Reply #16 on: Aug 3rd, 2002, 9:40am » |
Quote Modify
|
on Jul 30th, 2002, 3:33pm, Brion wrote:Here's yet another way (and very close variation to a previous answer). This method does not assume your friend has a lock, nor does it require sending an infinite amount of keys.
Assume you have two locks and two keys (more locks and keys work just as well). We'll call them keys A and B (with corresponding locks).
1. Lock key B inside the box with lock A
2. Send the box to your friend
3. Send the key separately to your friend (assume the key is intercepted and copied at this point, but sent on to cover the interception)
4. Your friend unlocks the box and removes key B
5. Your friend sends you back an unlocked, empty box
6. You place your item in the box, and lock it with lock B
7. Send the locked box (B) to your friend
8. Your friend can now open the locked box with key B
While this exposes key A to intruders, it is not used after the initial send, so a copy becomes useless anyway. Alternately, you could send a bunch of keys, have your friend choose one and find the missing key on the unlocked box's return. If an intruder took one of the keys you have evidence of tampering and can try again - but this exposes a lot of keys and is a waste of money.
Cheers!
Brion |
|
can't think of anything more secure than that. anyone got a way without compromising any keys?
|
|
IP Logged |
|
|
|
HammerSandwich
Newbie
Posts: 8
|
|
Re: ghetto encryption 1
« Reply #17 on: Aug 6th, 2002, 12:03pm » |
Quote Modify
|
Keys are K1...Kn, locks L1...Ln.
1) I put K1 in box, lock with L2, send.
2) Friend acknowledges receipt.
3) I send K2 in the open.
4) Friend removes K1 and returns empty box.
5) I send secret, secured with L1.
The only problem I see is if K2 is stolen. In that case, my friend will return the box still locked with L2, which I (having a copy of all my keys) will replace with L3. Then we start at the top.
|
|
IP Logged |
|
|
|
James
Guest
|
 |
Re: ghetto encryption 1
« Reply #18 on: Aug 17th, 2002, 12:56am » |
Quote Modify
Remove
|
The last couple of solutions are close but still not perfect. We need to consider the possibility that the attacker can intercept all packages from you to your friend and then substitute those package with fakes so neither you nor your friend knows that there is a man in the middle. Here is how an attacker can do it.
1. you sent your friend a box with a key1 inside and lock it with lock2
2. attacker intercepts and keeps your box and sent your friend a fake locked box with an arbitrary key inside.
3. you sent your friend key2
4. attacker intercepts and keeps your key2 and sent your friend a different key that can be used to unlock the fake box. the attacker opens your box with key2 and takes key1
5. your friend sent back the fake box to you.
6. the attacker again intercepts and take back the fake box and sent you the real box
7. you sent the cargo lock inside the real box and lock it with lock1 to your friend
8. the attacker intercepts the box and opens the box with key1 from step 4.
We need a way for you and your friend to know for sure key1 really made it to your friend and is from you. One possibility would be to include a written secret message in the lock box along with key1 in step1. When your friend gets the box and key2 to open the box in subsequent steps, he should first call you back on the phone and read the message inside the box back to you. Now you know for sure key1 really did reach your friend safely. You friend also now knows the box and it's content is from you. There is no way for the attacker in step2 to put your message inside the fake box and sent it to your friend since at that moment you haven't sent the key to open the box yet. Only after this checks out do you sent the cargo locked with lock1 to your friend.
Note: this makes the assumption that the attacker cannot fake your friend's voice. If we want to avoid even this dependancy, you can ask your friend to tell you about a piece of knowledge that only you and your friend knows and the attacker is unlikely to know (i.e. how you guys first met, etc.).
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: ghetto encryption 1
« Reply #19 on: Aug 17th, 2002, 2:07pm » |
Quote Modify
|
James, I like your solution, but if we really want perfect security, like Potassium Chloride Man wants. If the intercepter is able to make a lucky guess about which key(s) to copy, then he can also make a lucky guess about what your secret message is.
However, I don't think that "perfect security" is a reasonable interpretation of "secure". I would define "secure" to mean that the effort required to break a scheme is worth more than the reward of breaking it. Nobody's going to expend a thousand dollars worth of effort to intercept a ten dollar bill, and the "secret message" method (or, for that matter, the "million keys method" proposed by Misha Kruk) can be made as secure as you like.
|
|
IP Logged |
|
|
|
James
Guest
|
Chronos,
Adding a secret message adds absolutely no additional cost to the solution. Just pick a random string, or for that matter use sshk-keygen, print it and include it into the box. The attacker has only one chance to guess it (no retry here) and there are gazillion possible string combination for him to choose from. There is no infinite key weighting an infinite amount problem here.
Secondly, it is the base assumption of the riddle that it is not difficult to intercept the key in transit and make copies or it. If you can intercept the key in transit why no all the parcels sent between you and your friend. By the way, even in real life, it is not too difficult to execute a man in the middle attack. For the small effort of including a random message, the major man in the middle security hole is plugged.
On a more fundamental level, man in the middle attack is a classic challenge that any security protocol worth it's muster must address.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: ghetto encryption 1
« Reply #21 on: Aug 18th, 2002, 12:33am » |
Quote Modify
|
The trick about asking personal information actually doesn't work as presented. The attacker just has to perform a man-in-the-middle on the phone conversation, simulating you to your friend and your friend to you.
|
|
IP Logged |
|
|
|
James
Guest
|
Alex, you are right. Related, another issue with many solutions so far is the assumption that there is another communication channel (using the phone) that the problem itself did not provide for. What if you and your friend are in a 3rd world country with no phone service?
This is getting complicated. Hahaha. However, the problem is still solvable if we allow for some shared secret information that only you and your friend knows from the start.
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: ghetto encryption 1
« Reply #23 on: Aug 20th, 2002, 4:16pm » |
Quote Modify
|
I'm not saying that the secret message adds to your cost to send the message, I'm saying that it decreases your enemy's expected return. He can still break the security, but he has only a very small chance of succeeding. The secret message method does not satisfy KClman's requirement of perfect security, because there is that miniscule chance of your enemy guessing correctly. In fact, I would venture to say that nothing could satisfy the requirement of perfect security, in any context. The secret message method does, however, satisfy the requirement of "good enough" security. The many-keys solution also satisfies this requirement, if you use enough keys, but it's probably more difficult to implement (who wants to pay the postage on several tons of keys?).
|
|
IP Logged |
|
|
|
Sycle
Newbie
Posts: 1
|
|
Re: ghetto encryption 1
« Reply #24 on: Aug 23rd, 2002, 5:10am » |
Quote Modify
|
I don' think I agree, if done correctly I think the secret message *does* satisfy the requirement for perfect security, at least as far as anything can.
The secret message is a secret key (software crypto sense) and if 'perfect security' is violated because the attacker might possibly be able to guess it first go, then why don't we assume that any lock you use is intrinsically insecure because maybe the attacker will just pick up a random piece of metal that happens to unlock it? All encryption schemes the world has ever known fall down in the face of the attacker getting 'lucky'.
It really depends on the constraints of the question and how your friend can transmit the secret message back to you (perhaps you're in adjacent apartments, and can shout information to each other meaning you have a verified but non private channel of communication -or- perhaps you have to commutate by phone and the attacker has sophisticated voice imitation technology and there are no trustworthy ways of talking to each other)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print