# Strength of CBC with Ciphertext Stealing

Is CBC with Ciphertext Stealing (CTS) considerably weaker than CBC with padding such as PKCS7?

I would imagine the most common situation where CTS is necessary would be due to some size constraint of an existing system, and redesign of the system is inconvenient. So, while it clearly reveals the length of the encrypted data, (in general) is this a significant enough weakness such that CTS should always be avoided?

I've read through the addendum to NIST SP800 38A on CTS variants, and while one could perhaps take this NIST recommendation as tacit approval of CTS's relative safety, there's no real mention of any weakness considerations and I've not been able to find any resources speaking directly to this topic.

-
IF you would go with a mode that relies on padding sizes to hide information on the plain text, then it should be documented very well within the protocol description. Otherwise switching to another mode such as counter mode later on would immediately expose the length. Note that adding a random number of bytes is not enough. Note also that padded modes of operation may be vulnerable to padding oracle attacks. This can be countered by adding a authentication tag (adding authenticity/integrity of the ciphertext). –  owlstead Aug 21 '13 at 15:15

In their 2012 paper "The Security of Ciphertext Stealing", Phillip Rogaway, Mark Wooding and Haibin Zhang prove that all the NIST-approved ciphertext stealing modes provide the same level of security as ordinary CBC mode, i.e. ciphertext indistinguishability under a chosen-plaintext attack. To quote their abstract:

"Abstract. We prove the security of CBC encryption with ciphertext stealing. Our results cover all versions of ciphertext stealing recently recommended by NIST. The complexity assumption is that the underlying blockcipher is a good PRP, and the security notion achieved is the strongest one commonly considered for chosen-plaintext attacks, indistinguishability from random bits (ind\$-security). We go on to generalize these results to show that, when intermediate outputs are slightly delayed, one achieves ind\$-security in the sense of an online encryption scheme, a notion we formalize that focuses on what is delivered across an online API, generalizing prior notions of blockwise-adaptive attacks. Finally, we pair our positive results with the observation that the version of ciphertext stealing described in Meyer and Matyas's well-known book (1982) is not secure."

In particular, in section 3 of the paper, the authors write:

"Turning now to the CBC-CS modes, we claim that these inherit CBC's security with no quantitative degradation. The needed observation is that $\text{CBC-CS1}^{IV}_K(P)$ is just $\text{CBC}^{IV}_K(P\ 0^∗)$ (minimal padding to the next multiple of $b$ bits) with some bits excised and some bits reordered. Which bits are excised and how bits are rearranged depends only on $|P|$. Thus if $\text{CBC}^{IV}_K(·)$ looks random, so too will look $\text{CBC-CS1}^{IV}_K(·)$. The same comments hold for CBC-CS2 and CBC-CS3; these are just diﬀerent rearrangements of the bits of $\text{CBC}^{IV}_K(P\ 0^∗)$. The observation and proof are formalized by the proposition below."

Edit: It should be noted that all these indistiguishability results assume that the length of the plaintext (and corresponding ciphertext) is fixed and known to the attacker. If used to encrypt variable-length messages, all the commonly used block cipher modes of operation leak information about the length of the plaintext.

As you correctly note, CBC mode without ciphertext stealing does leak slightly less information about the plaintext length than other modes (like CFB, OFB, CTR or CBC-CS), since in traditional CBC mode the message is padded to the next multiple of the cipher block size (usually 8 or 16 bytes). However, this incidental side effect isn't really something you should generally rely on to conceal your plaintext lengths, at least unless you can be sure that just knowing whether or not, say, a message is less than 16 bytes long won't ever be the critical piece of information the attacker is looking for. Instead, if you do care about concealing the length of the plaintext, you should pad your messages yourself to some fixed length before encrypting them.

-
This doesn't really answer the OP's question, which was about the degree of risk due to leaking the length. This is the one respect in which CBC-CTS does not achieve the same level of security as plain CBC, as CBC-CTS leaks more precise information about the plaintext length. –  D.W. Aug 21 '13 at 2:51
@D.W.: Good point, I forgot to address that part of the question. That said, even plain CBC still leaks most of the length of the plaintext, it just rounds it up to the nearest cipher block size (i.e. typically 8 or 16 bytes). If you're in a situation where leaking the plaintext length matters, you should pad your messages yourself to a sufficiently long fixed length, rather than relying on the limited and incidental padding provided by CBC mode. –  Ilmari Karonen Aug 21 '13 at 9:11

Sadly, there's no uniform answer to this. The answer will depend upon your specific application domain. In some application domains, revealing the exact length of the plaintext is not a problem. In other application domains, it is a very serious problem. There's no one-size-fits-all answer. That's probably why you don't find much discussion of this.

For a real-world example where leaking plaintext lengths can cause serious problems, see the CRIME and BREACH attacks on SSL.

-