Cipher-block chaining (CBC)

Cipher-block chaining (CBC) is a common chaining mode in which the previous block's ciphertext is xored with the current block's plaintext before encryption:

${\displaystyle C_{i}=E_{K}(C_{i-1}\oplus P_{i}).}$

Since there isn't a "previous block's ciphertext" for the first block, an initialization vector (IV) must be used as ${\displaystyle C_{-1}}$. This, in turn, makes CBC tweakable in some ways.

CBC suffers from some problems. For example, if the IVs are predictable, then an adversary may leave a "watermark" on the disk, i.e., store a specially created file or combination of files identifiable even after encryption. The exact method of constructing the watermark depends on the exact function providing the IVs, but the general recipe is to create two encrypted sectors with identical first blocks ${\displaystyle b_{1}}$ and ${\displaystyle b_{2}}$; these two are then related to each other by ${\displaystyle b_{1}\oplus IV_{1}=b_{2}\oplus IV_{2}}$. Thus the encryption of ${\displaystyle b_{1}}$ is identical to the encryption of ${\displaystyle b_{2}}$, leaving a watermark on the disk. The exact pattern of "same-different-same-different" on disk can then be altered to make the watermark unique to a given file.

To protect against the watermarking attack, a cipher or a hash function is used to generate the IVs from the key and the current sector number, so that an adversary cannot predict the IVs. In particular, the ESSIV approach uses a block cipher in CTR mode to generate the IVs.

Liskov, Rivest, and Wagner (LRW)

In order to prevent such elaborate attacks, different modes of operation were introduced: tweakable narrow-block encryption (LRW and XEX) and wide-block encryption (CMC and EME).

Whereas a purpose of a usual block cipher ${\displaystyle E_{K}}$ is to mimic a random permutation for any secret key ${\displaystyle K}$, the purpose of tweakable encryption ${\displaystyle E_{K}^{T}}$is to mimic a random permutation for any secret key ${\displaystyle K}$ and any known tweak ${\displaystyle T}$. The tweakable narrow-block encryption (LRW)^[5] is an instantiation of the mode of operations introduced by Liskov, Rivest, and Wagner^[6] (see Theorem 2). This mode uses two keys: ${\displaystyle K}$ is the key for the block cipher and ${\displaystyle F}$ is an additional key of the same size as block. For example, for AES with a 256-bit key, ${\displaystyle K}$ is a 256-bit number and ${\displaystyle F}$ is a 128-bit number. Encrypting block ${\displaystyle P}$ with logical index (tweak) ${\displaystyle I}$ uses the following formula:

${\displaystyle {\begin{aligned}X&=F\otimes I,\\C&=E_{K}(P\oplus X)\oplus X.\end{aligned}}}$

Here multiplication ${\displaystyle \otimes }$ and addition ${\displaystyle \oplus }$ are performed in the finite field (${\displaystyle {\text{GF}}\left(2^{128}\right)}$ for AES). With some precomputation, only a single multiplication per sector is required (note that addition in a binary finite field is a simple bitwise addition, also known as xor): ${\displaystyle F\otimes I=F\otimes (I_{0}\oplus \delta )=F\otimes I_{0}\oplus F\otimes \delta }$, where ${\displaystyle F\otimes \delta }$ are precomputed for all possible values of ${\displaystyle \delta }$. This mode of operation needs only a single encryption per block and protects against all the above attacks except a minor leak: if the user changes a single plaintext block in a sector then only a single ciphertext block changes. (Note that this is not the same leak the ECB mode has: with LRW mode equal plaintexts in different positions are encrypted to different ciphertexts.)

Some security concerns exist with LRW, and this mode of operation has now been replaced by XTS.

LRW is employed by BestCrypt and supported as an option for dm-crypt and FreeOTFE disk encryption systems.

Xor–encrypt–xor (XEX)

Another tweakable encryption mode, XEX (xor–encrypt–xor), was designed by Rogaway^[7] to allow efficient processing of consecutive blocks (with respect to the cipher used) within one data unit (e.g., a disk sector). The tweak is represented as a combination of the sector address and index of the block within the sector (the original XEX mode proposed by Rogaway^[7] allows several indices). The ciphertext, ${\displaystyle C}$, is obtained using:

${\displaystyle {\begin{aligned}X&=E_{K}(I)\otimes \alpha ^{j},\\C&=E_{K}(P\oplus X)\oplus X,\end{aligned}}}$

where:

${\displaystyle P}$ is the plaintext,

${\displaystyle I}$ is the number of the sector,

${\displaystyle \alpha }$ is the primitive element of ${\displaystyle {\text{GF}}(2^{128})}$ defined by polynomial ${\displaystyle x}$; i.e., the number 2,

${\displaystyle j}$ is the number of the block within the sector.

The basic operations of the LRW mode (AES cipher and Galois field multiplication) are the same as the ones used in the Galois/Counter Mode (GCM), thus permitting a compact implementation of the universal LRW/XEX/GCM hardware.

The original XEX has a weakness.^[8]

CBC–mask–CBC (CMC) and ECB–mask–ECB (EME)

CMC and EME protect even against the minor leak mentioned above for LRW. Unfortunately, the price is a twofold degradation of performance: each block must be encrypted twice; many consider this to be too high a cost, since the same leak on a sector level is unavoidable anyway.

CMC, introduced by Halevi and Rogaway, stands for CBC–mask–CBC: the whole sector encrypted in CBC mode (with ${\displaystyle C_{-1}=E_{A}(I)}$), the ciphertext is masked by xoring with ${\displaystyle 2(C'_{0}\oplus C'_{k-1})}$, and re-encrypted in CBC mode starting from the last block. When the underlying block cipher is a strong pseudorandom permutation (PRP) then on the sector level the scheme is a tweakable PRP. One problem is that in order to decrypt ${\displaystyle P_{0}}$ one must sequentially pass over all the data twice.

In order to solve this problem, Halevi and Rogaway introduced a parallelizable variant called EME (ECB–mask–ECB). It works in the following way:

• the plaintexts are xored with ${\displaystyle L=E_{K}(0)}$, shifted by different amount to the left, and are encrypted: ${\displaystyle P'_{i}=E_{K}(P_{i}\oplus 2^{i}L)}$;
• the mask is calculated: ${\displaystyle M=M_{P}\oplus M_{C}}$, where ${\displaystyle M_{P}=I\oplus \bigoplus P'_{i}}$ and ${\displaystyle M_{C}=E_{K}(M_{P})}$;
• intermediate ciphertexts are masked: ${\displaystyle C'_{i}=P'_{i}\oplus 2^{i}M}$ for ${\displaystyle i=1,\ldots ,k-1}$ and ${\displaystyle C'_{0}=M_{C}\oplus I\oplus \bigoplus _{i=1}^{k-1}C'_{i}}$;
• the final ciphertexts are calculated: ${\displaystyle C_{i}=E_{K}(C'_{i})\oplus 2^{i}L}$ for ${\displaystyle i=0,\ldots ,k-1}$.

Note that unlike LRW and CMC there is only a single key ${\displaystyle K}$.

CMC and EME were considered for standardization by SISWG. EME is patented, and so is not favored to be a primary supported mode.^[18]