Block ciphers, DES and AES

Question 1

What are 2 widely deployed block ciphers?

Answer 1

AES and DES

Question 2

Wha are block ciphers?

Answer 2

Symmetric key

Each block of plaintext is encrypted with the same key

Each block has a fixed size, often between 64 and 256 bits.

Used in certain configurations called modes of operation.

Question 3

What is the encryption technique Confusion?

Answer 3

Use substitution to make the relationship between the key and the ciphertext as complex as possible.

Question 4

What is the encryption technique diffusion?

Answer 4

Involves transformations that dissipate the statistical properties of the plaintext across ciphertext.

Question 5

What is a product cipher?

Answer 5

Cryptosystem

Encryption function is formed by applying several sub-encryption functions.

Most block ciphers are compositions of function f_i, where each f_i has a different key K_i

C = E(P, K) = f_i(…,( f2 ( f1 (P,K1), K2)…) Ki)

Question 6

What are iterated ciphers?

Answer 6

A class of product ciphers

Encryption process divided into r similar rounds

sub-encryptions are all the same round function g

Each round-key Ki is derived from an overall master key K..

Question 7

What is a round function?

Answer 7

The sub-encryption function used in iterate ciphers

Question 8

What is a key schedule in iterate ciphers?

Answer 8

The process that derives sub-keys from a master key

Question 9

Give an example of how a ciphertext is derived through r rounds of an iterate cipher

Answer 9

W0 = P
W1 = g(w0, k1)
W2 = g(w1, k2)
…
Wr = g(w_(r-1), k_r)
C = Wr

Question 10

Give an example of how a ciphertext is decrypted through r rounds of an iterate cipher

Answer 10

Wr = C
W_(r-1) = g^-1 ( Wr, Kr)
W_(r-2) = g^-1 ( Wr-1, Kr-1)
…
W0 = g^-1 ( W1, K1)
P = W0

Question 11

What does an iterate cipher need to have to be able to decrypt?

Answer 11

A round function g that have an inverse g^-1
with g^-1(g(W,ki), ki) = W for all Ki and blocks W

Question 12

What type of block cipher is DES (Data Encryption Standard)

Answer 12

Feistel ciphers

Question 13

What type of block cipher is AES (Advanced Encryption Standard)

Answer 13

Substitution-Permutation Networks (SPNs)

Question 14

What is a Feistel cipher?

Answer 14

Iteration cipher

The round function swaps the two halves of the block and forms a new right hand half.

Question 15

Why is the Feistel cipher process often called a Feistel network?

Answer 15

The process can be seen as a network which the two halves of the plaintext block travel through

Question 16

Describe feistel encryption

Answer 16

Plaintext: P = Wo
Split plaintext into two halves: W0 = (L0, R0)

For each round r, perform:
Li = Ri-1
Ri = Li-1 XOR f(Rw-1, K1)

C = Wr
C = (Lr, Rr)

Question 17

Describe feistel decryption

Answer 17

C = (Lr, Rr)

For each round r, perform:
Li-1 = Ri XOR f(Li, Ki)
Ri-1 = Li

P = (L0, R0)

Question 18

Does every round function allow decryption when using Feistel cipher?

Answer 18

Yes, Feistel don’t use an inverse, so any function f allows decryption.

Because of this, the choice of f is critical for security

Question 19

What is substitution-permutation network (SPNs)?

Answer 19

Iterated cipher

Block length n must allow for each block to be split into m sub-blocks of length l.

n = lm

2 permutations are defined

Permutation P_S operates on sub-blocks of size r bits
P_s: {0, 1}^r -> {0, 1}^r

The permutation P_s is normally called an S-box (substitution box)

Permutation P_p swaps the inputs from {1, …, n}. This is similar to the transposition cipher

Pp: {1, 2, …, n} -> {1, 2, …, n}

Question 20

How is the SPNs round function defined?

Answer 20

Ki is XORed with the current state block Wi

Each sub-block gets the same substitution applied using Ps

The whole block is permuted using Pp, at bit level (transposition)

Question 21

What properties does good block ciphers have?

Answer 21

Avalanche effects with respect to both key and plaintext

Question 22

What is Plaintext avalance?

Answer 22

Small change in P should result in a large change in C.

Ideally, 1 bit change in P should change each bit in C with the probability 1/2.

Relates to diffusion

Question 23

What is key avalanche?

Answer 23

Small change in key should result in a large change in the resulting C, when applied to the same plaintext.

Relates to confusion

Question 24

What is differential cryptoanalysis?

Answer 24

Chosen plaintext attack

Idea: Difference between two input plaintexts, can be correlated to the difference between two output ciphertexts

Question 25

What is linear cryptoanalysis?

Answer 25

Known plaintext attack Can theoretically be used to break DES

Question 26

What defines the security of DES?

Answer 26

It resides in the difficulty of decryption without knowledge of the key. This is because enc and dec definitions are public property.

Question 27

What is DES

Answer 27

16-round Feistel cipher Key length: 56 bits block length: 64 bits

Question 28

Define DES encryption

Answer 28

1. 64 bits of P (input block) are permuted according to an initial fixed permutation IP 2. 16 rounds of Feistel operation are applied, denoted by function f. A different 48-bit subkey is used for each round of f. 3. A fixed inverse permutation, IP^-1, is applied Output from 1-3 is ciphertext C

Question 29

What is DES's Feistel operation (function f)

Answer 29

1. 32 bits expanded to 48 2. Bitwise modulo two, add 48 bits to 48 bit subkey 3. break 48 bits into 8 blocks of 6 bits 4. put block i into substitution table i, resulting in a block length of 4 (now 8 blocks of 4 instead of 6) 5- Apply permutation to resulting 32 bits

Question 30

What is the key schedule of DES?

Answer 30

Each of the 16 rounds involves 48 bits of the 56 bit key. The key is defined by a series of permutations and shifts on the full 56 bit key

Question 31

How can you do a brute force attack on a block cipher?

Answer 31

Testing all 2^k possible keys Right key can be identified by using a small number of cipher blocks. Looking for low entropy in the decrypted P

Question 32

What is double encryption?

Answer 32

K1 and K2 are two keys of the block cipher C = E( E(P1,K1), K2) Key length of original block is k Brute force qould require 2^(2k-1) trials on avarage

Question 33

What is a meet in the middle attack on double encryption?

Answer 33

We have a P and C pair which satisfy: 1. For each key, store C' = E(P, K) in memory 2. Check whether D(C,K') = C' for any K' 3. K from step 1 is K1, and K' from step 2 is K2 4. Check whether key values in step 3 work for other (P, C) pairs This requires storage for one P for every possible key

Question 34

What is required to be able to do the meet in the middle attack on DES?

Answer 34

Storage of one P for every key Single enc for every key Single dec for every key Store: - 2^56 64-bit blocks - 2^56 enc operations - 2^56 dec operations

Question 35

What is triple encryption?

Answer 35

C = E( D( E(P, K1), K2 ), K3 ) Secure from the meet-in-the-middle attack

Question 36

What are the three options for triple decryption?

Answer 36

Three independent keys K1 = K3 K1 = K2 = K3, vulnerable to brute force

Question 37

What is AES?

Answer 37

Symmetric block cipher 128-bit block 128, 192, 256 bit master key Number of rounds (NR) is 10, 12, 14 (128, 192, 256 bit) byte-based design Substitution-permutation network - initial round key addition - NR-1 rounds final round

Question 38

How is state defined in AES?

Answer 38

Using a matrix of bytes. Example: A block size of 16 bytes gives a 4x4 matrix

Question 39

What 4 basic operations does AES consist of?

Answer 39

1. ByteSyb (non-linear substitution) 2. ShiftRow (permutation) 3. MixColumn (diffusion) 4. AddRoundKey This creates a substitution-permutation network wit n=128 and l=8 S-box is a lookup table and mathematically defined in GF(2^8)

Question 40

What is GF(2^8) in AES?

Answer 40

Galois Fields These are finite fields GF(2^8) provides a mathematical basis for byte substitution and diffusion

Question 41

What is the key schedule of AES?

Answer 41

Master key: 128 bits (or 192, 256) Rounds use 128-bit subkey. Each round uses one subkey. An additional initial subkey is also required. Meaning, for 128-bit key, 10 rounds are done, and 11 keys are required. The schedule derives the 128-bit subkeys from the 128-bit master key

Question 42

What are related key attacks?

Answer 42

Attacker is able to obtain C encrypted with a key related to the actual key, in a specified way.

Question 43

What are some attacks that have appeared for AES?

Answer 43

Attacks on reduced-round versions Related key attacks Attacks that are able to reduce effective key size by around 2 bits

Question 44

Compare DES and AES

Answer 44

Block size: DES-64, AES-128 Key size: DES-56, AES-128, 192, 256 Design structure: - both are iterate - DES has feistel structure, AES is SPN - DES is bit-based, AES is byte-based - AES is faster in HW and SW

Question 45

Which of AES and DES is in use today?

Answer 45

AES, but DES is still in use in older applications

Question 46

what is a key schedule?

Answer 46

The process of derive sub-keys for use in a round function, from a master key

Question 47

What are 2 widely used general block cipher designs?

Answer 47

Feistel ciphers: DES Substitution-Permutation Networks (SPNs): AES

Question 48

What should modern block ciphers be designed to be immune to?

Answer 48

Differential and linear cryptanalysis