3 ms·

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

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.

Buge 13y ago
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.
- mechanical_fish 13y ago
  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/exponential-wall2.png 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.
bdonlan 13y ago
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!
Shorel 13y ago
> 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.

Buge 13y ago

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.

mechanical_fish 13y ago
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/exponential-wall2.png 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.

bdonlan 13y ago

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!

Shorel 13y ago

> 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.