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.
- Put your name and net id on
each page of your solution.
- If you typeset your solution, use 11 point or larger font and
8.5×11 in. paper.
- Use at most
one page (both sides, if necessary) for each problem.
- Put each solution
on a separate sheet of paper.
Thus, you should submit three sheets of paper.
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:
- A → B : A
- B → A : r1
- A → B : {A,r1}kA
- B → S : {A,{A,r1}kA}kB
- 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 K
A and B knows
K
B). 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
K
A 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.
- A → B: A requests some action by B
- B → A.bas: Please authenticate A to B
[Steps 1–5 of Needham-Schroeder for A.bas and B]
- B → A: B's response to request (a) if authentication
in (b) succeeds
- 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.
-
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:
- A sends B an encrypted message m1 = {p}KA
- B sends A a reply that wraps m1 in an additional layer of
encryption using B's public key KB.
- 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.