Constructing VIL-MACs from FIL-MACs: Message authentication under weakened assumptions

Authors: J. An and M. Bellare

Abstract: Many practical MACs are designed by iterating applications of some fixed-input-length (FIL) primitive, namely one like a block cipher or compression function that only applies to data of a fixed length. Existing security analyses of these constructions either require a stronger security property from the FIL primitive (eg.~pseudorandomness) than the unforgeability required of the final MAC, or, as in the case of HMAC, make security assumptions about the iterated function itself. In this paper we consider the design of iterated MACs under the (minimal) assumption that the given FIL primitive is itself a MAC. We look at three popular transforms, namely CBC, Feistel and the Merkle-Damgard method, and ask for each whether it preserves unforgeability. We show that the answer is no in the first two cases and yes in the third. The last yields an alternative cryptographic hash function based MAC which is secure under weaker assumptions than existing ones.

Ref: Extended abstract in Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes in Computer Science Vol. 1666, M. Wiener ed, Springer-Verlag, 1999. Full paper available below.

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