Security of Practical Cryptosystems Using Merkle-Damgard Hash Function in the Ideal Cipher Model.
Yusuke Naito, Kazuki Yoneyama, Lei Wang, Kazuo Ohta · 2009
Abstract. Since the Merkle-Damg˚ard (MD) type hash functions are differentiable from ROs even when compression functions are modeled by ideal primitives, there is no guarantee as to the security of cryptosystems when ROs are instantiated with structural hash functions. In this paper, we study the security of the instantiated cryptosystems whereas the hash functions have the well known structure of Merkle-Damg˚ard construction with Stam’s type-II compression function (denoted MD-TypeII) in the Ideal Cipher Model (ICM). Note that since the Type-II scheme includes the Davies-Meyer compression function, SHA-256 and SHA-1 have the MD-TypeII structure. We show that OAEP, RSA-KEM, PSEC-KEM, ECIES-KEM and many other encryption schemes are secure when using the MD-TypeII hash function. In order to show this, we customize the indifferentiability framework of Maurer, Renner and Holenstein. We call the customized framework “indifferentiability with condition”. In this framework, for some condition α that cryptosystem C satisfies, if hash function H is indifferentiable from RO under condition α, C is secure when RO is instantiated with H. We note the condition of “prefix-free ” that the above schemes satisfy. We show that the MD-TypeII hash function is indifferentiable from RO under this condition. When the output length of RO is incompatible with that of the hash function, the output size is expanded by