How is an AES Encrypted Message Decrypted with Random Padding?

Question

One thing I was surprised to learn about AES is that random padding can be added to the message to make it a multiple of block size. What I can not wrap my head around is how this random padding can reliably be removed from the message upon decryption, given that if it is generated by a truly random process, the recipient has no information about it.

• What are the properties of random padding (and I realize there are different ways to do it but I'm looking for an illustrative example) that allow it to be reliably removed from the message?
• Is it true that in order to decrypt the message you must have information about the padding scheme in addition to the secret?

Answer 1

What are the properties of random padding (and I realize there are different ways to do it but I'm looking for an illustrative example) that allow it to be reliably removed from the message?

You can do random padding with AES, but you'd have to reserve say the very last byte to tell how many bytes of padding were added.

For example, for a 4 byte blocksize cipher, say your message is 04 (in hex). To make it 4 bytes we need to add three bytes, so we add two bytes of random padding, then one byte 02. So what would really be fed into the block cipher would be 04 ac 92 02. The recipient needs to know that this scheme is being used. They would then read the last byte and know that two bytes of random padding were added. Those bytes would be removed and the final message 04 would be returned.

I believe most people using AES do not use random padding though. Deterministic methods are just as secure. RSA, however, needs random padding for security.

Is it true that in order to decrypt the message you must have information about the padding scheme in addition to the secret?

Yes. Otherwise it would be impossible to strip off the padding. This information does not need to be secret and can thus be specified in a protocol field or upon handshake.