The Security of Ciphertext Stealing
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
To appear in the proceedings of FSE 2012. Springer, 2012.
Full version available in pdf.