SHA-1 broken

Bruce Schneier reports (on his excellent "Schneier on Security " blog) that SHA-1 has been broken. Many of you have never heard of SHA-1, so a brief explanation is in order: SHA-1 is the most commonly used "cryptographic hash" — a specialized software or hardware function that is used as a kind of building block for many kinds of cryptographic systems. For example, the certificates that your web browser decodes (to let you use secure web sites) depend on cryptographic hashes.

Bruce's posting is an interesting read, and contains a pointer to a short paper by the three Chinese scientists who actually did the breaking. As Bruce points out, the sky is not falling:

For the average Internet user, this news is not a cause for panic. No one is going to be breaking digital signatures or reading encrypted messages anytime soon. The electronic world is no less secure after these announcements than it was before.

But there's an old saying inside the NSA: "Attacks always get better; they never get worse." Just as this week's attack builds on other papers describing attacks against simplified versions of SHA-1, SHA-0, MD4, and MD5, other researchers will build on this result. The attack against SHA-1 will continue to improve, as others read about it and develop faster tricks, optimizations, etc. And Moore's Law will continue to march forward, making even the existing attack faster and more affordable.

Jon Callas, PGP's CTO, put it best: "It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off."

The bar in the (forever) ongoing war between the cryptographers and the cryptanalysts just got raised a bit higher. It reminds me a bit of an earlier technological battle that I participated in, between the copy protection vendors and the folks (like me) who found ways around their clever tricks. Whatever the underlying technology, physics, and mathematics, there always seem to be either mistakes made or unexpected vulnerabilities uncovered that allow the "other side" room to exploit. But there is a huge difference with the cryptographic systems: the world generally (cryptanalysts aside) takes the efficacy of cryptographic systems for granted as they're used every day for secure web browsing, digital signatures, and the like. These systems protect transactions involving immense sums (in aggregate, I mean), and they protect the privacy of all of us — even if you don't use the Internet, information about you is all over it.

So this was for me a somewhat discomfiting news report. The good news, I suppose, is that the team who first managed to break SHA-1 (at least I hope they were the first!) is more interested in publishing their results than they are in exploiting them. Let's hope that's a continuing phenomenon in the cryptographic wars...