CS5430 System Security

CS5430 Homework 3: Attacking Authentication Protocols

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

Due: Feb 21, 2020 at 11:59pm. No late assignments will be accepted.

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

Use 10 point or larger font.
Put each problem into a separate file and submit it to the correct CMS submission box for that problem.
Use at most 1 page per problem.

Problem 1. Consider the following variation of the Needham-Schroeder protocol. In this variation, line 4 has been changed: challenge r' is no longer encrypted before it is sent.

Needham-Schroeder Protocol:

  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'   where r' is a new random value
  5.  A --> B: {r'}K_AB

Does the modified protocol lead to vulnerabilities not present with the original? Justify your conclusion either by (i) explaining why attackers are not better off or (ii) giving general principles being violated as well as a specific attack.

Problem 2. Below is an authentication protocol, where k is a key shared only by principals A and B. Some design notes are included after each step.

1.  B --> A:  B, r
       % B records R_B:=r and (upon receipt) A records R_A:=r

2.  A --> B:  A, {A, r+1}k
       % B believes that B is in dialog with A
       % if and only if
       % - B receives this message and
       % - decrypting with k yields "A" and "r+1" = R_B+1

3.  B --> A:  B, {B, r-1}k
       % A believes that A is in dialog with B
       % if and only if
       % - A receives this message and
       % - decrypting with k yields "B" and "r-1" = R_A-1

(a) Show how a Dolev-Yao attacker T could cause one or more "beliefs" given above to be unsound.

(b) A natural question is whether such attacks can be avoided by using different expressions for responses "r+1" in line 2 and "r-1" in line 3. Such a protocol can be described as follows.

1.  B --> A:  B, r
2.  A --> B:  A, {A, F(r) }k
3.  B --> A:  B, {B, G(r) }k

What, if any, properties of functions F and G would prevent attacks like the one predicted in (a).

Problem 3. Consider the following key distribution protocol. Instead of using nested encryption (like Needham Schroeder) it uses a nonce r to link two separate encrypted blobs (like Otway-Rees).

1.  A --> KDC: A,B,r
2.  KDC --> A: A,B, {A,r,K_AB}K_A, {B,r,K_AB}K_B
3.  A --> B:   A,B, {r}K_AB, {B,r,K_AB}K_B

(a) What should cause A to reject message 2?

(b) What should cause B to reject message 3?

(c) Exhibit a man-in-the middle attack that would allow an intruder T thereafter to understand and/or alter communications between A and B, assuming that communication is encrypted using the "shared key" each receives from a run of this protocol.