Paper 2009/479 Original: eprint.iacr.org/2009/479 ↗
Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512
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.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2009-09-29: last updated
- 2009-09-29: published
- Short URL
- https://ia.cr/2009/479
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2009/479}
}