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.