CSCI 6268 - Foundations of Computer and Network Security - Fall 2002

Assignment #3

Due: Oct 22nd, 2002 at 10am MDT


1. Suppose Bob has an RSA cryptosystem with a large modulus n which is impractical for any adversary to factor. Alice has a message she wishes to send to Bob which is a string of uppercase alphabetical characters without spaces or punctuation. For example, the message might be "HELLOTHERE". In order to encode her message, she first converts each letter to a number between 0 and 25 using the normal method: A is 0, B is 1, C is 2, ... , and Z is 25. This yields a list of numbers, each number being between 0 and 25. Then she encrypts each of these numbers as usual with Bob's RSA public key. For example, if she has the message "HI", this results in the numbers 7 and 8. If Bob's public key is (n=18721, e=25), then the ciphertext is 725 mod 18721, 825 mod 18721.

Explain why this is a poor use of RSA by giving an attack on this system. You cannot assume that you can factor n. Illustrate your attack by decrypting the following ciphertext which was generated using the public key (n=18721, e=25): 

18718, 13444, 4644, 13444, 1437, 0, 17173, 13444

2. As we well-know, CBCMAC is secure only if the number of blocks in the length of the message is fixed. We define a new MAC called XMAC which is a modification of CBCMAC attempting to allow msgs of any length. XMAC is defined as follows: choose two random keys, K and L, where K is a 56-bit DES key and L is a 64-bit string. Let CBCMACK be the CBCMAC over DES with key K. Now define XMAC(M) = CBCMACK(M) xor L. Please answer the following two questions, giving a convincing argument for your answers.

  1. Is XMAC secure over messages with a fixed block-length?
  2. Is XMAC secure over messages of any block length?

3. Define a two-party authentication and key-exchange protocol based on a combination of Diffie-Hellman and Lamport's hash-based authentication. Detail the assumptions and the goals of this protocol as well as the procedures for Alice and Bob. Discuss the vulnerabilities of your protocol with respect to passive and active attackers.

4. Propose a variant of Diffie-Hellman that assumes that Alice and Bob share a secret key to use with a symmetric cipher. The goal of this variant is to protect the basic Diffie-Hellman from a "man-in-the-middle" attack. Does this protocol provide any form of authentication? If not, please extend it to achieve mutual authentication? Suppose Alice and Bob use the result of your extended Diffie-Hellman to obtain a session key to encrypt their conversation (for privacy). Does your protocol protect Alice and Bob's conversations from future compromises to Alice's or Bob's secrets? If not, try to extend or change the protocol to achieve this additional goal.