Block Ciphers

Question 1

What is a block cipher?

Answer 1

A block cipher is a function which maps n-bit plaintext blocks to n-bit ciphertext blocks, where n is called the block length.

Question 2

Define the following terms related to the complexity of block cipher attacks:

• data complexity
• storage complexity
• processing complexity

Answer 2

• data complexity: expected number of input units (ciphertext) required
• storage complexity: expected number of storage units required
• processing complexity: expected number of operations required to process input data and/or fill storage with data (at least one time unit per storage unit)

Out of these 3 aspects, the one that is most difficult to achieve is usually the one that limits how quickly the attacker can crack a particular cipher.

Question 3

At a minimimum, what must a block cipher do to be considered secure?

Answer 3

• The effective key size should be large enough to preclude exhaustive key search, and
• The block size should be sufficiently large to preclude exhaustive data analysis
• A block cipher is considered computationally secure if these conditions hold and no known attacks have both data and processing complexity significantly less than 2ⁿ and 2^m, respectively.

Question 4

How many plaintext-ciphertext pairs does an attacker need to crack a block cipher using the squareroot attack?

Answer 4

Using the squareroot attack, it actually turns out that you only need 2^n/2 plaintext-ciphertext pairs.

e.g For t = 64, you would need 2³² pairs.

Question 5

Explain the birthday paradox.

Answer 5

• The birthday paradox states that if there are 23 people in a room, the probability that any 2 of them have the same birthday is greater than 0.5!
• This seems unlikely if you think about it intuitively. There are 365 days in a year, so half of that is 183. You would think that you would need to have 183 people in a room before the probability was greater than 50% that two would share the same birthday.
• But this is not the right way to analyze this problem. The right way is to look at the probability that any two pairs of people already in the room have the same birthday.

Question 6

What are the 4 most common modes of operation for a block cipher?

Answer 6

• **ECB (Electronic Codebook) **
• **CBC (Cipher-block Chaining) **
• **CFB (Cipher Feedback) **
• **OFB (Output Feedback) **

Question 7

Describe the ECB mode of operation.

Answer 7

• The “E” block is the encryption function, which is a block cipher, encrypting a block of t characters at a time.
• The input x_j is n bits long, and is fed through the encryption function E. A key is applied to produce the ciphertext output.
• The output c_j is also usually n bits long, (i.e. usually we look at the case where there is no data expansion).

Question 8

Describe the CBC mode of operation.

Answer 8

• Here, the input c_j-1 is XOR’d with x_j. So the ciphertext from the previous block will be XOR’d with the plaintext data of the current block, making this a one-time pad.
• The output of this goes into the encryption block.
• So the encryption function returns c_j, which you feed back into the next iteration of encryption, hence the term “chaining”.
• The first block is XOR’d with a random block of text called c₀, which is used to start the whole CBC Mode.

Question 9

Describe the CFB mode of operation.

Answer 9

• In CFB mode, you are essentially using the block cipher as a keystream generator.
• You start with an initialization vector IV.
• Take the input data I_j, shift it over r bits, and replace the missing bits with the r c_j-1 bits
• You feed I_j from the vector to the encryption block.
• The encryption block produces the output O_j.
• Then you only use the r leftmost bits of O_j, and you XOR these with the input x_j to produce the final ciphertext c_j .
• c_j is only r bits long.
• This is an approximation of the one-time pad Vernam Cipher.
• You are using the block cipher as the keystream generator. So your keystream is the r leftmost bits of Oj.
• Then, c_j is fed back into the beginning of this mechanism.
• Whenever you shift bits, you are adding diffusion, i.e. confusion.

Question 10

Describe the OFB mode of operation.

Answer 10

• This mode actually uses the output O_j of the encryption to feedback into the initialization vector.
• This mode is similar to the CFB Mode in that you use the block cipher to generate key strings.
• Again, you only use the r leftmost bits of the output O_j, and you XOR these r bits with the plaintext message x_j to produce the ciphertext c_j.