Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1007/s11432-018-9568-2 | Science China Information Sciences |
Keywords | DocType | Volume |
Merkle-Damgård, random oracle, indifferentiability, prefix free, length extension attack | Journal | 62 |
Issue | ISSN | Citations |
3 | 1869-1919 | 0 |
PageRank | References | Authors |
0.34 | 14 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kamel Ammour | 1 | 0 | 0.34 |
Lei Wang | 2 | 0 | 0.34 |
Dawu Gu | 3 | 644 | 103.50 |