Abstract
The contribution of the paper is two-fold. First, we design a novel permutation-based hash mode of operation FP, and analyze its security. We show that any n-bit hash function that uses the FP mode is indifferentiable from a random oracle up to 2n/2 queries (up to a constant factor), if the underlying 2n-bit permutation is free from any structural weaknesses. Based on our further analysis and experiments, we conjecture that the FP mode is resistant to all non-trivial generic attacks with work less than the brute force, mainly due to its large internal state. We compare the FP mode with other permutation-based hash modes.
To put this into perspective, we propose a concrete hash function SAMOSA using the new mode and the P-permutations of the SHA-3 finalist grøstl. Based on our analysis we claim that the SAMOSA family cannot be attacked with work significantly less than the brute force. We also provide hardware implementation (FPGA) results for SAMOSA to compare it with the SHA-3 finalists. In our implementations, SAMOSA family consistently beats Grøstl, Blake and Skein in the throughput to area ratio. With more efficient underlying permutation, it seems possible to design a hash function based on the FP mode that can achieve even higher performances.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andreeva, E., Mennink, B., Preneel, B.: The parazoa family: generalizing the sponge hash functions. Int. J. Inf. Sec. 11(3), 149–165 (2012)
ATHENa Project Website, http://cryptography.gmu.edu/athena
Biryukov, A., Dunkelman, O., Keller, N., Khovratovich, D., Shamir, A.: Key Recovery Attacks of Practical Complexity on AES-256 Variants with up to 10 Rounds. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 299–319. Springer, Heidelberg (2010)
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Sponge Functions. In: ECRYPT 2007 (2007), http://sponge.noekeon.org/SpongeFunctions.pdf (accessed March 2012)
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)
Bhattacharyya, R., Mandal, A.: On the Indifferentiability of Fugue and Luffa. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 479–497. Springer, Heidelberg (2011)
Bhattacharyya, R., Mandal, A., Nandi, M.: Security 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)
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)
Blackburn, S.R., Stinson, D.R., Upadhyay, J.: On the complexity of the herding attack and some related attacks on hash functions. Des. Codes Cryptography 64(1-2), 171–193 (2012)
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)
De Cannière, C., Sato, H., Watanabe, D.: The Luffa Hash Function. In: The 1st SHA-3 Candidate Conference
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)
Gaj, K., Homsirikamol, E., Rogawski, M., Shahid, R., Sharif, M.U.: Comprehensive Evaluation of High-Speed and Medium-Speed Implementations of Five SHA-3 Finalists Using Xilinx and Altera FPGAs. Cryptology ePrint Archive, Report 2012/368 (2012), http://eprint.iacr.org/2012/368.pdf
Gauravaram, P., Knudsen, L., Matusiewicz, K., Mendel, F., Rechberger, C., Schlaffer, M., Thomsen, S.: Groestl - a SHA-3 candidate. In: The 1st SHA-3 Candidate Conference
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)
Küçük, Ö.: Design and Analysis of Cryptographic Hash Functions. PhD thesis, KU Leuven (2012), http://www.iacr.org/phds/?p=detail&entry=777
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)
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)
Matusiewicz, K., Naya-Plasencia, M., Nikolić, I., Sasaki, Y., Schläffer, M.: Rebound Attack on the Full Lane Compression Function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 106–125. Springer, Heidelberg (2009)
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)
Moody, D., Paul, S., Smith-Tone, D.: Improved Indifferentiability Security Bound for the JH Mode. In: 3rd SHA-3 Candidate Conference (2012)
NIST. Secure hash standard. In: Federal Information Processing Standard, FIPS 180-2 (April 1995)
Nandi, M., Paul, S.: Speeding Up the Wide-Pipe: Secure and Fast Hashing. In: Gong, G., Gupta, K.C. (eds.) INDOCRYPT 2010. LNCS, vol. 6498, pp. 144–162. Springer, Heidelberg (2010)
Latif, K., Rao, M.M., Aziz, A., Mahboob, A.: Efficient Hardware Implementations and Hardware Performance Evaluation of SHA-3 Finalists. In: The Third SHA-3 Candidate Conference, Washington D.C., March 22-23 (2012)
Paul, S., Homsirikamol, E., Gaj, K.: A Novel Permutation-based Hash Mode of Operation FP and The Hash Function SAMOSA. Full version will appear in IACR ePrint Archive
Rivest, R.: The MD5 message-digest algorithm. IETF RFC 1321 (1992)
Rivest, R.: The MD6 Hash Function
Wu, H.: The JH Hash Function. In: The 1st SHA-3 Candidate Conference (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Paul, S., Homsirikamol, E., Gaj, K. (2012). A Novel Permutation-Based Hash Mode of Operation FP and the Hash Function SAMOSA . In: Galbraith, S., Nandi, M. (eds) Progress in Cryptology - INDOCRYPT 2012. INDOCRYPT 2012. Lecture Notes in Computer Science, vol 7668. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34931-7_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-34931-7_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34930-0
Online ISBN: 978-3-642-34931-7
eBook Packages: Computer ScienceComputer Science (R0)