1. Zero-knowledge protocols
1. Let p be a prime and g a generator modulo p. Given y = g^x Alice claims she knows the discrete logarithm x of y. She wants to convince Bob of this fact but she does not want to reveal x to him. Give a zero-knowledge protocol for this problem.
2. Zero-knowledge authentication protocols do not exchange a secret key. For what classes of applications are they useful? Give two concrete, non contrived, scenarios for which you would use a zero-knowledge authentication protocol.
2. Passwords

Consider the following scenario: Alice wants to login on a computer system. In order to gain access she has to communicate her password to the system. Unfortunately the keyboard (and the cable connection between the keyboard and the system) cannot be trusted since there may be a passive adversary recording the key strokes or tapping the line.

Conversely, let us assume that the display used by Alice (and the connection between the system and the display) is secure, meaning it cannot be monitored by an adversary.

Devise a password protocol that will allow Alice to access the system without disclosing her keys to the adversary.

3. Authentication protocol design

Choose three principles given by Needham and Abadi in their guidelines for designing cryptographic protocols paper. For each, give an example where their principle applies and results in an improved protocol, and an example where their principle leads to a poorer protocol.

4. Intentional leaks

Suppose I want to leak information out of a secure facility (for example, the secret plans for Intel’s new processor). Pick one of the authentication protocols we discussed in class and describe how I can deliberately leak information using this protocol.

 

5. Secure clock synchronization

You want to synchronize computers to the real time. One solution is to buy a WWV receiver or a GPS receiver. What are the security threats with this approach? (The relevant information about WWV and GPS receivers is just the existence of a time signal.)

Devise a secure way to synchronize real time at minimum cost and minimum human intervention.

6. Logic of authentication

In this problem you will apply a slight modification of the BAN Logic to the concrete STS protocol discussed in Lecture 2. Assume p is a large prime, g is a generator modulo p and all operations are performed modulo p.

Assume the BAN Logic with the following modifications:

• Assume that the symbols P ^K Q and P ^K Q have the same meaning (P and Q share a key K that can be used for both encryption or authentication).
• Introduce a new construct DH(P, g^x): g^x is the Diffie-Hellman public-key of principal P. In particular this means that P knows x.
• Introduce a new deduction rule that we will call the DH rule:

P believes DH(P, g^x), P believes DH(Q, g^y)

P believes P ^K Q

where K = g^xy

• Introduce a new deduction rule that we will call the strong signature rule (SSR):

P believes ^PK Q, P sees {x}_PK^-1

P believes x

Now here is a description of the idealized STS protocol you are going to work with (here K = g^xy):

1. A -> B: DH(A, g^x)
2. B -> A: DH(B, g^y), {DH(B, g^y), g^x} PB^-1
3. A -> B: {DH(A, g^x), g^y} PA^-1

We want to prove that

A believes A ^K B (Goal 1)

and

B believes A ^K B (Goal 2)

starting with the following assumptions:

A believes fresh(g^x)     B believes fresh(g^y)

A believes DH(A, g^x)    B believes DH(B, g^y)

A believes ^PB B        B believes ^PA A

1. Prove formally the goals (1) and (2) of the protocol. Show all your deduction steps.
2. Suppose we drop the SSR rule. Can you still prove the two goals? If not, can you identify a flaw in the STS protocol that corresponds to the use of the SSR rule? What fix to the original, concrete form of the STS protocol could you suggest that would fix the flaw?
7. Models of authentication

To show a correspondence between different models of authentication protocols, give an encoding of the Dolev-Yao algebraic model of computation for name-stamp protocols (Section III of their paper) in terms of the Abadi-Tuttle state-machine model of computation (Section 5 of their paper).

Back to Lectures

Heather L. Marko
Last Modified: September 1998