What's the generally accepted way of padding more than 255 bytes?
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.