Problem 1: Consider the following protocol. There exists a trusted server, T, that shares a secret key with any participant in the network. That is, for a participant A, A and T share a secret key K_A. The protocol allows a participant A to send to another participant B, a secret message Al. In the following, to describe the protocol we use the notation A → B : M to denote the fact that A sends to B a message M. The protocol works as follows:

1. A generates a random key R and sends the following message to T, containing A's identity, the fact that it wants to communicate with B and the value R encrypted with the key A shares with T:

A → T : A, B, E(K_A, R).

2. T decrypts the last field of the message with the key shared with A, obtains R, encrypts it with the key T shares with the intended destination, B and sends the result to A:

T → A : E(K_B, R).

3. A uses the key R generated in the first step to encrypt the intended message Al and sends the encrypted value, along with the value received in step 2 from T, to B:

A → B : E(R, M), E(K_B, R).

4. B uses its secret key K_B to decrypt the second field of the received message and obtains R. It then uses R to decrypt the first field of the message, to obtain R.

The above protocol seems secure, as all messages travel over the wires in encrypted format. It has however a major flaw: in the first step of the protocol, T does not authenticate A.

Show how another participant C can exploit this problem, to capture messages from previous runs of the protocol and impersonate A with T in another round of the protocol.

Problem 2: Remember the Needham Schroeder protocol. The protocol has a weakness when an old session key K, shared by A and B is compromised. That is, assume the attacker M gets hold of an old session key K. M can then launch a successful attack All he has to do is to capture A's message to B in step 5:

E_B(K, A).

Then, using knowledge of the old key K and the above message, M can contact B (in the Needham Schroeder protocol) and pretend to be A. Show how this can be done, through the sequence of steps of the attack.

Show how to use timestamps to prevent this attack.

Problem 3: Consider the following "Authentication and Key Exchange" protocol. Trent is a trusted third party, a public key authority that stores a database that maps each user of the system to the user's public key. For instance, Trent stores for Alice her public key pk_A and for Bob, his public key pk_B.

The protocol starts with Alice sending to Trent the following message:

A → T : Req, B, T₁

where T₁ is the current time of Alice. Trent replies with

T → A : S_T(B, pk_B, T₁)

where S_T(M) denotes the signature of Trent of a message M. The signature of T binds Bob to his public key pk_B, stored by Trent. Simultaneously, Bob contacts Trent in a similar manner:

B → T : Req, A, T₂

 where T₂ is the current time of Bob. Trent replies with

T → B : S_T(A, Pk_A, T₂)

At this point, Alice and Bob engage in the following authentication protocol:

A → B : E_B(A, N₁)

where E_B(M) denotes the encryption of message M with the public key of Bob. N₁ is a random number generated by Alice. Bob decrypts this message using his private key, extracts N₁, generates a random N₂ and sends the following message to Alice:

B → A : E_A(N₁, N₂)

E_A(M) denotes the encryption of Al with the public key of Alice. Alice decrypts this message with her private key, recovers N₁ and compares it against the value she initially generated. If the values do not match, she aborts the protocol. Otherwise, she extracts N₂, then sends the following message to Bob:

A → B : E_B(N₂)

Bob decrypts this message with his private key and recovers N₂. It compares N₂ with the value he generated earlier. If they do not match, he aborts the protocol. Otherwise, A and B use a function of N₁ and N₂ to create a shared key.

Explain what is the purpose of the N₁ and N₂ random values.

Show that this protocol is vulnerable to a man-in-the-middle attack. Provide details of the attack. Hint Think of the attack for the Denning-Sacco solution studied in class.