Paper 2006/016

Message Modification for Step 21-23 on SHA-0

Yusuke Naito and Yu Sasaki and Takeshi Shimoyama and Jun Yajima and Noboru Kunihiro and Kazuo Ohta

Abstract

In CRYPTO 2005, Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin proposed an efficient collision attack on SHA-0. Collision messages are found with complexity $2^{39}$ SHA-0 operations by using their method. Collision messages can be obtained when a message satisfying all sufficient conditions is found. In their paper, they proposed message modifications that can satisfy all sufficient conditions of step 1-20. However, they didn't propose message modifications for sufficient conditions after step 21. In this paper, we propose message modifications for sufficient conditions of step 21-23. By using our message modifications, collision messages are found with complexity $2^{36}$ SHA-0 operations.