CS513 Homework 2: Cryptography and its uses

General Instructions. You are expected to work alone on this assignment.

Due Oct. 11 on paper at the beginning of class. Assignments may be submitted via CMS. See class information for policies on grading and late assignments.

To facilitate grading, format your solutions as follows.

Solutions that do not satisfy the formatting guidelines may be returned ungraded.


Problem 1

Consider the following one-way authentication protocol with a trusted server S, based on shared-key cryptography with keys kA and kB shared between A and S and between B and S, respectively:

  1. A → B : A
  2. B → A : r1
  3. A → B : {A,r1}kA
  4. B → S : {A,{A,r1}kA}kB
  5. S → B : {A, r1}kB

At the end of a correct run of the protocol, B should be convinced that the initiator of the protocol is in fact the principal claimed in the initial message (in this case A). Exhibit a replay attack that would allow an intruder T to impersonate A.

Problem 2

Retrofitting security onto existing applications can be subtle. For simplicity, consider a system in which all keys are fresh and in which (as one finds with the Internet) the sender's address that appears in a message header cannot be trusted. Moreover, assume A is a legacy client program that may not be changed and B is a legacy server program that may be changed (but minimally).

The Needham-Schroeder protocol can be used to ascertain if principals are who they purport to be (i.e., A knows KA and B knows KB). Thus, one might be tempted to deploy a completely independent local daemon A.bas, which we might call a background authentication service, on the host executing A. A.bas knows KA and speaks Needham-Schroeder in response to requests it receives from any principal. The expectation is that this structure would allow B to ascertain whether A is the principal it purports to be, as follows.

  1. A → B: A requests some action by B
  2. B → A.bas: Please authenticate A to B [Steps 1–5 of Needham-Schroeder for A.bas and B]
  3. B → A: B's response to request (a) if authentication in (b) succeeds
  1. Suppose that attacker T cannot eavesdrop or intercept messages sent among A, A.bas, B and KDC. (This might be a reasonable assumption for certain network topologies.) Explain how T can nevertheless impersonate A as far as B is concerned and therefore obtain service from B in the name of A.
  2. Is it possible to fix this protocol without modifying legacy client program A? Explain.

Problem 3

We saw in class that the ElGamal cryptosystem can be used to do rerandomization of a ciphertext without access to the private key. It can do more. Explain how to build on ElGamal to allow rekeying reencryption, analogous to our solution to the pirate problem:
  1. A sends B an encrypted message m1 = {p}KA
  2. B sends A a reply that wraps m1 in an additional layer of encryption using B's public key KB.
  3. A strips its encryption off this reply and sends B a message {p}KB.
Explain in detail how this can be done. (Hint: message 2 can contain additional information) Why doesn't the analogous approach work with RSA?

Problem 4

Examine the Amazon web site and discuss briefly how well it adheres to each of the aspects of the U.S. Fair Information Principles and Practice (FIPP), to the extent that you can determine.