Padding in CBC mode

Question

Hi I have just started learning about ciphers and padding, and just wanted to know why is padding needed in CBC mode encryption, is it to get the blocks to all be of the same n-bit length? And why is it likely that this implementation of CBC mode using padding provides a padding oracle to an attacker? How does this work?

Answer 1

why is padding needed in CBC mode encryption, is it to get the blocks to all be of the same n-bit length?

Yes. Block ciphers (like AES) require the input block to be a certain length (128 bits in the case of AES), and CBC uses blocks of the plaintext as input to the block cipher (after an XOR step). Block ciphers are not designed to operate on a partial block.

why is it likely that this implementation of CBC mode using padding provides a padding oracle to an attacker?

All modern encryption designs include a "message authentication code" (MAC) to prevent an attacker from tampering with the ciphertext and IV. MACs are like digital signatures on the data -- if someone tries to change the ciphertext somehow, then the decryption code can detect that it was tampered with because the signature will no longer be valid.

Unfortunately, some implementations use MACs improperly (or not at all). This allows an attacker to tamper with the ciphertext in various ways and observe its effect on the decryption code. Does it crash? Does it give a specific error? Etc.

One particular type of error that could be observed is a padding error. This would occur when the ciphertext is decrypted, and the decryption code discovers that it was not properly padded (e.g. it's not valid PKCS7 padding). This allows an attacker to submit modified ciphertexts and discover whether or not the corresponding plaintext is properly padded.

For example, suppose the attacker wants to decrypt the third block of a four-block ciphertext. If the attacker submits a modified ciphertext containing only the first three blocks, then the decryption code will expect the third block to contain padding. The decryption code will now reveal to the attacker whether or not the third block is considered properly padded (since if it's not, it will return a padding error). Notice how the attacker has just learned information about the plaintext! This may be a small piece of information, but decryption code should never reveal information like this to an attacker.

The attacker can continue, however, and actually "decrypt" the block byte-by-byte. During decryption, the third block is calculated as AES-decrypt(key, ciphertext-block-3) XOR ciphertext-block-2. By making changes to the second block, the attacker can actually affect what the third block decrypts to!

The attacker begins by modifying the last byte of the second block, trying different values until the decryption no longer results in a padding error. Once the attacker finds one that works, the attacker can deduce (with good probability) that this caused the third block to be decrypted to something ending with 01. Why? Because any block ending with 01 is considered properly padded, according to PKCS7.

Now for the math: we know that the last byte of AES-decrypt(key, ciphertext-block-3) XOR'd with the byte we found = 01. Therefore, 01 XOR'd with the last byte we found will give us the last byte of AES-decrypt(key, ciphertext-block-3). Since we remember the original last byte of the second block, we can XOR it with the last byte of AES-decrypt(key, ciphertext-block-3), and this will give us the last byte of the plaintext of the third block.

With this knowledge, the attacker can then proceed similarly for each preceding byte of the third block, cracking each byte one-at-a-time.