Paper 2004/207
On Corrective Patterns for the SHA-2 Family
Philip Hawkes, Michael Paddon, and Gregory G. Rose
Abstract
The Secure Hash Standard (SHS) [3] includes hashing algorithms denoted SHA-n, (n in {224, 256, 384, 512}) for producing message digests of length n. These algorithms are based on a common design, sometimes known as SHA-2, that consists of a message schedule and a register. The most successful attacks on the SHA algorithms are Chabaud-Joux differential collisions [1, 2, 4, 5, 7], which are based on finding a corrective pattern for the register. Previous analysis of the SHA-2 algoritms [4] indicated that, for all SHA-2 algorithms, the best corrective pattern has probability 2^-66. We find that the complexity of obtaining a collision is 2^39 when the register state is unknown. Of this complexity, a factor of 2^9 corresponds to conditions on the internal state that must be satisfied, and a factor of 2^30 corresponds to 30 bits of internal state that must be guessed correctly in order to generate a collision. When the register state is known (as is the case when generating a hash) then the guessed bits are known and the complexity is reduced to 2^9. The simple analysis of the message schedule in [4] determines limits on the probability of collision for SHA-2, and was sufficient at that time to conclude that the algorithms resist the attacks. In [4] the claimed complexity is compared against the birthday attack bound of 2^n/2. However, the corrective pattern can be converted into a second pre-image attack for which the complexity should be greater than 2^n. When accounting for the complexity of 2^9 per corrective pattern, the previous analysis of the message schedule yields lower bounds on the complexities 2^27 for SHA-224/256 and 2^45 for SHA-224/256. These complexities are significantly less than the 2^n bound. It is no longer certain that SHA-2 resists this attack. More detailed analysis of the message schedule is required.
Note: Note that this paper does not suggest that the SHA-2 family is broken in any way, merely that further study of the data expansion function is necessary.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- SHA-256second preimage attack
- Contact author(s)
- ggr @ qualcomm com
- History
- 2004-08-22: received
- Short URL
- https://ia.cr/2004/207
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2004/207,
author = {Philip Hawkes and Michael Paddon and Gregory G. Rose},
title = {On Corrective Patterns for the {SHA}-2 Family},
howpublished = {Cryptology {ePrint} Archive, Paper 2004/207},
year = {2004},
url = {https://eprint.iacr.org/2004/207}
}