Counter Mode

cryptography

Definition

Counter Mode

Counter mode is a mode of operation for a block cipher in which the cipher is applied to a sequence of nonce-counter values to generate a keystream.

Mechanism

Counter mode does not encrypt the plaintext blocks directly. Instead, it encrypts a sequence of inputs derived from a nonce and a counter. The resulting block sequence is used as a keystream, which is XORed with the plaintext.

This makes CTR behave like a stream cipher built from a block cipher.

Encryption

For plaintext block $P_i$:

$$C_i=P_i\oplus E_k(N\parallel ct{r}_i)$$

¹

Decryption

Decryption uses the same keystream:

$$P_i=C_i\oplus E_k(N\parallel ct{r}_i)$$

¹

The plaintext blocks do not influence the keystream. For fixed key $k$, nonce $N$, and counter values $ct{r}_1,\dots ,ct{r}_n$, the keystream is fixed in advance.

Properties

Parallelisation

Encryption and decryption can be fully parallelised, and random read access is possible.

Error Propagation

A bit flip in a ciphertext block causes a bit flip at the corresponding position in the plaintext. A bit flip in the nonce produces unpredictable errors in all decrypted blocks.

Same keystream for encryption and decryption

Let

$$K_i=E_k(N\parallel ct{r}_i).$$

Then encryption computes

$$C_i=P_i\oplus K_i,$$

and decryption computes

$$P_i=C_i\oplus K_i.$$

The same keystream block $K_i$ is used in both directions.

Malleability

Because ciphertext is obtained by XORing plaintext with a keystream, modifying the ciphertext modifies the plaintext in a predictable way.

Suppose a ciphertext block satisfies

$$C=P\oplus K$$

for some keystream block $K$. If an attacker replaces $C$ by

$$C^{\prime }=C\oplus \Delta ,$$

then the decrypted plaintext becomes

$$P^{\prime }=C^{\prime }\oplus K=(C\oplus \Delta )\oplus K=P\oplus \Delta .$$

So an attacker can force a chosen plaintext change by choosing the same XOR difference in the ciphertext.

This is why CTR provides confidentiality, but not integrity protection.

Changing one field value

Suppose part of the plaintext contains the ASCII string logs, and the attacker wants the decrypted plaintext to contain flag instead.

The attacker computes

$$\Delta =\text{logs}\oplus \text{flag}$$

and XORs the corresponding ciphertext bytes with $\Delta$.

The modified ciphertext then decrypts to flag at exactly that position.

logs to flag

In ASCII:

$$\begin{array}{rl}\text{l}\oplus \text{f}& =\text{0a}\\ \text{o}\oplus \text{l}& =\text{03}\\ \text{g}\oplus \text{a}& =\text{06}\\ \text{s}\oplus \text{g}& =\text{14}\end{array}$$

Therefore, the required XOR difference is:

$$\text{0a030614}$$

If these four bytes are XORed into the ciphertext at the position corresponding to logs, the decrypted plaintext becomes flag.

Why equal length matters

The same method works cleanly only when the old and new plaintext fragments have the same length.

For example, logs can be changed to flag, since both strings have length $4$.

In contrast, logs cannot be changed to secret by modifying only the corresponding ciphertext bytes, since the two strings have different lengths. CTR malleability lets the attacker change bytes in place, but it does not let the attacker insert or remove bytes.

Nonce

CTR mode requires that the nonce be unique for each encryption under the same key. If the same nonce is reused, then the same keystream is reused, which breaks security.

Nonce reuse

Suppose two plaintexts $P$ and $P^{\prime }$ are encrypted under the same key and the same nonce. Then the same keystream $K$ is used for both, so

$$C=P\oplus K\text{and}{C}^{\prime }=P^{\prime }\oplus K.$$

Therefore,

$$C\oplus C^{\prime }=P\oplus P^{\prime }.$$

The keystream cancels out, so the relation between the two plaintexts is exposed.

Footnotes

1. 192.019 Introduction to Security ↩ ↩²