Paper 2008/121

New proofs for old modes

Mark Wooding

Abstract

We study the standard block cipher modes of operation: CBC, CFB, and OFB and analyse their security. We don't look at ECB other than briefly to note its insecurity, and we have no new results on counter mode. Our results improve over those previously published in that (a) our bounds are better, (b) our proofs are shorter and easier, (c) the proofs correct errors we discovered in previous work, or some combination of these. We provide a new security notion for symmetric encryption which turns out to be rather useful when analysing block cipher modes. Finally, we pay attention to different methods for selecting initialization vectors for the block cipher modes, and prove security for a number of different selection policies. In particular, we introduce the concept of a `generalized counter', and prove that generalized counters suffice for security in (full-width) CFB and OFB modes and that generalized counters encrypted using the block cipher (with the same key) suffice for all three modes.

Note: This was originally written about four years ago. I've finally gotten around to tidying it up sufficiently. I suspect that some of the results have been superceded since it was originally written (e.g., by Dan Bernstein (2005)), but I think I'd rather publish it as is. Besides, the results on ciphertext stealing and IV policy still seem new and useful. There was originally going to be a section on CBCMAC as well, but I forgot how the proof was going to work and I've lost my notes. I don't think that this is a great loss, since the result is very much out of date now anyway.