CS5430 System Security - Homework 2: Cryptography

Due Feb 16, 10am. No late assignments will be accepted.

Submit your solution using CMS. Prepare your solution using Word (.doc) or some ascii editor (.txt), as follows:

• Use 10 point or larger font.
• Start each problem's solution on a new page.
• Use at most 1 page per problem.

1 Weak Collision Resistance

We mentioned in class that Strong Collision Resistance implies Weak Collision Resistance. To prove this fact, we might prove the contrapositive: given any adversary A that can break Weak Collision Resistance, we can construct a new adversary B that can break Strong Collision Resistance.

1. Suppose we are given an algorithm A that violates Weak Collision Resistance for some hash function h. If A takes hash function h and a value x as input and produces A(h, x) as output, then what properties of A(h, x) would imply that Weak Collision Resistance is violated for h?
2. Given adversary A from question 1, we might construct an algorithm B that takes hash function h as input and violates Strong Collision Resistance by producing B(h) = (x, x'). What properties of x and x' would imply that Strong Collision Resistance is violated?
3. Assume that B can invoke A. Give an algorithm for B that causes B to violate Strong Collision Resistance for h.

2 Nonces and CBC Mode

Consider the following simple protocol between principals A and B that share a key K_AB.

• A chooses a fresh nonce r (i.e., r satisfies Uniqueness)
• A → B : {r}_KAB
• B → A : {r + 1}_KAB

This exchange purports to demonstrate to A that B knows K_AB. Suppose that r is at most as large as the block size for the encryption function and that r satisfies Uniqueness, but not Unpredictability (so an adversary can be assumed to know r). Further assume that adversary T does not know K_AB and that CBC mode is used here exactly as described in class and in the notes (so, for example, without any integrity checks). Let the encryption function satisfy Non-Malleability when used on a fixed-size block.

1. If encryption is performed in CBC mode (so the adversary actually receives iv and c₁ for some iv and ciphertext block c₁), can T impersonate B to A without interacting with B?
2. Can such attacks succeed if r is larger than the block size?

3 Probabilistic Encryption Schemes

Consider the following transformations of a given deterministic encryption scheme (E, D) to a probabilistic scheme (E', D'). In each scheme, assume that adversaries know E and D and have access to a machine that performs E_k for messages of the adversary's choice, as in the CPA model. Also assume that E is a pseudorandom function.

For each of the following schemes, state problems with the scheme under the CPA model or argue that the scheme is secure under CPA. If attacks can be performed on a scheme, state what property is not satisfied by this scheme to allow these attacks.

1. Adding a nonce that satisfies Uniqueness and Unpredictability:
   • E'_k(m): choose random r and output r || E_k(m || r).
   • D'_k(r || c): compute D_k(c) = m || r and remove the suffix r to get the message m.
2. Using a nonce that satisfies Uniqueness (but not Unpredictability) as a new key:
   • E'_k(m): choose nonce r and output E_k(r) || E_r(m).
   • D'_k(c₁ || c₂): compute r = D_k(c₁) and then m = D_r(c₂).