A Scheme to base a Hash Function on a Block Cipher

概要

論文の詳細を見る
This article discusses the provable security of an iteratedhash function using a block cipher. It assumes the construction usingthe Matyas-Meyer-Oseas (MMO) scheme for the compression functionand the Merkle-Damg˚ard with a permutation (MDP) for the domainextension transform. It is shown that this kind of hash function, MDPMMO,is indifferentiable from the variable-input-length random oraclein the ideal cipher model. It is also shown that HMAC using MDPMMOis a pseudorandom function if the underlying block cipher is apseudorandom permutation under the related-key attack with respect tothe permutation used in MDP. Actually, the latter result also assumesthat the following function is a pseudorandom bit generator:(E_<IV>(K ⊕ opad) ⊕ K ⊕ opad)||(E_<IV> (K ⊕ ipad) ⊕ K ⊕ ipad) ,where E is the underlying block cipher, IV is the fixed initial value ofMDP-MMO, and opad and ipad are the binary strings used in HMAC.This assumption still seems reasonable for actual block ciphers, thoughit 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 maybe reduced to the security of the underlying block cipher to more extentwith the MMO compression function than with the Davies-Meyer (DM)compression function, though the DM scheme is implicitly used by thewidely used hash functions such as SHA-1 and MD5.