著者

廣瀬 勝一 桑門 秀典

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告コンピュータセキュリティ(CSEC) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.71, pp.221-228, 2008-07-17

---

本稿では,ブロック暗号を用いた MMO 圧縮関数と MDP 定義域拡大より構成されるハッシュ関数 MDP-MMO の証明可能安全性を論じる。また理想暗号モデルを仮定して, MDP-MMC がランダムオラクルとの識別不能性 (indifferentiability) を満たすことを示す.次に,MDP で使用きれる置換に関する関連鍵攻撃の下でブロック暗号が擬似ランダム置換であれば,MDP-MMO を用いて構成される HMAC が擬似ランダム関数であることを示す.なお,HMAC に関する結果は,(Eiv(K?opad)?K?opad)??Eiv(K?ipad)?K?ipad) が擬似ランダムビット列生成器であるという仮定も要求する.ここで,E はブロック暗号,IV は MDP-MMO で定められた初期値,opad と ipad は HMAC で定められた系列である.この仮定は,E のブロック暗号としての擬似ランダム性により保証きれないものの,実現可能性の観点からは妥当であると考えられる.This article discusses the provable security of a hash function using a block cipher. It assumes the construction using the Matyas-Meyer-Oseas (MMO) scheme for the compression function and the Merkle-Damgard 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 a permutation used in MDP. Actually, the latter result also assumes that the following function is a pseudorandom bit generator: (Eiv(K竓賓pad)竓必竓賓pad)竏」竏」Eiv(K竓品pad)竓必竓品pad), 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.