Hacker News Reader

Comment by DaveChild | Hacker News Reader

MD5 isn't the issue - it's the lack of salting. Without a salt, almost any hash can be cracked with a rainbow table. With a salt, you'd need to know the salt for each hash, and then generate a new rainbow table, in order to recover the original password.

View on HN

This isn't really the issue. The real issue is that MD5 (though these hashes are SHA1, which has the same problem) are too easily computed; they are practically byte-forceable. I don't need a rainbow table to compute hashes when I can slam out millions in short order using a GPU. You have a good point about needing to know the salt, but getting the salt is generally easy because it's usually stored in the same place as the hashes (and this practice is fine, because hiding the salts doesn't improve security significantly on its own).

This is a major reason to use bcrypt.

Let's forget about bcrypt for a second.

What prevents developers from adding a large DB-wide salt (in addition to normal salt) to every password? Wouldn't that prevent bruteforce attacks regardless of the hashing algorithm?

Is there a significant time difference in computing the SHA1 hash of 40 bytes versus say, 128 bytes?

128 bytes is not "large". I was thinking more along the lines of megabyte+. There is no question that it will slow down hash computations, because you would need to process more data. The question is, can you efficiently parallellize this in a commodity hardware (GPUs)?

Random nonces have very little to do with what makes SHA1 insecure and bcrypt secure. Developers have a very weird and totally misplaced faith in the ability of random "salts" to secure passwords.

We're speaking about a very specific attack here: bruteforce. And I'm speaking about a very specific type of "salt" (which could probably be called something else, since it's not the same as normal unique-per-password salt): large, database-wide string of random bytes.

If every password is padded with such a string before hashing, computing the hash would be slower. Obviously, it would be slower because you would have to process more data. An interesting question is whether this would also make it less parallelizable by the virtue of having more information than would fit into GPU cache.

None of this makes much sense to me, sorry. Brute-force password cracking has worked on salted passwords since Alec Muffett released Crack in the early '90s. The amount of extra computational power required to hash a password and a salt is negligible.

The only thing "salts" do is prevent rainbow table precomputation, but it's just a quirk of the late '90s and early '00s that "rainbow tables" ever became a mainstream attack method: one bad Microsoft password hash and a series of bad web applications. Long before the MD4 LANMAN hash was ever released, people were breaking salted Unix passwords with off-the-shelf tools, on much, much slower computers than we have now.

Computing a hash on 1MB of data is slower than computing a hash of 6-8 bytes of data. Brute-force attacks are based on trying different passwords and seeing that after being salted they generate the same hash as in the database. Therefore, adding a large string to the password before hashing would force the attacker to hash that string. The question is, can this be pre-computed once or efficiently parallelized?

You're advocating creating a 1MB "salt" string to slow down hashes? That's the same as simply iterating your hash function enough times to invoke the block function repeatedly.

Just use bcrypt, scrypt, or PBKDF2. People have already figured this problem out.

First, I do not advocate anything here. I asked a question.

Second, working with a large string of bits is the same as recursive hashing only if you can pre-compute some small intermediate state of the hash function for that string independently from the password you're trying to guess. If you can't, you would have to work with the entire string for every new password tried.

I answered your question: using a very large "salt" to force a password hash to run more block functions is a bad idea.

Modern password crackers are extremely fast without precomputing anything.

How much slower would you estimate it being?

1MB of data will have 16384 SHA 256 blocks. So that's roughly the slowdown I would expect, minus the time it takes to initialize the algorithm for a particular message.

That's not that interesting by itself, but it is interesting to think about how this would affect computing the hashes on GPUs.

And how high can you crank the work factor for, say, bcrypt?

The difference is that if it's salted you need to work to get a specific password. Without salting you can test a generated hash (rainbow table) against all 6.9 million hashes at the same time.

Not defending the choice - bcrypt is obviously a much better way to go.

The thing is, though, that it's trivial to slam through that set of salted passwords. It's like unsecured Wi-Fi versus WEP: "door unlocked" versus "'No Trespassing' sign."

To be clear, MD5 (or SHA1 as these apparently are) is a problem. Passwords should be stored using a cryptographic hash function that is designed to hash passwords (read: be slow), not a generic cryptographic hash function (which are designed to be fast). This is exactly the problem that bcrypt was created to solve (among others).

I think people are missing the point that SHA2 is light years ahead of MD5. MD5 has had known security flaws for years.

>Do not use the MD5 algorithm Software developers, Certification Authorities, website owners, and users should avoid using the MD5 algorithm in any capacity.

http://www.kb.cert.org/vuls/id/836068

This is from over 3 years ago.

The primary problem with using either as a password hash is their speed.

I agree, but my point is that the "use bcrypt" drum has only been beating for a couple years to my knowledge: http://codahale.com/how-to-safely-store-a-password/

Wind the clock back 3-5 years and it's still stupid to use MD5. I could kind of understand some old code laying around that was less secure.

Still, it doesn't matter. As long as one can generate a rainbow table for the hash function, then password lookups will be a O(1) operation. The rainbow table for md5 is moderately small, sha1 is bigger, and I'm sure sha2 is even bigger than the sha1 table.

I'm discussing SHA-2 vs MD5. I wouldn't use any hash function without a salt.... which makes the discussion of rainbow tables irrelevant.

The security differences between SHA2 and MD5 are irrelevant to the matter at hand. If they were MD5 hashes they'd be broken approximately as quickly and in exactly the same way.

Reply on news.ycombinator.com