CS5430 Homework 2: Authentication Protocols

General Instructions. You are expected to work alone on this assignment.

Due: Feb 19 (Tues) 11:59pm. No late assignments will be accepted.

Submit your solution using CMS. Prepare your solution as .pdf, as follows:

Consider only Dolov-Yao attackers. You may assume that keys are unique.

Problem 1:

The following protocol is designed to prove to A and B that they share a key K with each other. 

A --> B:  {N_A}K   where N_A is a fresh nonce
B --> A:  {N_B}K, N_A   where N_B is a fresh nonce
A --> B:  N_B
Can A and/or B reach the wrong conclusion if attackers are present? If so, give the attack; otherwise, give an informal explanation of the protocol's correctness.

Problem 2:

Consider yet another variation of the key distribution protocols discussed in lecture. 

1.  A --> KDC: A,B,N
2.  KDC --> A: {N,A,B}K_A, {N,K_AB}K_A
3.  KDC --> B: {N,A,B}K_B, {N,K_AB}K_B
4.  A --> B:  {N+1}K_AB   compare value N+1 with contents of message 3
5.  B --> A:  {N-1}K_AB   compare value N-1 with contents of message 2
Does this protocol provide A and B with a shared key K_AB that they can trust for their secret communications? If not, describe the attack; otherwise, give an informal explanation of the protocol's correctness.

Problem 3:

The following protocol allows a client A to suggest a shared key K_AB for communicating with B rather than depending on a server to generate that key. So server S is used in the protocol only as a secure communications channel from A to B, because

Assume that principals A, B, and S ignore any message they receive that contains a timestamp that is more than 5 seconds old. 

A --> S:  A, {T_A, B, K_AB}K_AS   where T_A is current time
S --> B:  {T_S, A, K_AB}K_BS   where T_S is current time

Unfortunately, this protocol is flawed. An intruder T can force B to adopt an instance of K_AB that is arbitrarily old. Show that attack.

Problem 4:

With the Needham-Schroeder protocol, a single server provides a pair of principals (say) A and B with a shared key K_AB. Here is that protocol, as presented in the on-line lecture notes. 

  1.  A --> KDC: A,B,r    where r is a new random value
  2.  KDC --> A: {A,B,r, K_AB, {A,B,K_AB}K_B}K_A
  3.  A --> B: A,B, {A,B,K_AB}K_B
  4.  B --> A: {r'}K_AB   where r' is a new random value
  5.  A --> B: {r' + 1 }K_AB

But in a large network, it makes sense to partition users across several KDC servers --- KDC_1, KDC_2, ..., KDC_n --- and to assign a single server KDC(u) to each user u. User u knows the identity of KDC(u) and communicates with KDC(u), but u communicates with no other KDC server. Therefore, KDC(u) is the only KDC server that is provisioned with key K_u.

Describe modifications to the above version of the Needham-Schroeder protocol that would allow the modified protocol to be used in this distributed setting. The modified protocol should allow an arbitrary pair of users to obtain a shared key for communication, even if those users are served by different KDC servers.

Assume servers KDC_1, KDC_2, ..., KDC_n are trustworthy.