6

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!

Katie Paige
  • 63
  • 1
  • 8

2 Answers2

4

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.

user515430
  • 3,341
  • 2
  • 17
  • 13
  • In your answer above, what does m0 refer to? – Zeeno Mar 06 '14 at 13:49
  • m0 is just an arbitrary byte. By choosing it suitably we can get the desired result. – user515430 Mar 06 '14 at 15:31
  • So if i'm only interested in changing the first byte of the message, should I only be looking at xor-ing the first byte of the ciphertext with the first byte of the IV? – Katie Paige Mar 06 '14 at 15:36
  • 1
    @Katie, you are correct. All the action is with the first byte (of the ciphertext, the IV and the resulting plaintext). A little surprising given that AES is a block cipher. – user515430 Mar 06 '14 at 15:45
  • I tried to test this out using the same original string message, a key of "3a5633476a3076545456f3d3d58" and an iv of "357324276e4f74292272232951" with a resulting ciphertext of "1aa9a27b982bd8d75727bf3bece0289eb41a8b91201819c6a3270d7b079f 1b8200a33ed141a9de2c0405d41079cb68fb54c53a24877c2cb88dcc63eb 2b1e3d0b" I figured I could test the accuracy by xor-ing 31(1) with 35(first byte of iv) to see if I got 1a, but instead I got 04. Am I going about this incorrectly? – Katie Paige Mar 06 '14 at 16:25
  • 1
    @Katie, getting close. The 04 is the first byte of the D(k, C), i.e. the AES decryption of the first cipherblock. In CBC you get the first block of the plaintext by xor-ring D(k, C) with the IV. Here is a hint, write a small program that modify the first byte of IV to all possible values and look at the resulting plaintext. – user515430 Mar 06 '14 at 16:40
  • So I would only need to change the first byte of the ciphertext to change the original message to the new one? – Katie Paige Mar 06 '14 at 16:54
  • @Katie, you only need to change the first byte of the IV. – user515430 Mar 06 '14 at 16:59
  • Thank you so much for your help! Sorry for repeatedly asking questions but I wanted to make sure I understood the concept. I appreciate it. – Katie Paige Mar 06 '14 at 17:07
  • 1
    Is there any place with an explanation why this works for CBC mode too? This means that flipping a bit in the plaintext means flipping exactly the same bit in the ciphertext, and it seems really shocking considering that there is a ciphering box in the middle. – polettix Jul 08 '17 at 22:14
  • @polettix see my answer below. – logi-kal May 03 '18 at 17:38
1

@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).

logi-kal
  • 7,107
  • 6
  • 31
  • 43