Let IV, c1, c2, c3, . . . be a CBC-mode encryption of message m1, m2, m3, . . . , where each message block mi is n-bits long. Suppose an attacker (who does not know the key) knows the first block m1 (e.g., it is predictable header information). Suppose m01 is a different n-bit string. Show how the attacker can make a new ciphertext IV 0 , c01 , c02 , c03 , . . . which decrypts to m01 , m2, m3, . . . , even though they do not know the key that was used for the encryption.
Question
Let IV, c1, c2, c3, . . . be a CBC-mode encryption of message m1, m2, m3, . . . , where each message block mi is n-bits long. Suppose an attacker (who does not know the key) knows the first block m1 (e.g., it is predictable header information). Suppose m01 is a different n-bit string. Show how the attacker can make a new ciphertext IV 0 , c01 , c02 , c03 , . . . which decrypts to m01 , m2, m3, . . . , even though they do not know the key that was used for the encryption.
Solution
In CBC (Cipher Block Chaining) mode, each block of plaintext is XORed with the previous ciphertext block before being encrypted. This means that an attacker can manipulate the first block of plaintext by manipulating the initialization vector (IV).
Here's how an attacker can create a new ciphertext which decrypts to m01, m2, m3, ...:
-
The attacker knows the first block of plaintext m1 and wants to change it to m01. They calculate the XOR of m1 and m01 to get a value d. This value d represents the difference between m1 and m01.
-
The attacker then XORs d with the original IV to get a new IV (IV0). This new IV0 will cause the first block of plaintext to be m01 when decrypted.
-
The attacker leaves the rest of the ciphertext blocks (c1, c2, c3, ...) unchanged. Because these blocks are XORed with the ciphertext of the previous block before being decrypted, and the ciphertext of the first block hasn't changed, these will still decrypt to the original plaintext (m2, m3, ...).
So the new ciphertext is IV0, c1, c2, c3, ..., and it will decrypt to m01, m2, m3, ... under the same key as the original ciphertext. The attacker has successfully manipulated the first block of plaintext without knowing the key.
Similar Questions
Write down decryption in CBC mode, and give a detailed explanation why it works
LetM1 = {0000 0001, 0101 0000, 1111 1000} be a message space andM2 = {1010 0100, 1110 0011, 1011 0101} be another. (In case the typesetting is unclear, these are sets containing three bitstrings of length 8.) Suppose two ciphertexts are received c1 = 1011 1011 and c2 = 0101 1110. Suppose you know c1 is a one-time pad encryption of a message in M1 with key k and that c2 is one-time pad encryption of a message in M2 with the same key k. What are the two messages and what is the key?
Explain why CBC mode encryption cannot be parallelised, but decryption can be parallelised.
This question is about why one should use different keys when doing encrypt-then-MAC. It is based on Exercise 9.8 in Boneh-Shoup. Suppose Enc is a block cipher with n-bit blocks. We build an authenticated encryption scheme from Enc by using CBC-mode with random IV , and using a MAC also built from CBC-mode. So an encryption of an n-bit message m is a triple (c0, c1, t) where c0 = IV , c1 = Enck(IV ⊕ m), and t = Enck(Enck(c0) ⊕ c1). (a) Write down the operations and checks performed by the authenticated decryption algorithm on input (r, c, t). (b) Write down an encryption of the n-bit zero message and explain why an attacker who asks for encryptions of zero can get many pairs (r, Enck(r)) for random n-bit strings r. (c) Suppose an attacker who does not know k is given r, c = Enck(r) and r 0 , c0 = Enck(r 0 ) for random r = r 0 . Show that (r, r0 ⊕ c, c0 ) is accepted by the decryption algorithm.
Suppose an attacker who does not know k is given r, c = Enck(r) and r 0 , c0 = Enck(r 0 ) for random r = r 0 . Show that (r, r0 ⊕ c, c0 ) is accepted by the decryption algorithm.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.