Cryptology ePrint Archive: Report 2009/259

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

Cameron McDonald and 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.

Category / Keywords: Hash Functions, Differential Path, Boomerang Attack, SHA-1

Date: received 1 Jun 2009, withdrawn 10 Aug 2009

Contact author: cmcdonal at ics mq edu au

Available format(s): (-- withdrawn --)

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.

Version: 20090810:130014 (All versions of this report)

Short URL: ia.cr/2009/259

Discussion forum: Show discussion | Start new discussion