Pseudo random oracle of Merkle-Damgård hash functions revisited
Pseudo random oracle of Merkle-Damgård hash functions revisited
复制标题
重新审视 Merkle-Damgård 哈希函数的伪随机预言
DOI：
10.1007/s11432-018-9568-2
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Dawu Gu
中科院分区：
文献类型：
--
作者：
Kamel Ammour;Lei Wang;Dawu Gu
遵循众所周知的随机预言方法，需要一个加密哈希函数来满足伪随机预言（PRO）的属性，这与随机预言没有区别。本文纯粹从理论角度重新审视了流行的哈希函数模式的 PRO 属性。原始Merkle-Damgård模式（有时称为强化Merkle-Damgård）由于长度扩展攻击而不能满足PRO安全性。为了解决这个问题，人们提出了一系列的变体，其中包括采用无前缀填充或修改最终的原语调用等调整。从这些调整中，我们得出了一个称为无前缀计算的通用结构属性。事实上，迄今为止发布的所有 PRO 安全 Merkle-Damgård 变体都是无前缀计算。因此，出现了一个关于 PRO 安全性本质的有趣问题：无前缀计算是 PRO 安全 Merkle-Damgård 哈希函数的必要条件吗？本文给出了否定的答案。我们研究了长度扩展抵抗和无前缀计算之间的区别，发现长度扩展抵抗并不一定意味着无前缀计算。因此，我们构建了一个专用的 Merkle-Damgård 变体作为反例，它是 PRO 安全的，但不是无前缀计算。
Following the well-known random oracle Methodology, a cryptographic hash function is required to satisfy the property of pseudo-random oracle (PRO), that is indifferentiable from a random oracle. This paper revisits the PRO property of popular hash function modes purely from a theoretical point of view. OriginalMerkle-Damgård mode (sometimes referred to as Strengthened Merkle-Damgård) does not satisfy the PRO security due to the length-extension attack. To remedy it, a series of variants have been proposed with tweaks of either adopting a prefix-free padding or modifying the final primitive call. From these tweaks, we derive a common structural property named prefix-free computing. Indeed, all PRO-secure Merkle-Damgård variants published so far are prefix-free computing. Hence, an interesting question with respect to the nature of PRO security arises: is prefix-free computing a necessary condition for PRO-secure Merkle-Damgård hash function? This paper gives a negative answer. We investigate the difference between length-extension resistance and prefix-free computing, and find that length-extension resistance does not necessarily imply prefix-free computing. Consequently, we construct a dedicated Merkle-Damgård variant as a counterexample that is PRO-secure but not prefix-free computing.
登录
查看更多内容
DOI：
10.1007/11935230_20
发表时间：
2006-12
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
M. Bellare;Thomas Ristenpart
通讯作者：
M. Bellare;Thomas Ristenpart
DOI：
10.3390/cryptography2020011
发表时间：
2018-06
期刊：
Cryptogr.
影响因子：
--
作者：
Shoichi Hirose
通讯作者：
Shoichi Hirose
DOI：
10.1007/978-3-540-71039-4_27
发表时间：
2008-02
期刊：
--
影响因子：
--
作者：
D. Chang;M. Nandi
通讯作者：
D. Chang;M. Nandi
DOI：
10.1007/978-3-540-24638-1_2
发表时间：
2004-02
期刊：
--
影响因子：
--
作者：
U. Maurer;R. Renner;Clemens Holenstein
通讯作者：
U. Maurer;R. Renner;Clemens Holenstein
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