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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. A merged version will appear in the ASIACRYPT2009.
Keywords
SHA-256SHA-512hashpreimage attackmeet-in-the-middle
Contact author(s)
sasaki yu @ lab ntt co jp
History
2009-09-29: received
Short URL
https://ia.cr/2009/479
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/479,
      author = {Yu Sasaki and Lei Wang and Kazumaro Aoki},
      title = {Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512},
      howpublished = {Cryptology ePrint Archive, Paper 2009/479},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/479}},
      url = {https://eprint.iacr.org/2009/479}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.