SHA-1 Cracking Improvements and Cryptanalysis

In December of last year, researcher Jens Steube presented a big improvement in the efficiency to crack passwords using SHA-1 at the Passwords^12 conference in Oslo. In short, by focusing on the word expansion phase of SHA-1, he was able to reduce the number of operations by 21%. The reason why this is possible is that under some given conditions, a number of XOR operations have always a fixed result or cancel each other out. The result is that if you arrange your work in a smart way, password cracking can be speeded up with a factor of 25%.

His results seem amazing, especially because they seem so basic at the same time as many researchers have been trying to break SHA-1 for so many years. Indeed, as Joachim Strömbergson noted, SHA-1 was published in 1995, almost twenty years ago. One would expect that finding such simplifications would be the first thing a researcher would try to do. There are a few factors that should be considered though:

First of all, Jens Steube was able to make these reductions in the context of brute-force password cracking. Brute-force password cracking is basically a cipher-text only attack, and then it's indeed possible to arrange the chosen plaintexts such that you can exploit the optimisations that Jens Steube discovered. Cryptanalysis, however, usually concentrates on trying to find a collision in the hash function, and except for brute-force birthday attacks, this means in most cases you can't choose the plaintext any way you like.

Second, even though Jens Steube was able to find some shortcuts in the SHA-1 algorithm under a certain set of conditions, it doesn't seem that he was able to reduce the fundamental complexity of the SHA-1 algorithm. I'm no expert on SHA-1 and therefore in no position to really consider how good the attack is, but the number of conditions may just as well outweigh the progress. But I'll come back to that shortly.

Third, and finally, as impressing as a reduction of operations by 21% may sound, it doesn't represent such a big progress in the world of cryptology. In that world, progress isn't measured in percentages, but on an exponential scale. The base for that scale is usually 2, so that the results can be related to the number of bits in the search space. For SHA-1, the digest size is 160, which means that the search space is 2¹⁶⁰. A brute-force birthday attack would then roughly require about 2⁸⁰ cipher-texts to be calculated in order to find a collision. A reduction of 21% would then be equivalent to reducing this number to 2^79.66. This number should be compared to the best known attack on SHA-1, by Marc Stevens, which requires 2⁶⁰ SHA-1 operations. Or, if you prefer to work with percentages, Marc Stevens' attack is equivalent to reducing the calculation time of the brute-force birthday attack by 99.9999%.

Having said all this, I hope the reader doesn't have the impression that I don't think Jens Steube's attack is impressive. Because it really is. Cryptanalysis is a one-sided arms race, where the attackers invent new weapons against old algorithms all the time. Jens Steube's attack is such a new weapon against SHA-1. Often, new weapons can be combined with old weapons to build even better weapons. This means that in the worst case, Jens Steube's attack brings no progress except for password cracking. But we can hope that his findings can be combined with somebody else's attack, like e.g. the one from Marc Stevens, or give some other inspiration to improve it. If some sort of combination of attacks is possible, one can probably expect that the number of operations could be reduced from 2⁶⁰ to 2^59.66.

Theoretically possible, but very unlikely because of the preconditions needed to apply the attack, would be a reduction of 21% of the complexity to attack SHA-1, not just the calculation of SHA-1. That would reduce the complexity from 2⁶⁰ to 2^47.4. However, the conditions to apply Jens Steube's attack may represent some added complexity or extra calculations needed to actually find a collision, and therefore increase the number again. But maybe, just maybe, Jens Steube's attack contains a clue to reduce it even further, to make breaking SHA-1 trivial. I don't think that's very likely, but you never know.