iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-642-32298-3_10
Indifferentiability of Domain Extension Modes for Hash Functions | SpringerLink
Skip to main content

Indifferentiability of Domain Extension Modes for Hash Functions

  • Conference paper
Trusted Systems (INTRUST 2011)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 7222))

Included in the following conference series:

Abstract

In this paper, we show that four domain extension modes for hash functions: pfMD, chopMD, NMAC and HMAC have different indifferentiable security levels. Our synthetic analysis shows the chopMD, NMAC and HMAC modes can sustain more weaknesses of the compression function than the pfMD mode. For the pfMD mode, there exist 12 out of 20 collision resistant PGV hash functions which are indifferentiable from a random oracle. This is an improvement on the result of Chang et al. For the chopMD, NMAC and HMAC modes, all the 20 PGV compression functions are indifferentiable from a random oracle. The chopMD mode has better indifferentiable security bound but lower output size than the pfMD, NMAC and HMAC mode; and the HMAC mode can be implemented easier than NMAC. We also show that there exist flaws in the indifferentiability proofs by Coron et al., Chang et al. and Gong et al.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Andreeva, E., Neven, G., Preneel, B., Shrimpton, T.: Seven-Property-Preserving Iterated Hashing: ROX. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 130–146. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  2. Bellare, M., Ristenpart, T.: Multi-Property-Preserving Hash Domain Extension and the EMD Transform. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 299–314. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  3. Bellare, M., Ristenpart, T.: Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 399–410. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  4. Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the Indifferentiability of the Sponge Construction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  5. Bhattacharyya, R., Mandal, A., Nandi, M.: Indifferentiability Characterization of Hash Functions and Optimal Bounds of Popular Domain Extensions. In: Roy, B., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 199–218. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  6. Black, J., Rogaway, P., Shrimpton, T.: Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 320–335. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  7. 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. U.S. Patent Number 4,908,861, March 13 (1990)

    Google Scholar 

  8. 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, vol. 4284, pp. 283–298. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  9. Chang, D., Nandi, M.: Improved Indifferentiability Security Analysis of chopMD Hash Function. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 429–443. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  10. Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård Revisited: How to Construct a Hash Function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005)

    Google Scholar 

  11. Coron, J.S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgard Revisited: How to Construct a Hash Function (Full Version) (2007), http://people.csail.mit.edu/dodis/ps/merkle.ps ; A preliminary version was accepted by CRYPTO 2005. LNCS, vol. 3621, pp. 430–448 (2005)

  12. Coron, J.-S., Patarin, J., Seurin, Y.: The Random Oracle Model and the Ideal Cipher Model Are Equivalent. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 1–20. Springer, Heidelberg (2008)

    Google Scholar 

  13. Damgård, I.B.: A Design Principle for Hash Functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)

    Google Scholar 

  14. Dodis, Y., Reyzin, L., Rivest, R.L., Shen, E.: Indifferentiability of Permutation-Based Compression Functions and Tree-Based Modes of Operation, with Applications to MD6. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 104–121. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  15. Dodis, Y., Ristenpart, T., Shrimpton, T.: Salvaging Merkle-Damgård for Practical Applications. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 371–388. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  16. Gong, Z., Lai, X., Chen, K.: A Synthetic Indifferentiability Analysis of Some Block-Cipher-Based Hash Functions. Designs, Codes and Cryptography 48(3) (September 2008)

    Google Scholar 

  17. Hirose, S.: Some Plausible Constructions of Double-Block-Length Hash Functions. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 210–225. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  18. Hirose, S., Park, J.H., Yun, A.: A Simple Variant of the Merkle-Damgård Scheme with a Permutation. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 113–129. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  19. Hirose, S., Park, J., Yun, A.: A Simple Variant of the Merkle-Damgard Scheme with a Permutation. Journal of Cryptology (online first), doi:10.1007/s00145-010-9095-5

    Google Scholar 

  20. Kuwakado, H., Morii, M.: Indifferentiability of single-block-length and rate-1 compression functions. IEICE Trans. Fundamentals e90-A, 2301–2308 (2007)

    Article  Google Scholar 

  21. Kuwakado, H., Hirose, S.: Differentiability of four prefix-free PGV hash functions. IEICE Electronics Express 6(13), 955–958 (2009)

    Article  Google Scholar 

  22. Luo, Y., Gong, Z., Duan, M., Zhu, B., Lai, X.: Revisiting the Indifferentiability of PGV Hash Functions. Cryptology ePrint Archive: Report 2009/265

    Google Scholar 

  23. Maurer, U., Renner, R., Holenstein, C.: Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  24. Maurer, U., Tessaro, S.: Domain Extension of Public Random Functions: Beyond the Birthday Barrier. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 187–204. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  25. Merkle, R.C.: One Way Hash Functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, Heidelberg (1990)

    Google Scholar 

  26. Preneel, B., Govaerts, R., Vandewalle, J.: Hash Functions Based on Block Ciphers: A Synthetic Approach. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 368–378. Springer, Heidelberg (1994)

    Google Scholar 

  27. Winternitz, R.: A secure one-way hash function built from DES. In: Proceedings of the IEEE Symposium on Information Security and Privacy, pp. 88–90 (1984)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Luo, Y., Lai, X., Gong, Z. (2012). Indifferentiability of Domain Extension Modes for Hash Functions. In: Chen, L., Yung, M., Zhu, L. (eds) Trusted Systems. INTRUST 2011. Lecture Notes in Computer Science, vol 7222. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32298-3_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-32298-3_10

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-32297-6

  • Online ISBN: 978-3-642-32298-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics