Chosen Plaintext Attack on DES/AES

Question

PERSON A sends messages to PERSON B using AES, CBC, PKCS5Padding with an IV that is incremented by one after each message. If PERSON Z knows that the first block of the plain-text of any message is either "Yes" or "No", can she launch an attack that decrypts the first block of a given message? Hint: Chosen Plaintext Attack

My answer is I do not think it is possible to mount an attack that decrypts the first block because of the avalanche effect. Any changes, whether if it is the size or the content, atleast 50% of the content in CT changes.

Is there anything missing or totally wrong in my answer??

Answer 1

Let's say we have a message (sent by Person A) encrypted with CBC using the IV $x$, and the first block of the message is either "Yes" or "No". We also assume the attacker has the capability of requesting the encryption of arbitrary chosen plaintexts (though he doesn't control the IV - it is always incremented after each encryption request). Let us also say the IV is predictable by the attacker (an incremented IV is predictable so long as the attacker always knows and/or can control when the encryption function is used). In other words, the attacker knows that if he requests the encryption of some plaintext then the IV used to encrypt it will be $x \oplus k$ for some value $k$. Let's denote the IV the attacker predicts will be used if he makes a request by $IV_z$ ("z" for Person Z), i.e. $IV_z = x \oplus k$.

In which case the attack is simple: Request the encryption of a plaintext where the first block is "Yes" $\oplus$ $k$. Because of how CBC works, the first block of ciphertext, $C_z$, will be: $C_z = E(Yes \oplus k \oplus IV_z) = E(Yes \oplus k \oplus x \oplus k) = E(Yes \oplus x)$.

Now the attacker compares $C_z$ to the first block of the encrypted message sent by Person A, which we will denote as $C_a$. If the message sent by Person A started with a "Yes" then $C_a = E(Yes \oplus IV_a) = E(Yes \oplus x)$. So if the message started with "Yes" then $C_z = C_a$. Conversely, if the message started with "No" then $C_z \neq C_a$. So simply by comparing $C_z$ with $C_a$ the attacker can easily determine the first block of the message.

Answer 2

It is not safe to use a non-random (that is, predictable to the attacker) IV in CBC mode. Remember: it will be xor'd into the next block.

See Why is using a Non-Random IV with CBC Mode a vulnerability? for more information.

Answer 3

Just look at the diagram.

First block gets xor'ed with the IV, and then fed through the encryption function.

It says the IV has 1 added to it. Applying Kerckhoff's principle, this is public knowledge.

So, just make your own plaintext of "Yes" in an array of bytes, xor it with 1, then send it for encryption. The 1 will cancel with the 1 that was added to the IV and you are left with just the "Yes" xor'ing with the IV. Hence, you get a valid encryption of "Yes".

This works because addition in bits is under modulus 2. Use truth table of xor to see that xor is basically addition modulus 2. So "Yes" xor 1 xor IV xor 1 is the same as "Yes" xor IV xor 1 xor 1 and you know anything xor with itself is just zero.

Now for every message you intercept, just use your CPA as a reference. If the first block of the intercepted message equals your cipher, it's a "Yes". Else, it's a "No".

Whenever you see anything funky going on, ignore any complex reasonings. It's usually something simple like xor eating everything away and you're left with something you can work with.