Broken Hash Functions

This is a post about cryptography, but not "crypto". There will be no talk of NTFs, the latest meltdowns, or wallets of any sort.

Instead, I wanted to talk briefly about the state of broken hash functions. SHA-1 was in the news last week, with NIST finally declaring it "end of life", suggesting it be phased out by early 2031.

Now this shouldn't be news to anyone in the security community. We've known SHA-1 was fundamentally broken since 2005, and reminded again in 2017 with the SHAttered attack.

But what does "broken" really mean? Is SHA-1 dangerous in all cases, or just some? Is is just something that cryptographers and security people get worked up about, or is it actually something that regular developers need to care about?

Well, in my opinion, it's a little from column 'A' and a little from column 'B'.

But let's get this out of the way up front: Don't use SHA-1. Use SHA-256, SHA-512, or SHA-3. Don't use exotic hash functions or try to roll your own. If you see MD5, turn around and walk the other way. If you're storing passwords, you'll need to do something else too (more on that later).

Now, the attacks against SHA-1 break the "collision resistance" property of cryptographic hash functions. Collision resistance means that it should be really, really hard for anyone to find two different input strings that have the same hash value. We define "really, really hard" to mean, "you might as well just search all inputs, one by one, until you find one by chance" -- or "brute force".

SHA-1 has 160 bits of output, which means 80 bits of collision resistance (due to the Birthday Paradox). This means you should have to try (roughly) 2⁸⁰ guesses before you find two strings that have the same hash value. In practice, researchers have been able to get that down to around 2⁶¹, or around 500,000 times faster than brute force.

But collision resistance is just one of a few properties that hash functions have. The other important one is called "pre-image resistance". This one is about, "if you give me a hash output, can I find an input string that would generate it?". SHA-1 maintains pre-image resistance, and shows no visible signs of weakness.

Does this mean SHA-1 is safe to use?

The truth is, "it depends". If you're a cryptographer, you're certainly capable to determining whether a particular use of a hash function demands pre-image resistance, collision resistance, or both. But you're probably not a cryptographer, and as much as it may bruise your ego, you're probably not equipped to make this call. Sorry.

Can I still store passwords as hashed SHA-1?

Absolutely not! This was a terrible idea back in 1995, and is still a terrible idea. But it's not at all about weaknesses in SHA-1 -- instead, it's easy to just "hash all of the passwords" through SHA-1, or SHA-512, or SHA-3, or whatever, and compare to the list retrieved from your database. Instead, you need to use some combination of salt, pepper, iterated hashing, encryption, and memory-hard algorithms to ensure that an attacker with a database dump can't learn anything interesting.