Bitflip Attack on CBC: Change of the IV

Given an AES-CBC encrypted ciphertext, it is possible to change the outcome of the decryption in a predictable way: If you know some bytes of the first plaintext block, you can change these bytes by changing the initialization vector (IV). This is one type of a so called bitflip attack. It doesn't matter if we use AES or some other block cipher. But I will demonstrate the attack with AES-256. To follow this tutorial, you'll only need a shell on a *nix operating system with the OpenSSL command line utility installed.

I won't explain the details of CBC; if you're not familiar with it, I recommend the relevant section of Crypto 101. There you'll find also the description of a more realistic use case for bitflip attacks, that is: smuggling content into encrypted cookies.

Let's say, the original plaintext is <p>Hello World!</p>, encoded in UTF-8 or some similar encoding scheme (similar in the sense that one ASCII character is encoded by one byte and that the encoding is an extension of ASCII).

To generate the ciphertext, we need a 256-bit key and an IV with the length of one
block, i.e. 128 bit. We'll use be154e2343408caa1f11ab3445bdd34c as IV and
be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c as key (both are given here in hexadecimal representation).

We generate the ciphertext with OpenSSL:

$ echo "<p>Hello World!</p>" | openssl enc -aes-256-cbc \
    -iv be154e2343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c \
    > ciphertext.enc

Let's assume that we want the decrypted text to be :) Hello World!</p>. This means that the IV must be changed so that <p> (3c703e in hexadecimal UTF-8 representation) becomes :)_ (3a2920 in hexadecimal UTF-8 representation), where _ denotes a whitespace character.

To generate the new IV, take the first three bytes of the original IV, say abc, and calculate:

  abc XOR ("<p>" XOR ":) ")
= be154e XOR (3c703e XOR 3a2920)

I'll explain below why this does the trick. First the calculation:

    0011 1100 0111 0000 0011 1110 (3c703e, original plaintext, "<p>")
XOR 0011 1010 0010 1001 0010 0000 (3a2920, desired output, ":) ")
---------------------------------
    0000 0110 0101 1001 0001 1110

    1011 1110 0001 0101 0100 1110 (be154e, initial segment of IV)
XOR 0000 0110 0101 1001 0001 1110 (last result)
---------------------------------
    1011 1000 0100 1100 0101 0000

The result is b84c50 in hexadecimal representation. So the new IV is b84c502343408caa1f11ab3445bdd34c.

Test it by decrypting the ciphertext with it:

$ openssl enc -aes-256-cbc -d \
    -in ciphertext.enc \
    -iv b84c502343408caa1f11ab3445bdd34c \
    -K be154e2343408caa1f11ab3445bdd34cbe154e2343408caa1f11ab3445bdd34c

Voilà, you should see :) Hello World!</p>.

Why does this IV do what we want? Well, because of how CBC works, we know:

AES_decrypt(first_ciphertext_block, key) XOR IV = first_plaintext_block

If xyz are the first three bytes of the result of AES_decrypt, and abc are the first three bytes of the IV, we have:

xyz XOR abc = "<p>"

We changed the first three bytes of the IV by XORing the original plaintext and the desired output. So, the question is: Why does the following hold?

xyz XOR (abc XOR ("<p>" XOR ":) ")) = ":) "

Well, here is why:

  xyz XOR (abc XOR ("<p>" XOR ":) "))
= (xyz XOR abc) XOR ("<p>" XOR ":) ")  [because XOR is associative]
= "<p>" XOR ("<p>" XOR ":) ")          [as noted above]
= ("<p>" XOR "<p>") XOR ":) "          [because XOR is associative]
= ":) "                                [because x XOR x = 0 and 0 XOR x = x]