To hash or not to hash?

[Daald]

But how do you keep track of the random salt, without also storing it somewhere?

It doesn't matter. It's a one way function and it does not partially help figuring it out. You still have to go through the entire dictionary and hash with the salt which requires the cracker to have the algorithm in which you place the salt in the password string.

For example in a system I created we went about it like this.

MD5 the password + ';' + username

SHA the MD5 string + a random salt stored in the table with the password.

As you can see it would be pretty hard for them to crack. They need very extensive rainbow tables to crack the SHA since it has such random characters in it.

After they get that, they will need very extensive MD5 tables to get the real password.


ETA: The salt is also there ruin uniformity of users password strings that generally pick similar passwords.

 

[Dessi]

He would have to create a rainbow table using your salt, which takes a long time.

Define a long time. There are 114,196,053,024 passwords between 1 and 8 characters long consisting upper and lowercase alphanumeric letters and !@#$%^&*().

On a GeForce 8800 Ultra, a high-end graphics card in 2007, you can compute 108.6M MD5 hashes per second, which is the whole password space in about 18 minutes.

And that's just brute force. If the salt is the same for all users passwords, its basically useless against a rainbow table attack. If the salt varies by each user, such as prepending the userID, attackers efficiency is reduced to about one password every 18 minutes.

Still, hashing with MD5 and SHA-1 has the disadvantage that they're designed for fast computation, which works in favor of attackers. Best strategy is to use a slow hash function to slow down attackers as much as possible. If take 0.3 seconds to compute a bcrypt hash, then computing the full 11 billion password space takes about... 1100 years.

 

[nathan]

The point of all of this is to make it so difficult that the attacker gives up and hits an easier target - or resorts to the XKCD method if they really need your password.

AKA Rubber Hose Cryptography

 

[Evilgiraffe]

Define a long time. There are 114,196,053,024 passwords between 1 and 8 characters long consisting upper and lowercase alphanumeric letters and !@#$%^&*().

On a GeForce 8800 Ultra, a high-end graphics card in 2007, you can compute 108.6M MD5 hashes per second, which is the whole password space in about 18 minutes.

And that's just brute force. If the salt is the same for all users passwords, its basically useless against a rainbow table attack. If the salt varies by each user, such as prepending the userID, attackers efficiency is reduced to about one password every 18 minutes.

Still, hashing with MD5 and SHA-1 has the disadvantage that they're designed for fast computation, which works in favor of attackers. Best strategy is to use a slow hash function to slow down attackers as much as possible. If take 0.3 seconds to compute a bcrypt hash, then computing the full 11 billion password space takes about... 1100 years.

Um, I think your calculation of the password space is off by a few orders of magnitude.

72 possibilities, 1-8 characters = 72 + 72² + 72³ + . . . + 72⁸
= 7.32 x 10¹⁴ possibilities or 6.75 x 10⁹ minutes of MD5 hashing on your graphics card. Not a trivial crack.

 

[DavidS]

AKA Rubber Hose Cryptography

Be civil: Purchase Key Attack

 

[DrDave]

Um, I think your calculation of the password space is off by a few orders of magnitude.

72 possibilities, 1-8 characters = 72 + 72² + 72³ + . . . + 72⁸
= 7.32 x 10¹⁴ possibilities or 6.75 x 10⁹ minutes of MD5 hashing on your graphics card. Not a trivial crack.

Shouldn't it be 6.75x 10⁶ seconds? You've divided by 108,600 and I think it should be 108,600,000 if I understand correctly and you've left the result in seconds but quoted minutes.

That makes 11,200 minutes, or about 78 days so still not easy

 

[aggle-rithm]

You do store it somewhere. When someone wants to log in, you take the password they give you, add the salt, and hash the result. You compare that to the stored hash.

Even if the attacker has your salt (which is no problem because it is kept in the database right next to the hash) it doesn't help him. He would have to create a rainbow table using your salt, which takes a long time. Then he would have to try crack your salted hash password. The thing that makes it all worth while is that you use a different salt for every password. All the work done in creating all of the gigabytes of a rainbow table would have to be repeated for every password. That makes it very time consuming and expensive to crack a salted hash password.

The point of all of this is to make it so difficult that the attacker gives up and hits an easier target - or resorts to the XKCD method if they really need your password.

I understand now, thanks.

 

[aggle-rithm]

The point of all of this is to make it so difficult that the attacker gives up and hits an easier target - or resorts to the XKCD method if they really need your password.

I think it's funny that popular culture creates the myth of hackers who have some brilliant insight into guessing or cracking passwords, when often in real life all they have to do is call someone on the phone and say, "Yeah, I'm the computer guy. What's your password?"

 

[megaresp]

Shouldn't it be 6.75x 10⁶ seconds? You've divided by 108,600 and I think it should be 108,600,000 if I understand correctly and you've left the result in seconds but quoted minutes.

That makes 11,200 minutes, or about 78 days so still not easy

Depends how many computers you have available to do the task. Any criminal enterprise worth its salt )) should be able to split the task up into chunks and send it out to a network of zombies.

 

[megaresp]

Question for Dessi

If take 0.3 seconds to compute a bcrypt hash, then computing the full 11 billion password space takes about... 1100 years

Dessi, I must have missed something. I don't understand why bcrypt is makes any difference in a brute-force attack? Isn't brute-force about assembling strings of characters and seeing if they work?

If you can steal the database then you can steal (for example) the scripts that govern logging in to the site. So do you actually need to apply the bcrypt algorythm to the submitted password to discover that it's the one?

 

[DrDave]

Depends how many computers you have available to do the task. Any criminal enterprise worth its salt )) should be able to split the task up into chunks and send it out to a network of zombies.

I was using my own definition of easy - where it is less than 77 computer days

 

[MortFurd]

Dessi, I must have missed something. I don't understand why bcrypt is makes any difference in a brute-force attack? Isn't brute-force about assembling strings of characters and seeing if they work?

If you can steal the database then you can steal (for example) the scripts that govern logging in to the site. So do you actually need to apply the bcrypt algorythm to the submitted password to discover that it's the one?

You have to use the hash function to generate the rainbow table that you use to speed up your attack. Conversely, if you want to try every password until you find one that fits you still have to use the hash function. Either way, using a slow hash function causes the attacker to work much harder.

 

[Dessi]

Um, I think your calculation of the password space is off by a few orders of magnitude.

72 possibilities, 1-8 characters = 72 + 72² + 72³ + . . . + 72⁸
= 7.32 x 10¹⁴ possibilities or 6.75 x 10⁹ minutes of MD5 hashing on your graphics card. Not a trivial crack.

Whoops, screwed up my math. I think I calculated Permutations(from 72 take 1) + Permutations(from 72 take 2) + Permutations(from 72 take 3)... and so on, which would have totally ignored passwords with duplicate letters.

72 days is a long time to brute force the whole password space, not really impossible for attackers who invest in several GPUs to crack all of them, but I think most rainbow tables would pare down the list of possible to common passwords, dictionary words, and variations which replace letters with symbols to reduce the password space and time to generate the rainbow table.

 

[megaresp]

I was using my own definition of easy...

I generally find my own definitions make life so much easier. But what else would you expect from someone as youthful, attractive, slim and charming as I?

 

[megaresp]

You have to use the hash function to generate the rainbow table that you use to speed up your attack. Conversely, if you want to try every password until you find one that fits you still have to use the hash function. Either way, using a slow hash function causes the attacker to work much harder.

Ah, I think the penny just dropped (and made an echo when it hit).

I think you are saying the criminal masterminds that hacked their way into my server and stole my database and scripts, and then brute-force it, will still have to run the login script against the various cominations of random characters they're testing.

If it takes half a second to generate a single hash, even though it's being run on their own servers, it will take them a long time to finally produce a result.

Especially if I've used a unique salt for every password. And I suspect that cracking one won't provide useful clues that improve the strike-rate on others either.

Or am I still wide of the mark?

If I store the unique salts in a separate database on another server, this presumably makes their lives as criminal scum even harder because...

• It slows the process down further
• They're less likely to crack both servers
• I may be able to detect when remote requests are coming in from an unauthorised source. In which case I can deduce a cracked server, force a password change (both site and Linux accounts), and generate a new table of unique salts
• If I can detect a request for a salt from an IP other than my approved list, I can presumably return false data and let the crooks waste their time

Yes? No? Dreaming? Overkill?

 

[MortFurd]

Ah, I think the penny just dropped (and made an echo when it hit).

I think you are saying the criminal masterminds that hacked their way into my server and stole my database and scripts, and then brute-force it, will still have to run the login script against the various cominations of random characters they're testing.

If it takes half a second to generate a single hash, even though it's being run on their own servers, it will take them a long time to finally produce a result.

Especially if I've used a unique salt for every password. And I suspect that cracking one won't provide useful clues that improve the strike-rate on others either.

Or am I still wide of the mark?

If I store the unique salts in a separate database on another server, this presumably makes their lives as criminal scum even harder because...

• It slows the process down further
• They're less likely to crack both servers
• I may be able to detect when remote requests are coming in from an unauthorised source. In which case I can deduce a cracked server, force a password change (both site and Linux accounts), and generate a new table of unique salts
• If I can detect a request for a salt from an IP other than my approved list, I can presumably return false data and let the crooks waste their time

Yes? No? Dreaming? Overkill?

The attacker doesn't do his tests against your login script.

He has a copy of all of your password hashes. He goes through his list of possible passwords (dictionary or whatever) and runs each of those through teh hash function on his computer - an MD5 hash run on one computer on a particular password will return the same has even if you run the MD5 has on another computer with a different implementation. He uses the hash function on his computer, then checks to see if the has matches anything in the database he swiped. He doesn't need access to your system for this. If he finds a password that generates a hash the same as one in the database, then he takes not of it and the user name it goes with. He can tehn use that to log on to your system.

The point of using a slow hash is that there are algorithms (like bcrypt mentioned above) which run slowly on anybody's hardware. It's not that there's a pause in it or something, it just takes a LONG time to calculate. For a normal login, nobody cares about an extra second. When you are trying to brute force passwords, then it does matter.

 

[Daald]

Or am I still wide of the mark?

Nope. You got it.

If I store the unique salts in a separate database on another server, this presumably makes their lives as criminal scum even harder because...

• It slows the process down further
• They're less likely to crack both servers
• I may be able to detect when remote requests are coming in from an unauthorised source. In which case I can deduce a cracked server, force a password change (both site and Linux accounts), and generate a new table of unique salts
• If I can detect a request for a salt from an IP other than my approved list, I can presumably return false data and let the crooks waste their time

Yes? No? Dreaming? Overkill?

Well, the point is that if they get as far as the back end database then all these things are minor annoyances.

When we double hashed and salted the passwords in that project I did, we mostly did that to protect against some IT person stealing the login table or some sort of error in our code which would cause the table to be returned.

In that case that data would be almost completely useless to them since it would take forever to crack one password. They would also have to use the entire ASCII range since we added characters in the hash that we don't allow users to type.

Another way to make it harder is to add a slow hashing algorithm like Dessi suggested to further hinder their efforts.

In the end you have to realize that if they have everything all you are doing is slowing them down and you can't keep your data completely secure. Don't forget that all the people that would have the resources to pull stuff like this off are not the people doing most of the hacking nowadays. Most hackers look for easy marks.

If you are writing something where security is essential (banks, secret gov stuff), then you have to realize that you have to involve everybody from the user, to the network, to the machines to the software to preserve your security. You can't do it all from just the software.

 

[Evilgiraffe]

Shouldn't it be 6.75x 10⁶ seconds? You've divided by 108,600 and I think it should be 108,600,000 if I understand correctly and you've left the result in seconds but quoted minutes.

That makes 11,200 minutes, or about 78 days so still not easy

Yup, you're right. I read it as 108.5M Hash min^-1 when it was obviously 108.5M Hash s^-1. Still it's a very big number either way.