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

M. Bellare, R. Guerin, P. Rogaway

We describe a new approach for authenticating a message using a
finite pseudorandom function (PRF). Our "XOR MACs" have several nice
features, including parallelizability, incrementality, and provable
security. 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.