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 KA. 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(KA, 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(KB, 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(KB, R).
4. B uses its secret key KB 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:
EB(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 pkA and for Bob, his public key pkB.
The protocol starts with Alice sending to Trent the following message:
A → T : Req, B, T1
where T1 is the current time of Alice. Trent replies with
T → A : ST(B, pkB, T1)
where ST(M) denotes the signature of Trent of a message M. The signature of T binds Bob to his public key pkB, stored by Trent. Simultaneously, Bob contacts Trent in a similar manner:
B → T : Req, A, T2
where T2 is the current time of Bob. Trent replies with
T → B : ST(A, PkA, T2)
At this point, Alice and Bob engage in the following authentication protocol:
A → B : EB(A, N1)
where EB(M) denotes the encryption of message M with the public key of Bob. N1 is a random number generated by Alice. Bob decrypts this message using his private key, extracts N1, generates a random N2 and sends the following message to Alice:
B → A : EA(N1, N2)
EA(M) denotes the encryption of Al with the public key of Alice. Alice decrypts this message with her private key, recovers N1 and compares it against the value she initially generated. If the values do not match, she aborts the protocol. Otherwise, she extracts N2, then sends the following message to Bob:
A → B : EB(N2)
Bob decrypts this message with his private key and recovers N2. It compares N2 with the value he generated earlier. If they do not match, he aborts the protocol. Otherwise, A and B use a function of N1 and N2 to create a shared key.
Explain what is the purpose of the N1 and N2 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.