cryptography supervision 2

In the CBC mode of operation, the initial vector (IV) is chosen uniformly at random, using a secure source of random bits. Show that CBC would not be CPA secure if the initial vector could be anticipated by the adversary, for example because it is generated instead using a counter or a time-stamp.

If the adversary could anticipate the initial vector, then CBC would be deterministic from the perspective of the adversary. Concretely, in the security game, if I could predict the initial vector for each message $C_0^t$, I could request encryption of the modified message with the first block $M_0^{\prime }:=M_0^t\oplus C_0^t$. When the challenger encrypts this, the initial vector cancels out — the rest of the process is fully deterministic, so this attack removes all nondeterminism from CBC.

Explain for each of the discussed modes of operation (ECB, CBC, CFB, OFB, CTR) of a block cipher how decryption works.

electronic codebook

the simplest way to use a block cipher to encrypt an arbitrary-length message. it’s very simple:

1. pad your message to a multiple of the block length
2. apply the block cipher to each block

this is is bad. notably, it is not CPA secure, since it is deterministic.

Link to original

cipher block chaining

cipher block chaining is a way to nondeterministically encrypt an arbitrary-length message using a block cipher.

1. pad your message to a multiple of the block length
2. generate a random initial vector (IV) $C_0$. this is the first ciphertext.
3. before encrypting block $M_i$, XOR it with $C_{i-1}$, i.e. $C_i:=E_K(M_i\oplus C_{i-1})$
4. and then output the ciphertext $C:=C_0||C_1||\dots ||C_m$.

in diagram form:

note that you expect to see a block cipher input repeated after $\sqrt{2^n}$ blocks have been encrypted with the same key $K$, where $n$ is the block size in bits (TODO: why? so what?)

Link to original

cipher feedback mode

cipher feedback mode (CFB) is another mode of operation for a block cipher. a weakness of CBC is a full block is required before the ciphertext can be sent, which CFB attempts to improve.

1. start with a random initial vector $C_0$ as in CBC.
2. output $C_i:=M_i\oplus E_K(C_{i-1})$

note that once $C_{i-1}$ is computed, the block cipher step for $C_i$ can be computed immediately — no waiting for $M_i$ required. this means that as bits of $M_i$ arrive, we can encrypt them immediately without waiting for the block to fill.

an ancillary advantage is that we don’t have to pad the last block.

Link to original

output feedback mode

output feedback mode (OFB) lets us turn a block cipher into a stream cipher.

Link to original

A sequence of plaintext blocks $M_1,\dots ,M_8$ is encrypted using DES into a sequence of ciphertext blocks. Where an IV is used, it is numbered $C_0$. A transmission error occurs and one bit in ciphertext block $C_3$ changes its value. As a consequence, the receiver obtains after decryption a corrupted plaintext block sequence $M_1^{\prime },\dots ,M_8^{\prime }$. For the discussed modes of operation (ECB, CBC, CFB, OFB, CTR), how many bits do you expect to be wrong in each block $M_i$ ? (Hint: You may find it helpful to draw decryption block diagrams.)

Your opponent has invented a new stream-cipher mode of operation for 128-bit key AES. He thinks that OFB could be improved by feeding back into the key port rather than the data port of the AES chip. He therefore sets $R_0=K$ and generates the key stream by $R_{i+1}=E_{R_i}(R_0)$. Is this better or worse than OFB?

The problem here is that you generate your key only once, and this variant of OFB is deterministic given a certain key. This means that in the setup of the CPA game we had previously, this mode of operation is deterministic, so it can’t be CPA secure — it’s worse than OFB.

In practice, relying on the key for both the encryption procedure and the nondeterminism for encrypting the blocks means that you can never encrypt multiple messages with the same key. This means you have to do a lot of key distribution, which is hard.