06. Block Cipher Modes of Operation

Block ciphers encrypt single blocks of data, but many applications require multiple blocks to be encrypted sequentially and breaking the plaintext into blocks and encrypting them separately can be insecure.

Modes of operation are standardized with different security and efficiency characteristics.

NIST has many standards (e.g. SP 800-38 series) for this.

Important Features of Different Modes

Different modes can provide confidentiality, authentication (and integrity) or both.

Modes for confidentiality normally include randomization.

Different modes have different efficiency and communication properties.

Randomized Encryption

Problem: the same plaintext block is encrypted to the same ciphertext block every time - allows patterns to be found in long ciphertexts.

Prevention: randomizing encryption schemes by using an initialization vector (IV) which propagates through the entire ciphertext. It may need to be either random or unique.

Alternatively, there could be a variable state which is updated with each block.

Efficiency

Parallel processing: encrypting/decrypting multiple plaintext/ciphertext blocks in parallel.

Error propagation: a bit error in the ciphertext which results in multiple bit errors in the plaintext after decryption.

Padding

Requiring the plaintext to consist of complete blocks.

NIST suggested padding method: append a single $1$ bit to the data string, then with $0$ s until the last block is completed.

Notation

Plaintext message $P$ of length $n$ blocks
$t$ -th plaintext block $P_t$ for $1 \le t \le n$
Ciphertext message $C$
$t$ -th ciphertext block $C_t$ for $1 \le t \le n$
Key $K$
Initialization vector $IV$

Modes can be applied to any block cipher.

Confidentiality Modes

Electronic Code Book (ECB) Mode

A basic mode of a block cipher; each block is encrypted with a key, IV is not used.

Encryption

C_t = E(P_t, K)

Decryption

P_t = D(C_t, K)

Properties

Randomized	Padding	IV	Parallel encryption	Parallel decryption
No	Required	None	Yes	Yes

Error propagation: within blocks.

Cipher Block Chaining (CBC) Mode

Blocks chained together: the plaintext XORed with previous ciphertext (or IV for the first block) and then encrypted.

Encryption

C_t = E(P_t \oplus C_{t - 1}, K)

for $1 \le t \le n$ where $C_0 = IV$ .

Decryption

P_t = D(C_t, K) \oplus C_{t - 1}

Where $C_0 = IV$ .

Properties

Randomized	Padding	IV	Parallel encryption	Parallel decryption
Yes	Required	Random	No	Yes

Error propagation: within blocks and into specific bits in the next block.

Parallel decryption means that decryption does not require the plaintext of previous block. However, it does require the ciphertext of the previous block.

Commonly used for bulk encryption, was often used in TLS up to TLS 1.2.

Counter (CTR) Mode

Synchronous stream cipher mode.

Encryption

The counter and a nonce (IV) are initialized using a random value $N$ :

T_t = N \| t

That is, $T_t$ is the concatenation of the nonce $N$ with the block number $t$ .

Then, this result is encrypted with the key $K$ :

O_t = E(T_t, K)

Finally, it is XORed with the plaintext block $P_t$ :

\begin{aligned} C_t &= O_t \oplus P_t \\ &= E(N \| t, K) \oplus P_t \end{aligned}

Decryption

P_t = O_t \oplus C_t

Properties

Randomized	Padding	IV	Parallel encryption	Parallel decryption
Yes	Optional	Unique	Yes	Yes

A one-bit change in ciphertext produces one-bit change in the plaintext at the same location.

This allows access to specific plaintext blocks without decrypting the whole stream.

CTR mode is the basis for authenticated encryption in TLS 1.2.

Authentication Mode

Message Integrity

Ensuring messages are not altered in transmission: preventing an adversary from re-ordering, replacing, replication and deleting message blocks to alter the received message.

Message integrity and authentication are treated as the same thing.

Proving message integrity is independent from using encryption for confidentiality.

Message Authentication Code (MAC)

T = \mathrm{MAC}(M, K)

Where $M$ is an arbitrary-length message and $K$ a secret key $K$ .

The output $T$ is a short, fixed-length tag.

Given both parties share the key $K$ :

The sender computes $T = (M, K)$
The message $M$ and tag $T$ are sent
The receiver computes $T' = \mathrm{MAC}(M', K)$ on the received message $M'$ and checks that $T' = T$

MAC Properties

Only the sender and receiver can produce $T$ from $M$ .

If $T' = T$ , the receiver can conclude the message received is from the expected sender and has not been modified in transit. Otherwise, the receiver can conclude $(M', T)$ was not sent by the expected sender.

It has the basic security property of unforgeability: it is infeasible to produce $M$ and $T$ such that $T = \mathrm{MAC}(M, K)$ without knowledge of $K$ .

Basic CBC-MAC

Using block cipher to create a MAC providing message integrity (but not confidentiality).

If $P$ is the message with $n$ blocks:

C_t = E(P_t \oplus C_{t - 1}, K)

For $1 \le t \le n$ such that $C_0 = IV$ .

$T = \mathrm{CBC\text{-}MAC}(P, K)$ is the last cyphertext: $T = C_n$ .

It is unforgeable as long as the message length is fixed.

$IV$ must be fixed and public (e.g. all zeroes): CBC-MAC with a random IV is NOT secure:

If the IV is random, the IV needs to be sent along with the MAC
$C_0 = E(P_t \oplus IV, K)$
Hence, the attacker can modify $P_t$ and $IV$ together such that XORing them gives the same result. As $C_0$ is not modified, none of the subsequent ciphertexts (and hence the tag) stays unchanged

Cipher-based MAC (CMAC)

Standardized, NIST version of CBC-MAC. The IV is all zeroes. The below is as per RFC4493.

Two keys $K_1$ and $K_2$ are derived from the original key $K$ .

$K_1$ OR $K_2$ is XORed with $M_n$ (with padding as necessary).

For $1 \le t \le n - 1$ and $C_0 = IV = 00\dots00$ :

C_t = E(P_t \oplus C_{t - 1}, K)

For the final block:

P_n' = \begin{cases} K_1 \oplus P_n , & \text{block complete} \\ K_2 \oplus (P_n \| 100\dots00_2), & \text{block incomplete} \end{cases}

(That is, $P_n$ concatenated with 1 and then enough zeros to fill up a block)

Then do the same operation as with the previous blocks , except that $P_n'$ is used:

C_n = E(P_n' \oplus C_{n - 1}, K)

Finally, $\mathrm{CMAC}(P, K) = \mathrm{MSB}_{Tlen}(C_n)$

NIST allows the length of the tag, $Tlen$ , to be any number of bits, although 64 bits or greater is recommended.

The standard recommends the MAC tag $T$ to be of at least length $\mathrm{log}_2(lim/R)$ where:

$lim$ is a limit on how many invalid messages are detected before $K$ is changed
$R$ is the acceptable probability that a false message is accepted

Authenticated Encrypted Mode

Two types of input data:

Payload: both encrypted and authenticated
Associated data: only authenticated

NIST specifies two modes:

NIST SP-800-38C (2004) for Counter with CBC-MAC
NIST SP-800-38D (2007) for Galois/Counter (GCM)

Both use CTR mode but add integrity in different ways.

Both are used in TLS 1.2 and 1.3.

Counter with CBC-MAC (CCM) Mode

CBC-MAC for authentication of all data, CTR mode encryption for the payload.

Inputs:

Nonce $N$ for CTR mode
Payload $P$ of $Plen$ bits
Associated data $A$

Compute the CBC-MAC tag, getting $T$ with length $Tlen$ .

Split the message $M$ into blocks of $128$ bits. That is, into $m = \lceil Plen/128 \rceil$ blocks:

S = S_0 \| S_1 \| \dots S_m

Then, use CTR mode to compute blocks.

C = (P \oplus \mathrm{MSB}_{Plen}(S)) \| (T \oplus \mathrm{MSB}_{Tlen}(S_0))

From RFC3610:

Authentication using CBC-MAC:
- Blocks $B_0 \dots B_n$ generated. $B_0$ contains the metadata such as the nonce, payload length etc. Later blocks contain the payload and associated data.
  
  $\begin{aligned} &X_i = \begin{cases} E(B_0, K), & i = 0 \\ E(B_i \oplus X_{i - 1}, K), & i = 1, \dots, n \end{cases} \\ \\ &T = \text{MSB}_{\text{Tlen}}(X_n) \end{aligned}$
Encryption using CTR mode:
- Generate a keystream $S_i = E(\text{Flags} \| N \| i)$ where $i$ is the block number.
- Output message $C_i = S_i \oplus P_i$ . $S_i$ starts with $S_1$ , not $S_0$
- Output authentication value $U = T \oplus S_0$
Decryption requires key $K$ , nonce $N$ , authenticated data $A$ and ciphertext $C$
- Authenticated data must be sent separately!

CCM Mode Format

Lengths of $N$ and $P$ are included in the first block.

If $A$ is non-zero, then formatted from the second block onwards, including its length.

e.g. TLS 1.2: $T$ 8 bytes, $N$ 12 octets, max payload size $2^{24} - 1$ bytes.