Message Modification for Step 21-23 on SHA-0

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

Paper 2006/016

Message Modification for Step 21-23 on SHA-0

Yusuke Naito, Yu Sasaki, Takeshi Shimoyama, Jun Yajima, 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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: SHA-0 Message Modification
Contact author(s): tolucky @ ice uec ac jp
History: 2006-01-17: received
Short URL: https://ia.cr/2006/016
License: CC BY

BibTeX

@misc{cryptoeprint:2006/016,
      author = {Yusuke Naito and Yu Sasaki and Takeshi Shimoyama and Jun Yajima and Noboru Kunihiro and Kazuo Ohta},
      title = {Message Modification for Step 21-23 on {SHA}-0},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/016},
      year = {2006},
      url = {https://eprint.iacr.org/2006/016}
}