Cryptography and computer security - Tutorial 3.11.2020

Block ciphers

Substitution-permutation network	Feistel cipher

Exercise 1

Let \(y\) be the output of a SPN on input \(x\), where \(\ell=m=N_r=4\), and permutations \(\pi_S\) and \(\pi_P\) be defined as

and

Suppose that the round key \(K_1 = {\tt 0x3954}\) is given in a hexadecimal notation. Compute one round of the SPN for the plaintext \(x = {\tt 0x295C}\).

x = 0x295C = 0010 1001 0101 1100
K = 0x3954 = 0011 1001 0101 0100
    0x1008 = 0001 0000 0000 1000
    0x4EE3 = 0100 1110 1110 0011
y = 0x6E71 = 0110 1110 0111 0001

Exercise 2

Consider a \(2\)-round Feistel network with encryption function \(f(R, K) = R \oplus K\). Assume that all subkeys are equal, i.e., \(K = K_0 = K_1 = K_2\), with subkey size being half the block size. Show that this cipher is not secure.

\[ \begin{aligned} L_1 &= R_0 & R_1 &= L_0 \oplus R_0 \oplus K \\ L_2 &= R_1 & R_2 &= L_1 \oplus R_1 \oplus K \\ &= L_0 \oplus R_0 \oplus K &&= R_0 \oplus (L_0 \oplus R_0 \oplus K) \oplus K \\ &&&= L_0 \\ L_3 &= R_2 & R_3 &= L_2 \oplus R_2 \oplus K \\ &= L_0 &&= (L_0 \oplus R_0 \oplus K) \oplus L_0 \oplus K \\ &&&= R_0 \end{aligned} \]

Exercise 3

Prove that decryption in a Feistel cipher can be done by applying the encryption algorithm to the ciphertext with the key schedule reversed.

\[ \begin{aligned} L_{i+1} &= L_i \oplus F(R_i, K_i) & R_{i+1} &= R_i \\ L_i &= L_{i+1} \oplus F(R_{i+1}, K_i) & R_i &= R_{i+1} \end{aligned} \]

Attacks on block ciphers

• DES (Data Encryption Standard)
  • \(\text{DES} : \lbrace 0, 1 \rbrace^{64} \times \lbrace 0, 1 \rbrace^{56} \to \lbrace 0, 1 \rbrace^{64}\)
  • \(\text{DES}^{-1} : \lbrace 0, 1 \rbrace^{64} \times \lbrace 0, 1 \rbrace^{56} \to \lbrace 0, 1 \rbrace^{64}\)
  • exhaustive key search: \(2^{56}\) operations, \(O(1)\) space
• AES (Advanced Encryption Standard)
  • \(\text{AES} : \lbrace 0, 1 \rbrace^{128} \times \lbrace 0, 1 \rbrace^{128} \to \lbrace 0, 1 \rbrace^{128}\)
  • \(\text{AES}^{-1} : \lbrace 0, 1 \rbrace^{128} \times \lbrace 0, 1 \rbrace^{128} \to \lbrace 0, 1 \rbrace^{128}\)
  • exhaustive key search: \(2^{128}\) operations, \(O(1)\) space

Exercise 4

Since DES has too short keys (\(56\) bits), we decide to combine DES with XOR to achieve \(120\)-bit encryption. We pick a \(56\)-bit key \(k_1\) for regular DES and a \(64\)-bit key \(k_2\). To encrypt a block \(m\), we first encrypt it using DES and then XOR the result with the second key. Mathematically, our encryption scheme is:

\[ \text{DESX}_{k_1, k_2}(m) = \text{DES}_{k_1}(m) \oplus k_2 . \]

Show that DESX is not much more secure than basic DES, as far as exhaustive key search goes.

• Assume we know \((m_i, c_i)\) such that \(\text{DESX}_{k_1, k_2}(m_i) = c_i\).
• We can try for each \(k_1 \in \lbrace 0, 1 \rbrace^{56}\): check if \(k_2 := \text{DES}_{k_1}(m_i) \oplus c_i\) is constant

Input: (m[i], c[i]), i = 1, 2, ... n >= 2

for k1 in {0, 1}^56:
  k2 = DES_k1(m[1]) ^^ c[1]
  for i = 2, ..., n:
    if k2 != DES_k1(m[i]) ^^ c[i]:
      break
  else: # for loop has not been broken
    add (k1, k2) to the list of candidate keys

• Time complexity: \(n \cdot 2^{56}\)
• Space complexity: \(O(1)\)

Exercise 5

We now look at the following variant of key whitening with DES. Suppose that the message \(m\) and the keys \(k_1\) and \(k_2\) are \(64\) and \(56\) bits long. The encryption is defined as

\[ \text{DESW}_{k_1, k_2}(m) = \text{DES}_{k_2}(m \oplus k_1) \]

Show that breaking DESW is roughly as difficult as a brute force attack against single DES.

• Assume we know \((m_i, c_i)\) such that \(\text{DESW}_{k_1, k_2}(m_i) = c_i\).
• \(\text{DES}^{-1}_{k_2}(c_i) \oplus m_i = k_1\)

Input: (m[i], c[i]), i = 1, 2, ... n >= 2

for k2 in {0, 1}^56:
  k1 = DES^-1_k2(c[1]) ^^ m[1]
  for i = 2, ..., n:
    if k1 != DES^-1_k2(c[i]) ^^ m[i]:
      break
  else: # for loop has not been broken
    add (k1, k2) to the list of candidate keys

• Time complexity: \(n \cdot 2^{56}\)
• Space complexity: \(O(1)\)

\[ \text{2DES}_{k_1, k_2}(m) = \text{DES}_{k_1}(\text{DES}_{k_2}(m)) \]

Input: (m, c)

H = empty hash table
for k1 in {0, 1}^56:
  H[DES^-1_k1(c)] = k1
for k2 in {0, 1}^56:
  s = DES_k2(m)
  if s in H:
    add (H[s], k2) to the list of candidate key

• Time complexity: \(2 \cdot 2^{56}\)
• Space complexity: \(120 \cdot 2^{56}\) bits

Exercise 6

Suppose that we encrypt a message \(m\) in three DES rounds:

\[ c = \text{DES}_{k_3}(\text{DES}_{k_2}^{-1}(\text{DES}_{k_1}(m))) . \]

When does this scheme reduce to single DES?

Modes of operation

Exercise 7

For each mode of operation, give the mathematical expression of the decryption and draw the corresponding block diagram.

Exercise 8

For which modes of operation does \(E_k(m \oplus x) = E_k(m) \oplus x\) hold?

Exercise 9

Which modes of operation allow random access to the ciphertext blocks? That is, if the recipient has the information \((i, c_i)\), can they decrypt the message \(m_i\) without having any other ciphertext blocks? If not, what additional information do they need?

Exercise 10

Suppose an attacker changes one block of the ciphertext \(c_i\) into \(c'_i \not= c_i\). Which blocks are then decrypted incorrectly when using ECB, CBC, CFB, OFB and CTR modes?