# How to pad messages with large amount of padding

I'm playing around with an application for secure email-like communication and I want to perform length hiding padding on the plaintext messages so they always have a consistent size before encrypting with AES.

I would like to do PKCS7 style padding (if possible), because it's easy to figure out how much to strip from the decrypted output, but how would you do such a padding if the amount of padding exceeds what can be described with one byte? i.e. if I have a message that is 2.000 bytes in size and I want to pad it to become 16.000 bytes in size. This requires a padding size of 14.000 bytes which is 0x36B0 in hex, how would the padding look like for such a value and how can I know that I should take the last two bytes instead of the last byte to find the padding size?

-
I strongly encourage you not to invent your own cryptosystem. You will be a victim of Schneier's law. If you think you'll be safe by sticking with an AES core and writing glue code, you're gonna have a bad time. –  Stephen Touset Jun 21 '13 at 20:45
Don't worry, I'm not inventing my own crypto at all, I just want to hide the length of the actual plaintext payload so that if "Mallory" gets access to an encrypted message, she can't tell the difference between a short message and a long message. All ciphertext will have the same length, regardless of the length of the actual plaintext payload. The plaintext could be "Hello World!" or it could be a super long important message. She has no way of telling from the ciphertext. –  Keke Alho Jun 21 '13 at 20:54
To the other part of your question, it's generally not something I've ever seen people care about. Part of that is because it can be impractical — unless you use an extreme amount of extra padding, I will still be able to tell if your message contained (for instance) HD video versus something like an image or PDF, or only textual data. –  Stephen Touset Jun 21 '13 at 22:53
@StephenTouset If you apply say 2% padding, that's usually enough to hide which video you encrypted and not just that you encrypted some video. So even if you only apply a moderate amount of padding the gain is pretty big. The current version of Tahoe-LAFS doesn't apply padding, which I consider a pretty big flaw. –  CodesInChaos Jun 23 '13 at 8:35
@StephenTouset, I don't think it's quite that bad. And we don't know his situation. There are many considerations: who are the attackers? What are the consequences if they learn the message length? Is it just message length, or does time of transmission reveal sensitive information? What about number of messages? Who the messages are sent to? I think the OP needs to examine all aspects of traffic analysis, figure out what's important to his security situation, then implement it. It may be more than padding he needs, but it's still not "roll-your-own-algorithm" bad. –  John Deters Jun 24 '13 at 14:06

As you note, PKCS7 padding isn't designed to do exactly what you want; it's really designed to allow you to pad up to the next multiple of the block size, that is, to the next multiple of 8 or 16. That it does rather well; however, it's not designed to do what you want with it.

I would note that for block ciphers, as long as you also include a good Message Authentication Code or some other way of ensuring integrity, that the actual padding method isn't critical to security; the AES encryption itself will ensure that there is no information leakage other than message length, and the MAC will ensure that, if the attacker tries to play games with modifying the message, well, that'll always result in a MAC failure, and so that attacker won't learn anything). This is true even if you try to design a padding scheme specifically to leak information (assuming, of course, that your padding method doesn't use the key).

Hence, the only real constraints on your padding scheme is:

• Not to leak any information do to the message length (that's the one thing AES does not disguise)

• Be able to remove the padding to obtain the original message without ambiguity

As long as you follow those two constraints, you're golden. One obvious way to meet both goals is to pad the message out to a fixed length; and then add a 2 (or 4) byte 'original message length' at either the beginning or the end of the message.

I'm assuming that you aren't concerned about interoperability with existing systems; if you are, then you'll need to live within whatever system they are using.

And, the above answer "the padding method is not critical" applies only to block ciphers along with some MAC); when you consider other cryptographical primitives (say, RSA), the padding method does become important in those cases.

-
This presumes that OP can and will implement encrypt-then-MAC correctly, not accidentally leak lengths through timing information (used strlen? oops.), and one of a zillion other ways to get it wrong. –  Stephen Touset Jun 21 '13 at 20:51
Although I suppose OP could pad the message manually, and then feed it through an existing, standardized encryption mode (e.g., AES in GCM mode) that itself implements padding. –  Stephen Touset Jun 21 '13 at 20:52
Another option could be to send two cryptograms for each message. The first would contain the length of the message, and the second would be the encrypted message with an arbitrary amount of truly random data padded onto the end. –  Stephen Touset Jun 21 '13 at 22:50
@StephenTouset For email like systems timing isn't that big a concern, but if you care about timing I'd worry more about higher level systems working on the plaintext rather than about the padding stripping code. Since this padding is protected by the MAC a timing difference doesn't allow forgery or anything really bad beyond losing a bit of length hiding. –  CodesInChaos Jun 22 '13 at 8:17
Right, my concern was that a fault implementation of a homemade padding scheme could easily negate the entire benefit it's supposed to provide. –  Stephen Touset Jun 23 '13 at 4:44