To see how this causes a problem for Mallory, let’s review his attempt to subvert the protocol. He can still substitute his own public keys for Alice’s and Bob’s in steps (1) and (2). But now, when he intercepts half of Alice’s message in step (3), he cannot decrypt it with his private key and re-encrypt it with Bob’s public key. He must invent a totally new message and send half of it to Bob. When he intercepts half of Bob’s message to Alice in step (4), he has the same problem. He cannot decrypt it with his private key and re-encrypt it with Alice’s public key. He has to invent a totally new message and send half of it to Alice. By the time he intercepts the second halves of the real messages in steps (5) and (6), it is too late for him to change the new messages he invented. The conversation between Alice and Bob will necessarily be completely different.

Mallory could possibly get away with this scheme. If he knows Alice and Bob well enough to mimic both sides of a conversation between them, they might never realize that they are being duped. But surely this is much harder than sitting between the two of them, intercepting and reading their messages.

Key Exchange with Digital Signatures

Implementing digital signatures during a session-key exchange protocol circumvents this man-in-the-middle attack as well. Trent signs both Alice’s and Bob’s public keys. The signed keys include a signed certification of ownership. When Alice and Bob receive the keys, they each verify Trent’s signature. Now they know that the public key belongs to that other person. The key exchange protocol can then proceed.

Mallory has serious problems. He cannot impersonate either Alice or Bob because he doesn’t know either of their private keys. He cannot substitute his public key for either of theirs because, while he has one signed by Trent, it is signed as being Mallory’s. All he can do is listen to the encrypted traffic go back and forth or disrupt the lines of communication and prevent Alice and Bob from talking.

This protocol uses Trent, but the risk of compromising the KDC is less than the first protocol. If Mallory compromises Trent (breaks into the KDC), all he gets is Trent’s private key. This key enables him only to sign new keys; it does not let him decrypt any session keys or read any message traffic. To read the traffic, Mallory has to impersonate a user on the network and trick legitimate users into encrypting messages with his phony public key.

Mallory can launch that kind of attack. With Trent’s private key, he can create phony signed keys to fool both Alice and Bob. Then, he can either exchange them in the database for real signed keys, or he can intercept users’ database requests and reply with his phony keys. This enables him to launch a man-in-the-middle attack and read people’s communications.

This attack will work, but remember that Mallory has to be able to intercept and modify messages. In some networks this is a lot more difficult than passively sitting on a network reading messages as they go by. On a broadcast channel, such as a radio network, it is almost impossible to replace one message with another—although the entire network can be jammed. On computer networks this is easier and seems to be getting easier every day. Consider IP spoofing, router attacks, and so forth; active attacks don’t necessarily mean someone down a manhole with a datascope, and they are not limited to three-letter agencies.

Key and Message Transmission

Alice and Bob need not complete the key-exchange protocol before exchanging messages. In this protocol, Alice sends Bob the message, M, without any previous key exchange protocol:

(1)  Alice generates a random session key, K, and encrypts M using K.

E_K(M)

(2)  Alice gets Bob’s public key from the database.

(3)  Alice encrypts K with Bob’s public key.

E_B(K)

(4)  Alice sends both the encrypted message and encrypted session key to Bob.

E_K(M), E_B(K)

For added security against man-in-the-middle attacks, Alice can sign the transmission.

(5)  Bob decrypts Alice’s session key, K, using his private key.

(6)  Bob decrypts Alice’s message using the session key.

This hybrid system is how public-key cryptography is most often used in a communications system. It can be combined with digital signatures, timestamps, and any other security protocols.

Key and Message Broadcast

There is no reason Alice can’t send the encrypted message to several people. In this example, Alice will send the encrypted message to Bob, Carol, and Dave:

(1)  Alice generates a random session key, K, and encrypts M using K.

E_K(M)

(2)  Alice gets Bob’s, Carol’s, and Dave’s public keys from the database.

(3)  Alice encrypts K with Bob’s public key, encrypts K with Carol’s public key, and then encrypts K with Dave’s public key.

E_B(K), E_C(K), E_D(K)

(4)  Alice broadcasts the encrypted message and all the encrypted keys to anybody who cares to receive it.

E_B(K), E_C(K), E_D(K), E_K(M)

(5)  Only Bob, Carol, and Dave can decrypt the key, K, each using his or her private key.

(6)  Only Bob, Carol, and Dave can decrypt Alice’s message using K.

This protocol can be implemented on a store-and-forward network. A central server can forward Alice’s message to Bob, Carol, and Dave along with their particular encrypted key. The server doesn’t have to be secure or trusted, since it will not be able to decrypt any of the messages.

3.2 Authentication

When Alice logs into a host computer (or an automatic teller, or a telephone banking system, or any other type of terminal), how does the host know who she is? How does the host know she is not Eve trying to falsify Alice’s identity? Traditionally, passwords solve this problem. Alice enters her password, and the host confirms that it is correct. Both Alice and the host know this secret piece of knowledge and the host requests it from Alice every time she tries to log in.