4 ms·

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 o

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!

cmurphycode 13y ago
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.
mechanical_fish 13y ago
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!

cmurphycode 13y ago

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.

mechanical_fish 13y ago

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!