Chapter 3
Basic Protocols

3.1 Key Exchange

A common cryptographic technique is to encrypt each individual conversation with a separate key. This is called a session key, because it is used for only one particular communications session. As discussed in Section 8.5, session keys are useful because they only exist for the duration of the communication. How this common session key gets into the hands of the conversants can be a complicated matter.

Key Exchange with Symmetric Cryptography

This protocol assumes that Alice and Bob, users on a network, each share a secret key with the Key Distribution Center (KDC) [1260]—Trent in our protocols. These keys must be in place before the start of the protocol. (The protocol ignores the very real problem of how to distribute these secret keys; just assume they are in place and Mallory has no idea what they are.)

(1)  Alice calls Trent and requests a session key to communicate with Bob.

(2)  Trent generates a random session key. He encrypts two copies of it: one in Alice’s key and the other in Bob’s key. Trent sends both copies to Alice.

(3)  Alice decrypts her copy of the session key.

(4)  Alice sends Bob his copy of the session key.

(5)  Bob decrypts his copy of the session key.

(6)  Both Alice and Bob use this session key to communicate securely.

This protocol relies on the absolute security of Trent, who is more likely to be a trusted computer program than a trusted individual. If Mallory corrupts Trent, the whole network is compromised. He has all of the secret keys that Trent shares with each of the users; he can read all past communications traffic that he has saved, and all future communications traffic. All he has to do is to tap the communications lines and listen to the encrypted message traffic.

The other problem with this system is that Trent is a potential bottleneck. He has to be involved in every key exchange. If Trent fails, that disrupts the entire system.

Key Exchange with Public-Key Cryptography

The basic hybrid cryptosystem was discussed in Section 2.5. Alice and Bob use public-key cryptography to agree on a session key, and use that session key to encrypt data. In some practical implementations, both Alice’s and Bob’s signed public keys will be available on a database. This makes the key-exchange protocol even easier, and Alice can send a secure message to Bob even if he has never heard of her:

(1)  Alice gets Bob’s public key from the KDC.

(2)  Alice generates a random session key, encrypts it using Bob’s public key, and sends it to Bob.

(3)  Bob then decrypts Alice’s message using his private key.

(4)  Both of them encrypt their communications using the same session key.

Man-in-the-Middle Attack

While Eve cannot do better than try to break the public-key algorithm or attempt a ciphertext-only attack on the ciphertext, Mallory is a lot more powerful than Eve. Not only can he listen to messages between Alice and Bob, he can also modify messages, delete messages, and generate totally new ones. Mallory can imitate Bob when talking to Alice and imitate Alice when talking to Bob. Here’s how the attack works:

(1)  Alice sends Bob her public key. Mallory intercepts this key and sends Bob his own public key.

(2)  Bob sends Alice his public key. Mallory intercepts this key and sends Alice his own public key.

(3)  When Alice sends a message to Bob, encrypted in “Bob’s” public key, Mallory intercepts it. Since the message is really encrypted with his own public key, he decrypts it with his private key, re-encrypts it with Bob’s public key, and sends it on to Bob.

(4)  When Bob sends a message to Alice, encrypted in “Alice’s” public key, Mallory intercepts it. Since the message is really encrypted with his own public key, he decrypts it with his private key, re-encrypts it with Alice’s public key, and sends it on to Alice.

Even if Alice’s and Bob’s public keys are stored on a database, this attack will work. Mallory can intercept Alice’s database inquiry and substitute his own public key for Bob’s. He can do the same to Bob and substitute his own public key for Alice’s. Or better yet, he can break into the database surreptitiously and substitute his key for both Alice’s and Bob’s. Then he simply waits for Alice and Bob to talk with each other, intercepts and modifies the messages, and he has succeeded.

This man-in-the-middle attack works because Alice and Bob have no way to verify that they are talking to each other. Assuming Mallory doesn’t cause any noticeable network delays, the two of them have no idea that someone sitting between them is reading all of their supposedly secret communications.

Interlock Protocol

The interlock protocol, invented by Ron Rivest and Adi Shamir [1327], has a good chance of foiling the man-in-the-middle attack. Here’s how it works:

(1)  Alice sends Bob her public key.

(2)  Bob sends Alice his public key.

(3)  Alice encrypts her message using Bob’s public key. She sends half of the encrypted message to Bob.

(4)  Bob encrypts his message using Alice’s public key. He sends half of the encrypted message to Alice.

(5)  Alice sends the other half of her encrypted message to Bob.

(6)  Bob puts the two halves of Alice’s message together and decrypts it with his private key. Bob sends the other half of his encrypted message to Alice.

(7)  Alice puts the two halves of Bob’s message together and decrypts it with her private key.

The important point is that half of the message is useless without the other half; it can’t be decrypted. Bob cannot read any part of Alice’s message until step (6); Alice cannot read any part of Bob’s message until step (7). There are a number of ways to do this:

— If the encryption algorithm is a block algorithm, half of each block (e.g., every other bit) could be sent in each half message.

— Decryption of the message could be dependent on an initialization vector (see Section 9.3), which could be sent with the second half of the message.

— The first half of the message could be a one-way hash function of the encrypted message (see Section 2.4) and the encrypted message itself could be the second half.