---
tags: vaje, kirv, block, attacks, modes
hackmd: https://hackmd.io/73gHVgn-TYWScyNk4sEvUA
plugins: mathjax
---
# Cryptography and computer security - Tutorial 3.11.2020

---

## Block ciphers

| Substitution-permutation network | Feistel cipher |
| - | - |
|  |  |

### Exercise 1

Let <i>$y$</i> be the output of a SPN on input <i>$x$</i>, where <i>$\ell=m=N_r=4$</i>, and permutations <i>$\pi_S$</i> and <i>$\pi_P$</i> be defined as

| <i>$z$</i> | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
| ---------- | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| <i>$\pi_S(z)$</i> | E | 4 | D | 1 | 2 | F | B | 8 | 3 | A | 6 | C | 5 | 9 | 0 | 7 |

and

| <i>$z$</i> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| ---------- | - | - | - | - | - | - | - | - | - | -- | -- | -- | -- | -- | -- | -- |
<i>$\pi_P(z)$</i> | 1 | 5 | 9 | 13 | 2 | 6 | 10 | 14 | 3 | 7 | 11 | 15 | 4 | 8 | 12 | 16

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

----

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 <i>$2$</i>-round Feistel network with encryption function <i>$f(R, K) = R \oplus K$</i>. Assume that all subkeys are equal, i.e., <i>$K = K_0 = K_1 = K_2$</i>, 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)
- <i>$\text{DES} : \lbrace 0, 1 \rbrace^{64} \times \lbrace 0, 1 \rbrace^{56} \to \lbrace 0, 1 \rbrace^{64}$</i>
- <i>$\text{DES}^{-1} : \lbrace 0, 1 \rbrace^{64} \times \lbrace 0, 1 \rbrace^{56} \to \lbrace 0, 1 \rbrace^{64}$</i>
- exhaustive key search: <i>$2^{56}$</i> operations, <i>$O(1)$</i> space
* AES (Advanced Encryption Standard)
- <i>$\text{AES} : \lbrace 0, 1 \rbrace^{128} \times \lbrace 0, 1 \rbrace^{128} \to \lbrace 0, 1 \rbrace^{128}$</i>
- <i>$\text{AES}^{-1} : \lbrace 0, 1 \rbrace^{128} \times \lbrace 0, 1 \rbrace^{128} \to \lbrace 0, 1 \rbrace^{128}$</i>
- exhaustive key search: <i>$2^{128}$</i> operations, <i>$O(1)$</i> space

---

### Exercise 4

Since DES has too short keys (<i>$56$</i> bits), we decide to combine DES with XOR to achieve <i>$120$</i>-bit encryption. We pick a <i>$56$</i>-bit key <i>$k_1$</i> for regular DES and a <i>$64$</i>-bit key $k_2$. To encrypt a block <i>$m$</i>, 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 <i>$(m_i, c_i)$</i> such that <i>$\text{DESX}_{k_1, k_2}(m_i) = c_i$</i>.
* We can try for each <i>$k_1 \in \lbrace 0, 1 \rbrace^{56}$</i>: check if <i>$k_2 := \text{DES}_{k_1}(m_i) \oplus c_i$</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: <i>$n \cdot 2^{56}$</i>
* Space complexity: <i>$O(1)$</i>

---

### Exercise 5

We now look at the following variant of key whitening with DES. Suppose that the message <i>$m$</i> and the keys <i>$k_1$</i> and <i>$k_2$</i> are <i>$64$</i> and <i>$56$</i> 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 <i>$(m_i, c_i)$</i> such that <i>$\text{DESW}_{k_1, k_2}(m_i) = c_i$</i>.
* <i>$\text{DES}^{-1}_{k_2}(c_i) \oplus m_i = k_1$</i>

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: <i>$n \cdot 2^{56}$</i>
* Space complexity: <i>$O(1)$</i>

----

$$
\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: <i>$2 \cdot 2^{56}$</i>
* Space complexity: <i>$120 \cdot 2^{56}$</i> bits

---

### Exercise 6

Suppose that we encrypt a message <i>$m$</i> 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](https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Confidentiality_only_modes)

### 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 <i>$E_k(m \oplus x) = E_k(m) \oplus x$</i> hold?

---

### Exercise 9

Which modes of operation allow random access to the ciphertext blocks? That is, if the recipient has the information <i>$(i, c_i)$</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 <i>$c_i$</i> into <i>$c'_i \not= c_i$</i>. Which blocks are then decrypted incorrectly when using ECB, CBC, CFB, OFB and CTR modes?