Block cipher modes – Secgroup Ca' Foscari

When using block ciphers we have to face the problem of encrypting plaintexts that are longer than the block size. We then adopt a mode of operation, i.e., a scheme that repeatedly applies the block cipher and allows for encrypting a plaintext of arbitrary size.

Electronic CodeBook mode (ECB)

This is the simplest mode and is, in fact, what we have done so far with classic ciphers: the plaintext X is split into blocks $x_1,x_2,\ldots,x_n$ whose size is exactly the same as the size of the cipher block. Each block is then encrypted independently using the fixed key k. For example, a substitution cipher applies to letters. What we do is to split the plaintext into single letters that are encrypted independently.

$\begin{matrix} x_1 & x_2& \ldots ~~~~~~& x_n\\\downarrow& \downarrow&&\downarrow\\k\rightarrow\fbox{E}~~~~~~&k\rightarrow\fbox{E}~~~~~~&\ldots~~~~~~&k\rightarrow\fbox{E}~~~~~~\\\downarrow&\downarrow& &\downarrow\\y_1 & y_2 & \ldots ~~~~~~& y_n\end{matrix}$

Decryption is done, as expected, by reversing the scheme:

$\begin{matrix} y_1 & y_2& \ldots ~~~~~~& y_n\\\downarrow& \downarrow&&\downarrow\\k\rightarrow\fbox{D}~~~~~~&k\rightarrow\fbox{D}~~~~~~&\ldots~~~~~~&k\rightarrow\fbox{E}~~~~~~\\\downarrow&\downarrow& &\downarrow\\x_1 & x_2 & \ldots ~~~~~~& x_n\end{matrix}$

Pros: This scheme has the advantage of being very simple and fast, especially on multi-core computers. Notice, in fact, that each single encryption/decryption can be performed independently.

Cons:The security of the scheme, however, is poor:

It mainly conveys all the defects of monoalphabetic classic ciphers: equal plaintext blocks are encrypted in the same way. This allows for the construction of a code-book (from which the mode name) mapping ciphertexts back to plaintexts. It is often the case, in practice, that part of a plaintext is fixed due to the message format, for example. Think of a mail starting with “Dear Alice, …”. If we know a part of the plaintext, we know how the blocks containg that part are encrypted. We can use this information to decrypt other parts of the message, whenever we see the same block occurring.

ECB encrypted Tux from wikipedia gives a great immediate visualization of the codebook problem described above.
Another crucial limitation of this mode is the complete absence of integrity: an attacker in the middle might duplicate, swap, eliminate encrypted blocks and this would correspond to a plaintext where the same blocks are duplicated, swapped, eliminated. Again, having information about the format of the plaintext, an attacker might be able to obtain a different meaningful plaintext. How critical is this attack really depends on the application. But it is not a good idea to leave such an easy opportunity.

Cipher Block Chaining mode (CBC)

This mode solves or mitigates all the issues of ECB discussed above: it prevents equal plaintexts to be encrypted the same way and, at the time, it provides a higher degree of integrity, even if it is not yet satisfactory on this aspect. The idea is to “chain” encryption of blocks using the previous encrypted block. The first block is chained with a special number called Initialization Vector (IV) that is kept secret together with key $k$ .

$\begin{array}{r@{}c@{~~~~~~~}r@{}c@{~~~~~~~}c@{~~~~~}r@{}c}& x_1 && x_2& \ldots&& x_n\\&\downarrow&&\downarrow&&&\downarrow\\IV\rightarrow&\oplus& y_1\rightarrow&\oplus&&y_{n-1}\rightarrow&\oplus\\&\downarrow&& \downarrow&&&\downarrow\\k\rightarrow&\fbox{E}&k\rightarrow&\fbox{E}&\ldots&k\rightarrow&\fbox{E}\\&\downarrow&&\downarrow&&&\downarrow\\& y_1 && y_2 & \ldots&& y_n\end{array}$

Decryption is as follows:

$\begin{array}{r@{}c@{~~~~~~~}r@{}c@{~~~~~~~}c@{~~~~~}r@{}c}& y_1 && y_2& \ldots&& y_n\\&\downarrow&&\downarrow&&&\downarrow\\k\rightarrow&\fbox{D}&k\rightarrow&\fbox{D}&\ldots&k\rightarrow&\fbox{D}\\&\downarrow&&\downarrow&&&\downarrow\\IV\rightarrow&\oplus& y_1\rightarrow&\oplus&&y_{n-1}\rightarrow&\oplus\\&\downarrow&& \downarrow&&&\downarrow\\& x_1 && x_2 & \ldots&& x_n\end{array}$

Pros: As mentioned above, CBC never encrypts the same plaintext block in the same way, preventing the code-book attack. Integrity is improved, but is not yet completely satisfactory. If an attacker swaps, duplicates or eliminates encrypted blocks this will result in at least one corrupted plaintext block. Notice however that this might be unnoticed at the application level and, again, we cannot leave to the application the whole task of checking integrity of decrypted messages.

Cons: Using xor introduces a new weakness: the attacker manipulating one bit of an encrypted block $y_i$ obtains that the same bit of plaintext $x_{i+1}$ is also manipulated. At the same time $x_i$ is corrupted.

Exercise: Write the expressions for CBC encryption and decryption of the i-th block and show, formally, that $D^{CBC}_k(E^{CBC}_k(x_i)) = x_i$ .
Hint: to avoid defining a special expression for $y_1$ , you can let $y_0 = IV$ .

Output FeedBack mode (OFB)

We now see two modes of operation that “transform” block ciphers into stream ciphers. The general idea is to use the block cipher to generate a complex key stream. Encryption is then performed by just XORing the plaintext blocks with the keys of the stream. Intuitively, this is like one-time-pad with a generated key stream. The more the stream is close to a random stream the more the cipher will be close to a perfect one.

$\begin{array}{r@{}c@{~~~~~~~}r@{}c@{~~~~~~~}c@{~~~~~}r@{}c}& IV && z_1& \ldots&& z_{n-1}\\&\downarrow&&\downarrow&&&\downarrow\\k\rightarrow&\fbox{E}&k\rightarrow&\fbox{E}&\ldots&k\rightarrow&\fbox{E}\\&\downarrow&&\downarrow&&&\downarrow\\&z_1&&z_2&&&z_n\\&\downarrow&&\downarrow&&&\downarrow\\x_1\rightarrow&\oplus& x_2\rightarrow&\oplus&&x_{n}\rightarrow&\oplus\\&\downarrow&& \downarrow&&&\downarrow\\& y_1 && y_2 & \ldots&& y_n\end{array}$
Notice that key generation is completely independent of the plaintext and ciphertext. In fact, it is possible to generate the key stream offline, having key $k$ , and perform encryption later on, when necessary. Decryption simply consists of “swapping the arrows” when performing the XOR: ciphertexts are XORed with the key stream to recover the plaintexts.

Notice that the generation of the key stream is, in fact, CBC encryption of a zero plaintext. It is thus possible to reuse CBC implementations to compute it. Notice also that the plaintext blocks can be smaller that the size of the block cipher. In that case it is possible to use part of the key and use the remaining part for the next block. For example, if the size of the block is 128 bits (like in AES), and we have to encrypt single bytes we have that one key can be split into 128/8 = 16 keys of 8 bits, each used to encrypt a single byte.

Pros: This cipher is very efficient (key can be precomputed using CBC) and allows for the encryption of streams of plaintexts. Key stream is generated through a block cipher which makes it very hard to be predicted.

Cons: This stream cipher is synchronous since the key stream is independent of the plaintext. As a consequence, if we reuse the same IV with the same key we obtain the same key stream. Since encryption is XOR, attacking the cipher is the same as attacking one-time-pad when the key is used more than once. Thus, the IV must be changed any time we encrypt a new message under the same key k.
Moreover, an attacker in the middle can arbitrarily manipulate bits of the plaintext by swapping the corresponding bits in the ciphertext. No decrypted blocks will be corrupted. For this reason this mode should only be used in application where integrity of the exchanged message is not an issue or is achieved via additional mechanisms. An example could be satellite transmissions where an attacker is extremely unlikely to be in the middle and confidentiality is the only issue. In this setting, absence of integrity becomes useful to avoid noise propagation: an error on one bit will only affect one bit of the plaintext.

Cipher FeedBack mode (CFB)

This mode mitigates the problems of OFB by making the key stream dependent on the previous encrypted element. To preserve the ability of encrypting plaintexts of size less than or equal to the size of the block of the cipher (e.g. a single byte), this mode uses a shift register that is updated at each step: the register is shifted to the left the number of bits of previous ciphertext (8 for a byte), and such a ciphertext is copied into the rightmost bits of the register:

$\begin{array}{r@{}c@{~~~~~~~}cr@{}c@{~~~~~~~}c@{~~~~~}cr@{}cc} \multicolumn{3}{l}{\fbox{~~~~~~IV~~~~~~}} & \multicolumn{3}{l}{\stackrel{\longleftarrow}{\fbox{~~~~IV~~~~\begin{math}|y_1\end{math}}}} &&\multicolumn{3}{l}{\stackrel{\longleftarrow}{\fbox{\begin{math}\ldots |y_{n-2}|y_{n-1}\end{math}}}} \\&\downarrow&&&\downarrow&&&&\downarrow\\k\rightarrow&\fbox{E}&&k\rightarrow&\fbox{E}&\ldots&&k\rightarrow&\fbox{E}\\&\downarrow&&&\downarrow&&&&\downarrow\\&z_1&&&z_2&&&&z_n\\&\downarrow&&&\downarrow&&&&\downarrow\\x_1\rightarrow&\oplus &&x_2\rightarrow&\oplus&&&x_{n}\rightarrow&\oplus\\&\downarrow&&& \downarrow&&&&\downarrow\\& y_1 &&& y_2 & \ldots&&& y_n\end{array}$

Decryption is as follows:

$\begin{array}{r@{}c@{~~~~~~~}cr@{}c@{~~~~~~~}c@{~~~~~}cr@{}cc} \multicolumn{3}{l}{\fbox{~~~~~~IV~~~~~~}} & \multicolumn{3}{l}{\stackrel{\longleftarrow}{\fbox{~~~~IV~~~~\begin{math}|y_1\end{math}}}} &&\multicolumn{3}{l}{\stackrel{\longleftarrow}{\fbox{\begin{math}\ldots |y_{n-2}|y_{n-1}\end{math}}}} \\&\downarrow&&&\downarrow&&&&\downarrow\\k\rightarrow&\fbox{E}&&k\rightarrow&\fbox{E}&\ldots&&k\rightarrow&\fbox{E}\\&\downarrow&&&\downarrow&&&&\downarrow\\&z_1&&&z_2&&&&z_n\\&\downarrow&&&\downarrow&&&&\downarrow\\x_1\leftarrow&\oplus &&x_2\leftarrow&\oplus&&&x_{n}\leftarrow&\oplus\\&\uparrow&&& \uparrow&&&&\uparrow\\& y_1 &&& y_2 & \ldots&&& y_n\end{array}$

As for OFB, the key stream is generated and then XORed to the ciphertexts to reconstruct the plaintexts.

Pros: This mode provides a higher degree of integrity with respect to OFB: whenever one bit of one ciphertext is modified, the next BSize/CSize plaintexts are corrupted, where BSize is the size of the block of the cipher (e.g., 128 bites) and CSize is the size of the single ciphertext (e.g., 8 bits). For example, with AES and 8 bits of plaintext/ciphertext sizes, we have 128/8 = 16 corrupted decryptions. This number corresponds to the number of left shifts necessary for a ciphertext to exit the shift register.

Cons: On the other hand, this cipher is slower than OFB as it requires the previous ciphertext to compute the next, meaning that parallelization is impossible when encrypting. Moreover, for noisy transmissions (e.g., satellite, TV, …) it has the problem of propagating an error on a single bit over the next BSize/CSize plaintexts, which are completely corrupted.