Paper 2009/259

Differential Path for SHA-1 with complexity $O(2^{52})$

Cameron McDonald, Philip Hawkes, and Josef Pieprzyk

Abstract

Although SHA-1 has been theoretically broken for some time now, the task of finding a practical collision is yet to be completed. Using some new approaches to differential analysis, we were able to find a new differential path which can be used in a collision attack with complexity of $O(2^{52})$. This is currently the lowest complexity attack on SHA-1.

Note: The attack complexity reported in this paper was based on two results: 1. The nonlinear differential path in Round 1 uses 5 auxiliary differentials in a Boomerang attack. 2. The linear differential path for Rounds 2-4 has a cost evaluation of $2^{57}$ ct. Manuel. The overall collision attack requires $2^{52}$ message pairs that conform to the differential for Round 1 (achieved by message modification). The cost evaluation for point 2 above was reported by Manuel in November 2008. We have recently discovered this evaluation to be incorrect. This implies the complexity given in this paper is also incorrect. We have decided to withdraw the current paper. A new paper featuring updated results and new results will appear soon.

Metadata
Available format(s)
-- withdrawn --
Publication info
Published elsewhere. Unknown where it was published
Keywords
Hash FunctionsDifferential PathBoomerang AttackSHA-1
Contact author(s)
cmcdonal @ ics mq edu au
History
2009-08-10: withdrawn
2009-06-03: received
See all versions
Short URL
https://ia.cr/2009/259
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.