A block cipher is an algorithm that performs encryption and decryption of plaintext in blocks (for example, 128-bit blocks). It’s obvious that to encode plaintext with a length different from the block size, we need a separate high-level module that will perform split and append operations on the plaintext, coupled with some other transformations. Such transformations are called block cipher modes.
In general, let’s define the block cipher as follows:
- Encrypt: $Enc(m, k) = c$ - function that encrypts plaintext $m$ using key $k$ and outputs ciphertext $c$.
- Decrypt: $Dec(c, k) = m$ - function that decrypts ciphertext $c$ using key $k$ and outputs plaintext $m$.
ECB (electronic codebook) mode
The most obvious cipher mode is ECB mode, which performs encryption for every block separately.
$c_i = Enc(m_i, k)$
This mode is considered to be the worst mode of all. If two parts of the input plaintext are equal (which happens really often in real texts), it produces the same ciphertext, which can be used by hackers to break our cipher.
CBC (cipher block chaining) mode
One of the most popular modes is CBC mode, which performs an XOR operation on every next block of plaintext with the previous ciphertext. This mode lacks the disadvantage of ECB mode and outputs different ciphertexts even for the same plaintexts.
$c_i = Enc(m_i \oplus c_{i-1}, k)$
$m_i = Dec(c_i, k) \oplus c_{i-1}$
For the initial block encryption, it uses a special initialization vector that has to be unique for every new encryption. If we use the same initialization vectors for different encryptions, it can cause the same problems as in ECB mode.
Let’s review several approaches to generating the initialization vector.
- Simply using the counter 0,1,2,3… is not recommended because of really weak randomness. Because of the peculiarities of real texts, using this initialization vector will not increase security significantly.
- A random initialization vector can be really safe for most cases, but it requires access to a really good random number generator. Also, it adds one more cipher block to every encryption, which increases the size of the resulting ciphertext.
- Using nonce values combines the two previous methods. For a nonce (a number used only once), we can select, for example, a message number and then generate the initialization vector $c_0$ by separately encrypting this value. Then, we can add this number to the resulting ciphertext in a raw format, and on the decryption side, it will be possible to generate our initialization vector.
OFB (output feedback) mode
Using this mode, we will not encrypt our plaintext directly. Instead, we will use a block cipher to generate a pseudo-random byte stream and combine it with plaintext using an XOR operation (as in a one-time-pad cipher). Such an approach is also referred to as a stream cipher.
$k_i = Enc(k_{i-1}, k)$
$c_i = m_i \oplus k_i$
It’s easy to observe that such an approach also requires an initialization vector, as in CBC mode. One of the advantages of this algorithm is that encryption and decryption methods are the same. Also, it does not require appending to the plaintext to fill the entire block—we can use as much as needed.
One of the greatest vulnerabilities of this mode is that using the same initialization vectors causes more security risks than in all previous modes. For example, for plaintexts $m, \hat{m}$ and ciphertexts $c, \hat{c}$ generated with the same initialization vectors we can calculate $c \oplus \hat{c} = m \oplus k \oplus \hat{m} \oplus k = m \oplus \hat{m}$. So, with knowledge of one of the plaintexts, a hacker can easily recover the other plaintext.
Also, if one of the $k_i$ appears twice, it will cause the whole chain to repeat. This problem is more likely to occur after a large number of encryptions (see the collisions section below), so it is obviously necessary to limit the maximum number of encryptions per key.
CTR (counter) mode
CTR mode can be described as a modification of OFB mode because it utilizes the same approaches.
$k_i = Enc(nonce | i, k)$
$c_i = m_i \oplus k_i$
This mode requires $nonce | i$ to be the same size as the block. Then, for example, for a 128-bit block, we can use 48 bits for the message number, 16 bits for any nonce data, and 64 bits for the counter $i$. Then, we are able to encrypt a maximum of $2^{48}$ messages per key, with a maximum message size of $2^{64}$ bits.
CBC vs CTR
- Appending: CBC requires appending to the plaintext to fill the block, CTR - not.
- Speed: CTR allows concurrent calculation of ciphertext blocks.
- Implementation: CTR requires only encryption function to implement (decryption is the same).
- Reliability: if information about the nonce leaks, then a hacker will be able to receive more information about the message in case of CTR.
- Nonce: In most implementations, CBC requires a nonce as well as CTR.
Collisions
I’ve focused a lot on the probability that two ciphertexts for the same keys appear to be the same. In all cases, it is easy to check that such a match gives more information to a hacker about the plaintext. But what is the resulting probability of such a collision? Imagine we’ve encrypted $M$ blocks of plaintext; then we can select about $M(M - 1)/2$ pairs from them. For a block size of $n$, the probability of two blocks being equal is $2^{-n}$, so the entire probability of receiving same ciphertexts will be $\frac{M(M-1)}{2^{n+1}}$. This value reaches one if $M \simeq 2^{n/2}$. So, for the 128-bit cipher, we will receive a collision with high probability after $2^{64}$ encryptions. This observation can be referred to as the birthday paradox.