Consider message $P$ being split into $n$ blocks that match the block size of the underlying block cipher. The message has fixed length and the length is always a multiple of the block size.

Encryption using CTR mode: \begin{align} C_0 &= P_0 \oplus E_k(nonce\mathbin\|0) \\ C_1 &= P_1 \oplus E_k(nonce\mathbin\|1) \\ \vdots & \quad\quad\vdots\\ C_{n-1} &= P_{n-1} \oplus E_k(nonce\mathbin\|(n-1)) \end{align}

Why is the following MAC tag not secure: $T = (P_0 \oplus P_1 \oplus \cdots P_{n-1}) \oplus E_k(nonce\mathbin\||n)$ ?

  • 2
    $\begingroup$ Welcome to Cryptography.SE. What is the origin of this question? Have you ever heard of the bit flipping attack on CTR mode? $\endgroup$ – kelalaka May 22 at 11:15
  • $\begingroup$ Hint: Besides bitflipping, what happens when you use even number of identical blocks? What happens if you now replace the said identical blocks with a different but still identical blocks. $\endgroup$ – Manish Adhikari May 22 at 12:17

Bit flipping

Flip the bit in the position $x$ on ciphertext block $C_i$ then on the block $C_j$ where $i \neq j$ and similarly for the plaintext $P_i$ and $P_j$. The the new MAC result

$$T = (P_0 \oplus P_1 \oplus \cdots \oplus \bar{P_i} \oplus \cdots \oplus \bar{P_j} \oplus \cdots \oplus P_{n-1}) \oplus E_k(nonce||n)$$ will be the same for the plaintext $Q = (P_0\mathbin\| P_1 \mathbin| \cdots \mathbin\|\bar{P_i}\mathbin\|\cdots \mathbin\|\bar{P_j}\mathbin\|\cdots \mathbin\|P_{n-1})$

Now, send $(Q,T)$ as the message and the tag to the target and they will accept it as a valid tag. This flipping is not related to a single position. The attacker can choose more than one position as longs as the resulting x-or is the same.


Flip is $\bar{x} := x \oplus 1 $ then

\begin{align} \bar{C_i} &= \bar{P_i} \oplus E_k(nonce\mathbin\|i-1)\\ C_i \oplus 1 &= P_i \oplus 1 \oplus E_k(nonce\mathbin\|i-1)\\ C_i &= P_i \oplus E_k(nonce\mathbin\||1)\\ \end{align}

So $\bar{C_i}$ and $\bar{P_i}$ work as an attack on the ciphertext. The tag calculates on the messages, therefore one-bit change will be not enough. We need to modify even pairs exactly at the same positions.


Bit flipping attack:

The attacker can flip e.g. bit 0 in $C_0$ and flip bit 0 in $C_1$. Due to the construction of CTR, any change to the ciphertext will lead to an identical change in the plaintext.

Changing the same bits in an even number of blocks will lead to a collision in the checksum, resulting in the same $T$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.