CS5430 (Fall 2023) Homework 2:

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

Due: Sept 29, 2023 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.

          Submit each problem (as a separate file) into the correct CMS submission box for that problem.

Assume that the threat is a Dolev-Yao attacker.

Problem 1:

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

1.  A --> KDC: A, B, r_1, r_2

2.  KDC --> A: A, B, {A, r_1, K_AB}K_A, {B, r_2, K_AB}K_B

3.  A --> B:   A, B, {B, r_2, 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.



Problem 2:

The following key distribution protocol was inspired by Otway-Rees (which is described in the on-line lecture notes); 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


Assume that the protocol terminates, with no participant crashing.  What are the strongest conditions for ii and iii, below. We give those conditions for i, so you can see an example of the kind of answer we are expecting.

  1. What can A can assume about K_AB and who knows it?

A can assume that only principals holding either K_A or K_B know K_AB. This is at most {A,B,KDC}. A can also assume that K_AB is fresh since message 4 contains r1 which A created in message 1. Unlike Otway-Rees, A cannot assume that B participated in this run of the protocol (note that B does not encrypt any messages). Therefore the completion of the protocol cannot be used to determine that B interacted with A and therefore has the key.

  1. What can B can assume about K_AB and who knows it?


  1. What can KDC can assume about K_AB and who knows it?


Problem 3:

Consider the following shared-key authentication protocol, which uses functions F() and G() to generate nonces.  Assume that A and B are the only principals that know shared key k.


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 Dolev-Yao attacks.



Problem 4:

A  self-signed certificate is a digitally signed bitstring that contains a public key K_A that can be used to verify digital signatures created with the private key k_A used to sign that bitstring.  Presumably, these keys would be associated with the principal A.


Here is an example of a self-signed certificate that A might send to a server S as the first step in creating an account for playing a game.

1.  A --> S:  < register: A, K_A, n >k_A    for fresh n


If this registration message is received by S and S deems  the digital signature valid according to the verification key K_A the registration message contains then S creates an account for A to play the game and S stores verification key K_A.  Thereafter,  A would be expected to use signing key k_A to digitally sign messages to S for each move that A submits in playing the game; and S would use K_A to verify that a message came from A before undertaking the move that the message purports to have come from A.


(a)  What action would you recommend that S take upon receiving a  second instance of message 1, correctly signed, but containing a different verification key K_A?


(b) Each message from a player A to S would include a description of the next move S is making and would be digitally signed using k_A.  Discuss the advantages and disadvantages of including the following additional information in each of these messages.


(i) time of day. 


(ii) a sequence number. 


(iii) the verification key K_A, so that the server does not have to store this information and in order to obviating the need for a registration message.