Of the many difficult problems dealing with public key cryptography, there are few so hard to crack as public key authentication. Public keys are easy to obtain (that’s why they are “public”), and because of this, it is hard to be sure that a certain key belongs to a certain person, what is known as authentication. Usually it is recommended that the key be handed out in person or that it be identified (directly or through a one-way hash) by a rich communication medium such as voice or video.
But sometimes it might be possible to do it strictly by email, even though you suspect someone might be watching. Read on for details.
If you cannot make contact with the other person through a rich channel such as voice or video, you’re going to have to start using somebody’s public key without knowing for sure if that public key is genuine. Trust will build up gradually, as the messages sent back and forth serve to confirm the identity of the participants. But there are ways to discover if a public key is fake with only a few messages traveling back and forth.
The easiest thing to do is to send a message to the public key owner, including a question whose answer only the two of you know, and asking him/her to send you his/her public key, encrypted with a symmetric key that is the answer to that question. If the answer is correct, you’ll be able to decrypt the message, and thus retrieve the genuine public key (which should match the one you have). An interloper who is watching and perhaps modifying your traffic won’t be able to decrypt the message in order to change it, and thus he/she must be content with preventing you from getting that message, in which case you’ll know the public key in your possession have is fake.
But the easy way has the problem that the other person’s answer must be exactly the answer I know, down to the smallest spelling detail, or the message won’t decrypt. There is another way to authenticate a public key using a variation on the “interlock protocol,” which admits answers that don’t have to be exact. It is enough if the persons asking the questions can recognize the answers as valid in a more general sense.
This protocol is based on the “interlock protocol,” first described by Rivest and Shamir in this paper. In essence, people encrypt messages but only send half, and wait to get the other person’s first half of a reply before sending out the second half. This causes a “man in the middle” a big headache because, since he cannot decrypt half an encrypted message, he needs to make up messages to keep the exchange going, or his cover is blown. Unfortunately, it has been shown that this protocol can be defeated by a particularly clever interloper, using this method. Does that mean that the interlock protocol is no good? Far from it. What’s needed is extra cleverness in the way it is set up. As a clever user says in this posting, the key lies in asking questions that require an answer.
So here ‘s the way you can set up a slightly modified interlock protocol in order to authenticate a public key. Since the following is extracted from the manual for PassLok, which uses non-standard nomenclature for the sake of novice users, let’s get that out of the way first. In PassLok, a public key is called a Lock, and a private key a Key. A digital signature is a Stamp, and a one-way hash is an ID. Encrypting is referred to as “locking” and decrypting as “unlocking”.
With that clarified, let’s look at this exchange between Alice and Bob:
1. Alice obtains her friend Bob’s Lock, but she fears that it might be counterfeit and someone else might be unlocking the messages she sends to Bob, reading them, perhaps changing them, and then re-locking them with Bob’s actual Lock for him to read. So Alice sends Bob this email:
“Dear Bob. I just got your Lock for the app called PassLok from your email signature. I fear that I’m under surveillance, so it’s very important that I make sure that this Lock actually belongs to you. Here’s what I want you to do:
a. Write a question whose answer only the two of us know, and lock it with my Lock, which is included at the bottom of this email. Then split it in two parts and send me the first part. I’ll be waiting for it.
b. When I get it, I’ll send you the first half of a similar question, which has been locked with your Lock. When you get it, send me the second half of your locked question.
c. When I get that, I’ll send you the second half of my question, and also the answer to yours, which then I’ll be able to read. I’ll send the answer locked with your Lock.
d. If I answered your question correctly, put together the two halves of my question and unlock it. Then write the answer, lock it with my Lock, and send it back to me. Then I’ll know that your Lock is authentic. Your friend, Alice.”
2. When Bob gets this, he decides it’s going to be fun to do all his, and writes a question whose answer only Alice knows, locks it with her Lock, which was appended to her email, splits the locked message into two parts, and sends Alice the first half.
3. Alice gets the first half, and writes her question to Bob. Then she locks it with Bob’s presumed Lock, but only sends him the first half. Because nobody can unlock half a message, she must wait to get the second half of Bob’s message in order to answer his question.
4. Bob gets the first half of Alice’s locked question, and he sends her the second half of his locked question.
5. Alice gets the second half of Bob’s question. Now she can put the two halves together and unlock them with her Key. She writes a message answering Bob’s question, locks it with Bob’s presumed Lock (no need to split it now), and sends it back to him along with the second half of her question to Bob.
6. Bob gets Alice’s email and can now unlock both messages from her. He sees the correct answer to his question in the first one, so he unlocks the one containing Alice’s question. He writes the answer, locks it with Alice’s Lock, and sends it to her. Had he been unable to unlock Alice’s question, he would have told her so. If her answer to his question was wrong, he would have told her, too.
7. Alice gets Bob’s message, unlocks it and, seeing the correct answer to her question, is satisfied that Bob’s Lock is authentic. Otherwise she gets a message from Bob telling her that things didn’t work out, or something other than a message answering her question, or nothing at all, and she decides that “Bob’s Lock” was bad.
An alternative to splitting locked messages is to make the ID of the locked or unlocked message and send it ahead of the message itself, or apply a Stamp to the message and send the Stamp ahead of the message. The recipient will then check the ID or Stamp after the message is received, and will know that something’s wrong if it is not the same. Another option is not to lock the answers to the questions, in steps 5 and 6, since authentication also works if those messages are not locked; locking just preserves those answers, which might be sensitive, from a less-than-powerful eavesdropper who might see the exchange.
If Alice does not know Bob well enough to be able to ask him a question whose answer is known only to the two of them, or maybe Bob doesn’t know Alice well enough to ask a similar question, there is still something they can do, so long as Alice can recognize Bob in some way, and Bob can recognize Alice. Instead of a personal question, the asker can direct the other person to simply repeat something contained in the “question” message, but to do so in a video or audio recording, which is then put somewhere in the cloud, and the URL is sent back as an answer. The asker will then see or hear the other person, whom he/she recognizes, saying something that she/he would not be saying unless she/he has read the question message.
Let’s see how this protocol foils Mallory, who is able to intercept and modify their communications without them knowing anything. He poses as Alice before Bob, and as Bob before Alice. In this case, Alice does not have Bob’s genuine Lock, but one that Mallory made in order to impersonate Bob. Likewise, Bob does not get the Lock that Alice sent in step 1, but one for which Mallory has the Key.
Things begin to go wrong for Mallory in step 3. Since Mallory cannot yet read Alice’s question but nevertheless has to send something to Bob to keep the exchange going, he must send him a question from “Alice” that likely has nothing to do with the question the real Alice has asked. That, or pretend in step 2 that Bob is refusing to go along with the game, which is not going to do much to reassure Alice.
Mallory will then get the whole question from Bob, so he will be able to unlock it, re-lock it, and pass it along to Alice in step 4, and then get from her a reply that will satisfy Bob in step 6. But the damage has been done. Mallory is committed to sending Bob the second half of a question from “Alice” that is most likely not the question the real Alice asked, or otherwise Bob won’t be able to unlock the message, and Mallory’s cover will be blown. Bob might not discover the ruse at this point, but it is highly unlikely that his answer, or whatever else Mallory can come up with to replace it, will satisfy the real Alice’s question. Then she’ll know someone’s in-between and Bob’s Lock is not authentic.
If now they repeat steps 2 to 6 all over with one new question from either side, but this time with Alice asking the first question, Bob will also notice that something is wrong. But what if there is no Mallory, and “Bob’s Lock” was not being used to listen in but was simply corrupted or mistaken for another Bob’s Lock? Then Bob will simply be unable to unlock Alice’s question in step 6, and he will alert her of that fact. It is possible that a Mallory could still be watching without attempting to modify the messages passing through him unless he really has to, but it is unlikely that he could replace Bob’s announcement that the protocol failed with something that would satisfy Alice, because at that stage Alice won’t accept anything but a correct answer to her question, or she will decide that “Bob’s Lock” is bad.
It took some homework and three emails from each side, after which they still don’t know each other’s authentic Lock (which would be impossible with Mallory changing everything, anyway), but Alice has avoided being duped by an enemy.