CS5430 System Security

CS5430 Homework 1: Authenticating Computers

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

Due 2/17 at 11:59pm. No late assignments will be accepted.

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

Use 10 point or larger font.
Start each problem's solution on a new page.
Use at most 1 page per problem.
Pur your name and net id on each page. Failure to do wo will result in a grade deduction.

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

Problem 1:

Below are three simple authentication protocols, where r is a nonce, x*y denotes multiplication, and x**y denotes exponentiation.

Protocol 1:
1  B --> A:  B,r (where r is fresh at B)
2  A --> B:  {(A*B)+r}K_AB
3        B:  Let m be message received
             Check whether Dec(K_AB,m) = (A*B)+r

Protocol 2:
1  B --> A:  B
2  A --> B:  {(A**B)}K_AB
3        B:  Let m be message received
             Check whether Dec(K_AB,m) = (A**B)

Protocol 3:
1  B --> A:  B,r (where r is fresh at B)
2  A --> B:  {(A**B)+r}K_AB
3        B:  Let m be message received
             Check whether Dec(K_AB,m) = (A**B)+r

Attacker T desires to impersonate A to B. For which protocols will T succeed? Give attacks or describe the reason they fail.

Problem 2:

Consider a schematic version of the key distribution protocols we discussed in lecture.

1  A --> KDC: A, B, r  (where r is fresh at A)
2  KDC --> A: A, B, {x, K_AB}K_A, {y, K_AB}K_B
3  A --> B:   A, B, {y, K_AB}K_B

where x and y denote finite strings constructed from the three symbols "A" , "B" , and "r" . Different choices of x and y that a protocol designer makes could lead to protocols having different properties. This question explores the implications of the choices that the protocol designer might make.

Give replacements for x and y that make it possible to perform man-in-the-middle attacks but impossible to perform replay attacks of message 2. Exhibit the man-in-the-middle attack.
Give replacements for x and y that make it impossible to perform man-in-the-middle attacks and impossible to perform replay attacks of message 2.

Problem 3:

The following key distribution protocol is purported to defend against the type attack discussed in the notes against Otway-Rees.

1. A --> B: n,A,B, {r1,n,A,B}K_A 
2. B --> C: n,A,B, {r1,n,A,B}K_A, {r2,n,A,B}K_B
3. C --> B: n, {r1+1,K_AB}K_A, {r2+1,K_AB}K_B
4. B --> A: n, {r1+1,K_AB}K_A

Does this defense work? Either exhibit a type attack against this revised protocol or explain why the attack is stopped by the changes.