Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / SHA-0,Message Modification

Date: received 14 Jan 2006

Contact author: tolucky at ice uec ac jp

Available format(s): PDF | BibTeX Citation

Version: 20060117:204650 (All versions of this report)

Short URL: ia.cr/2006/016

Discussion forum: Show discussion | Start new discussion