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. (Here n is the block length of the underlying block cipher and [.] denotes the ceiling operation.) 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, EAXE, 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.
Ref: An extended abstract of this paper appeared in the Proceedings of the 11th International Workshop on Fast Software Encryption (FSE 2004), Lecture Notes in Computer Science Vol. 3017, R. Bimal and W. Meier eds, Springer-Verlag, 2004. Full paper available below.
Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).