Commutative lock solution

This is a solution to problem 15 on the hard interview questions node. It's a simple one. Alice puts medicine in chest, puts her padlock on chest, locks her padlock. Eve sends chest to Bob. Bob puts his padlock on the chest and locks it. Eve sends chest to Alice. Alice unlocks her padlock and keeps it. Eve sends chest to Bob. Bob unlocks his padlock and opens chest.

Just want to make a comment on Zaratustra's solution.

Let's consider a real-world application of the above "cryptography" algorithm. This algorithm only works if our encryption function is commutative, i.e., encrypting with lock A then lock B gives you the same result as encrypting with lock B then lock A. So what encryption algorithms are like that in the real world? The one time pad (maybe others, but let's consider this one for now). The problem with the one time pad is that both parties need a copy of the pad for this simple kind of encryption to work.

But in our example, Alice doesn't need Bob's key, and vice versa, to outsmart Eve. So how come we can't employ their algorithm for use with the one time pad? Well, this is too easy for Eve to break. Let's say Alice has a message M, and generates some random bits A, and sends (A xor M) over to Bob, who has his own random bits B, and sends back (B xor (A xor M)) , which is the same as (A xor (B xor M)). Alice then sends (A xor (A xor (B xor M))), which is the same as (B xor M), since (A xor A) = 0. Bob receives (B xor M), from which he can easily get M.

So what can Eve do? First of all, she sees all the intermediate messages, in particular, (A xor M) and (B xor (A xor M)). She can just xor these two together to get B, then in the last step, when Alice sends over (B xor M), Eve can just use B to get M.

Furthermore, Eve can just generate her own set of bits E, and instead of actually giving the message to Bob in the first step, she just sends back (E xor (A xor M)), and continues the algorithm as if she were Bob. Alice is none the wiser, and in the end Eve is able to get M. This is called a "man in the middle" attack. There are ways around such an attack, though, but that is beyond the scope of this writeup.

(Continuing the 'real-world' application of this)
 
Assuming Eve only wants to steal 'useful' items, or assuming you can generate an infinite number of padlocks (which you can on a computer), you could just let Bob send Alice his unlocked padlock, then Alice locks the medicine in the chest. Of course, this has the slight problem, where Alice could swap the padlock for one of her own.
 
In the real world, that basically means, you can give everyone a copy of your RSA public key (padlock), because it's only useful for encrypting (locking) things, you need the private key (the key) to decrypt (unlock) it -- however you need to be sure you have the correct padlock, lest you be tricked into encrypting something to some evil third party.