Second-Preimage Analysis of Reduced SHA-1

摘要

Many applications using cryptographic hash functions do not require collision resistance, but some kind of preimage resistance. That's also the reason why the widely used SHA-1 continues to be recommended in all applications except digital signatures after 2010. Recent work on preimage and second preimage attacks on reduced SHA-1 succeeding up to 48 out of 80 steps (with results barely below the 2~n time complexity of brute-force search) suggest that there is plenty of security margin left. In this paper we show that the security margin is actually somewhat lower, when only second preimages are the goal. We do this by giving two examples, using known differential properties of SHA-1. First, we reduce the complexity of a 2nd-preimage shortcut attack on 34-step SHA-1 from an impractically high complexity to practical complexity. Next, we show a property for up to 61 steps of the SHA-1 compression function that violates some variant of a natural second preimage resistance assumption, adding 13 steps to previously best known results.