It is foolish to encrypt arbitrary strings—not only those sent by untrusted third parties, but under any circumstances at all. Attacks similar to the one discussed in Section 19.3 can be mounted. Secure proof-of-identity protocols take the following, more complicated, form:

(1)  Alice performs a computation based on some random numbers and her private key and sends the result to the host.

(2)  The host sends Alice a different random number.

(3)  Alice makes some computation based on the random numbers (both the ones she generated and the one she received from the host) and her private key, and sends the result to the host.

(4)  The host does some computation on the various numbers received from Alice and her public key to verify that she knows her private key.

(5)  If she does, her identity is verified.

If Alice does not trust the host any more than the host trusts Alice, then Alice will require the host to prove its identity in the same manner.

Step (1) might seem unnecessary and confusing, but it is required to prevent attacks against the protocol. Sections 21.1 and 21.2 mathematically describe several algorithms and protocols for proving identity. See also [935].

Mutual Authentication Using the Interlock Protocol

Alice and Bob are two users who want to authenticate each other. Each of them has a password that the other knows: Alice has P_A and Bob has P_B. Here’s a protocol that will not work:

(1)  Alice and Bob trade public keys.

(2)  Alice encrypts P_A with Bob’s public key and sends it to him.

(3)  Bob encrypts P_B with Alice’s public key and sends it to her.

(4)  Alice decrypts what she received in step (2) and verifies that it is correct.

(5)  Bob decrypts what he received in step (3) and verifies that it is correct.

Mallory can launch a successful man-in-the-middle attack (see Section 3.1):

(1)  Alice and Bob trade public keys. Mallory intercepts both messages. He substitutes his public key for Bob’s and sends it to Alice. Then he substitutes his public key for Alice’s and sends it to Bob.

(2)  Alice encrypts P_A with “Bob’s” public key and sends it to him. Mallory intercepts the message, decrypts P_A with his private key, re-encrypts it with Bob’s public key and sends it on to him.

(3)  Bob encrypts P_B with “Alice’s” public key and sends it to her. Mallory intercepts the message, decrypts P_B with his private key, re-encrypts it with Alice’s public key, and sends it on to her.

(4)  Alice decrypts P_B and verifies that it is correct.

(5)  Bob decrypts P_A and verifies that it is correct.

Alice and Bob see nothing different. However, Mallory knows both P_A and P_B.

Donald Davies and Wyn Price describe how the interlock protocol (described in Section 3.1) can defeat this attack [435]. Steve Bellovin and Michael Merritt discuss ways to attack this protocol [110]. If Alice is a user and Bob is a host, Mallory can pretend to be Bob, complete the beginning steps of the protocol with Alice, and then drop the connection. True artistry demands Mallory do this by simulating line noise or network failure, but the final result is that Mallory has Alice’s password. He can then connect with Bob and complete the protocol, thus getting Bob’s password, too.

The protocol can be modified so that Bob gives his password before Alice, under the assumption that the user’s password is much more sensitive than the host’s password. This falls to a more complicated attack, also described in [110].

SKID

SKID2 and SKID3 are symmetric cryptography identification protocols developed for RACE’s RIPE project [1305] (See Section 25.7). They use a MAC (see Section 2.4) to provide security and both assume that both Alice and Bob share a secret key, K.

SKID2 allows Bob to prove his identity to Alice. Here’s the protocol:

(1)  Alice chooses a random number, R_A. (The RIPE document specifies a 64-bit number). She sends it to Bob.

(2)  Bob chooses a random number, R_B. (The RIPE document specifies a 64-bit number). He sends Alice:

R_B,H_K(R_A,RB,_B)

H_K is the MAC. (The RIPE document suggests the RIPE-MAC function—see Section 18.14.) B is Bob’s name.

(3)  Alice computes H_K(R_A,R_B,B) and compares it with what she received from Bob. If the results are identical, then Alice knows that she is communicating with Bob.

SKID3 provides mutual authentication between Alice and Bob. Steps (1) through (3) are identical to SKID2, and then the protocol proceeds with:

(4)  Alice sends Bob:

H_K(R_B,A)

A is Alice’s name.

(5)  Bob computes H_K(R_B,A), and compares it with what he received from Alice. If the results are identical, then Bob knows that he is communicating with Alice.

This protocol is not secure against a man-in-the-middle attack. In general, a man-in-the-middle attack can defeat any protocol that doesn’t involve a secret of some kind.

Message Authentication

When Bob receives a message from Alice, how does he know it is authentic? If Alice signed her message, this is easy. Alice’s digital signature is enough to convince anyone that the message is authentic.

Symmetric cryptography provides some authentication. When Bob receives a message from Alice encrypted in their shared key, he knows it is from Alice. No one else knows their key. However, Bob has no way of convincing a third party of this fact. Bob can’t show the message to Trent and convince him that it came from Alice. Trent can be convinced that the message came from either Alice or Bob (since no one else shared their secret key), but he has no way of knowing which one.

If the message is unencrypted, Alice could also use a MAC. This also convinces Bob that the message is authentic, but has the same problems as symmetric cryptography solutions.