CS513 Homework 2: Cryptography

Due Sept 26, 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 (single-spaced).
• 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 always 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 protocol between principals A and B that share a key KAB.

• 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 KAB. 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 KAB 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,c1 for some iv and ciphertext block c1), can T impersonate B to A without interacting with B?
2. Can such attacks succeed if r is larger than the block size?
3. Answer question 1 when r satisfies Unpredictability as well as Uniqueness. Does your attack succeed always or only with some probability?

3 Probabilistic Encryption Schemes

Consider the following strengthenings of deterministic encryption scheme (E, D) to 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 pseudo-random 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.

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) and remove the suffix r.
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₂).
3. Using a nonce that satisfies Uniqueness and Unpredictability as a new random key:
   • E'_k(m): choose random r and output E_k(r) || E_r(m).
   • D'_k(c₁ || c₂): compute r = D_k(c₁) and then m = D_r(c₂).