Course:Fall 2009 Exercises 2

From CRYPTUTOR

(Difference between revisions)
Jump to: navigation, search
Revision as of 09:02, 22 October 2009
Manojmp (Talk | contribs)

← Previous diff		 Current revision
Manojmp (Talk | contribs)

Line 24: Line 24:
* <math>A \rightarrow B: {\mathrm E}_{PB}(N_A, A)</math> (where <math>N_A</math> is a fresh nonce, picked by A) * <math>A \rightarrow B: {\mathrm E}_{PB}(N_A, A)</math> (where <math>N_A</math> is a fresh nonce, picked by A)
* <math>B \rightarrow S: B,A </math> (B sends the identities to S) * <math>B \rightarrow S: B,A </math> (B sends the identities to S)
- * <math>S \rightarrow A: {\mathrm E}^{-1}_{SS}( K_{PA}, A) </math> (S sends A's public key to B)+ * <math>S \rightarrow B: {\mathrm E}^{-1}_{SS}( K_{PA}, A) </math> (S sends A's public key to B)
* <math>B \rightarrow A: {\mathrm E}_{PA}(N_B, N_A) </math> (where <math>N_B</math> is a fresh nonce picked by B) * <math>B \rightarrow A: {\mathrm E}_{PA}(N_B, N_A) </math> (where <math>N_B</math> is a fresh nonce picked by B)
* <math>A \rightarrow B: {\mathrm E}_{PB}(N_B) </math> (A and B agree on <math>N_A,N_B</math> at this point) * <math>A \rightarrow B: {\mathrm E}_{PB}(N_B) </math> (A and B agree on <math>N_A,N_B</math> at this point)

Current revision

  1. Impossibility of information-theoretic public-key encryption.
    1. [15 pts] Show that no public-key encryption scheme can be secure against computationally unbounded adversaries. More concretely, show that if (\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec}) is a public-key encryption scheme with perfect correctness (i.e., for all messages M and valid key-pairs (PK,SK), we have \mathsf{Dec}_{SK}(\mathsf{Enc}_{PK}(M))=M) then there is a function \mathsf{Eve} such that for all messages M and valid public-keys PK, \mathsf{Eve}_{PK}(\mathsf{Enc}_{PK}(M))=M (note that \mathsf{Eve} uses only the public-key and not the secret-key).
    2. [Extra Credit] (This problem uses information theoretic terminology.) Show an information theoretic statement that if Alice and Bob do not share private information, then whatever information Alice can convey to Bob using a public-key encryption scheme (which may or may not be perfectly correct), Eve gets the entire information. More precisely, show that for any probabilistic algorithms \mathsf{KeyGen} and \mathsf{Enc}, I(PK,C;M) = I(PK,SK,C;M) where (PK,SK)\gets\mathsf{KeyGen} and C\gets\mathsf{Enc}_{PK}(M) and M comes from an arbitrary distribution. I(X;Y) denotes the mutual information between the random variables X and Y.
  2. Pitfalls in fiddling with CCA secure schemes. To protect against packet corruptions while transmission, suppose one uses an "enhanced" encryption scheme (\mathsf{Gen},\mathsf{Enc}^*,\mathsf{Dec}^*), derived from an encryption scheme (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec}) as follows. The ciphertext in the enhanced scheme consists of three ciphertexts independently generated as encryptions of the plaintext under the original scheme. i.e., \mathsf{Enc}^*(m)=(c_1,c_2,c_3), where c_i\leftarrow\mathsf{Enc}(m). For decryption, the three ciphertexts are decrypted. If at least two of the ciphertexts decrypt to the same message, that message is output as the decryption. Otherwise an error message is produced.
    1. [10 pts] Show that (\mathsf{Gen},\mathsf{Enc}^*,\mathsf{Dec}^*) is IND-CPA secure, if (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec}) is.
    2. [10 pts] Show that (\mathsf{Gen},\mathsf{Enc}^*,\mathsf{Dec}^*) is not IND-CCA secure, even if (\mathsf{Gen},\mathsf{Enc},\mathsf{Dec}) is.
  3. Preimage collision resistance and second-preimage collision resistance are incomparable. In this problem we consider hash functions on a finite domain (from {0,1}n(k) to {0,1}k).
    1. [10 pts] Suppose \mathcal{H} is preimage collision resistant. Modify \mathcal{H} to \mathcal{H}' (possibly with a different domain), so that the latter remains preimage collision resistant, but is not second-preimage collision resistant. (Prove these properties of \mathcal{H}'.)
    2. [10 pts] Given a CRHF \mathcal{H} which compresses by two bits (say from n bits to n − 2 bits), construct a CRHF \mathcal{H}' that compresses by one bit (say from n + 1 bits to n bits), such that the function f(h',x) = (h',h'(x)) (where h'\in\mathcal{H}') is not a OWF. (In both \mathcal{H} and \mathcal{H}', collision-resistance holds when the hash function is drawn uniformly at random from the family.)
    3. [Extra Credit] (Sufficiently Shrinking) CRHF implies OWF. Below we say that "x has a collision under f" if there exists an x' \ne x such that f(x) = f(x').
      1. Let \mathcal{H} be a CRHF and suppose that for every h\in\mathcal{H} and every x, x has a collision under h. Show that the function f(h,x) = (h,h(x)) is a OWF.
      2. Now suppose that for each h\in\mathcal{H}, all but a negligible fraction of x's have a collision under h. Show that the function f(h,x) = (h,h(x)) is a OWF.
      3. Show that if \mathcal{H} is a CRHF from n bits to n / 2 bits, then the function f(h,x) = (h,h(x)) is a OWF.
  4. [15 pts] Compare the security of HMAC with a simpler construction that appends the secret key to the data being authenticated. I.e., MACK(x) = H(x | | K). Describe an attack on the simpler construction that the HMAC construction prevents.
  5. The Needham-Schroeder Public Key protocol uses a trusted server, S, to help two parties exchange secret keys with each other. A priori, there are no secrecy or authentication guarantees on the communication network, and the parties know only each other's identities and a public key of the server S. The server, S, knows public keys of all the users. The goal of the protocol is that at the end A and B should agree on random nonces NA and NB (chosen by A and B respectively). The protocol is described at the end.
    1. [10 pts] There is a (famous) man-in-the-middle attack on this protocol, whereby a party in the system can set up a shared key with B, while she thinks she has shared that key with A. Describe such an attack (without looking it up!). [Hint: The adversary can run a concurrent session with A. It is similar to an attack described in the lecture.]
    2. [10 pts] Suggest a (small) fix for the attack.
    3. [10 pts] If you were designing this protocol today, using public-key encryption and signatures, how would you do it?
    4. [Extra Credit] How will you define the security guarantee of the scheme you design? Can you prove that your scheme indeed meets the security definition?

Needham-Schroeder (Public Key) Protocol: The protocol is described in terms of a public key encryption algorithm E. It is a deterministic encryption scheme with the property that {\mathrm E}_{PK}({\mathrm E}_{SK}^{-1}(M)) = M. If M is sufficiently random, {\mathrm E}_{SK}^{-1}(M) is assumed to behave like a signature on M (though it does not give existential unforgeability). PA,PB are Alice and Bob's public keys and SA,SB are their secret keys, respectively. Likewise, the server's public and secret keys are PS,SS. 

* A \rightarrow S: A,B (A sends the identities to S)
* S \rightarrow A: {\mathrm E}^{-1}_{SS}( K_{PB}, B ) (S sends B's public key to A)
* A \rightarrow B: {\mathrm E}_{PB}(N_A, A)  (where NA is a fresh nonce, picked by A)
* B \rightarrow S: B,A (B sends the identities to S)
* S \rightarrow B: {\mathrm E}^{-1}_{SS}( K_{PA}, A) (S sends A's public key to B)
* B \rightarrow A: {\mathrm E}_{PA}(N_B, N_A) (where NB is a fresh nonce picked by B) 
* A \rightarrow B: {\mathrm E}_{PB}(N_B) (A and B agree on NA,NB at this point)
Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Course:Fall_2009_Exercises_2"