Bit Flipping Attack on CBC Mode

Question

To perform a bit flipping attack, the previous block is modified by using XOR. This results in an altered plaintext. However, now the ciphertext of the previous block is altered, hence it will result in an invalid format. Am I correct or am I missing something?

For example, suppose I have the following plaintext name=jcconvenant;photo=picture.jpg;admin=false;colour=red;

and the correspoding ciphertext c26a5697689463d662f540e55e2a1ecef9c5df20133dfe49d6d3c369679a95ff4f4c5a490f530b2a2f25db40da64f1e9302724ce61b9a435e23f4d600252a143

Suppose we perform a bit flipping attack and get the following ciphertext c26a5697689463d662f540e55e2a1ecef9c5df20133dfe49d6c1d07071c495ff4f4c5a490f530b2a2f25db40da64f1e9302724ce61b9a435e23f4d600252a143

Then the resulting plaintext will still look corrupted.

¶ä╚° h8ì│►Nƒz│Ioé¤ßkü2KÀQiý4I@pg;admin=true;;colour=red;

Is there a way to perform bit flipping while still obtaining a valid plaintext?

Answer 1

The Bit Flipping attack

Decryption process in CBC mode is performed as \begin{align} P_1 =& Dec_k(C_1) \oplus IV\\ P_i =& Dec_k(C_i) \oplus C_{i-1},\;\; 1 < i \leq nb, \end{align} where $nb$ is the number of blocks.

If you know the position of the target byte, then you can modify the corresponding ciphertext position in the previous ciphertext block. For example; if you modify a byte in the ciphertext $C_{i-1}$, then $P_i$ will be changed by one block since $C_{i-1}$ only affects the plaintext $P_i$ by $\oplus$. We can see visually in the below figure;

$\color{red}{\textbf{Red case:}}$ A ciphertext byte of $C_2$ modified. This affects the corresponding byte in the next plaintext block $P_3$ and the corresponding full plaintext block $P_2$ which has the same index as the modified ciphertext which is garbage. This can be seen as there is an error.

$\color{ForestGreen}{\textbf{Green case:}}$ an $\text{IV}$ byte is modified (green), this affects only the corresponding byte in the first plaintext $P_1$. If the target plaintext is in the first block, this will not leave a trace.

An example

Consider this simple message

msg = "Buy 1000 lots of waffles"

Now the attacker intercepts the message and now the default structure and want to modify it into

msg = "Buy 5000 lots of waffles"

Here is the sample Python code ( the full code is here );

def bitFlip( pos, bit, data):
    raw = b64decode(data)

    list1 = list(raw)
    list1[pos] = chr(ord(list1[pos])^bit)
    raw = ''.join(list1)
    return b64encode(raw)

With a call ctx = bitFlip(4,4,ctx) changes the 1 into 5.

This is the green case attack, that leaves no garbage block. Some file formats, like PDF, can live with the red case attack.

A Little Theory

CBC mode for encryption can only provide Ind-CPA security. CPA security doesn't resist active attacks, like CCA (See this post Ind- notions for details). Therefore an active attacker can modify the pure CBC ciphertext on their behalf. If the message format is known, this can cause devastating effects especially if the important part is in the first block.

The Mitigation

The attack is possible since there is no integrity and authentication on the data. A MAC or an HMAC can be used to prevent this like AES-CBC-HMAC if the CBC mode is a must to use.

In other cases, it is better to use modern encryption schemes. The authenticated encryption with Associated Data (AEAD) which provides confidentiality, integrity, and authenticity. The examples are AES-GCM and ChaCha20-Poly1305. In TLS 1.3., CCM,GCM, and poly1305 are standardized authenticated encryption modes.

There are alternatives to the above like AES-GCM-SIV which is designed to resist the (nonce,key) pair resue problem of the CTR based encryptions ( all of TLS 1.3 has) and xChaha20-Poly1305 that uses 192-bit nonces to reduce the chance of collision into very low probability.