Paper 2009/479

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

Yu Sasaki, 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.

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.