How to alter CBC encrypted text to change the message

Question

I'm currently in the process of learning about encryption and i'm hoping to find more clarification on what I learned.

Suppose the message "100 dollars should be moved from account 123456 to 555555" was encrypted using aes-128-cbc and a random IV. My professor says it's possible to alter the encrypted text so that when it's decrypted again, the message reads "900 dollars should be moved from account 123456 to 555555". How do you go about doing this?

I tried figuring it out on my own by generating my own key and iv, encrypting the message, then converting it to hex characters to work with. From there can I swap out some characters then decrypt? I tried playing around with this but something always seemed to go wrong.

We're using a basic linux command line for this.

Any help or explanation would be awesome!

Answer 1

Suppose the string was encrypted using a one-time-pad and the resulting ciphertext is "B8B7D8CB9860EBD0163507FD00A9F923D45...". We know that the first byte of plaintext, the digit 1, has ASCII code 0x31. The first byte of the ciphertext is 0xB8. If k0 denotes the first byte of the key, then 0x31 xor k0 = 0xB8. Decoding a one-time-pad is just xor-ing the ciphertext with key. So, the person decoding gets the first byte of the plaintext as 0x31 = 0xB8 xor k0. If we xor the first byte of ciphertext with m0, then the person decoding the ciphertext will get (0xB8 xor m0) xor k0. But this is just (0xB8 xor k0) xor m0 as xor is commutative and associative. The last expression can be reduced to 0x31 xor m0. Now we want to change the resulting byte to 0x39, the ASCII code for the digit 9. So we need to solve 0x31 xor m0 = 0x39. But that is simple just xor with 0x31 on both sides.

The same principle applies when using CBC mode. You can modify the IV in a similar way to change the decoded message.

Answer 2

@user515430's reasoning above is based on the fact that every ciphertext C is linearly dependent from the plaintext P (since C = P ⊕ K).

Actually, as @polettix makes us notice, in CBC encryption we have that, e.g. for the 6-th block of a certain text, C₆ = E(P₆ ⊕ C₅, K), given a key K; and if E(·) is a good encryption function we shoud loose such linearity.

But, in CBC decryption, the 6-th block of plaintext will be obtained as P₆ = D(C₆, K) ⊕ C₅, so it will be linearly dependent not from C₆, but from C₅.

Re-wording, if you want to change a plaintext block in CBC, just change the previous chiphertext block.

See also https://crypto.stackexchange.com/q/30407/36884 (for the record, Cryptography StackExchange is the right site for this kind of question).