A strict evaluation method on the number of conditions for the SHA-1 collision search

ABSTRACT

This paper proposes a new algorithm for evaluating the number of chaining variable conditions(CVCs) in the selecting step of a distrubance vector (DV) for the analysis of SHA-1 collision attack. The algorithm is constructed by combining the following four strategies, "Strict Differential Bit Compression", "DV expansion", "Precise Counting Rules in Every Step" and "Differential Path Confirmation for Rounds 2 to 4", that can evaluate the number of CVCs morestrictly compared with the previous approach.

REFERENCES

• 1: E. Biham, R. Chen, A. Joux, P. Carribault, C. Lemuet, and W. Jalby. Collisions in SHA-0 and reduced SHA-1. In EUROCRYPT2005, pages 36--57. International Association for Cryptologic Research (IACR), May 2005.
• 2: C. D. Cannière, F. Mendel, and C. Rechberger. On the full cost of collision search for SHA-1. In ECRYPT Hash Workshop. ECRYPT Network of Excellence in Cryptology, May 2007.
• 3: C. D. Cannière and C. Rechberger. Finding SHA-1 characteristics: General results and applications. In ASIACRYPT2006. International Association for Cryptologic Research (IACR), December 2006.
• 4: 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
• 5: P. Hawkes, M. Paddon, and G. Rose. Automated search for round 1 differentials for SHA-1: Work in progress. In NIST SECOND CRYPTOGRAPHIC HASH WORKSHOP. National Institute of Standards and Technology, August 2006.
• 6: A. Joux. Message modification, neutral bits and boomerangs: From which round should we start counting in SHA? In NIST SECOND CRYPTOGRAPHIC HASH WORKSHOP. National Institute of Standards and Technology, August 2006.
• 7: F. Mendel, N. Pramstaller, C. Rechberger, and V. Rijmen. The impact of carries on the complexity of collision attacks on sha-1. In Fast Software Encryption 2006. International Association for Cryptologic Research (IACR), March 2006.
• 8: Y. Naito, Y. Sasaki, T. Shimoyama, J. Yajima, N. Kunihiro, and K. Ohta. Improved collision search for SHA-0. In ASIACRYPT2006, pages 21--36. International Association for Cryptologic Research (IACR), December 2006.
• 9: NIST. Secure hash standard. In Federal Information Processing Standard. National Institute of Standards and Technology, April 1995.
• 10: M. Sugita, M. Kawazoe, and H. Imai. Gröbner basis based cryptanalysis of SHA-1. In Fast Software Encryption 2007. IACR, March 2007.
• 11: X. Wang. The collision attack on SHA-0. In available at http://www.infosec.sdu.edu.cn/people/wangxiaoyun. htm, 1997.
• 12: X. Wang. Cryptanalysis of hash functions and potential dangers. In Invited Talk at the Cryptographer's Track at RSA Conference 2006. RSA, February 2006.
• 13: X. Wang, A. C. Yao, and F. Yao. Cryptanalysis on SHA-1 hash function. In CRYPTOGRAPHIC HASH WORKSHOP. National Institute of Standards and Technology, November 2005.
• 14: X. Wang, Y. L. Yin, and H. Yu. Finding collisions in the full SHA-1. In CRYPTO2005, pages 17--36. International Association for Cryptologic Research (IACR), August 2005.
• 15: X. Wang and H. Yu. How to break MD5 and other hash functions. In EUROCRYPT2005, pages 19--35. International Association for Cryptologic Research (IACR), May 2005.
• 16: J. Yajima, Y. Sasaki, Y. Naito, T. Iwasaki, T. Shimoyama, N. Kunihiro, and K. Ohta. A new strategy for finding a differential path of SHA-1. In ACISP2007, pages 45--58. International Association for Cryptologic Research (IACR), July 2007.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
SHA-1, collision attack, disturbance vector, hash function