Originally posted by CribsYes, imagine that the two persons are on different continents and must use the postal system to send the box. The box cannot be sent without being securely locked. The keys cannot be transferred to the other person in any way, shape or form. There is no language-usage trick to this question. You are simply expected to adhere to the constraints. Do not assume anything further constraints.
Well, there is the degenerate solution that you just
physically hand the valuable item to your friend.
That meets all of the constraints, unless your notion
of "send" disallows this. If that is that case then you
should also not be able to physically hand over locks
and keys, and I maintain that your new problem has
no solution.
Dr. Cribs
-Ray.
Originally posted by rgoudieThen it can't be done. I'll work on a proof and post it here.
Yes, imagine that the two persons are on different continents and must use the postal system to send the box. The box cannot be sent without being securely locked. The keys cannot be transferred to the other person in any way, shape or form. There is no language-usage trick to this question. You are simply expected to adhere to the constraints. Do not assume anything further constraints.
-Ray.
Dr. Cribs
Problem:
Transfer an object securely to another party, possibly
making use of a locakable box, some lock/key pairs that
you posess, and some lock/key pairs that the other
party posesses.
Constraints:
No keys may be transfered.
No open locks may be transfered.
Assumption:
If the object is transfered in any manner other than in
a locked box, the transmission is insecure. (rgoudie,
if this assumption is invalid, please clarify the
definition of "secure".)
I claim that there is no valid solution to the problem.
Proof by Contradiction:
Suppose that the second party has securely received
the object for the first time.
Because the transmission was secure, it must be true
that it arrived in a locked box. Further it must be
true that the second party had a key to open that lock.
Now consider two cases: who put that lock on the box?
1) If it was the second party, then the second party must
have already had access to the object, but this contradicts
our supposition, so this case cannot be correct.
2) If it was the first party, then the lock would have had
to be open when in the posession of the first party, in order
to put in on the box. But if the lock was open in the first
party's posession, we must consider two sub-cases:
2a) The lock was unlocked by the first party. This case
cannot be correct because he would have had to have the key,
but key transfer is prohibited by the constraints.
2b) The lock was unlocked by the second party. This case
cannot be correct because the transfer of open locks is
prohibited by the constraints.
All cases that could have lead to the suppostion have been
shown to be impossible. Therefore, the supposition must be false.
The conclusion of this proof is that either the second party
had the object all along, or
There is no valid solution to the problem.
QED.
Let me address some points in your previous posting:
Transfer an object securely to another party, possibly making use of a locakable box
Not "possibly". For the purposes of this problem, the object must absolutely be sent inside the box which must be locked.
Assumption:
If the object is transfered in any manner other than in a locked box, the transmission is insecure. (rgoudie, if this assumption is invalid, please clarify the definition of "secure".)
This is correct. The transfer is considered secure if, and only if, the object is inside the locked box.
Now consider two cases: who put that lock on the box?
If it was the second party, then the second party must have already had access to the object, but this contradicts our supposition, so this case cannot be correct.
What supposition is that? Could this be the weak spot in your logic? 😉
-Ray.
Originally posted by rgoudieThis is the suppostion: "Suppose that the second party has securely received
What supposition is that? Could this be the weak spot in your logic? 😉
the object for the first time."
To elaborate on the contradiction, if the second party was the
one that put the lock on the box, then just prior to that, he
had access to the object. Then he locked it, and then unlocking
it again would make it his second access. The suppostion of the
proof is that we are considering his first access only.
There is no weak spot in my logic. The proof is sound.
If you don't agree with the conclusion, then you must
clarify the Problem as I have stated it.
Let me restate the problem and constraints:
The object of the problem is to transfer (say, via the postal system) an object to the recipient using a box that has a locking ring that is more than large enough to accomodate a lock. The box is large enough to contain the object. The object must be placed inside the locked box before it may be sent through the mail. Both parties possess a lock and key. Each party's key obviously opens their own lock, but will not open the other party's lock. No keys may be transferred to the other party in any manner whatsoever.
Given these constraints, it is possible to transfer the object to the other person.
Forget about any previous declarations. the wording in this posting more accurately reflects the situation. As long as the constraints implied by the language used above are met, anything else goes!
-Ray.
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by CribsYou put the item in the box, and you lock it with your key
Problem:
There is no valid solution to the problem.
QED.
And the padlock that you have, and you send it oversea
Your good friend now has the box, that he cannot yet unpack
He puts HIS padlock on it, and he promptly sends it back
You take your padlock off it, and resend it oversea
When your friend receives the box, he unlocks it - QED!
Originally posted by iamatigerExcellent, iamatiger!
You put the item in the box and lock it with your key
To the padlock that you bought and you send it oversea
Your friend he takes the box, that he cannot yet unpack
He puts his padlock on it and returns it back
You take your padlock o ...[text shortened]... it oversea
When your friend recieves the box he unlocks it, QED!
Cribs, I admire your tenacity. You didn;t give up for one second.
-Ray.
Originally posted by iamatigerWell done. I was obviously working under the
You put the item in the box, and lock it with your key
And the padlock that you have, and you send it oversea
Your friend he takes the box, that he cannot yet unpack
He puts HIS padlock on it, and then returns it back
You take your padlock off, and resend it oversea
When your friend receives the box, he unlocks it, QED!
assumption that the box could accommodate
one lock but no more.
Cribs
As a follow up question, can anybody point out why
this definition of "secure" is lacking? Not physically,
but logically. I'm not talking about smashing the box
with a hammer, but you may consider malicious third parties...
I'm also talking in the real world now, outside the context
of this problem.
BBarr's solution, which was what I originally had in mind
before the extra constraints were added, hints at it.
Dr. Cribs
One more follow up question, this time in the
context of the original problem without extra
constraints.
Can you name one advantage, with respect to
security, that bbarr's solution has over the final
agreed-upon solution? The definition of secure
is what I am getting at with this question. In other
words, construct a scenario in which bbarr's solution
provides an extra layer of security that the final
solution lacks.
Dr. Cribs
- Joined
- 26 Apr 03
- Moves
- 26771
Originally posted by CribsI can nick the knicknack
As a follow up question, can anybody point out why
this definition of "secure" is lacking? Not physically,
but logically. I'm not talking about smashing the box
with a hammer, but you may consider malicious third parties...
I'm also talking in the real world now, outside the context
of this problem.
BBarr's solution, which was what I originally had in mind
before the extra constraints were added, hints at it.
Dr. Cribs
If I intercept the box
And then I send it back
Tightly locked with my own locks
You will remove your locks
(That I'm your friend believing)
When you return the box
I procede with my thieving.
Originally posted by iamatigerExcellent. The proposed definition of security
I can nick the knicknack
If I intercept the box
And then I send it back
Tightly locked with my own locks
You will remove your locks
(That I'm your friend believing)
When you return the box
I procede with my thieving.
doesn't address authentication.
How about my second follow-up question?
I see four distinct advantages, in addition to
better addressing authentication, of bbarr's
solution.
Dr. Cribs
Originally posted by CribsEven in bbarr's proposed solution, there must be a way to authenticate the lock when it is received to be sure that it is the exact same lock sent by the other party. Someone may inmtercept the parcel with the lock and substitute their own lock.
Excellent. The proposed definition of security
doesn't address authentication.
How about my second follow-up question?
I see four distinct advantages, in addition to
better addressing authentication, of bbarr's
solution.
Dr. Cribs
-Ray.
Originally posted by rgoudieThis attack requires two interceptions, one on the
Even in bbarr's proposed solution, there must be a way to authenticate the lock when it is received to be sure that it is the exact same lock sent by the other party. Someone may inmtercept the parcel with the lock and substitute their own lock.
-Ray.
transmission of the open lock, and one again of the
locked box.
Bbarr's solution better addresses authentication (although
not perfectly) because he can authenticate (via whetever means,
such as a telephone communication of the lock's serial number)
before the object leaves his hands. In your solution, authentication
cannot be done until the object is transmitted, which may be
too late if the enemy already has his lock on it.
This is one of the four points that I was getting at
in my second follow-up question. The final solution requires
that the valuable object be transmitted 3 times, whereas
in bbarr's solution, it's only out of your hands once. The fewer
transmissions that occur, the fewer options and opportunities
for attack exist for the enemy.
Consider the attack where the enemy just wants to destroy
the object. You are giving him three chances instead of one.
So, in addition to this one, I still see three other distinct
advantages to bbarr's method. Do you know them?
Dr. Cribs