Hash Functions and MAC Algorithms Based on Block Ciphers B. Preneel* Katholieke Universiteit Leuven Department Electrical Engineering-ESAT Kardinaal Mercierlaan 94 B-3001 Heverlee, Belgium. Email : bart.preneel@esat .kuleuven.ac .be www. es at. kuleuven, ac. be/~ preneel Abstract. This paper reviews constructions of hash functions and MAC algorithms based on block ciphers. It discusses the main requirements for these cryptographic primitives, motivates these constructions, and presents the state of the art of both attacks and security proofs. 1 Introduction Hash functions and MAC algorithms are important tools to protect information integrity. Together with digital signature schemes, they play an important role for securing our electronic interactions, in applications such as electronic cash and electronic commerce. This paper discusses how to reduce the construction of these cryptographic primitives to that of another primitive, namely a block cipher. The focus is on the relation between the security and performance of the primitives. Section 2 contains (informal) definitions of hash functions and MAC algorithms. Next a general model for these functions is presented in Sect. 3. Section 4 lists brute force attacks on hash functions, and overviews constructions for hash functions based on block ciphers. This is followed by a similar treatment of MAC algorithms in Sect. 5. Finally some concluding remarks are made. 2 Definitions 2.1 Hash functions Hash functions were introduced in cryptography by W. Diffie and M. Hellman together with the concept of digital signatures. The basic idea is to sign a short 'digest' or 'fingerprint' of the message rather than the message itself. Hash functions are used in a more general context to replace the protection of the integrity of a large amount of data (in principle of arbitrary size) by a * F.W.O. postdoctoral researcher, sponsored by the National Fund for Scientific Re- search - Flanders (Belgium).271 short string of fixed length (m bits), the hash result. Applications require that the evaluation of the hash function is 'efficient'. Moreover, the hash function should be publicly known, and should not require any secret parameter (these hash functions have also been called MDCs or Manipulation Detection Codes). For cryptographic applications, one imposes three security requirements, that can be stated informally as follows: preimage resistance: for essentially all outputs, it is 'computationally infea- sible' to find any input hashing to that output; 2nd-preimage resistance: it is 'computationally infeasible' to find a second (distinct) input hashing to the same output as any given input; collision resistance: it is 'computationatly infeasible' to find two colliding in- puts, i.e., x and x' ~ x with h(x) = h(x'). A hash function that is preimage resistant and 2nd-preimage resistant is called one-way; a hash function that satisfies the three security properties is called collision resistant. Collision resistance may be required for digital signa- tures to preclude repudiation by the sender: if she can find a collision pair (x, x'), she can later claim that she has signed x' rather than x. Not all applications need collision resistance; hash functions that are only one-way are more efficient in terms of computation and storage (el. Sect. 4.1). Hash fimctions have also been used to construct new digital signature schemes (where the hash function is an integral part of the design). Other applications include the commitment to information without revealing it, the protection of pass-phrases, tick payments, key derivation, and key agreement. It should be pointed out that hash functions have often been used in applications that require new security properties, for which they have not been evaluated. 2.2 MAC algorithms The banking world used MACs already in the seventies. A MAC is a hash func- tion that takes as input a second parameter, the secret key. The sender of a mes- sage appends the MAC to the information; the receiver recomputes the MAC and compares it to the transmitted version. He accepts the information as authentic only if both values are equal. The goal is that an eavesdropper, who can modify the message, does not know how the update the MAC accordingly. Hence the main security property for a MAC is that for someone who does not know the key, it should be compu- tationally infeasible to predict the MAC value for a given message. Unlike digital signatures, MAC algorithms can only be used between mutually trusting parties, but they are faster to compute and require less storage than digital signatures. The attack model is as follows: an opponent can choose a number of inputs xi, and obtain the corresponding MAC value hK(xi) (his choice of xi might depend on the outcome of previous queries, i.e., the attack may be adaptive). Next he has to come up with an input x (# xi, Vi) and the value hg(x), which has to be correct with probability significantly larger than 1/2 m, with m the number272 of bits in the MAC result. If the opponent succeeds in finding such a value, he is said to be capable of an existential forgery. If the opponent can choose the value of x, he is said to be capable of a selective forgery. If the success probability of the attack is close to 1, the forgery is called verifiable. An alternative strategy is to try to recover the secret key K from a number of message/MAC pairs. A key recovery is more devastating than a forgery, since it allows for arbitrary selective forgeries. A MAC is said to be secure if it is 'computationally infeasible' to perform an existential forgery under an adaptive chosen text attack. Note that in many applications only known text attacks are feasible. For example, in a wholesale banking application one could gain a substantial profit if one could choose a single message and obtain its MAC. Nevertheless, it seems prudent to work with a strong definition. 3 General model Almost all hash functions are iterative processes, which repeatedly apply a simple compression function f. Therefore they are called iterated hash functions. The input x is padded to a multiple of the block size, and is divided into t blocks denoted xl through xt. It is then processed block by block. The