# Random data CBC padding scheme?

When using AES in CBC mode, padding is required when the last plaintext block has not the length required by the cipher. Let's say $$k$$ mode bytes would be required to fill the block. My idea was to pad the last block with $$k-1$$ random bytes followed by one byte that corresponds to the integer value of $$k$$ (or $$k-1$$). That is, it tells how much padding was added. When decrypting, the previous decrypted block is held back, until it is clear that it was not the second to last block. If it was, the padding is removed accordingly and the full plain text is obtained.

Is this a secure way to pad a message? More generally, are there problems that may arise from this method of padding, or can an incorrect padding scheme compromise the cipher?

• You might find this question and answer interesting. It's not new. This is a link to ISO 10126 Padding for you crypto nerds out there. May 23, 2021 at 21:55

How devastating padding oracle attacks are depends on the nature of the padding and how much partial plaintext the adversary is likely to know. A well-known example is the Lucky Thirteen attack, where the conjunction of allowing up to 256 bytes of padding, and having 13 bytes of known plaintext in a message header, leads to a practical attack to fully decrypt a TLS connection against an unprotected implementation in many realistic scenarios.

In your case, the opportunities are more limited for the attacker, but the scheme is still vulnerable. Suppose the adversary knows or can guess the first 15 bytes of plaintext in a block and would like to know the last byte. The adversary can send that block to be decrypted as a 16-byte message, and learn at least whether the last byte is a valid value (1 to 16). This is not a complete breach of confidentiality, but it is a breach of confidentiality.

Padding oracle attacks depend on the adversary learning whether the padding is correct. A defense is to not have any invalid padding. An easy tweak to your scheme has this property: make the top 4 bits of the last byte random as well. This way no padding is invalid and therefore no padding oracle attack is possible as such. However, the adversary may still be able to learn the length of the plaintext (for example by measuring very precisely how long it takes to process), and if the ciphertext was one crafted by the adversary, this length could be in fact a confidential byte of the message.

To have an actual secure cipher, you need to use authenticated encryption. Authenticated encryption is not vulnerable to chosen-ciphertext attacks because the attacker cannot forge a superficially valid ciphertext: all valid ciphertexts include an authentication tag which cannot be calculated without the secret key. You can build authenticated encryption by taking unauthenticated ciphertexts and adding a MAC (“encrypt-then-MAC”), and that works even if the encryption part is padded CBC. On this topic, see Should we MAC-then-encrypt or encrypt-then-MAC?. However, CBC has no advantage over streaming mode, and all common proper authenticated encryption modes use CTR mode for the encryption part.

• When $$k=0$$ which means that the last block is full, you need to tell that a new block is added. The new block has 15-random bytes and the final byte is 0x0F

Now it is complete.

As long as the block cipher is CPA secure like AES-CBC, there is no problem with the known-plaintext attack.

When we turn to padding oracle attack that is actually a decryption oracle that can be used to reveal all of the plaintext, not the encryption key. At first sight, your padding scheme is not vulnerable to padding oracle attack.

Is this a secure way to pad a message?

It seems better than PKCS#7 which is already the standard padding scheme. The correct way is not using CBC mode where padding oracle is applicable. Use streaming modes that don't require padding like CTR mode. Or, better switch to the modern mode of operation; Authenticated Encryption Mode with Associated Data like AES-GCM and ChaCha20-Poly1305both exist in TLS 1.3, and they don't require padding. They can provide you confidentiality, integrity, and authentication.

More generally, are there problems that may arise from this method of padding or can an incorrect padding scheme compromise the cipher?

Can't see that it is applicable to padding oracle attack. AES-CBC is CPA secure, no problem about the compromise of the key.

An interesting problem with this padding is that, what if an attacker deletes the last block, your padding easily accepts any setting as padding whereas the PKCS#5 has a special structure that one has to be lucky for valid padding if the last block is deleted. Yes, sending the length is a countermeasure.

I still suggest forgetting CBC mode, use it only data at rest.

• Is the padding oracle only applicable to "data in motion" (as opposed to "data at rest")? May 23, 2021 at 16:50
• I don't see as I said. Why do you need CBC mode? No random access, sequential encryption. May 23, 2021 at 16:53