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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Damgård I. A design principle for hash functions. In: Proceedings of the 9th Annual International Cryptology Conference, Santa Barbara, 1989. 416–427
Merkle R C. One way hash functions and DES. In: Proceedings of the 9th Annual International Cryptology Conference, Santa Barbara, 1989. 428–446
Bellare M, Rogaway P. Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, 1993. 62–73
Bellare M, Rogaway P. Optimal asymmetric encryption. In: Advances in Cryptology — EUROCRYPT’94. Berlin: Springer, 1995. 92–111
Andreeva E, Mennink B, Preneel B. Open problems in hash function security. Des Code Cryptogr, 2015, 77: 611–631
Naito Y. Indifferentiability of double-block-length hash function without feed-forward operations. In: Proceedings of the 22nd Australasian Conference on Information Security and Privacy, Auckland, 2017. 38–57
Bellare M, Boldyreva A, Palacio A. An uninstantiable random-oracle-model scheme for a hybrid-encryption problem. In: Advances in Cryptology - EUROCRYPT 2004. Berlin: Springer, 2004. 171–188
Canetti R, Goldreich O, Halevi S. The random oracle methodology, revisited (preliminary version). In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, Dallas, 1998. 209–218
Canetti R, Goldreich O, Halevi S. On the random-oracle methodology as applied to length-restricted signature schemes. In: Theory of Cryptography. Berlin: Springer, 2004. 40–57
Maurer U M, Renner R, Holenstein C. Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Proceedings of the 1st Theory of Cryptography Conference on Theory of Cryptography, Cambridge, 2004. 21–39
Coron J, Dodis Y, Malinaud C, et al. Merkle-damgård revisited: how to construct a hash function. In: Proceedings of the 25th Annual International Cryptology Conference, Santa Barbara, 2005. 430–448
Lee J. Indifferentiability of the sum of random permutations toward optimal security. IEEE Trans Inform Theor, 2017, 63: 4050–4054
Maurer U, Renner R. From indifferentiability to constructive cryptography (and back). In: Proceedings of the 14th International Conference on Theory of Cryptography, Beijing, 2016. 3–24
Moody D, Paul S, Smith-Tone D. Improved indifferentiability security bound for the JH mode. Des Code Cryptogr, 2016, 79: 237–259
Bagheri N, Gauravaram P, Knudsen L R, et al. The suffix-free-prefix-free hash function construction and its indifferentiability security analysis. Int J Inf Secur, 2012, 11: 419–434
Chang D, Lee S, Nandi M, et al. Indifferentiable security analysis of popular hash functions with prefix-free padding. In: Proceedings of the 12th international conference on Theory and Application of Cryptology and Information Security, Shanghai, 2006. 283–298
Chang D, Nandi M. Improved indifferentiability security analysis of chopmd hash function. In: Proceedings of the 15th International Workshop on Fast Software Encryption, Lausanne, 2008. 429–443
Chang D, Sung J, Hong S, et al. Indifferentiable security analysis of choppfmd, chopmd, a chopmdp, chopwph, chopni, chopemd, chopcs, and chopesh hash domain extensions. IACR Cryptol ePrint Arch, 2008, 2008: 407
Gong Z, Lai X, Chen K. A synthetic indifferentiability analysis of some block-cipher-based hash functions. Des Code Cryptogr, 2008, 48: 293–305
Bellare M, Ristenpart T. Multi-property-preserving hash domain extension and the EMD transform. In: Proceedings of the 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, 2006. 299–314
Hirose S, Park J H, Yun A. A simple variant of the Merkle-Damgård scheme with a permutation. J Cryptol, 2012, 25: 271–309
Hirose S. Sequential hashing with minimum padding. Cryptography, 2018, 2: 11
Liskov M. Constructing an ideal hash function from weak ideal compression functions. In: Proceedings of the 13th International Workshop on Selected Areas in Cryptography, Montreal, 2006. 358–375
Acknowledgements
This work was supported by National Natural Science Foundation of China (Grant Nos. 61602302, 61472250, 61672347), Natural Science Foundation of Shanghai (Grant No. 16ZR1416400), Shanghai Excellent Academic Leader Funds (Grant No. 16XD1401300), and 13th Five-Year National Development Fund of Cryptography (Grant No. MMJJ20170114).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Ammour, K., Wang, L. & Gu, D. Pseudo random oracle of Merkle-Damgård hash functions revisited. Sci. China Inf. Sci. 62, 32112 (2019). https://doi.org/10.1007/s11432-018-9568-2
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11432-018-9568-2