1
$\begingroup$

When plaintext padding is required, there are various commonly-used padding techniques. It seems the two most used approaches are :

  1. Always add at least one byte of padding, and have every byte of padding represent the number of bytes of padding added; or else
  2. Always add at least one byte of padding, and have the last byte of padding represent the number of bytes of padding added, whilst the other padding bytes are zero;

The very concept of a padding oracle relies on there being byte arrangements that are invalid based on the padding scheme used.

Another padding scheme seems extremely obvious to me, has no potential for oracle padding exploits (as all byte arrangements are valid), and results in approximately 6% fewer padding bytes being added to messages on average (assuming random distribution of message lengths and random message contents).

I describe the padding scheme below, but my question is simple : since this padding scheme is so obvious, and simple to implement, and eradicates all possibility of padding oracle attacks, and saves a smidgeon of storage space and bandwidth, why am I unable to find anyone else promoting this obvious scheme? Am I overlooking an obvious flaw? Has it been proposed before but widely rejected, and if so, why?

This is not a question about using MACs to prevent padding oracle exploits, nor am I suggesting not using MACs just because this padding scheme is impervious to padding oracle exploits, but I am a big fan of eliminating unnecessary weaknesses in individual components of a system even if the careful layering of components can mitigate the weaknesses. Padding oracles are so easy to have designed to be impossible, if the following scheme works, that I don't understand why we have the padding schemes we do.

The scheme :

If final block is less than full, add zeros until (exclusive) the final byte, then add a byte representing the number of padding bytes added. (So far, identical to one of the common schemes, EXCEPT that on receipt, we ignore the meant-to-be-zero bytes, and thus if they are corrupted in transit, it will not cause a padding validation failure.)

Assuming block size of 16 bytes, if final block is full, and final byte of final block has numeric value between 1 and 16 inclusive, add an entire padding block, filled with zeros except for the final byte, the which holds the number of padding bytes added (16 in this case). (Again, at this point, no different to one of the padding schemes already in common use, except that again, on receipt of a padded message, we entirely ignore padding bytes that we expect to be zero, and thus a corruption in transit will not cause a padding validation failure.)

Assuming block size of 16 bytes, if final block is full, and final byte of final block has numeric value of 0, or >= 17, no padding is required. (This is the one point of difference from the otherwise-identical common scheme.)

In this scheme, all byte sequences are valid, eliminating padding oracle problems.

And compared to the mainstream padding approaches, we save a smidgeon of storage space and bandwidth, because 1/16th of the time (assuming random distribution of message lengths, and random message contents), we have only 16/256ths (i.e. 1/16th) probability of needing to add a full block of padding bytes, meaning 15/16ths probability of saving ourselves the 16 padding bytes, as compared to always requiring a full block of padding as occurs in the equivalent situation with the mainstream padding schemes.

What am I missing, or else why do we live with padding schemes that need extremely careful use to prevent leaking sensitive data?

Thanks in advance for your answers!

$\endgroup$
1
$\begingroup$

Your scheme leaks information about the plaintext, outside of the length of the message. To be precise, it may leak the information that the last byte is between 1 and 16 or not.

$\endgroup$
  • $\begingroup$ Thankyou. A good and obvious point, that should've occurred to me. I'm dealing with large and highly-variable-length files (XML files and JPEG files), but I see that if this scheme was used on much more predictable plaintexts, the ciphertext length could give an additional subtle clue into which plaintext was employed, and/or insight into the final byte's contents, that in edge cases could be catastrophic. $\endgroup$ – Usas Sep 23 '14 at 1:17
  • $\begingroup$ Great, that's exactly what I was hinting at. Sorry, no famous new padding, it looked good from a distance to me as well. $\endgroup$ – Maarten Bodewes Sep 23 '14 at 7:39

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.