Home Original page

Speeding Up the Wide-Pipe: Secure and Fast Hashing

Abstract

In this paper we propose a new sequential mode of operation – the Fast wide pipe or FWP for short – to hash messages of arbitrary length. The mode is shown to be (1) preimage-resistance preserving, (2) collision-resistance-preserving and, most importantly, (3) indifferentiable from a random oracle up to \(\mathcal{O}(2^{n/2})\) compression function invocations. In addition, our rigorous investigation suggests that any variants of Joux’s multi-collision, Kelsey-Schneier 2nd preimage and Herding attack are also ineffective on this mode. This fact leads us to conjecture that the indifferentiability security bound of FWP can be extended beyond the birthday barrier. From the point of view of efficiency, this new mode, for example, is always faster than the Wide-pipe mode when both modes use an identical compression function. In particular, it is nearly twice as fast as the Wide-pipe for a reasonable selection of the input and output size of the compression function. We also compare the FWP with several other modes of operation.

Preview

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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)

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

  3. Bhattacharya, 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)

  4. Bhattacharyya, R., Mandal, A., Nandi, M.: NandiSecurity Analysis of the Mode of JH Hash Function. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 168–191. Springer, Heidelberg (2010)

  5. Biham, E., Dunkelman, O.: A framework for iterative hash functions – HAIFA. In: Second NIST Cryptographic Hash Workshop 2006 (2006)

  6. Brassard, G. (ed.): CRYPTO 1989. LNCS, vol. 435. Springer, Heidelberg (1990)

  7. 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)

  8. Damgård, I.: A Design Principle for Hash Functions. In: Brassard [6], pp. 416–427

  9. Rivest, R. et al.: The MD6 Hash Function 16

  10. 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)

  11. Joux, A.: Multicollisions in Iterated Hash Functions: Application to Cascaded Constructions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004)

  12. Kelsey, J., Kohno, T.: Herding Hash Functions and the Nostradamus Attack. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 183–200. Springer, Heidelberg (2006)

  13. Kelsey, J., Schneier, B.: Second Preimages on n-Bit Hash Functions for Much Less than 2n Work. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 474–490. Springer, Heidelberg (2005)

  14. Klimov, A., Shamir, A.: New Cryptographic Primitives Based on Multiword T-Functions. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 1–15. Springer, Heidelberg (2004)

  15. Lucks, S.: A failure-friendly design principle for hash functions. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 474–494. Springer, Heidelberg (2005)

  16. Maurer, U.M., 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)

  17. Merkle, R.C.: One Way Hash Functions and DES. In: Brassard [6], pp. 428–446

  18. NIST. Secure hash standard. In: Federal Information Processing Standard, FIPS-180 (1993)

  19. NIST. Secure hash standard. In: Federal Information Processing Standard, FIPS 180-1 (April 1995)

  20. Rivest, R.: The MD4 message-digest algorithm. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 303–311. Springer, Heidelberg (1991)

  21. Rivest, R.: The MD5 message-digest algorithm. IETF RFC 1321 (1992)

  22. Wagner, D.: A Generalized Birthday Problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (2002)

  23. Wu, H.: The JH Hash Function. In: The 1st SHA-3 Candidate Conference

Download references

Author information

Authors and Affiliations

  1. C.R. Rao AIMSCS Institute, Hyderabad, India

    Mridul Nandi

  2. National Institute of Standards and Technology, Security Technology Group, 100 Bureau Dr., MS 8931, Gaithersburg, MD, 20899, USA

    Souradyuti Paul

  3. Dept. ESAT/COSIC, Katholieke Universiteit Leuven, Kasteelpark Arenberg 10, B–3001, Leuven-Heverlee, Belgium

    Souradyuti Paul

Authors

  1. Mridul Nandi
  2. Souradyuti Paul

Editor information

Editors and Affiliations

  1. Department of Electrical and Computer Engineering, University of Waterloo, Waterloo, Ontario, Canada

    Guang Gong

  2. Indian Statistical Institute, Applied Statistics Unit, 203 B. T. Road, 700108, Kolkata, India

    Kishan Chand Gupta

About this paper

Cite this paper

Nandi, M., Paul, S. (2010). Speeding Up the Wide-Pipe: Secure and Fast Hashing. In: Gong, G., Gupta, K.C. (eds) Progress in Cryptology - INDOCRYPT 2010. INDOCRYPT 2010. Lecture Notes in Computer Science, vol 6498. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17401-8_12

Download citation

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Publish with us