CS513 System Security

CS513 Homework 2: Authentication Protocols

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

Due Sept. 26, 2004. Submit your solution on paper in class. No late assignments will be accepted.

To facilitate grading, format your solutions as follows.

Put your name and net id on each page of your solution.
Typeset your solution, using 10 point or larger font and use 8.5 x 11 inch paper.
Use at most one page (single sided) for each problem (so what you submit comprises 3 sheets of paper).
Start each problem's solution on a separate side.

Solutions that do not satisfy the formatting guidelines will be returned, ungraded.

Consider only Dolov-Yao attackers. You may assume that keys are unique, an assumption easily discharged by salting keys.

Problem 1:

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

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, {B,r,K_AB}K_B

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

Which of the following modified protocols is best? Give a sentence or two explaining what changes have been made to each protocol version and also what the significance of those changes is.

PROTOCOL A
1.  A --> KDC: A,B,M,r     For some M chosen by A
2.  KDC --> A: A,B,M, {A,r,M,K_AB}K_A, {B,r,M,K_AB}K_B
3.  A --> B:   A,B,M, {B,r,M,K_AB}K_B

PROTOCOL B
1.  A --> KDC: A,B,M,r     For some M chosen by A
2.  KDC --> A: A,B,M, {A,M,r,K_AB}K_A, {A,B,r,M,K_AB}K_B
3.  A --> B:   A,B,M, {A,B,r,M,K_AB}K_B

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

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

Problem 2:

The Otway-Rees protocol corrects certain deficiencies in previous protocols. The protocol is:

1. A   --> B:   n,A,B, {n,A,B,r1}K_A  (A chooses n, r1 at random)
2. B   --> KDC: n,A,B, {n,A,B,r1}K_A, {n,A,B,r2}K_B  (B chooses r2 at random)
3. KDC --> B:   n,{r1,K_AB}K_A, {r2,K_AB}K_B (KDC creates K_AB)
4. B   --> A:   n,{r1,K_AB}K_A

For each of the following protocols, either argue that the new protocol is equivalent to Otway-Rees or that it is different. Two protocols are equivalent if beliefs by the participating principals are not changed and the sets of attacks admitted are the same. Use no more than three sentences for each protocol.

PROTOCOL A
1. A   --> B:   n,A,{n,A,B,r1}K_A  (A chooses n, r1 at random)
2. B   --> KDC: n,B,{n,A,B,r1}K_A, {n,A,B,r2}K_B  (B chooses r2 at random)
3. KDC --> B:   n,{r1,K_AB}K_A, {r2,K_AB}K_B (KDC creates K_AB)
4. B   --> A:   n,{r1,K_AB}K_A

PROTOCOL B
1. A   --> B:   n,A,B,r1, {n,A,B,r1}K_A  (A chooses n, r1 at random)
2. B   --> KDC: n,A,B,r1,r2, {n,A,B,r1}K_A, {n,A,B,r2}K_B  (B chooses r2 at random)
3. KDC --> B:   n,{r1,K_AB}K_A, {r2,K_AB}K_B (KDC creates K_AB)
4. B   --> A:   n,{r1,K_AB}K_A 

PROTOCOL C
1. A   --> B:   n,A,B, {n,B,r1}K_A  (A chooses n, r1 at random)
2. B   --> KDC: n,A,B, {n,B,r1}K_A, {n,A,r2}K_B  (B chooses r2 at random)
3. KDC --> B:   n,{r1,K_AB}K_A, {r2,K_AB}K_B (KDC creates K_AB)
4. B   --> A:   n,{r1,K_AB}K_A 

PROTOCOL D
1. A   --> B:   n,A,B, {n,A,B,r1}K_A  (A chooses n, r1 at random)
2. B   --> KDC: n,A,B, {{n,A,B,r1}K_A, n,A,B,r2}K_B  (B chooses r2 at random)
3. KDC --> B:   n,{{r1,K_AB}K_A, r2,K_AB}K_B (KDC creates K_AB)
4. B   --> A:   n,{r1,K_AB}K_A

PROTOCOL E
1. A   --> B:   n,A,B, {n,A,r1}K_A  (A chooses n, r1 at random)
2. B   --> KDC: n,A,B, {n,A,r1}K_A, {n,B,r2}K_B  (B chooses r2 at random)
3. KDC --> B:   n,{r1,K_AB}K_A, {r2,K_AB}K_B (KDC creates K_AB)
4. B   --> A:   n,{r1,K_AB}K_A 

PROTOCOL F
1. A   --> B:   n,A,B, {n,B,r1}K_A  (A chooses n, r1 at random)
2. B   --> KDC: n,A,B, {n,B,r1}K_A, {n,A,r2}K_B  (B chooses r2 at random)
3. KDC --> B:   n,{r2,K_AB}K_B 
4. KDC --> A:   n,{r1,K_AB}K_A

Do any of your answers change if the assumption regarding key uniqueness is removed? If so, explain which and why.

Problem 3:

The following key distribution protocol was inspired by Otway-Rees; the designer was concerned with the cost of encryption and therefore eliminated the encryptions used for Otway-Rees messages 1 and 2.

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

When the protocol terminates (with no participant crashing), what are the strongest conditions that

A can assume about K_AB and who knows it?
B can assume about K_AB and who knows it?
KDC can assume about K_AB and who knows it?

If these assumptions differ from Otway-Rees, state the differences explicitly.