Abstract
Hamsi is one of 14 remaining candidates in NIST’s Hash Competition for the future hash standard SHA-3. Until now, little analysis has been published on its resistance to differential cryptanalysis, the main technique used to attack hash functions. We present a study of Hamsi’s resistance to differential and higher-order differential cryptanalysis, with focus on the 256-bit version of Hamsi. Our main results are efficient distinguishers and near-collisions for its full (3-round) compression function, and distinguishers for its full (6-round) finalization function, indicating that Hamsi’s building blocks do not behave ideally.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aumasson, J.P., Käsper, E., Knudsen, L.R., Matusiewicz, K., Odegaard, R., Peyrin, T., Schlffer, M.: Differential distinguishers for the compression function and output transformation of Hamsi-256. Cryptology ePrint Archive, Report 2010/091 (2010)
Bellare, M., Micciancio, D.: A new paradigm for collision-free hashing: Incrementality at reduced cost. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 163–192. Springer, Heidelberg (1997)
Bernstein, D.J.: Better price-performance ratios for generalized birthday attacks. In: SHARCS (2007), http://cr.yp.to/papers.html#genbday
Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: Note on zero-sum distinguishers of keccak-f. NIST mailing list (2010), http://keccak.noekeon.org/NoteZeroSum.pdf
Biham, E., Anderson, R.J., Knudsen, L.R.: Serpent: A new block cipher proposal. In: Vaudenay, S. (ed.) FSE 1998. LNCS, vol. 1372, pp. 222–238. Springer, Heidelberg (1998)
Khovratovich, D., Biryukov, A., Nikolić, I.: Distinguisher and related-key attack on the full AES-256. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 231–249. Springer, Heidelberg (2009)
Knudsen, L.R.: Truncated and higher order differentials. In: Preneel, B. (ed.) FSE 1994. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995)
Kücük, O.: The hash function Hamsi. Submission to NIST (January 2009), http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/HamsiUpdate.zip
Kücük, O.: Reference implementation of Hamsi. Submission to NIST (January 2009)
Lai, X.: Higher order derivatives and differential cryptanalysis. In: Blahut, R., Costello Jr., D., Maurer, U., Mittelholzer, T. (eds.) Communications and Cryptography, pp. 227–233. Kluwer, Dordrecht (1992)
Mendel, F., Nad, T.: A distinguisher for the compression function of simd-512. In: Roy, B.K., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 219–232. Springer, Heidelberg (2009)
Nikolić, I.: Near collisions for the compression function of Hamsi-256. CRYPTO rump session (2009), http://rump2009.cr.yp.to/936779b3afb9b48a404b487d6865091d.pdf
NIST: Announcing request for candidate algorithm nominations for a new cryptographic hash algorithm (SHA-3) family. Federal Register Notice. 72(112) (November 2007), http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf
Singh, B., Alexander, L., Burman, S.: On algebraic relations of Serpent S-boxes. Cryptology ePrint Archive, Report 2009/038 (2009)
Wagner, D.: The boomerang attack. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 156–170. Springer, Heidelberg (1999)
Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (2002)
Wang, M., Wang, X., Jia, K., Wang, W.: New pseudo-near-collision attack on reduced-round of Hamsi-256. Cryptology ePrint Archive, Report 2009/484 (2009)
Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the hash functions MD4 and RIPEMD. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 1–18. Springer, Heidelberg (2005)
Wang, X., Yin, Y.L., Yu, H.: Finding collisions in the full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)
Wang, X., Yu, H.: How to break MD5 and other hash functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)
Wang, X., Yu, H., Yin, Y.L.: Efficient collision search attacks on SHA-0. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 1–16. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aumasson, JP. et al. (2010). Distinguishers for the Compression Function and Output Transformation of Hamsi-256. In: Steinfeld, R., Hawkes, P. (eds) Information Security and Privacy. ACISP 2010. Lecture Notes in Computer Science, vol 6168. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14081-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-14081-5_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14080-8
Online ISBN: 978-3-642-14081-5
eBook Packages: Computer ScienceComputer Science (R0)