XOR MACs: New methods for message authentication using finite pseudorandom functions

Authors: M. Bellare, R. Guerin and P. Rogaway

Abstract: We describe a new approach for authenticating messages. Our ``XOR MACs'' have several nice features, including parallelizability, incrementality, and provable security.

Our method uses any finite pseudorandom function (PRF). The finite PRF can be ``instantiated'' via DES (yielding an alternative to the CBC MAC), via the compression function of MD5 (yielding an alternative to various ``keyed MD5'' constructions), or in a variety of other ways.

The proven security is quantitative, expressing the adversary's inability to forge in terms of her (presumed) inability to break the underlying finite PRF. This is backed by attacks showing the analysis is tight. Our proofs exploit linear algebraic techniques, and relate the security of a given XOR scheme to the probability that a certain associated matrix is of full rank.

Our analysis shows that XOR schemes are actually more secure than the CBC MAC, in a sense that we can make precise.

Ref: Extended abstract in Advances in Cryptology - Crypto 95 Proceedings, Lecture Notes in Computer Science Vol. 963, D. Coppersmith ed, Springer-Verlag, 1995. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).

Related work