Malleability attacks against encryption without authentication

Question

Suppose there is a message that is encrypted with AES-128-CBC. The message is as follows, new lines are used to delimit the 16 byte boundary for each block:

Wire funds from:
Alice to Bob in 
 the amount of $
1

Because this message is encrypted using CBC mode, any modification of the first block of cipher text would propagate throughout the message. However, the amount of the fund transfer falls in the last block. I am under the assumption that an attacker can use the property of Malleability to alter the last block and produce a valid amount that is greater than \$1 in far fewer than $2^{128}$ operations.

Is this a correct assumption? Is there a name for this attack or do you know of a real world example?

My instinct is that if you just need one byte of the 16 byte block to be of a specific value then it would only require $2^8$ operations because the other 120 bits of the plain text could be any value. For example lets say we wanted the last block of cipher text to decrypt to 9\0 (where \0 denotes a single null byte, and the message would be interpreted as \$9), then it would take only $2^{16}$ operations to find this cipher text block.

Is there something I am missing?

Answer 1

First of all, you stated:

Because this message is encrypted using CBC mode, any modification of the first block of cipher text would propagate throughout the message.

Actually, that's not true. Here's the CBC mode operation in the decryption direction:

(Public domain image from Wikimedia Commons.)

If you examine the process closely, you will see that a specific plaintext block depends only on two ciphertext blocks (or a ciphertext block and the IV for the very first plaintext block).

So, if you modify a ciphertext block $N$ (say, flip one of the bits), then the resulting plaintext will have block $N$ garbled (because the modified block goes through the decryption, and unless we picked a ciphertext block which we already knew the decryption of, the result will be unpredictable). In addition, block $N+1$ will have the corresponding bits modified (in our example, the same bit will be flipped). And, there will be no other changes; all other plaintext blocks will be exactly what they were in the original message.

So, how can we use this observation? Well, if block $N$ is the one we want to affect, and we don't mind if block $N-1$ decrypts to something unpredictable, the obvious approach is to modify block $N-1$ of the ciphertext. If we guess that the real plaintext is $A$ (which corresponds to \$1), and we want it to read $B$ (which corresponds to (\$1000000), then we exclusive or $A \oplus B$ into ciphertext block $N-1$; this will cause the last ciphertext block to read exactly as we want it to.

Answer 2

To learn more about this sort of attack, see my answer Don't use encryption without message authentication, where I detail many examples of systems that were broken because they used encryption without authentication.

You will see that there is a wide variety of attacks that may be applicable, depending upon specific details of how the system works. You haven't provided enough details to assess exactly which of these might be applicable, and frankly it's probably not worth your time to analyze a hypothetical system in great detail, but there are many: reaction attacks, ciphertext modification, and more.

So, read about the failures of deployed systems. I think you'll learn a lot about how this can fail and why cryptographers recommend you should always use authenticated encryption, any time you think you need to encrypt.

Answer 3

Yes, in theory, but this doesn't usually work in practice. You are right in that the last-block ciphertext in this example is malleable to some extent, but not as much as you seem to suggest. It is true that here, if you were to change the last ciphertext block so that the first byte of its corresponding plaintext corresponds to some value you chose, it would only take you $2^7$ trials on average.

However, as you identified, it would make the rest of the block garbage. As this is the last block, it often happens to contain the padding information, and it will therefore be impossible to correctly decrypt the message with overwhelming probability (as the padding will be malformed), which will defeat the point and reveal your tampering as well.

With regard to padding, it depends on the padding mode used - some modes will make this attack rather successful, but others will make it more difficult. For instance, from this page, bit padding will make it hard on you, because you will probably need a lot of consecutive zero bits in the plaintext block for decryption to succeed, whereas with byte padding, you only need the last byte to have the right value in it for decryption to work, which is easier to achieve (well, technically, you also need a bunch of zero bytes before, but some implementations skip that step - which is a vulnerability, by the way).

Now, if the rest of the block is not padding data (for instance, if padding is disabled as a result of the plaintext being guaranteed to be a multiple of 16 bytes in length, or if padding is stored somewhere else), and is completely ignored by the receiver for some reason (this could work with a null byte if it is interpreted as a null-terminated string, as you suggested), then this works and you have a malleable ciphertext weakness that can be exploited if the attacker knows the rough format of the plaintext.

This is a good example of why encryption without authentication is worthless, and you should always attach a MAC to any ciphertext to ensure it arrives intact to its destination.