Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / block cipher modes, cbc, cfb, ofb

Date: received 13 Mar 2008, last revised 13 Mar 2008

Contact author: mdw at distorted org uk

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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.

Version: 20080317:212143 (All versions of this report)

Short URL: ia.cr/2008/121

Discussion forum: Show discussion | Start new discussion