Cryptography and Computer Security
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
| $z$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $\pi_S(z)$ | E | 4 | D | 1 | 2 | F | B | 8 | 3 | A | 6 | C | 5 | 9 | 0 | 7 |
and
| $z$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $\pi_P(z)$ | 1 | 5 | 9 | 13 | 2 | 6 | 10 | 14 | 3 | 7 | 11 | 15 | 4 | 8 | 12 | 16 |
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?