4 ms·

>hash(salt|pwd) -> no rainbow table because of salt. The attacker can use a dictionary attack. I'm having trouble understanding this. So what does the attacker

by yaeger 13y ago

>hash(salt|pwd) -> no rainbow table because of salt. The attacker can use a dictionary attack. I'm having trouble understanding this. So what does the attacker do? He captured the encrypted passwords and he got all the salts. What does he do now? Instead of generating a "normal" table by doing hash(<anyPWcomboThereIs>), he is now doing has(salt|<anyPWComboThereIs>) Is that right? So basically, all that the salt does is to prolong the cracking. Say I had 10 users, so I would have 10 salts in my db. Without the salts, the attacker would have "just" had to calculate the hash(anyPWcomboThereIs) table. But now, he would have to do this 10 times because there are 10 different salts which could have been used to create the encrypted password. Is that right?

efdee 13y ago
Rainbow tables remove the need for doing hash(anyPwComboThereIs). They are huge hash->plaintext dictionaries where you just enter the hash and get the plaintext. If the website adds salt to the hashes, you need a rainbow table for every hash, which is practically unfeasible, so you have to revert to attempting to guess the password.
- bigiain 13y ago
  You don't even need to burn your own disk space for those lists. Try just feeding '5f4dcc3b5aa765d61d8327deb882cf99' into Google. Or 'f25a2fc72690b780b2a14e140ef6a9e0'. Or pretty much anything else that's ever showed up in a publicly leaks MD5 password dump (or plaintext password dump).
InclinedPlane 13y ago
It's a look up table operation vs. a per-item computation, essentially. If you have passwords hashed using md5 and no salt then you just go get a giant pre-computed library of hashes and you go through each hash and figure out if it's in your library. This is EXTREMELY fast, and with modern computing power and memory/storage capacities these libraries can be huge and won't just include things like common passwords and dictionary words but also random strings of characters up to fairly long lengths. With this sort of attack you just filter the list of hashes through your table and you end up with a list of passwords. The important thing about un-salted hashes is that no matter how much work is put into building the table it's amortized over the total number of passwords attacked, over all time. Which drastically lowers the amount of effort per password. With a per-entry salt this sort of attack is no longer possible. Instead you are forced to do a brute force attack on each and every password. If, hypothetically, it took a week to generate a really good rainbow table then it would take essentially just one week to crack nearly 860,000 passwords. Whereas with unique salts it would take 860,000 weeks. However, that's only in the hypothetical case. In practice many people have weak passwords, and a well-built system can compute a huge number of md5 hashes per second. Someone built a multi-GPU monster system that could compute 180 billion md5 hashes per second while only taking up about half of a standard server rack of space (5x 4U). So if you toss an extremely large dictionary of password guesses with even millions or tens of millions of entries it will still take only a fraction of a second to check each hash, so you can crack a significant number of passwords (at leas the ones that aren't incredibly strong) in only a matter of days.

by yaeger 13y ago

efdee 13y ago

Rainbow tables remove the need for doing hash(anyPwComboThereIs). They are huge hash->plaintext dictionaries where you just enter the hash and get the plaintext. If the website adds salt to the hashes, you need a rainbow table for every hash, which is practically unfeasible, so you have to revert to attempting to guess the password.

bigiain 13y ago
You don't even need to burn your own disk space for those lists. Try just feeding '5f4dcc3b5aa765d61d8327deb882cf99' into Google. Or 'f25a2fc72690b780b2a14e140ef6a9e0'. Or pretty much anything else that's ever showed up in a publicly leaks MD5 password dump (or plaintext password dump).

InclinedPlane 13y ago

It's a look up table operation vs. a per-item computation, essentially. If you have passwords hashed using md5 and no salt then you just go get a giant pre-computed library of hashes and you go through each hash and figure out if it's in your library. This is EXTREMELY fast, and with modern computing power and memory/storage capacities these libraries can be huge and won't just include things like common passwords and dictionary words but also random strings of characters up to fairly long lengths. With this sort of attack you just filter the list of hashes through your table and you end up with a list of passwords. The important thing about un-salted hashes is that no matter how much work is put into building the table it's amortized over the total number of passwords attacked, over all time. Which drastically lowers the amount of effort per password. With a per-entry salt this sort of attack is no longer possible. Instead you are forced to do a brute force attack on each and every password. If, hypothetically, it took a week to generate a really good rainbow table then it would take essentially just one week to crack nearly 860,000 passwords. Whereas with unique salts it would take 860,000 weeks. However, that's only in the hypothetical case. In practice many people have weak passwords, and a well-built system can compute a huge number of md5 hashes per second. Someone built a multi-GPU monster system that could compute 180 billion md5 hashes per second while only taking up about half of a standard server rack of space (5x 4U). So if you toss an extremely large dictionary of password guesses with even millions or tens of millions of entries it will still take only a fraction of a second to check each hash, so you can crack a significant number of passwords (at leas the ones that aren't incredibly strong) in only a matter of days.