Modes of Operation

Try a demo of

Encoding schemes: From characters to integers and bits

In cryptography we often encrypt and sign messages that contains characters, but asymmetric key cryptosystems (Alice and Bob uses different keys) such as RSA and ElGamal are based on arithmetic operations on integer. And symmetric key cryptosystems (Alice and Bob uses the same key) such as DES and AES are based on bitwise operations on bits (a bit is either equal 0 or 1 and is an abbreviation for binary digit). Therefore, we have to convert the characters into integers or bits before we apply the cryptosystem to the message.

Because a computer can only handle bits, there already exists a method for converting characters into integers or bits, that uses the ASCII (American Standard Code for Information Interchange) table. A part of the ASCII table from Wikipedia is listed in the following table (notice that the binary representation on the Wikipedia site is only seven bits but we use eight bits, i.e. we have prepended an extra 0):

(space) 32 20 00100000
! 33 21 00100001
$\vdots$ $\vdots$ $\vdots$ $\vdots$
A 64 40 01000001
B 66 42 01000010
$\vdots$ $\vdots$ $\vdots$ $\vdots$
a 97 61 01100001
b 98 62 01100010
$\vdots$ $\vdots$ $\vdots$ $\vdots$

E.g. if Alice wants to send the message "Hey Bob!" encrypted to Bob with a symmetric key cryptosystem, she first converts it into its integer representation and then into its binary representation:

\eqalign{ H &\rightarrow 72 &&\rightarrow 01001000 \\ e &\rightarrow 101 &&\rightarrow 01100101 \\ y &\rightarrow 121 &&\rightarrow 01111001 \\ &\rightarrow 32 &&\rightarrow 00100000 \\ B &\rightarrow 66 &&\rightarrow 01000010 \\ o &\rightarrow 111 &&\rightarrow 01101111 \\ b &\rightarrow 98 &&\rightarrow 01100010 \\ ! &\rightarrow 33 &&\rightarrow 00100001 }

I.e. the message "Hey Bob!" is represented with integers as "72 101 121 32 66 111 98 33" and in binary as "01001000 01100101 01111001 00100000 01000010 01101111 01100010 00100001".

Bitwise operators

In math we are all familiar with the arithmetic operations such as addition, subtraction, multiplication and division. However, a computer works on bit strings, i.e. strings of 0's and 1's, and therefore needs similar operations when given two bit strings. The most important bitwise operations are NOT, AND, OR and XOR. In the following we give the result of the operations with one or two bits as input.

The NOT operation is often represented as !:

• $!0 = 1$
• $!1 = 0$

The AND operation is represented as $\wedge$:

• $0 \wedge 0 = 0$
• $1 \wedge 0 = 0$
• $0 \wedge 1 = 0$
• $1 \wedge 1 = 1$

The OR operation is represented as $\vee$:

• $0 \vee 0 = 0$
• $1 \vee 0 = 1$
• $0 \vee 1 = 1$
• $1 \vee 1 = 1$

The XOR (exclusive OR) operation is represented as $\oplus$:

• $0 \oplus 0 = 0$
• $1 \oplus 0 = 1$
• $0 \oplus 1 = 1$
• $1 \oplus 1 = 0$

PRF- and CPA-security of symmetric key cryptosystems

Alice and Bob's adversary Eve can make the following types of attacks on a symmetric key cryptosystem such as DES and AES:

• Ciphertext only attack: Eve tries to guess the key used to encrypt an observed ciphertext sent between Alice and Bob.
• Known plaintext attack: Eve somehow know the plaintext of an observed ciphertext sent between Alice and Bob and tries to guess the key.
• Chosen plaintext attack (CPA): Eve cheats Alice or Bob to encrypt a message of her choice and with her knowledge of the ciphertext and plaintext she tries to guess the used key.
• Chosen ciphertext attack (CCA): Eve can send a ciphertext to Alice or Bob and they return the decrypted message. With her knowledge of the ciphertext and plaintext she tries to guess the used key.

Symmetric key cryptosystems can be divided into two groups; deterministic and probabilistic cryptosystems. A deterministic cryptosystem such as DES and AES uses no randomness during the encryption, i.e. the same plaintext encrypted twice with the same key returns always the same ciphertext (which can be observed by Eve). This problem can be solved with a probabilistic cryptosystem such as the various modes of operations there exists for DES and AES, which uses randomness in form of an initialization vector.

In a good deterministic cryptosystem there should be no relation between the plaintext and ciphertext whatsoever when the key is unknown, i.e. encryption in a deterministic cryptosystem should behave like a truly random function. If this is the case we say that the encryption function is a pseudo-random function (PRF) and the cryptosystem is PRF-secure if Eve's advantage in guessing correct in the following game is negligible:

Eve sends a message $m$ to an oracle and it returns a ciphertext $c$ where $c$ is either an encryption of $m$ using the encryption function of the cryptosystem or an encryption of $m$ using a truly random function. Eve then tries to guess which encryption function the oracle used.

With a probabilistic cryptosystem we can achieve higher security compared to a deterministic cryptosystem and therefore we require that Eve can't tell the difference between a real encryption of hers message $m$ and an encryption of a random message with no relation at all to $m$. We say that a probabilistic cryptosystem is CPA-secure if Eve's advantage in guessing correct in the following game is negligible:

Eve sends a message $m$ to an oracle and it returns a ciphertext $c$ where $c$ is either an encryption of $m$ or a random message with the same length as $m$. Eve then tries to guess what $c$ is an encryption of.

Hence, if a probabilistic cryptosystem is CPA-secure the only information that a ciphertext leaks is the length of the encrypted message.

The cryptography explained

A block cipher such as DES or AES only encrypts one block of a fixed size (56-bit for DES and 128-bit for AES), but often the data we want to encrypt (the plaintext) is larger than 56-bit or 128-bit. This problem is solved by using a mode of operation which describes how to repeatedly apply DES or AES (both encryption and decryption) on plaintexts (and ciphertexts) with size larger than one block.

Most modes of operation requires an initialization vector, denoted $IV$ (or $ctr$ in one of the mode of operation), which is a random bit string with the same length as a block, i.e. either 56-bit or 128-bit. The initialization vector adds randomness to the encryption, i.e. if we encrypt the same plaintext twice with the same key, but with different initialization vectors, the corresponding ciphertexts have no relation at all. It's therefore important that the initialization vector is unique for every encryption but it doesn't need to be secret, because as you may see in the following they are added to the ciphertext after encryption.

In 1980 the first four modes of operation was developed for DES (which also can be used with AES):

• The electronic codebook (ECB) mode
• The cipher block chaining (CBC) mode
• The cipher feedback (CFB) mode
• The output feedback (OFB) mode

Later in 2001 NIST (the US National Institute of Standards and Technology) added the following mode of operation for AES:

• The counter (CTR) mode

The size of the key $K$ used in a mode of operation depends on the used block cipher, i.e. whether it is DES or AES. For DES is the key 56-bit and for AES is the key 128-, 192- or 256-bit. In the following we assume that the plaintext $m$ can be evenly divided into $t$ blocks $m_{1}, m_{2}, \dots, m_{t}$.

So, what if the last block of the plaintext $m_{t}$ is shorter than the size of one block, i.e. shorter than 56-bit or 128-bit? Because DES and AES only works on blocks of 56-bit and 128-bit respectively we have to pad $m_{t}$ such that it has the correct length. There exists various ways of padding the blocks but as you may see in the demo we add the missing $p$ bytes $p$ times, all with value $p$, at the end of $m_{t}$. E.g. if we want to encrypt the message "Hello Alice" with AES and the length of this message is 368 bit, we can divide it into three blocks $m_{1}, m_{2}, m_{3}$. Now $m_{1}$ and $m_{2}$ each are 128 bit, as they should, but $m_{3}$ is only 112 bit, i.e. we need 16 bit. Because 16 bit is the same as 2 byte (8 bit is 1 byte) we pad $m_{3}$ with "22", i.e. we actually encrypt the message "Hello Alice22".

In the mode of operation we present it's only the ECB and CBC modes which requires the last block padded before encryption if it's to short. The stream ciphers such as CFB, OFB and CTR mode doesn't require padding because the plaintext is XORed with a key stream.

The electronic codebook (ECB) mode corresponds to the naive use of the block cipher, i.e. given the plaintexts $m_{1}, m_{2}, \dots, m_{t}$ each plaintext is encrypted with the same key $K$ and produces the ciphertexts $c_{1}, c_{2}, \dots, c_{t}$. The same method is used in decryption, i.e. $c_{i} = E_{K}(m_{i})$ and $m_{i} = D_{K}(c_{i})$ where $E_{K}$ is the encryption algorithm and $D_{K}$ is the decryption algorithm. Therefore, in ECB mode will the encryption of the same plaintext always result in the same ciphertext, which is a serious weakness if the plaintext space is small.

In the cipher block chaining (CBC) mode is the first ciphertext block (for encryption) equal the initialization vector $IV$ and the remaining $t$ ciphertext blocks are the encryption of the $i$-th plaintext block XORed with the previous ciphertext block, i.e. $c_{0} = IV$ and $c_{i} = E_{K}(c_{i-1} \oplus m_{i})$. During decryption is the $i$-th plaintext block computed by first decrypting the $i$-th ciphertext block and then XOR it with the previous ciphertext block, i.e. $m_{i} = D_{K}(c_{i}) \oplus c_{i-1}$. Notice that if the plaintext block $m_{i}$ during encryption is altered then $c_{i}$ and all subsequent ciphertext blocks will be affected. This property makes the CBC mode very useful for authentication and is used in the CBC-MAC.

The output feedback (OFB) mode uses a key stream $z_{1}, z_{2}, \dots, z_{t}$ where the first block in the key stream $z_{0}$ is equal the initialization vector $IV$ and the remaining $t$ blocks are the encryption of the previous block, i.e. $z_{0} = IV$ and $z_{i} = E_{K}(z_{i-1})$. The key stream is used during encryption and decryption where the $i$-th ciphertext is the XOR of the $i$-th plaintext and the $i$-th key stream, i.e. $c_{i} = m_{i} \oplus z_{i}$, and the $i$-th plaintext is the XOR of the $i$-th ciphertext and the $i$-th key stream, i.e. $m_{i} = c_{i} \oplus z_{i}$. Notice that only the encryption algorithm is used which makes it suitable for small devices with limited computer power such as chip cards etc.

The cipher feedback (CFB) mode also uses a key stream where the $i$-th key stream is the encryption of the previous ciphertext block, i.e. $z_{i} = E_{K}(c_{i-1})$. During encryption is the first ciphertext block equal the initialization vector $IV$ and the remaining $t$ ciphertext blocks are the XOR of the $i$-th plaintext block and the $i$-th key stream, i.e. $c_{0} = IV$ and $c_{i} = m_{i} \oplus z_{i}$. Decryption is almost the same with $m_{i} = c_{i} \oplus z_{i}$. Notice again that only the encryption algorithm is used.

The counter (CTR) mode is similar to the OFB mode, but with the key stream generated slightly different. In the CTR mode is the initialization vector called a counter vector and is denoted $ctr$. The key stream is then the XOR of $ctr$ and the counter $i$, i.e. $T_{i} = ctr \oplus i \; mod \; 2^{n}$ where $n$ is the block size in byte. During encryption is the $i$-th ciphertext block equal the XOR of the $i$-th plaintext block and the encryption of the $i$-th key stream, i.e. $c_{i} = m_{i} \oplus E_{K}(T_{i})$. During decryption is the $i$-th plaintext equal the XOR of the $i$-th ciphertext block and the encryption of the $i$-th key stream, i.e. $m_{i} = c_{i} \oplus E_{K}(T_{i})$. Notice that the encryption algorithm is used in both encryption and decryption and the key stream is only the XOR of $ctr$ and the counter $i$, i.e. we can run CTR mode in parallel because the key stream doesn't depend on previously blocks.

It's recommended to use either CBC or CTR mode where CTR mode has the advantage that it's fast because it can run in parallel and it only use the encryption algorithm.

The electronic codebook (ECB) mode algorithm
 Key exchange Alice and Bob agree on the key $K$. Encryption Alice: Uses the key $K$ with the encryption algorithm $E$ to encrypt plaintext blocks $m_{i}$ by $c_{i} = E_{K}(m_{i})$. Alice sends the ciphertext blocks $c$ to Bob. Decryption Bob: Uses the key $K$ with the decryption algorithm $D$ to decrypt ciphertext blocks $c_{i}$ by $m_{i} = D_{K}(c_{i})$.
The cipher block chaining (CBC) mode algorithm
 Key exchange Alice and Bob agree on the key $K$. Encryption Alice: Generates a random initialization vector $IV$ with same length as the block size. Uses the key $K$ with the encryption algorithm $E$ to encrypt plaintext blocks $m_{i}$ by $c_{0} = IV$ and $c_{i} = E_{K}(c_{i-1} \oplus m_{i})$. Alice sends the ciphertext blocks $c$ to Bob. Decryption Bob: Uses the key $K$ with the decryption algorithm $D$ to decrypt ciphertext blocks $c_{i}$ by $c_{0} = IV$ and $m_{i} = D_{K}(c_{i}) \oplus c_{i-1}$.
The output feedback (OFB) mode algorithm
 Key exchange Alice and Bob agree on the key $K$. Encryption Alice: Generates a random initialization vector $IV$ with same length as the block size. Uses the key $K$ with the encryption algorithm $E$ to encrypt plaintext blocks $m_{i}$ by $z_{0} = IV$, $z_{i} = E_{K}(z_{i-1})$ and $c_{i} = m_{i} \oplus z_{i}$. Alice sends the ciphertext blocks $c$ to Bob. Decryption Bob: Uses the key $K$ with the encryption algorithm $E$ to decrypt ciphertext blocks $c_{i}$ by $z_{0} = IV$, $z_{i} = E_{K}(z_{i-1})$ and $m_{i} = c_{i} \oplus z_{i}$.
The cipher feedback (CFB) mode algorithm
 Key exchange Alice and Bob agree on the key $K$. Encryption Alice: Generates a random initialization vector $IV$ with same length as the block size. Uses the key $K$ with the encryption algorithm $E$ to encrypt plaintext blocks $m_{i}$ by $c_{0} = IV$, $z_{i} = E_{K}(c_{i-1})$ and $c_{i} = m_{i} \oplus z_{i}$. Alice sends the ciphertext blocks $c$ to Bob. Decryption Bob Uses the key $K$ with the encryption algorithm $E$ to decrypt ciphertext blocks $c_{i}$ by $c_{0} = IV$, $z_{i} = E_{K}(c_{i-1})$ and $m_{i} = c_{i} \oplus z_{i}$.
The counter (CTR) mode algorithm
 Key exchange Alice and Bob agree on the key $K$. Encryption Alice: Generates a random initialization vector $ctr$ with same length as the block size. Uses the key $K$ with the encryption algorithm $E$ to encrypt plaintext blocks $m_{i}$ by $T_{i} = ctr \oplus i \; mod \; 2^{n}$ and $c_{i} = m_{i} \oplus E_{K}(T_{i})$ where $i \geq 0$ and $n$ is the block size in byte. Alice sends the ciphertext blocks $c$ to Bob. Decryption Bob: Uses the key $K$ with the encryption algorithm $E$ to decrypt ciphertext blocks $c_{i}$ by $T_{i} = ctr \oplus i \; mod \; 2^{n}$ and $m_{i} = c_{i} \oplus E_{K}(T_{i})$ where $i \geq 0$ and $n$ is the block size in byte.
Decryption

Try a demo of the encryption scheme using one of the mode of operation here.

Example

Alice needs to send an email $m$ to Bob that contains sensitive information, and hence, she encrypts the email before she sends it to Bob. They first agree on using AES in CTR mode and the 128-bit key $K = 01001000 \dots$.

Alice then divides the email $m$ into 128-bit blocks. Assume that the email fits into three blocks $m_{1}, m_{2}, m_{3}$ and the 128-bit counter vector is $ctr = 00000110 \dots$. She then encrypts the plaintext blocks by first computing the keystream $T_{i} = ctr \oplus i \: mode \: 2^{16}$ (where $n = 16$ because 128 bit is equal to 16 byte), and then encrypting the $i$-th plaintext block by $c_{i} = m_{i} \oplus E_{K}(T_{i})$:

\eqalign{ T_{1} &= ctr \oplus 1 \; mod \; 2^{128} = 00000110 \dots \\ c_{1} &= m_{1} \oplus E_{K}(T_{1}) = 11010101 \dots \\ T_{2} &= ctr \oplus 2 \; mod \; 2^{128} = 10000110 \dots \\ c_{2} &= m_{2} \oplus E_{K}(T_{2}) = 10100101 \dots \\ T_{3} &= ctr \oplus 3 \; mod \; 2^{128} = 10000110 \dots \\ c_{3} &= m_{3} \oplus E_{K}(T_{3}) = 10111001 \dots }

She then sends the ciphertext blocks $c_{1}, c_{2}, c_{3}$ to Bob.

Bob decrypts the received ciphertext blocks by first computing the key stream just as Alice did, i.e. $T_{i} = ctr \oplus i \: mode \: 2^{16}$, and then decrypting the $i$-th ciphertext block by $m_{i} = c_{i} \oplus E_{K}(T_{i})$:

\eqalign{ T_{1} &= ctr \oplus 1 \; mod \; 2^{128} = 00000110 \dots \\ m_{1} &= c_{1} \oplus E_{K}(T_{1}) = 01010100 \dots \\ T_{2} &= ctr \oplus 2 \; mod \; 2^{128} = 10000110 \dots \\ m_{2} &= c_{2} \oplus E_{K}(T_{2}) = 01100101 \dots \\ T_{3} &= ctr \oplus 3 \; mod \; 2^{128} = 10000110 \dots \\ m_{3} &= c_{3} \oplus E_{K}(T_{3}) = 01111001 \dots }

The plaintext is then the concatenation of the plaintext blocks, i.e. $m = m_{1} \: \| \: m_{2} \: \| \: m_{3}$.