What's the generally accepted way of padding more than 255 bytes?

Question

There are plenty of popular padding schemes in use today. ANSI X.923 and PKCS#7 come to mind. However, all of them work on single bytes at a time. This is hardly surprising: padding for cryptographic purposes is usually just to 16 bytes and a single byte can hold the value 255.

I was wondering if there was any generally accepted method of padding when we need to add more than 255 bytes of padding. PKCS#7 obviously wouldn't work since you'd have to have multiple bytes for every byte normally. ANSI X.923 could be modified slightly to use more than one byte at the end to store the length of the padding, but this too comes with its own problems, namely that it doesn't work for every combination of inputs unless you do some dirty workarounds to manually take care of edge-cases, and even then I'm doubtful it'd work.

The solution I came up with was to simply run PKCS#7 multiple times. What I mean by that is if we want to pad 300 bytes, then pad up to 255 normally (by adding 255 bytes of value 255), then pad again up to 300 (by adding 45 bytes of value 45). When un-padding, you'd simply remove the top layer of 45 bytes, check to see if the next 255 values were all 255, and if they are, remove them all, and repeat.

I can't find a mention of anything similar to this, however, hence the question. Is there a standardized, accepted way?

Answer 1

Bit padding is one way to do this. There are also padding schemes that do pad using a special length encoding. This can be more efficient as you don't have to parse all the bytes. But in general bit padding should suffice.

Bit padding first (and always) adds a single bit valued 1 to the plaintext. Then it adds bits valued zero to the right until the length you require. It is extensively used internally for hash algorithms but sometimes it is also used for block ciphers. Unpadding consists of removing all zero bits from the right and then the one bit set to 1. This padding scheme is fully deterministic; it doesn't depend on the plaintext at all.

In bytes you get values such as:

6F 77 6C 73 74 65 61 64 - 80 00 00 00 00 00 00 00

for padding a value

6F 77 6C 73 74 65 61 64

up to 16 bytes (block size).

That means one bit set to 1 (byte 7, the highest bit usually), 7 zero bits to make a full byte and then any number of zero valued bytes.

It is easy to see that you can use this for any size of input, and any size of padding.

---

A variation of this scheme is to simply pad with bits that are a complement of the last bit of plaintext. Then you can just remove bits that are identical to the last bit. This scheme however depends on the plaintext, which makes it more cumbersome.