CS5430 Homework 2: Authentication of Machines

General Instructions. You may (but do no have to) collaborate with one other student on this assignment. If you do collaborate then both students should form a CMS group and submit their paper to that group. Both students are responsible for all of the answers.

Due: Sept 29, 2020 at 10:00am. No late assignments will be accepted.

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


  1. Review the version of the Needham-Schroeder protocol presented in the lecture videos.
    1. What is the significant difference between the version discussed in the video and the version of the Needham-Schroeder protocol presented in the reading?
    2. This difference leads to a vulnerability. Explain this vulnerability and describe an attack that exploits the vulnerability.
    3. A hash function is informally defined as a function that is efficient to compute but infeasible to invert. Could a cryptographic hash function be used to patch the vulnerability in (b) without additional messages and/or additional encryptions? Give the patch or explain why a hash function is insufficient.

  2. We have been assuming that for every user A, the KDC and A share a key K_A. In a moving target defense, periodic state changes are performed in order to invalidate information an adversary has previously discovered. Periodically changing a cryptographic key is an example of a moving target defense.

    The management for a KDC would like to help facilitate a moving target defense by allowing any user A to periodically replace shared key K_A with a new value. So the following protocol has been proposed for key-refresh:

    1. A --> KDC: A, r, refresh // r is a new random value
    2. KDC --> A: {A, r, newKey}K_A // newKey is a fresh random key chosen by the KDC

    At the end of step 2, KDC and A both store newKey as the new value for key K_A.

    1. Assume that type attacks are not possible and that communications channels are reliable, in the absence of an attacker. Describe a possible attack on this protocol by a Dolev-Yao attacker.
    2. Describe changes to the protocol that make the attack in (a) no longer possible.
    3. EXTRA CREDIT: Describe a different attack, along with a defense that blocks it.

  3. Here is the Otway-Reese protocol discussed in the reading.
    1. A --> B: n, A, B, {r1,n,A,B}K_A
    2. B --> KDC: n, A, B, {r1, n, A, B}K_A, {r2, n, A, B}K_B
    3. KDC --> B: n, {r1, K_AB}K_A, {r2, K_AB}K_B,
    4. B --> A: n, {r1, K_AB}K_A
    Each message used in this protocol has plaintext (unencrypted) variables, which might or might not be necessary. Create a version of the table below. Fill-in the table by indicating, for each protocol step and each plaintext variable in the message sent by that step, whether or not the plaintext occurrence of that variable can be deleted from the message without altering the security of the protocol. Give the reason that the deletion is or is not allowed.

    Step Variable Can it be deleted? Reason
    Step 1 n
    A
    B
    Step 2 n
    A
    B
    Step 3 n
    Step 4 n