A new hash family obtained by modifying the SHA-2 family

ABSTRACT

In this work, we study several properties of the SHA-2 design which have been utilized in recent collision attacks against reduced round SHA-2. Small modifications to the SHA-2 design are suggested to thwart these attacks. The modified round function provides the same resistance to linearization attacks as the original SHA-2 round function, but, provides better resistance to non-linear attacks. Our next contribution is to introduce the general idea of "multiple feed-forward" for the construction of cryptographic hash functions. This can provide increased resistance to the Chabaud-Joux type "perturbation-correction" collision attacks. The idea of feed-forward is taken further by introducing the idea of feed-forward across message blocks leading to resistance against generic multi-collision attacks. The net effect of the suggested changes to the SHA-2 design has insignificant impact on the efficiency of computing the digest.

REFERENCES

• 1: Florent Chabaud , Antoine Joux, Differential Collisions in SHA-0, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.56-71, August 23-27, 1998
• 2: Joan Daemen , Vincent Rijmen, The Design of Rijndael, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 3: Wei Dai. Crypto++ Library 5.5.2. http://www.cryptopp.com/.
• 4: Federal Register Vol. 72, No. 212. Announcing Request for Candidate Algorithm Nominations for a new Cryptographic Hash Algorithm (SHA-3) Family. U.S. Department of Commerce, National Institute of Standards and Technology(NIST), November 2, 2007. Available at http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf.
• 5: Henri Gilbert and Helena Handschuh. Security Analysis of SHA-256 and Sisters. In Mitsuru Matsui and Robert J. Zuccherato, editors, Selected Areas in Cryptography, 10th Annual International Workshop, SAC 2003, Ottawa, Canada, August 14--15, 2003, Revised Papers, volume 3006 of Lecture Notes in Computer Science, pages 175--193. Springer, 2003.
• 6: Philip Hawkes, Michael Paddon, and Gregory G. Rose. On Corrective Patterns for the SHA-2 Family. Cryptology eprint Archive, August 2004. Available at http://eprint.iacr.org/2004/207.
• 7: Sebastiaan Indesteege, Florian Mendel, Bart Preneel, and Christian Rechberger. Collisions and other Non-Random Properties for Step-Reduced SHA-256. In Selected Areas in Cryptography, 15th Annual International Workshop, SAC 2008, Revised Papers, 2008. To appear.
• 8: Antoine Joux. Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. In Matthew K. Franklin, editor, Advances in Cryptology - CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15--19, 2004, Proceedings, volume 3152 of Lecture Notes in Computer Science, pages 306--316. Springer, 2004.
• 9: Stefan Lucks. A failure-friendly design principle for hash functions. In Bimal K. Roy, editor, ASIACRYPT, volume 3788 of Lecture Notes in Computer Science, pages 474--494. Springer, 2005.
• 10: Florian Mendel, Norbert Pramstaller, Christian Rechberger, and Vincent Rijmen. Analysis of Step-Reduced SHA-256. In Matthew J. B. Robshaw, editor, Fast Software Encryption, 13th International Workshop, FSE 2006, Graz, Austria, March 15--17, 2006, Revised Selected Papers, volume 4047 of Lecture Notes in Computer Science, pages 126--143. Springer, 2006.
• 11: Florian Mendel, Norbert Pramstaller, Christian Rechberger, and Vincent Rijmen. Analysis of Step-Reduced SHA-256. Cryptology eprint Archive, March 2008. Available at http://eprint.iacr.org/2008/130.
• 12: Ivica Nikolić , Alex Biryukov, Collisions for Step-Reduced SHA-256, Fast Software Encryption: 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10-13, 2008, Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-71039-4_1]
• 13: Somitra Kumar Sanadhya and Palash Sarkar. New Local Collisions for the SHA-2 Hash Family. In Kil-Hyun Nam and Gwangsoo Rhee, editors, Information Security and Cryptology - ICISC 2007, 10th International Conference, Seoul, Korea, November 29--30, 2007, Proceedings, volume 4817 of Lecture Notes in Computer Science, pages 193--205. Springer, 2007.
• 14: Somitra Kumar Sanadhya and Palash Sarkar. A Combinatorial Analysis of Recent Attacks on Step Reduced SHA-2 Family. Cryptology ePrint Archive, Report 2008/271, 2008. http://eprint.iacr.org/2008/271.
• 15: Somitra Kumar Sanadhya and Palash Sarkar. Attacking Reduced Round SHA-256. In Steven Bellovin and Rosario Gennaro, editors, Applied Cryptography and Network Security - ACNS 2008, 6th International Conference, New York, NY, June 03--06, 2008, Proceedings, volume 5037 of Lecture Notes in Computer Science. Springer, 2008.
• 16: Somitra Kumar Sanadhya , Palash Sarkar, Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family, Proceedings of the 11th international conference on Information Security, September 15-18, 2008, Taipei, Taiwan [doi>10.1007/978-3-540-85886-7_17]
• 17: Somitra Kumar Sanadhya , Palash Sarkar, New Collision Attacks against Up to 24-Step SHA-2, Proceedings of the 9th International Conference on Cryptology in India: Progress in Cryptology, December 14-17, 2008, Kharagpur, India [doi>10.1007/978-3-540-89754-5_8]
• 18: Somitra Kumar Sanadhya , Palash Sarkar, Non-linear Reduced Round Attacks against SHA-2 Hash Family, Proceedings of the 13th Australasian conference on Information Security and Privacy, p.254-266, July 07-09, 2008, Wollongong, Australia [doi>10.1007/978-3-540-70500-0_19]
• 19: Secure Hash Standard. Federal Information Processing Standard Publication 180--2. U.S. Department of Commerce, National Institute of Standards and Technology(NIST), 2002. Available at http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf.
• 20: Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Finding Collisions in the Full SHA-1. In Victor Shoup, editor, Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14--18, 2005, Proceedings, volume 3621 of Lecture Notes in Computer Science, pages 17--36. Springer, 2005.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Standards (e.g., DES, PGP, RSA)

General Terms:
Algorithms, Security

Keywords:
SHA-2 hash family, cryptanalysis, reduced round attacks