1MDx-MAC and Building Fast MACs from Hash Functions

Abstract. We consider the security of message authentication code (MAC) algorithms, and the construction of MACs from fast hash func-tions. A new forgery attack applicable to all iterated MAC algorithms is described, the ¯rst known such attack requiring fewer operations than ex-haustive key search. Existing methods for constructing MACs from hash functions, including the secret pre¯x, secret su±x, and envelope meth-ods, are shown to be unsatisfactory. Motivated by the absence of a secure, fast MAC algorithm not based on encryption, a new generic construction (MDx-MAC) is proposed for transforming any secure hash function of the MD4-family into a secure MAC of equal or smaller bitlength and comparable speed.