The Security of Ciphertext Stealing

Authors:
Phillip Rogaway, Mark Wooding, and Haibin Zhang

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

References:
To appear in the proceedings of FSE 2012. Springer, 2012.

Full Version:
Full version available in pdf.