1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ After removing the 45 bytes, how do you determine if the 255 bytes of 255 are part of the original message or not? $\endgroup$ – user13741 Jan 11 '17 at 21:52
  • $\begingroup$ @user13741That's something you could say normally. How do you know that the 45 bytes at the end aren't part of the original message? What if the original message was already 300 bytes and so needed no more padding? $\endgroup$ – Awn Jan 11 '17 at 22:03
  • 2
    $\begingroup$ Most padding schemes avoid this by always requiring padding, even if the message is already a multiple of the block length, or 0. $\endgroup$ – user13741 Jan 11 '17 at 22:14
  • $\begingroup$ So if it's a multiple of 16, the last 16 bytes would have another 16-byte block appended? Today I learned. $\endgroup$ – Awn Jan 11 '17 at 22:26
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You're welcome. As said, this is a well known scheme, I didn't make it up :) $\endgroup$ – Maarten Bodewes Jan 11 '17 at 22:08
  • $\begingroup$ Just to clarify, by the complement of the last bit you mean a XOR, right? What is it XORed with? $\endgroup$ – Awn Jan 11 '17 at 22:10
  • 1
    $\begingroup$ Say the last (usually the least significant) bit is 1 then the padding consists of all zeros. If it is 0 then it consists of all ones. This makes it possible to just remove all bits valued the same from the end. By the way, it's not more efficient as I first wrote, so I'd forget about it. $\endgroup$ – Maarten Bodewes Jan 11 '17 at 22:12
  • $\begingroup$ Ah that makes sense. Noted; cheers anyways. $\endgroup$ – Awn Jan 11 '17 at 22:14
  • 2
    $\begingroup$ The padding scheme in the first section of this answer is designated "padding method 2" in the Handbook of Applied Cryptography, Algorithm 9.30 in the context of hash functions, with reference to a 1996 draft of ISO/IEC 10118-4. It is similarly named in ISO/IEC 9797-1:1999 in the context of MACs based on iterated block ciphers. $\endgroup$ – fgrieu Jan 12 '17 at 8:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.