Q1:

The goal of this task is to have you analyze and extend a cryptographic protocol. Alice, Bob and Mallory are students of Cryptography. At the beginning of the semester, they have all securely pair-wise exchanged their public keys. While Alice and Bob have become good friends, Mallory is secretly very jealous of Alice and only pretends to be friends with the two.

One day, Alice and Bob meet for a coffee at the end of class. Bob is really happy and tells Alice:

I have designed a new authentication protocol. It's really good, look!

1. B chooses a nonce NB and sends it to A, explicitly indicating sender and receiver:

2. A responds with a nonce NA and a signature:

3. B accepts and replies with a new nonce N'B:

Bob continues: This ensures the following. When the protocol is complete,

1. B can be sure that A created message 2 specifically as a response to B's first message. Thus, it must be A with whom B has executed the protocol!

2. The other way around, A can be sure that she is communicating with B because only B can create the signature in the third message!

Alice knows that authentication protocols can be vulnerable in very subtle ways. She takes a good long look at the protocol and then declares: I am afraid it's broken. An attacker can inject messages such that A would falsely assume she has run the protocol with B, while in fact she was talking to the attacker.

Bob is down-hearted, so Alice takes pity and explains to him why the protocol is vulnerable. Can you do the same?

Use the following attacker model: Assume that Mallory (M) can control all messages in the network, i.e. read, delete, modify etc. She is only limited by the cryptographic functions, which we assume to be perfect. She does not know any party's private keys (except her own).

1.1

Show that the authentication is broken, as Alice claims. Do this by giving a sequence of message exchanges that conform to the protocol specification yet constitute a violation of Bob's second claim. (Note: write down the full message exchange, not just your changes!)

1.2

State precisely which field in which protocol message causes the vulnerability and why. Change the identified field so the authentication property is not violated anymore. Give the new protocol flow.

1.3

The following is a variant of Bob's protocol that adds a weak kind of key establishment:

1. B -> A : B, A, NB, Kpub,A(KB)

2. A -> B : A, B, NA, NB,SigA(NA, NB, B), Kpub,B(KA)

3. B -> A : B, A, NB, NA, SigB(N'B,NA,A)

The shared key is then derived as (KA||KB) (i.e. concatenation). Explain why the key establishment does not meet the criteria for Perfect Forward Secrecy (PFS)

1.4

Show how to enable PFS. Write down the new message flow.

1.5

We said the key establishment is weak in Bob's version (we do not mean the lack of PFS here).

That is because there is a hidden vulnerability in there. Which one? (Say why!)