CS513 System Security

CS513 Homework 2: Cryptographic Protocols

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

Due Feb. 15, 2010 at 9am. Submit your solution using CMS. 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 (both sides, if necessary) for each problem (so what you submit comprises 6 sheets of paper).
Start each problem's solution on a separate side.

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

For the following problems consider only Dolov-Yao attackers.

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 an attack on executions this protocol that would thereafter allow an intruder T 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.

Problem 2:

The following key distribution protocol was inspired by the Otway-Rees protocol; the designer here was concerned with the cost of encryption and therefore eliminated the encryptions used for Otway-Rees messages 1 and 2. (The Otway-Rees protocol is described in the on-line lecture notes.)

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

Explain what if any effect this change has on what A and B can believe about the keys they have received upon termination of a protocol run? Be sure to comment on whether, when the protocol terminates, K_AB is a fresh key known only to principals A, B, KDC, or some subset thereof.

Problem 3:

What are called stream ciphers are symmetric key encryption algorithms in which the key and an initialization vector together serve as a kind of seed that produces an arbitrary (i.e., unbounded) length sequence of bits, called a keystream.

The key is secret and shared by two principals, an encrypting principal A (say) and the decrypting principal B (say).
A different random initialization vector is used for each encryption. The initialization vector is selected by the encrypting principal A and sent (in the clear) to the decrypting principal B, where it is used in performing decryption.

RC4 is a well known example of a stream cipher.

Using a stream cipher, a b bit input x is encrypted simply by computing the XOR ("exclusive or") of x with the length b keystream produced by the key.

We write "iv,{m}K" to denote what is produced by encrypting m using a stream cipher with shared key K and initialization vector iv. That is, by convention, the initialization vector in the clear precedes the encrypted bits as the output of the encryption function.

Explain how a receiver that knows the key can decrypt a message encrypted, as outlined above, with a stream cipher.
An attacker T is launching a man-in-the-middle attack for a protocol that contains the step:
```
17   A --> B:  A, B, iv1,{B}K_A, iv2,{A}K_A
```
Moreover, suppose this protocol employs a stream cipher. Is it possible for the attacker to intercept message 17 above and cause an altered message 17' to reach B as follows?
```
17   A --> T:  A, B, iv1,{B}K_A, iv2,{A}K_A
17'  T --> B:  T, B, iv1',{T}K_A, iv2',{A}K_A  for some iv1' and iv2' chosen by T
```
Explain how or argue why it is not possible.