Paper 2004/278

The Extended Codebook (XCB) Mode of Operation

David A. McGrew and Scott R. Fluhrer

Abstract

We describe a block cipher mode of operation that implements a `tweakable' (super) pseudorandom permutation with an arbitrary block length. This mode can be used to provide the best possible security in systems that cannot allow data expansion, such as disk-block encryption and some network protocols. The mode accepts an additional input, which can be used to protect against attacks that manipulate the ciphertext by rearranging the ciphertext blocks. Our mode is similar to a five-round Luby-Rackoff cipher in which the first and last rounds do not use the conventional Feistel structure, but instead use a single block cipher invocation. The third round is a Feistel structure using counter mode as a PRF. The second and fourth rounds are Feistel structures using a universal hash function; we re-use the polynomial hash over a binary field defined in the Galois/Counter Mode (GCM) of operation for block ciphers. This choice provides efficiency in both hardware and software and allows for re-use of implementation effort. XCB also has several useful properties: it accepts arbitrarily-sized plaintexts and associated data, including any plaintexts with lengths that are no smaller than the width of the block cipher. This document is a pre-publication draft manuscript.