×

zbMATH — the first resource for mathematics

A synthetic indifferentiability analysis of some block-cipher-based hash functions. (English) Zbl 1185.94052
Summary: At ASIACRYPT’06, D. Chang, S. Lee, M. Nandi and M. Yung [Lect. Notes Comput. Sci. 4284, 283–298 (2006; Zbl 1172.94567)] analyzed the indifferentiability of some popular hash functions based on block ciphers, namely, the twenty collision resistant PGV, the MDC2 and the PBGV hash functions, etc. In particular, two indifferentiable attacks were presented on the four of the twenty collision resistant PGV and the PBGV hash functions with the prefix-free padding. In this article, a synthetic indifferentiability analysis of some block-cipher-based hash functions is considered. First, a more precise definition is proposed on the indifferentiability adversary in block-cipher-based hash functions. Next, the advantage of indifferentiability is separately analyzed by considering whether the hash function is keyed or not. Finally, a limitation is observed in Chang et al.’s indifferentiable attacks on the four PGV and the PBGV hash functions. The formal proofs show the fact that those hash functions are indifferentiable from a random oracle in the ideal cipher model with the prefix-free padding, the NMAC/HMAC and the chop construction.

MSC:
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bellare M., Rogaway P.: Random oracle are practical: a paradigm for designing efficient protocols. In: ACM CCS’93, ACM, pp. 62–73 (1993).
[2] Black J., Rogaway P., Shrimpton T.: Black-box analysis of the black-cipher-based hash-function constructions from PGV. In: Advances in Cryptology–CRYPTO’02. LNCS 2442, pp. 320–335 (2002). · Zbl 1026.94522
[3] Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. SIAM J Comput. 32(3), 586–615 (2003) · Zbl 1046.94008 · doi:10.1137/S0097539701398521
[4] Brachtl B.O., Coppersmith D., Hyden M.M., Matyas S.M., Meyer C.H., Oseas J., Pilpel S., Schilling M.: Data authentication using modification detection codes based on a public one way encryption function. US Patent Number 4,908,861, 13 March 1990.
[5] Brown D.: Generic groups, collision resistance, and ECDSA. http://eprint.iacr.org/2002/026 (2002) Accessed 27 Feb 2002. · Zbl 1158.94379
[6] Canetti R., Goldreich O., Halevi S.: The randoom oracle methodology, revisited. In: Proceedings of 30th ACM Symposium on the Theory of Computing. ACM Press, pp. 209–218 (1998). · Zbl 1027.68603
[7] Chang D.H., Lee S.J., Nandi M., Yung M.: Indifferentiable security analysis of popular hash functions with prefix-free padding. In: Lai X., Chen K. (eds.), ASIACRYPT 2006, LNCS 4284, pp. 283–298 (2006). · Zbl 1172.94567
[8] Coron J.S., Dodis Y., Malinaud C., Puniya P.: Merkle-damgard revisited: how to construct a hash function. In: Advances in Cryptology–CRYPTO’05, LNCS 3621, pp. 21–39 (2005). · Zbl 1145.94436
[9] Damgard I.: A design principle for hash functions. In: Advances in Cryptology, Cyrpto’89, LNCS 435, pp. 416–427 (1989).
[10] Dent A.: Adapting the weakness of the random oracle to the generic model. In: ASIACRYPT 2002, LNCS 2501, pp. 101–109 (2002). · Zbl 1065.94546
[11] Fujisaki E., Okamoto T.: Secure integration of asymmetric and symmetric encryption schemes. In: CRYPTO’99, LNCS 1666, pp. 537–554 (1999). · Zbl 0942.94019
[12] Goldwasser S., Tauman Y.: On the (In) security of the Fiat-Shamir paradigm. In: FOCS 2003, IEEE Computer Society, pp. 102–122 (2003).
[13] Hirose S.: Some plausible constructions of double-block-length hash functions. In: FSE 2006, LNCS 4047, pp. 210–225 (2006). · Zbl 1234.94046
[14] Knudsen, L.R., Lai, X., Preneel, B.: Attacks on fast double block length hash functions. J. Cryptol. 11, 59–72 (1998) · Zbl 0972.94037 · doi:10.1007/s001459900035
[15] Lai X., Massey J.L.: Hash functions based on block ciphers. In: Advances in Cryptology-Eurocrypt’92, LNCS 658, pp. 55–70 (1993). · Zbl 0801.68046
[16] Lucks S.: A failure-friendly design principle for hash functions. In: ASIACRYPT 2005, LNCS 3788, pp. 474–494 (2005). · Zbl 1154.94414
[17] Maurer U., Renner R., Holenstein C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Theory of Cryptography–TCC 2004, LNCS 2951, pp. 21–39 (2004). · Zbl 1197.94196
[18] Merkle R.C.: One way hash functions and DES. In: Advances in Cryptology, Crypto’89, LNCS 435, pp. 428–446 (1989).
[19] Nielsen J.B.: Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case. In: CRYPTO’98, LNCS 2442, pp. 111–126 (2002). · Zbl 1027.68601
[20] Paillier P., Vergnaud D.: Discrete-log-based signatures may not be equivalent to discrete log. In: ASIACRYPT 2005, LNCS 3788, pp. 1–20 (2005). · Zbl 1146.94305
[21] Preneel B., Bosselaers A., Govaerts R., Vandewalle J.: Collision-free hash-functions based on blockcipher algorithms. In: Proceedings of 1989 International Carnahan Conference on Security Technology, pp. 203–210 (1989).
[22] Preneel B., Govaerts R., Vandewalle J.: Hash functions based on block ciphers: a synthetic approach. In: Advances in Cryptology-CRYPTO’93, LNCS 773, pp. 368–378 (1994). · Zbl 0877.94039
[23] Rogaway P., Shrimpton T.: Cryptographic hash-function basics: definitions, implications, and separations for preimage resistance, second-preimage resistance and collision resistance. In: FSE 2004, LNCS 3017, pp. 371–388 (2004). · Zbl 1079.68560
[24] Shannon, C.: Communication theory of secrecy systems. Bell Syst. Tech. J 28(4), 656–715 (1949) · Zbl 1200.94005
[25] Wang X., Yin Y., Yu H.: Finding collision in the Full SHA-1. In: CRYPTO’05, LNCS 3621, pp. 17–36 (2005). · Zbl 1145.94454
[26] Wang X., Yu H.: How to break MD5 and other hash functions. In: EUROCRYPT’05, LNCS 3494, pp. 19–35 (2005). · Zbl 1137.94359
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.