1 symmetric encryption

1.1 cryptographic primitive

1. components (alice, bob, key generator, encrypt, decrypt)
2. functionality (correctness)
3. security (confidentiality is preserved, perfect secrecy)

1.1.1 security notions

Adversary objective: learn confidential information. Typically it is key recovery.

• ciphertext only attack: using ciphertexts in transit only.
• known plaintext attack: same + known (or guess) the corresponding plaintexts
• chosen plaintext attack: force the sender to encrypt some messages selected by the adversary
• chosen ciphertext attack: force the receiver to decrypt some messages selected by the adversary

1.2 block ciphers

1.2.1 data encryption standard (DES)

Encrypts blocks of 64 bits. Key of length 64 bits, but 8 bits are parity bits. We use key schedule to get 16 rounds of 48 bit keys from the main key. We split the plaintext block into two 32 bit parts. We apply the Feistel scheme.

Susceptible to exhaustive search due to small key. There exist keys which produce very weak ciphers.

1.2.1.1 Feistel scheme

\Psi(F^{K_1}, \cdots, F^{K_k}) = \Psi^{-1}(F^{K_k}, \cdots, F^{K_1})

• uses a function over \{0, 1\}^{\frac{n}{2}} to be a function transforming into permutations over \{0, 1\}^n
• inverse permutations have same structure
• alternate round functions and halve swaps
• final halve swap omitted

1.2.2 advanced encryption standard (AES)

Encrypts blocks of 128 bits. Uses key of length 128, 192, or 256.

• transform the block to a 4 \times 4 matrix of bytes
• number of rounds 10, 12, or 14 depending on key length
• non-terminal round:
  • SubBytes: map each byte in matrix through a table
  • ShiftRows: shift rows by 0, 1, 2, 3 cells to the left (wrapping)
  • MixColumns: each column c we replace with Mc (M defined below)
  • AddRoundKey: cell-wise XOR between round key
• last round skips MixColumns

M = \begin{pmatrix} 0x02 & 0x03 & 0x01 & 0x01 \\ 0x01 & 0x02 & 0x03 & 0x01 \\ 0x01 & 0x01 & 0x02 & 0x03 \\ 0x03 & 0x01 & 0x01 & 0x02 \\ \end{pmatrix}

All operations are invertible. We however also need the inverse of M:

M^{-1} = \begin{pmatrix} 0x0e & 0x0b & 0x0d & 0x09 \\ 0x09 & 0x0e & 0x0b & 0x0d \\ 0x0d & 0x09 & 0x0e & 0x0b \\ 0x0b & 0x0d & 0x09 & 0x0e \\ \end{pmatrix}

Arithmetics happens in GF(2^8). We reduce everything modulo 2 and modulo x^8 + x^4 + x^3 + x + 1.

1.2.2.1 ECB mode

Encrypt each block of a larger plaintext independently with the same key. Can leak information on repeating blocks.

1.2.2.2 CBC mode

Start with an initialization vector (IV). We XOR it with first block and cipher it. Then, the result is XORed with the next block and then encrypted, this continues. So instead of just encrypting the block, we first mix the block with the cipher text from the previous block.

Three ways to handle IV:

1. use a non-secret constant IV (bad idea)
2. use secret IV which is part of the key (ok if not reused)
3. random IV that is sent in clear together with ciphertext

If a block of ciphertext is corrupted only this and the next block of plaintext is corrupted.

1.2.2.3 OFB mode

We encrypt IV and XOR with a block. The result of IV encryption is passed to next encryption for the next block. We must have a new IV for every plaintext. IV is a nonce (number used once).

1.2.2.4 CTR mode

Have a counter t_i and increment for each block. We encrypt the counter and XOR with the block. t_i must be a nonce but also across every block across every message. This means each block can be independently computed.

1.2.2.5 XTS mode

Used for hard disk encryption.

1.2.2.5.1 ciphertext stealing

Method for encrypting messages that cannot be evenly divided into blocks.

Let x and x' be the last two blocks where x' is shorter than block length.

1. let Enc(x) = y' || u where y' has same length as x'
2. y = Enc'(x'||u)
3. return y and y'

1.3 stream ciphers

Use a PRNG to generate a key stream. We seed the PRN with a fixed secret key and a nonce. Optimized for hardware, efficient.

We can:

1. synchronize participants to a nonce (requires being stateful)
2. send the nonce in clear with ciphertext (requires nonce being visible by an adversary)

1.3.1 RC4

Key length from 40 to 256 bits.

Weaknesses:

• there are some correlations between some output bytes and key bytes when the nonce is known
• output bytes are not uniformly distributed

1.4 bruteforce inversion

1.4.1 opening a safe

Asking the safe if a key is correct. By bruteforce we can find the correct key.

1.4.1.1 uniform distribution

Exhaustive search for all keys. Expected value of iterations is \frac{N + 1}{2} for N keys.

1.4.1.2 known distribution

Start search with the most probable keys (ordered by a permutation \sigma). Expected value of iterations is \min_\sigma(\sum_{i=1}^N P[K = k_{\sigma(i)}]i) for a permutation (order of tested keys) \sigma. This expected value is called the guesswork entropy of the distribution.

1.4.1.3 unknown distribution

We choose a random permutation and start testing. Expected value of iterations is \frac{N + 1}{2} for N keys.

1.4.1.4 key recovery game (online attack)

Online because we need to directly ask an oracle if a key is correct.

Game:

1. pick K \in_D \mathcal K
2. \mathcal A^{\mathcal O} \to k
3. return 1_{K = k}

1.4.1.4.1 with a clue

Game:

1. pick K \in_D \mathcal K
2. W \leftarrow clue about K
3. \mathcal A^{\mathcal O}(W) \to k
4. return 1_{K = k}

1.4.2 access control

• enrolment: enter user id and password. Register user id and a clue about password.
• access control: enter user id and password. Verify using the clue.

Example clue: the hash of a password.

1.4.3 offline attack

We use a stop test function to test whether the key candidate is consistent with the witness.

Offline key recovery:

1. pick K \in_D \mathcal K
2. W \leftarrow F(K)
3. \mathcal A(W) \to k
4. return 1_{K = k}

Inversion:

1. pick K \in_D \mathcal K
2. W \leftarrow F(K)
3. \mathcal A(W) \to k
4. return 1_{F(k) = W}

1.4.3.1 inversion by exhaustive search

For F : K \to Y let N = |K| and M = |Y|. Finds the pre-image (key) of some clue w \in_U Y. Try keys until F(k) = w.

E_F(P[\text{iterations} > i]) = (1 - \frac{1}{M})^i. Expected number of iterations is M(1 - e^{-\frac{N}{M}}) or just M when N \gg M.

1.4.4 metrics of attacks

• pre-computation time
• memory complexity
• time complexity
• number of online queries
• probability of success

1.4.5 grover’s algorithm

Runs on a quantum computer and does bruteforce in O(\sqrt N).

1.5 double encryption

We run encryption twice with two different keys. This is not much more secure. The security is only the sum of both encryptions rather than their product.

1.5.1 meet in the middle attack

Let y = C''_{k_2}(C'_{k_1}(x)) be a double encryption of two (possibly different) encryptions C'' and C' with keys from their respective key spaces \mathcal K'', \mathcal K'. We compute the encryption dictionary for \mathcal K' for x. Then we look for the middle encryption by checking keys from \mathcal K'' by doing decryption of the cipher text y.

1.6 security

• CPA-breaking \implies CPCA-breaking
• CPCA-secure \implies CPA-secure

1.6.1 key recovery

1.6.1.1 CPA (chosen plaintext attacks)

Game:

1. K \stackrel{\$}{\leftarrow} \{0, 1\}^k
2. Used \leftarrow \emptyset
3. W \leftarrow F(K)
4. \mathcal A^{OEnc} \to K'
5. return 1_{K = K'}

OEnc(N, X):

1. if N \in Used then return \bot
2. Used \leftarrow Used \cup {N}
3. return Enc(K, N, X)

1.6.1.2 CPCA (chosen plaintext/ciphertext attacks)

Game:

1. K \stackrel{\$}{\leftarrow} \{0, 1\}^k
2. Used \leftarrow \emptyset
3. W \leftarrow F(K)
4. \mathcal A^{OEnc, ODec} \to K'
5. return 1_{K = K'}

OEnc(N, X):

1. if N \in Used then return \bot
2. Used \leftarrow Used \cup {N}
3. return Enc(K, N, X)

ODec(N, Y):

3. return Dec(K, N, Y)

1.6.2 decryption

1.6.2.1 CPA (chosen plaintext attacks)

Game:

1. K \stackrel{\$}{\leftarrow} \{0, 1\}^k
2. X_0 \stackrel{\$}{\leftarrow} \mathcal D, N_0 \stackrel{\$}{\leftarrow} \mathcal N
3. Used \leftarrow \{N_0\}
4. Y_0 \leftarrow Enc(K, N_0, X_0)
5. W \leftarrow F(K)
6. \mathcal A^{OEnc}(N_0, Y_0) \to X
7. return 1_{X_0 = X}

OEnc(N, X):

1. if N \in Used then return \bot
2. Used \leftarrow Used \cup {N}
3. return Enc(K, N, X)

1.6.2.2 CPCA (chosen plaintext/ciphertext attacks)

Game:

1. K \stackrel{\$}{\leftarrow} \{0, 1\}^k
2. X_0 \stackrel{\$}{\leftarrow} \mathcal D, N_0 \stackrel{\$}{\leftarrow} \mathcal N
3. Used \leftarrow \{N_0\}
4. Y_0 \leftarrow Enc(K, N_0, X_0)
5. W \leftarrow F(K)
6. \mathcal A^{OEnc, ODec}(N_0, Y_0) \to X
7. return 1_{X_0 = X}

OEnc(N, X):

1. if N \in Used then return \bot
2. Used \leftarrow Used \cup {N}
3. return Enc(K, N, X)

ODec(N, Y):

1. if (N, Y) = (N_0, Y_0) then return \bot
2. return Dec(K, N, Y)

1.6.3 distinguisher

1.6.3.1 ideal cipher

An ideal cipher is a cipher taking a random key K and returning a permutation over the domain.

1.6.3.2 CPA (against distinguisher)

Adv = Pr[\Gamma_1 \text{ returns } 1] - Pr[\Gamma_0 \text{ returns } 1]

Game \Gamma_b:

1. K \stackrel{\$}{\leftarrow} \{0, 1\}^k
2. for every N, pick a length-preserving permutation \Pi_N over D
3. Used \leftarrow \{\}
4. \mathcal A^{OEnc} \to z
5. return z

OEnc(N, X):

1. if N \in Used then return \bot
2. Used \leftarrow Used \cup {N}
3. if b = 0 then return \Pi_N(X)
4. return Enc(K, N, X)

1.6.3.3 CPCA (against distinguisher)

Game \Gamma_b:

1. K \stackrel{\$}{\leftarrow} \{0, 1\}^k
2. for every N, pick a length-preserving permutation \Pi_N over D
3. Used \leftarrow \{\}
4. \mathcal A^{OEnc, ODec} \to z
5. return z

OEnc(N, X):

1. if N \in Used then return \bot
2. Used \leftarrow Used \cup {N}
3. if b = 0 then return \Pi_N(X)
4. return Enc(K, N, X)

ODec(N, Y):

1. if b = 0 then return \Pi_N^{-1}(Y)
2. return Dec(K, N, Y)

1.6.4 notions

• if we can recover the key, we can decrypt
• if we can decrypt we can recognize from the ideal cipher
• if we can break without chosen ciphertext, then we can also beak with