Course:Fall 2009 Exercises 1

From CRYPTUTOR

Jump to: navigation, search
[edit]

Exercises on Symmetric-Key Encryption

  1. [10 pts] Optimality of one-time pad. For a one-time encryption scheme \mathsf{Enc}: {\mathcal K}\times{\mathcal M} \rightarrow {\mathcal C} to be perfectly secret and correct, show that we require |{\mathcal K}|\ge|{\mathcal M}|.
  2. [20 pts] One-way, but every single bit of the preimage is predictable: For any function f:\{0,1\}^*\rightarrow \{0,1\}^*, define a function g_f\, as follows g_f(x,S)=(f(x|_S),S,x|_{\bar{S}}), where S is a subset of \{1,2,\ldots,|x|\} (represented as a bit vector of length | x | ). Here x|_S\, denotes a string obtained by choosing only those bits from x as specified by S and x|_{\bar S} contains the remaining bits.
    1. Show that if f is a one-way function, then so is g_f\,. You may assume that f is length-preserving (i.e., | f(x) | = | x | for all x).
    2. Show that no single bit of the input is a hard-core bit for g_f\,.
  3. [15 pts] True or False (give reasons):
    1. If G:\{0,1\}^k \rightarrow \{0,1\}^n is a PRG, then so is G':\{0,1\}^{k+\ell} \rightarrow \{0,1\}^{n+\ell} defined as G'(x \circ x') = G(x) \circ x' where x\in\{0,1\}^k, x'\in\{0,1\}^\ell, and \circ denotes concatenation.
    2. If F:\{0,1\}^k \times \{0,1\}^m \rightarrow \{0,1\}^n is a PRF, then so is
      1. F':\{0,1\}^{k} \times \{0,1\}^{m+\ell} \rightarrow \{0,1\}^{n+\ell} defined as F'(s ; x\circ x') = F(s;x) \circ x' where s\in\{0,1\}^k, x\in\{0,1\}^m, x'\in\{0,1\}^\ell.
      2. F':\{0,1\}^{k+\ell} \times \{0,1\}^m \rightarrow \{0,1\}^{n+\ell} defined as F'(s \circ s'; x) = F(s;x) \circ s' where s\in\{0,1\}^k, x\in\{0,1\}^m, s'\in\{0,1\}^\ell.
  4. [10 pts] The NCSA is building a PetaFLOPS computer that can execute 1015 floating point operations per second. Suppose that a single evaluation of a block-cipher (DES or AES) takes 10 FLOPs. How long would it take for the NCSA computer to recover a DES key, using a brute-force search? (Clearly state your attack algorithm.) How about a 128-bit AES key?
  5. [25 pts] Recall that the triple-DES (3DES) is a block-cipher that uses the DES block-cipher three times, with three different keys. The output ("ciphertext") of 3DES with key (K1,K2,K3), on input ("plaintext") P is defined as C = \mathrm{DES}_{K_1}(\mathrm{DES}_{K_2}^{-1}(\mathrm{DES}_{K_3}(P))) where DESK and \mathrm{DES}_{K}^{-1} stand for the application of the DES block-cipher in the forward ("encryption") and reverse ("decryption") directions. Suppose you are given oracle access to 3DES with a fixed key (K1,K2,K3). Describe an algorithm for recovering the keys. Your algorithm can use the DES block-cipher as a black-box (in either forward or reverse directions: i.e., feed it a (key,plaintext) pair and obtain a ciphertext, or feed it a (key,ciphertext) pair and obtain a plaintext). How many such calls to DES would you need to make? How much memory does your algorithm use?
  6. [20 pts] Consider a "two-message encryption scheme" \mathsf{Enc}^2 :{\mathcal K}\times{\mathcal M} \times \mathcal M \rightarrow {\mathcal C} \times \mathcal C.
    1. Define perfect secrecy for such an encryption.
    2. Let \mathcal M = \mathcal K = \mathcal C be the set of n-bit strings. Let \mathsf{Enc}^2(K,m_1,m_2) = (K\oplus m_1,K \oplus m_2), where \oplus is bit-wise xor-ing. Prove that this is not perfectly secret, according to your definition.
    3. How would you define SIM-twice security? Modify this definition to argue that the only information leaked by the above encryption scheme is m_1\oplus m_2.
    4. [Extra Credit] Below are the byte sequences obtained by encrypting two English text messages with the same one-time pad. Try and recover both messages:

Message 0 

b7  5d  56  7c  b4  7d  40  28  26  fb  8a  94  cb  19  b2  7a  75  f3  dd  d4  ee  6c  40  9a  c6
d7  dc  9b  6f  dc  49  db  6e  93  da  3c  16  7f  6f  b8  43  3d  ab  c7  18  aa  3e  df  6c  63
49  d7  98  f0  c3  7f  48  29  f7  14  64  e8  94  16  84  2f  10  b4  76  46  54  80  1e

Message 1 

b0  5c  5d  6d  b4  7d  56  32  26  b5  c4  92  98  4a  a7  6c  65  fa  c0  c4  ee  7d  44  88  d7
c6  d7  9b  70  d1  5c  8f  3c  88  dd  29  58  2f  7a  a3  55  6a  b7  d0  1f  f8  2f  c4  3f  37
55  da  d9  c7  8c  74  4d  38  ec  19  73  f3  99  00  ca  77  65  d1  05  35  31  f3  30
Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Course:Fall_2009_Exercises_1"
Personal tools