System and Network SecurityProblem Set 1

Problem Set 1

Handed: Sunday, February 16, 2003

Due: Sunday, March 9, 2003

Problem 1:

Assume that Alice and Bob know each other’s public key. Design an authentication protocol that uses exactly two messages (one message from Alice to Bob and one message from Bob to Alice) and accomplishes both mutual authentication and establishment of a session key.

Problem 2:
Suppose two parties Alice and Bob want to communicate privately. They both hold public keys in the traditional Diffie-Hellman model. An eavesdropper Eve stores all the encrypted messages between them and one day manages to break into Alice and Bob computers and to find the private keys, which correspond to their public keys. Show how using public-key cryptography we can achieve perfect forward secrecy, i.e., Eve will not be able to gain any knowledge about the messages that Alice and Bob exchanged before the disclosure of their private keys.
Problem 3:

Design a variant of Kerberos in which the workstation generates a TGT. The TGT will be encrypted with the user’s master key rather than the KDC’s master key. How does this scheme compare with standard Kerberos in terms of efficiency and security? What happens in each scheme if the user changes her password during a login session?

Problem 4:
Suppose we use Kerberos to secure electronic mail. The obvious way of accomplishing this is for Alice, when sending a message to Bob, to obtain a ticket for Bob and include that in the email message, and encrypt and/or integrity-protect the email message using the key in the ticket. The problem is that, in this solution, the KDC gives Alice a quantity encrypted with Bob’s password-derived master key, and then Alice could do off-line password guessing. How might Kerberos be extended to email without allowing off-line password guessing?
Problem 5:

Some government X attempts to regulate Public-Key Cryptography by requiring that the government be the only Certification Agency, and requiring that all public-key cryptography users have their keys certified by the government. Furthermore, in order to have his public key certified, a user must deposit (i.e., escrow) a copy of the corresponding private key with the government. Give two ways in which the users may defeat the government’s objective, and use the government-run CA service to provide authenticated private channels between arbitrary pairs of users that the government cannot listen in to. Assume that the government is only a passive listener, not an active attacker.

Problem 6:

In class, we studied key-distribution protocols that use a Key Distribution Center (KDC) and are based on symmetric-key cryptography. Below is another key-distribution protocol that uses a KDC and is based on public-key cryptography. We assume that the KDC knows the public key of each entity in the system, and we assume that each entity in the system knows the public key of the KDC. The protocol consists of seven messages as follows:

  1. A  KDC:A, B
  2. KDC  A:SIG Prv(KDC) ( B, Pub(B) )
  3. A  B:ENC Pub(B) ( R1, A )
  4. B  KDC:B, A, ENC Pub(KDC) ( R1 )
  5. KDC  B:SIG Prv(KDC) ( A, Pub(A) ) , ENC Pub(B) ( SIG Prv(KDC) ( R1, Ks, A, B ) )
  6. B  A:ENC Pub(A) ( SIG Prv(KDC) ( R1, Ks, A, B ) , R2 )
  7. A  B:ENCKs ( R2 )

In message 1, A informs the KDC of its intention to establish a secure connection with B. In message 2, the KDC returns to A a copy of B’s public-key certificate. In message 3, using B’s public key, A informs B of its desire to communicate and sends a random number R1. In message 4, B asks the KDC for A’s public-key certificate and requests a session key. In this message, B also includes A’s random number R1 encrypted with the KDC’s public key. In message 5, the KDC returns to B a copy of A’s public-key certificate, and it also sends to B the quadruple {R1, Ks, A, B}. This quadruple basically says that Ks is a secret key generated by the KDC on behalf of the session between A and B, and it is tied to R1. This quadruple is signed, using the KDC’s private key, to allow B to verify that the quadruple is indeed from KDC. This quadruple is also encrypted using B’s public key, so that no other entity may use the quadruple in an attempt to establish a fraudulent connection with A. In message 6, the quadruple {R1, Ks, A, B}, still signed with the KDC’s private key, is relayed to A, together with the random number R2 generated by B. All the foregoing are encrypted using A’s public key. In message 7, A retrieves the session key Ks and uses it send to B the encryption of R2.

Questions:

(a)What is the role of R1 in the protocol? Which attacks are possible if R1 is not included in the protocol?

(b)What is the role of R2 in the protocol? Which attacks are possible if R2 is not included in the protocol?

(c)Find an attack on the protocol if, instead the quadruple {R1, Ks, A, B} in messages 5 and 6 of the protocol, we were to use the triple {R1, Ks, B}.

(d)What is the role of message 7 in the protocol?

(e)Design an alternative to the above protocol that achieves the same functionality and uses only five messages in the following sequence:

  1. A  B:
  2. B  KDC:
  3. KDC  B:
  4. B  A:
  5. A  B:

Show each of the five messages transmitted.

Dr. Shlomo KipnisHU – Spring 2003