A Scheme to Base a Hash Function on a Block Cipher

Abstract. This article discusses the provable security of an iterated hash function using a block cipher. It assumes the construction using the Matyas-Meyer-Oseas (MMO) scheme for the compression function and the Merkle-Damg̊ard with a permutation (MDP) for the domain extension transform. It is shown that this kind of hash function, MDP-MMO, is indifferentiable from the variable-input-length random oracle in the ideal cipher model. It is also shown that HMAC using MDP-MMO is a pseudorandom function if the underlying block cipher is a pseudorandom permutation under the related-key attack with respect to the permutation used in MDP. Actually, the latter result also assumes that the following function is a pseudorandom bit generator: (EIV (K ⊕ opad)⊕K ⊕ opad)k(EIV (K ⊕ ipad)⊕K ⊕ ipad), where E is the underlying block cipher, IV is the fixed initial value of MDP-MMO, and opad and ipad are the binary strings used in HMAC. This assumption still seems reasonable for actual block ciphers, though it cannot be implied by the pseudorandomness of E as a block cipher. The results of this article imply that the security of a hash function may be reduced to the security of the underlying block cipher to more extent with the MMO compression function than with the Davies-Meyer (DM) compression function, though the DM scheme is implicitly used by the widely used hash functions such as SHA-1 and MD5.