Reference: Fast Software Encryption (FSE) 2004. Lecture Notes in Computer Science, vol. ??, pp. ??--??. Earlier version in ePrint Archive (eprint.iacr.org), Report 2003/069, April 2003.
Abstract: We propose a block-cipher mode of operation, EAX, for solving the problem of authenticated-encryption with associated-data (AEAD). Given a nonce N, a message M, and a header H, our mode protects the privacy of M and the authenticity of both M and H. Strings N, M, and H are arbitrary bit strings, and the mode uses 2⌈|M|/n ⌉ + ⌈|H|/n⌉ + ⌈|N|/n⌉ block-cipher calls when these strings are nonempty and n is the block length of the underlying block cipher. Among EAX's characteristics are that it is on-line (the length of a message isn't needed to begin processing it) and a fixed header can be pre-processed, effectively removing the per-message cost of binding it to the ciphertext.
EAX is obtained by first creating a generic-composition method, EAX2, and then collapsing its two keys into one. EAX is provably secure under a standard complexity-theoretic assumption. The proof of this fact is novel and involved.
EAX is an alternative to CCM, which was created to answer the
wish within standards bodies for a fully-specified and patent-free AEAD mode.
As such, CCM and EAX are two-pass schemes, with one pass for achieving privacy
and one for authenticity. EAX is simpler and more efficient than CCM,
avoiding, for example, elaborate padding rules or nonstandard parameters. With
EAX we aimed to do as well as possible, within the space of two-pass schemes,
with regard to issues of efficiency, simplicity, elegance, ease of correct use,
and provable-security guarantees.
Availability: pdf or ps
Rogaway's home page.