Merkle-Damgård Revisited: How to Construct a Hash Function
Merkle-Damgård Revisited: How to Construct a Hash Function
复制标题
DOI：
10.1007/11535218_26
复制
发表时间：
2005-08
期刊：
影响因子：
--
通讯作者：
J. Coron;Y. Dodis;Cécile Malinaud;P. Puniya
中科院分区：
文献类型：
--
作者：
J. Coron;Y. Dodis;Cécile Malinaud;P. Puniya
构造散列函数的最常见方式（例如，SHA-1）是在输入消息上添加压缩函数。压缩函数通常是从头开始设计的，或者是由分组密码组成的。在本文中，我们介绍了一个新的安全概念的散列函数，比碰撞阻力。在这个概念下，当固定长度的构建块被视为随机预言机或理想块密码时，任意长度的哈希函数H必须表现为随机预言机。关键属性是，如果一个特定的结构满足这个定义，那么任何被证明是安全的密码系统，假设他是一个随机预言机，如果插入这个结构（仍然假设底层的固定长度原语是理想的），仍然是安全的。在本文中，我们证明了SHA-1和MD5等散列函数背后的当前设计原则-（加强的）Merkle-Damgård变换-并不满足这种安全概念。我们提供了几个可证明满足这一概念的构造;这些新的构造对普通的Merkle-Damgård构造引入了最小的变化，并且在实践中很容易实现。
The most common way of constructing a hash function (e.g., SHA-1) is to iterate a compression function on the input message. The compression function is usually designed from scratch or made out of a block-cipher. In this paper, we introduce a new security notion for hash-functions, stronger than collision-resistance. Under this notion, the arbitrary length hash functionHmust behave as a random oracle when the fixed-length building block is viewed as a random oracle or an ideal block-cipher. The key property is that if a particular construction meets this definition, then any cryptosystem proven secure assumingHis a random oracle remains secure if one plugs in this construction (still assuming that the underlying fixed-length primitive is ideal). In this paper, we show that the current design principle behind hash functions such as SHA-1 and MD5 — the (strengthened) Merkle-Damgård transformation — does not satisfy this security notion. We provide several constructions that provably satisfy this notion; those new constructions introduce minimal changes to the plain Merkle-Damgård construction and are easily implementable in practice.