Hacker News Reader

Comment by tptacek | Hacker News Reader

You don't understand how GPU crackers work, or, for that matter, how Alec Muffet's "Crack" works, from the early 1990s, the original password cracker that everyone used to use to work on Unix password files. Suffice it to say: no, salting does not make a huge difference.

View on HN

Ok, I may be confused. I thought that with an unsalted list, you could try a password (generated by your algorithm of choice, whether that be dictionary based or brute force) and compare it to the entire list of hashes, because Alice's "123456" would hash to the same thing as Bob's "123456". But if the list was salted, Alice and Bob would have different stored hashes - and so you would not be able to parallelise cracking across users.

Yes, if you only want to crack Alice's password, the salt will not slow you down. But if your goal is to crack a million, wouldn't the salt slow you down?

If I'm missing something, I would really like to know. Always good to learn something new!

Your theory of salting-per-user is correct.

Rainbow tables are useful if the time it takes to compute is big enough that storing a large list is useful.

The GPU crackers are so fast nowadays that that isn't the case. If you can try 500M per second, that's about 10 GB of SHA1 generated! Imagine storing a day's worth of work in a rainbow table :)

It's better to use a proper password hash, which will be slow, and will likely have per-user salting built in, anyway.

Read the Ars Technica article.

The hole in your logic is: there is no point in guarding against the case where, if two users share the same password, cracking one will crack the other, because the only time that two users share a password is when that password is really weak.

What are the odds that two users share the same password? If passwords were totally random and 24 characters long the answer would be "pretty low". And the odds of cracking one of these passwords by brute force would also be pretty low. If only we lived in that world.

In the real world the odds of two users sharing a password are frighteningly high, but that's because most passwords are awful: they are things like "pizzapizza" or even "password". The cracking programs can crack one of these in a millisecond, because they are equipped with lists of thousands of real-world weak passwords harvested from real websites. And then, if another user shares this awful weak password, that user will also get cracked, a few milliseconds later. There is no point in "parallelising cracking across users" because it's so easy to just guess all the weak passwords for every user.

Another way to think about it: A salt could only help in cases where (a) two users share the same password, but (b) that password doesn't appear in the list of several million other real-world passwords that is built into the password cracker. And that just isn't worth worrying about.

But if there is a database of 1,000 unsalted password hashes with no people having the same password. Your password cracking regime does 1 trillion guesses. So you hash each guess then try it against each of the 1,000 password hashes. That is a total of 1 trillion hash operations.

But if the database has individually salted hashes then you need to do each hash operation individually for each user. That means you have to do 1 quadrillion hashes. That will take 1,000 times longer.

A factor of 1000 isn't that important.

Really. First, stare at this chart from the Ars Technica article:

http://cdn.arstechnica.net/wp-content/uploads/2012/08/expone...

This graph shows, roughly, that a short password can be brute forced in seconds using modern hardware. If it is just one character longer, it suddenly takes a week to brute-force. This is the miracle of exponential functions.

Now multiply the y axis by 1000. The long password now takes 1000 weeks. But the shorter one still only takes a few thousand seconds. If you are running your cracking program for a day, you'll get the same results you got before. The weak passwords are still weak enough to crack. The strong ones are still strong.

(Note, by the way, that it doesn't take 1000 times longer to guess 1000 salted passwords, because some of those passwords are super weak and will fall in seconds, after which one no longer needs to guess them. So, for example, once half the passwords have been broken, the new multiple is only 500. The Ars article explains this, but I didn't understand its wording at first.)

It is true that salt makes some difference. But it is not a meaningful difference. The difference between giving up 60% of your passwords and giving up 73% of your passwords is probably moot.

EDIT: And my example number of 73% is too low! That is bad news for MD5! Again, the article: they cracked 82% of a 16k-password file in one hour using only a single commodity GPU.

There actually is a point to parallelizing cracking across users. Consider: You're testing a specific password, say, "2398fje#f", and want to see if anyone is using that password. If there are no salts, you can hash this, then look it up in a hash table of password hash to user (or, to get more fancy, you can do things like performing a bloom filter lookup on the GPU, etc). If there are salts, however, you must hash it multiple times - potentially once for each user. This applies even if there is only one user using the password in question.

So the difficulty of the search is no longer proportional to the number of passwords tried, but rather proportional to the product of the number of users and number of passwords - a rather large increase!

> lists of thousands of real-world weak passwords

They are compiled in a different way but serve the very same purpose as a rainbow table. A list of precompiled hashes.

Thus, they are just a kind of rainbow table.

Therefore, rainbow tables do matter.

If you have a database of 100 unsalted hashed passwords and a dictionary of 10,000 words you could hash the 10,000 words and compare each resulting hash to each hash in the database. So that would take 10,000 hash operations.

But if the passwords were individually salted you would have to individually hash each dictionary item for each hash in the database. So that would be 1,000,000 hash operations.

Could you explain why? The post below explains about how two users really shouldn't share the same password, and if they do, it's easily crackable - that makes sense. However, if you had a list of 100,000 passwords and did, say, a brute force attack of all passwords with letters, numbers, and special characters to a length of 8, without salted hashes you would be able to run that brute force once and grab every password matching the criteria. With salts, you would have to run it once per salt. Am I off on that?

You're not wrong, but:

1. If you're using salt, it implies you chose to roll your own key function using hashes. That's a bad idea, because:

2. GPUs can produce so many combinations per second that the difference between salted and unsalted is basically indistinguishable for smart attackers.

Reply on news.ycombinator.com