Cryptology ePrint Archive: Report 2009/479

Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512

Yu Sasaki and Lei Wang and Kazumaro Aoki

Abstract: In this paper, we propose preimage attacks on 41-step SHA-256 and 46-step SHA-512, which drastically increase the number of attacked steps compared to the best previous preimage attack working for only 24 steps. The time complexity for 41-step SHA-256 is $2^{253.5}$ compression function operations and the memory requirement is $2^{16}\times 10$ words. The time complexity for 46-step SHA-512 is $2^{511.5}$ compression function operations and the memory requirement is $2^{3}\times 10$ words. Our attack is a meet-in-the-middle attack. We first consider the application of previous meet-in-the-middle attack techniques to SHA-2. We then analyze the message expansion of SHA-2 by considering all previous techniques to find a new independent message-word partition. We first explain the attack on 40-step SHA-256 whose complexity is $2^{249}$ to describe the ideas. We then explain how to extend the attack.

Category / Keywords: secret-key cryptography / SHA-256, SHA-512, hash, preimage attack, meet-in-the-middle

Publication Info: A merged version will appear in the ASIACRYPT2009.

Date: received 28 Sep 2009

Contact author: sasaki yu at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Note: This paper was originally submitted to Asiacrypt2009. The authors were told to merged the paper with another one. The merged version will appear in the ASIACRYPT2009.

This version is exactly the same as the original submittion except for added author's names and affiliations. Reviewer's comments are reflected in the merged version.

Version: 20090929:053720 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]