CVS revision: $Id: defense_against_middleperson_attacks.html,v 1.12 2003/10/27 23:20:05 zooko Exp zooko $
Goals
Possible other goals:
Possible Outline:
1. Introduce setting, problem. 2. Describe solution. 3. Discuss constraints imposed by solution. 4. Related work/no unconstraining solution. 5. Open questions: what are the limits of constraints?
a.k.a. mafia fraud, man-in-the-middle, middleperson. insert many citations here.
Alice wants to play a game of chess. She is concerned that someone might run the Chess Grandmaster attack, using her chess skills without her knowledge or consent, and taking the credit if she wins. Bob is in the same position.
Alice and Bob do not have any knowledge of each other. They share no secrets, they share no authenticated public key information, each is unaware of the other's identity and even of the other's existence.
Alice is ready to choose the first move in the chess game. She decides what her move is, then generates a message containing her move m1, her public key PKa, and a random nonce n1. Collectively, we'll call this message M1. She takes a cryptographic hash of M1, which we'll call "commitment one": C1 = hash(M1). Alice sends C1.
Now here's the part that's somewhat unusual in cryptographic protocols: Alice sits on her hands and waits for K seconds.
After K seconds have passed (as measured by Alice's local clock, which we assume runs roughly at the same speed as Bob's local clock), then Alice signs M1 using her private key and sends the signed message: {M1}_sig(PKa).
Bob receives C1. He then sits on his hands and waits for K seconds.
After Bob receives M1, and after his K-second timeout elapses (whether or not M1 arrived before or after the timeout elapsed), Bob proceeds.
He verifies Alice's digital signature, using the public key included in M1. He verifies that C1 = hash(M1). Then he makes his chess move in response to Alice's chess move. He generates a message containing his move m2, his public key PKb, Alice's public key PKa, Alice's original message M1, and a random nonce n2. We'll call this five-tuple M2. He then signs M2 with his private key, and in addition he encrypts it with Alice's public key. He sends the resulting signed, encrypted message: {{M2}_sig(PKb)}_enc(PKa).
When Alice receives this message, she first checks how much time has passed since she sent M1. If more than K seconds have passed, then she rejects the message on the grounds that she isn't sure that it wasn't generated by a pseudo-Chess-Grandmaster in the middle. The protocol (and the chess game) must now come to an ungraceful and irrecoverable end.
If Alice received M2 less than K seconds after she sent M1, then Alice proceeds.
Alice decrypts M2 and verifies Bob's digital signature using his public key as included in the message, and verifies that her public key as included in the message is correct.
Now, Alice knows the following things:
1. The person who knows the private key which matches public key PKb is also the person who originally chose chess move m2. Any pseudo-Chess-Grandmaster who attempted to substitute his public key for the real Bob's public key would not have been able to send the message in time.
2. The person who knows the private key which matches public key PKb signed message M2, so he knew the correct Alice public key PKa and he knew Alice's original chess move m1.
3. Since message M2 was encrypted with Alice's real public key PKa, it was not possible for anyone to read the contents of M2 (without breaking the public key encryption scheme) unless they are the person who chose chess move m2. (Careful here -- the message M2 that was received by Alice was created by the person who chose the actual chess move m2, but it is possible that there is another person who chose a different chess move in response to Alice's m1, and it is possible that that chess move was readable to the Man in the Middle. One way to put this is that if the message arrives in time Alice has gained assurance about the MITM-free-ness of the message M2 that she received, but not about her M1 nor about some possible message M2` that someone else might or might not have written. Another way to put it is that Bob doesn't get MITM-free-ness-assurance at all. This terrain really is rife with mental landmines, isn't it!)
stopped here...