3
$\begingroup$

For this question my focus is exclusively on symmetric block ciphers (with a particular interest in AES256 in CBC mode).

I have read much discussion on various ways to pad the plaintext so that the length of the input to the encryption algorithm is a multiple of the blocksize.

The real problem here is not padding to a suitable size (which, by itself, is trivial), but rather undoing such padding after decryption.

One very simple scheme for undoing the padding is to store the length of the (unpadded) plaintext in a header section, unencrypted. Then, after the ciphertext is decrypted, the raw result is truncated to this saved length.

Since this simple solution is never mentioned in discussions of padding (I've consulted several textbooks), I have to assume that there are some very serious problems with it, but these problems are never spelled out, and they are not obvious to me. What are they?

$\endgroup$
  • 1
    $\begingroup$ When used with compression plus allowing insertion of arbitrary strings by the adversary, then you get attacks like BREACH against HTTPS, where you can extract session cookie secrets by guessing bits at a time and observing how the compressed ciphertext gets smaller when a larger number of bits are guessed correctly. $\endgroup$ – Natanael Aug 18 at 19:18
3
$\begingroup$

Exposing the size of the plaintext has no security risks. The size of the plaintext is always considered public data. It's not done because it has limited benefit.

With a mode like CBC, you cannot encrypt a fractional block. You must pass a whole number of blocks to the encryption function. So you need padding in some form. The ciphertext is a whole number of blocks. If the ciphertext itself doesn't encode the message unambiguously, you need to pass the size separately, at least the size of the last block (or equivalently the size of the padding). In practice, that means you need at least one extra byte to indicate the size. If you do this, then the padding doesn't need to be unambiguous, so you can allow it to be empty if the plaintext happens to be a whole number of blocks. Compared with unambiguous padding, this method results in ciphertext-plus-size that's one block minus one byte shorter if the plaintext is a whole number of blocks, and one byte otherwise. So in terms of ciphertext size, it's a wash.

In terms of ciphertext and decoding complexity, passing the size separately makes things a little more complicated. The ciphertext isn't a black box anymore: the padding size needs to be sent with it. The ciphertext-plus-size can be a black box, but it's a little harder to process: the last pseudoblock is one byte longer than the others.

This scheme does have a security benefit. Since the recipient does not need to decode the padding, it eliminates direct padding oracle attacks, if done right. However this was poorly understood when CBC was in vogue: people generally followed the usual wisdom to verify everything, thus revealing information about the content of the last block. Today, serious protocol designers are well aware of the dangers of padding oracle attacks, but the solution is not to use padding at all.

$\endgroup$
1
$\begingroup$

There are a bunch of issues with prepending the message's length to a ciphertext (or indeed encoding it as the first few bytes of plaintext):

  • Lack of Benefit: Explicitly encoding the length when using CBC mode gives you a benefit in exactly one case: When the entire last block would be padding, because otherwise you will need the length and the padding.
  • Hinderance of stream processing: People like to encrypt data with the Init, Update, Final idiom and having to know the length of your message means you actually have to know it when you call Init which means that you will have to buffer your entire message instead of being able to stream it.
  • Width of the size: In the past, people would probably have chosen 4 bytes for the size, but do you really want to be limited to 4GB ciphertexts? Though of course ASN.1 again has already solved this problem.
  • Parsing of integers: You'd need a standard that specifies whether the size is encoded as little-endian or big-endian, because different platforms have different defaults. No such standard exists, though ASN.1 has this down.
$\endgroup$
  • $\begingroup$ If you send the size of the padding (or equivalently the size of the last plaintext block), most of these downsides don't apply. $\endgroup$ – Gilles Aug 18 at 15:15
1
$\begingroup$

the raw result is truncated to this saved length.

You can easily truncate only if you work with small data sets or if you need to encrypt/decrypt a single file / data set. If you have relatively big data set, let say 1 GB, you would first have to save them in a temporary file. If your OS does not support truncating files, you will have to reread this file and truncate it when writing again. If you have to decrypt multiple data streams in parallel (e.g. you have a system with many users, you are storing big amounts of log data, you are storing much data from sensors, etc.), this can be a huge performance problem. Where as with standard padding you need only a small part of data at any time: you decrypt them, save, move to another block.

$\endgroup$
  • $\begingroup$ The way we do it is we write the raw output to disk, and then use the Python file.truncate method (which I believe is just a wrapper for the standard C function truncate) to truncate the file to the desired size. I have tested this scheme with files of ~100GB without any problem. $\endgroup$ – kjo Aug 18 at 14:56

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.