password salting

From Visual Basic to GNU C, this is the place to talk programming.

Moderators: SecretSquirrel, just brew it!

password salting

Postposted on Wed Dec 15, 2010 6:51 am

Hello!

Sorry if this is a question that is difficult to answer but I don't know where else to turn for help.

I am developing an online game. It will have a database with potentially thousands of passwords, email addresses and usernames...

I want to do everything possible to keep this data secure, by using both encrypted communications and making sure that our database is secure from theft and hacking.

I have read up on password salting on google but every page usually just says add a salt to protect from rainbow tables. Many of these articles are old and out of date.

I am smart. I know that MD5s can be brute forced. I know that even if I salt my passwords, those salts can be reversed because apparently a large percentage of my passwords are going to be very weak. It is not too much more work to run a rainbow table or a brute force hash on the password "password" and find out what salt i am using. If my salts are dynamic then they can use multiple results for "password" and figure out my algorithm.

So, as I look into the future and try to come up with a real secure way to protect this user data, does anybody have any good links to read up on this?

My best solution right now is to generate a salt by taking random characters from the username and email address in a unique and reproducible way. Then I will take the salt and the password and hash them together. Then I will take that MD5 and hash it with the current date as well as a special password that only I know. Then store THAT in the data base, along with the date of last access. Every time the user logs in, the hash is recalculated by unencrypting the MD5 and reincrypting it with today's date.

Will this even add a good amount of protection or is there still a really easy way to get to the user data? Should i just use something different than MD5? Again... any links or leads to more info would be greatly appreciated.
ShadowTiger
Gerbil First Class
 
Posts: 119
Joined: Wed Oct 01, 2008 2:39 pm

Re: password salting

Postposted on Wed Dec 15, 2010 7:40 am

http://codahale.com/how-to-safely-store-a-password/

Don't assume your algorithm is going to be secret, or your salts will be (if they are per user they will have to be stored in the database anyway), if an attacker has access to your database, they may well have access to everything else.

Basically you need to make brute force decryption too slow to be effective. That's what the above link is advising, by using a (comparatively) slow hash function, combined with per user salts (this could just be the timestamp or any other random string) it will be infeasible for an attacker to crack any particular password, but still fast enough for your web apps purposes. Of course you'll probably want to combine this with some kind of 3 failed login attempts and the IP is blacklisted for x seconds/minutes/hours, to prevent DoS attacks. But hopefully this is a good starting point.
To understand recursion, you must first understand recursion.
AMM
Minister of Gerbil Affairs
 
Posts: 2010
Joined: Tue Jun 10, 2003 9:12 am
Location: London

Re: password salting

Postposted on Wed Dec 15, 2010 8:01 am

What is the platform you're targeting with this? For each platform, there are usually already packages out there that do exactly what you're asking. Creating something from scratch like that is dangerous because you don't know all of the pitfalls and it's pretty much guaranteed that the people who are developing the packages are more familiar with the problem than you are.
Image
Nitrodist
Grand Gerbil Poohbah
 
Posts: 3280
Joined: Wed Jul 19, 2006 1:51 am
Location: Minnesota

Re: password salting

Postposted on Wed Dec 15, 2010 8:19 am

thanks for the replies...

I am using C++ with a mysql database...

database is running on the same computer as the server currently but that probably won't be the case forever.

i don't really know that much about using mysql besides queries. I still have to setup an automated backup system.

my database is not hooked up to the web, it runs on the same network as our servers. It will never be configured for remote requests in the foreseeable future. The game is a regular windows exe client right now, though we may expand to other platforms.

I think that using B-crypt is a good idea... I will look into switching to that when my game goes live.

BTW my suggestion was NOT to store the salt in the database, but rather to calculate the salt using an algorithm. This would force the hacker to try every possible salt.
ShadowTiger
Gerbil First Class
 
Posts: 119
Joined: Wed Oct 01, 2008 2:39 pm

Re: password salting

Postposted on Wed Dec 15, 2010 8:38 am

ShadowTiger wrote:BTW my suggestion was NOT to store the salt in the database, but rather to calculate the salt using an algorithm. This would force the hacker to try every possible salt.


But you can't assume your algorithm is going to be secure. If they have access to your database, then they may well have access to your algorithms.
To understand recursion, you must first understand recursion.
AMM
Minister of Gerbil Affairs
 
Posts: 2010
Joined: Tue Jun 10, 2003 9:12 am
Location: London

Re: password salting

Postposted on Wed Dec 15, 2010 10:38 am

One MD5s biggest problems is the fact that two completely different passwords can potentially generate the same exact hash. To account for this, you salt the password with some other fields further lessening the likelihood. Some salts can be a combination of fields for the same user such as the Id in the database, really any field(s). So when the user enters their password "Phoenix123", perhaps search the database for their username and password, salting the password as MD5(MyUserName+Phoenix123) and find the match, for example.

The real trick is to make the operation too expensive to be feasible via brute force. I read an article the other day that stated that you can easily buy/rent cloud computer power in the thousands of CPUs for pretty cheap. Consider the Gawker incident recently; they were not able to, in their own time table, to break any password over 8 characters because it was too expensive. They did manage to get a ridiculous number of accounts that were

A) not salted
B) hashed with DES (old, out dated, inappropriate)
C) weak passwords [less than 8 characters]

I think the smartest thing you can do is force a password of a long length. Salting and Hashing are things you should always do. The hash in my mind is just more protection. Nothing is impervious and given enough computing power and time, nothing is secure. Even MD5 has been attacked.

This is over simplification on my part, I'm far from an expert and I lack a lot of the technical know-how for WHY of things when it comes to crypto - it's a hobby at the moment. Just remember the timeless adage that security through obfuscation is not security :)

edit: Neat link.
Corsair 600T | ASUS P8P67 PRO | Intel 2500k @ 4.4Ghz | EVGA 560 TI | G.SKILL Ripjaws Series 8GB | Corsair HX650 650W
steelcity_ballin
Gerbilus Supremus
Silver subscriber
 
 
Posts: 11907
Joined: Mon May 26, 2003 5:55 am
Location: Pittsburgh PA

Re: password salting

Postposted on Wed Dec 15, 2010 11:00 am

steelcity_ballin wrote:One MD5s biggest problems is the fact that two completely different passwords can potentially generate the same exact hash. To account for this, you salt the password with some other fields further lessening the likelihood. Some salts can be a combination of fields for the same user such as the Id in the database, really any field(s). So when the user enters their password "Phoenix123", perhaps search the database for their username and password, salting the password as MD5(MyUserName+Phoenix123) and find the match, for example.


This is a problem with any hash function, it is not unique to MD5. Collisions are NOT the reason salts are used.

Salts are used so that you cannot build what are called rainbow tables. A rainbow table is simply a precomputed table of all possible hashes given some input rule. So I can generate a rainbow table of say all MD5 values of 8 digit passwords build from alphanumeric input, if your password is 8 digits or less and doesn't use special characters it's MD5 value will be in my database. Depending on your computing resources you can generate rainbow tables of varying input types and lengths.

If you use salts then instead of storing MD5("password") you store MD5("password"+"random salt"). Now if an attacker acquires your list of MD5 hashes, and they also know the salt, they will not be able to use their precomputed rainbow table. This increases the computational resources the attacker has to throw at the problem.

steelcity_ballin wrote:The real trick is to make the operation too expensive to be feasible via brute force. I read an article the other day that stated that you can easily buy/rent cloud computer power in the thousands of CPUs for pretty cheap. Consider the Gawker incident recently; they were not able to, in their own time table, to break any password over 8 characters because it was too expensive. They did manage to get a ridiculous number of accounts that were

A) not salted
B) hashed with DES (old, out dated, inappropriate)
C) weak passwords [less than 8 characters]


Some of this is right, some not so. The problem with gawker was that they were using an inappropriate implementation that only looked at the first 8 digits of a users entered password. So even if a user had a 20 digit password, only the first 8 were being hashed and compared. Obviously this is a broken approach regardless of your hashing algorithm (though there are good reasons why MD5 should not be used anymore).


Remember that we are discussing here a worst case scenario (i.e an attacker has compromised your user account database), the aim of salting and hashing is to prevent an attacker being able to do anything useful with that information; it would be a lot better to prevent that compromise in the first place! Per user salts and a hash function such as bcrypt that takes a lot of computational time is a solution to *ONE* specific problem, "How do I stop an attacker who has acquired my user database from discovering my user's passwords?", there are still many other security related questions that need to be addressed in an application like this.
To understand recursion, you must first understand recursion.
AMM
Minister of Gerbil Affairs
 
Posts: 2010
Joined: Tue Jun 10, 2003 9:12 am
Location: London

Re: password salting

Postposted on Wed Dec 15, 2010 11:13 am

http://chargen.matasano.com/chargen/200 ... out-s.html

Here is an interesting article to read.

I think the general lesson to take away from all of this is "Do not design your own crypto-systems unless you are a security expert". Cryptography is notoriously tricky to do correctly, and many many people who are good software designers, implement BAD cryptography systems. Use something designed by an expert.
To understand recursion, you must first understand recursion.
AMM
Minister of Gerbil Affairs
 
Posts: 2010
Joined: Tue Jun 10, 2003 9:12 am
Location: London

Re: password salting

Postposted on Wed Dec 15, 2010 11:42 am

AMM wrote:
ShadowTiger wrote:BTW my suggestion was NOT to store the salt in the database, but rather to calculate the salt using an algorithm. This would force the hacker to try every possible salt.

But you can't assume your algorithm is going to be secure. If they have access to your database, then they may well have access to your algorithms.

Yeah, whether calculating the salt algorithmically helps you a lot or a little depends on whether there's an easy way for an attacker to discover the algorithm. If the algorithm is coded in a scripting language (i.e. plain text), it is easily discovered by anyone who manages to hack into the server. Coding it in a compiled language (and storing the source code elsewhere) will provide another layer of protection, but a determined attacker with access to the compiled code could still reverse engineer it.

To the OP: You really need to define the scope of the problem better. What sort of attacks do you want to defend against? If you're worried about someone stealing the user database, password encryption doesn't help; you need to be looking at securing the server itself and/or encrypting the data in the database. If you're protecting against people trying to guess simple passwords, there really is no good defense other than locking accounts out after some very small number of failed attempts; perhaps you should be enforcing minimum password lengths (or assigning people machine-generated passwords) instead. Most of the discussion thus far (password hashing and salting) only protects you against rainbow tables and other brute force methods -- i.e., how badly will you be compromised, given that someone has already managed to steal your password hash table. I think you may be losing the forest for the trees here...
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37472
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: password salting

Postposted on Thu Dec 16, 2010 5:18 am

Yeah, I guess I should have been more clear of what i was worried about. Thank you all for your responses, seeing you talk about it amongst eachother and the links you provide really help me understand the ecosystem i am working in.

Right now our game runs on a dedicated server that we rent for a monthly payment. I just used Remote Desktop to go in and setup the database and run our game server on that computer. Basically, anyone in the building where that server is hosted could easily gain access to my customer's data. Honestly I have no idea if that has ever happened, what security precautions are being taken, and who would be liable. I have plenty of trust for my hosting provider, but the number one rule of security is trust no one.

So basically I am mostly worried about a physical theft of data, though potentially someone else could use a vulnerability to remote connect to the server and steal data as well. If this did happen, the thief would have access to the database and our game server exe written in C++, which somewhere in the code has the password for the database hard coded into it. The thief would not have access to the source code, but could decompile the executable perhaps.

Since we are a small company I think hosting our own server would hinder our scaling capabilities greatly, so I was wondering if I could be proactive in minimizing the security holes instead of sending out emails to our customers explaining that their data had been stolen (hypothetically).
ShadowTiger
Gerbil First Class
 
Posts: 119
Joined: Wed Oct 01, 2008 2:39 pm

Re: password salting

Postposted on Thu Dec 16, 2010 5:46 am

You should at the very least have the database server set up with firewall rules to disallow connections except from certain whitelisted IP addresses, i.e. your game server. For testing purposes you would be better off having separate staging servers that aren't publicly accessible.

With what we've said already I think you should be reasonably able to secure your user's passwords against brute-force cracking. Physical security of the servers is probably well outside the scope of this discussion, but is obviously important. Depending on the OS you are using and the network setup there are various steps you can take to secure the servers against unauthorized access, i.e. IP whitelists, strong passwords for developer access, intrusion detection systems, server logs etc.

How does your client communicate the authentication process with the server? I hope passwords aren't being transmitted in plaintext!
To understand recursion, you must first understand recursion.
AMM
Minister of Gerbil Affairs
 
Posts: 2010
Joined: Tue Jun 10, 2003 9:12 am
Location: London

Re: password salting

Postposted on Thu Dec 16, 2010 7:54 am

Well at the end of the day you do need to trust the hosting provider, since they've got physical access to the hardware. Do they have Admin rights on the machine or is this a co-lo that you maintain entirely by yourself? And how far do you want to go to make it difficult for the hosting provider to steal your data? (I.e., how paranoid are you?)
(this space intentionally left blank)
just brew it!
Administrator
Gold subscriber
 
 
Posts: 37472
Joined: Tue Aug 20, 2002 10:51 pm
Location: Somewhere, having a beer

Re: password salting

Postposted on Thu Dec 16, 2010 10:48 am

ShadowTiger wrote:game server exe written in C++, which somewhere in the code has the password for the database hard coded into it. The thief would not have access to the source code, but could decompile the executable perhaps.
Or just run strings on the binary...
notfred
Grand Gerbil Poohbah
 
Posts: 3706
Joined: Tue Aug 10, 2004 10:10 am
Location: Ottawa, Canada

Re: password salting

Postposted on Sun Jan 02, 2011 7:10 am

The way that Prag Prog's RoR book does the passwords is with salting, of course.

They store the salt and the SHA-1 hash of the password + the salt. To generate the salt they take the ruby's object id (which is 8 decimal places long) and is added to the rand function which is 17-19 decimals long (with a period and a 0 at the beginning in it, so effectively 15-17).

The salt is now a integer number that is 23-25 decimal places long.

The line looks like this in ruby once you've got the salt:

Code: Select all
Digest::SHA1.hexdigest(password + salt)


Below is a working sample:

Code: Select all
irb(main):001:0> require 'digest'
=> true
irb(main):002:0> password = "s3cr3tpa4xw0rd"
=> "s3cr3tpa4xw0rd"
irb(main):003:0> salt = password.object_id.to_s + rand.to_s
=> "226525080.8670894735058609"
irb(main):004:0> #the object_id used in the tutorial is the temporary object that this data will be mapped to through its ORM, not the way it's shown here.
irb(main):005:0* hash = Digest::SHA1.hexdigest(password + salt)
=> "2dd8d02cc3d40571a54951588affad5c7ef3efcc"
irb(main):006:0>


So you store the SHA1 hash and the salt. To check if an entered password was valid later you just simply do this (continuing on here):

Code: Select all
irb(main):006:0> new_password = "hunter2"
=> "hunter2"
irb(main):008:0> hash == Digest::SHA1.hexdigest(new_password + salt)
=> false
irb(main):009:0> new_password = "s3cr3tpa4xw0rd"
=> "s3cr3tpa4xw0rd"
irb(main):010:0> hash == Digest::SHA1.hexdigest(new_password + salt)
=> true
irb(main):011:0>


This code is, of course, encapsulated within your security module, user module, etc., so that you only write this code once.
Image
Nitrodist
Grand Gerbil Poohbah
 
Posts: 3280
Joined: Wed Jul 19, 2006 1:51 am
Location: Minnesota

Re: password salting

Postposted on Wed Jan 19, 2011 12:29 pm

I just go all out and use SHA512 with a random GUID for a salt. Good luck rainbow-tabling that.

A Rainbow table attack just uses a list of know hashes as a "hash table" lookup. By adding a salt, you invalidate all the entries in the rainbow table, so the table would have to be re-computed and that takes A LONG TIME. By adding a random salt per password, there is no way of creating a single table for a reverse lookup. You would have to brute force every hash, even if you know the salt.

If someone tried to do a brute force against SHA512 with a GUID.. well.. they best be dedicated to the task.

Example. My i7 2.66ghz can do about 10MB/sec of SHA512 per thread. I have 8 threads. Assume the hacker wants to break a 8 char password. They have a 50% chance the correct password will be hit before the half-way point. There are 72 valid password chars. Guid salt plus 8 char password is 48 chars or 48 bytes to hash. At 10MB/sec on all 8 threads, it would take on average, 7.8 years to break the password via brute force. That's also assuming they know the password is 8 chars. If they don't know how many chars the password is, then they need to also go through all the permutations for 3,4,5,6,7 length passwords. Brute forcing a 9 char password would take about 72 times longer, so 567 years on my i7 2.66ghz.
bcronce
Gerbil
 
Posts: 18
Joined: Tue Jun 03, 2008 5:12 pm

Re: password salting

Postposted on Wed Jan 19, 2011 3:00 pm

ShadowTiger wrote:I am smart. I know that MD5s can be brute forced. I know that even if I salt my passwords, those salts can be reversed because apparently a large percentage of my passwords are going to be very weak. It is not too much more work to run a rainbow table or a brute force hash on the password "password" and find out what salt i am using. If my salts are dynamic then they can use multiple results for "password" and figure out my algorithm.


Here's where I think you're getting hung up Shadow. As an attacker, if I know some users are going to use weak, well known passwords (i.e. "love", "sex", "secret", "god"), why am I going to go through the effort of brute forcing/reverse-engineering the decryption of the hash + salt? If I have your list of usernames (due to physical/remote access to the database files wo/ encryption), I'm just going to try logging onto your game directly, trying each user against my common passwords.

What salting does (and per-user salting does even better) is make it more difficult for me to generateevery user's password. Remember: What the salt is and how it is applied are NOT a secret.
Intel i7 860, Asus P7P55D Pro, 4x2GB Corsair XMS3 1600 (CMX4GX3M2A1600C9), EVGA GTX 560 Ti Superclocked
Seagate 7200.7 160GB, WD Caviar Black 640GB, WD Caviar Green 1TB, WD Caviar Green 2TB
Dell 2408WFP and Dell 2407WFP-HC for dual-24" goodness
emorgoch
Gerbil Elite
 
Posts: 686
Joined: Tue Mar 27, 2007 11:26 am
Location: Toronto, ON


Return to Developer's Den

Who is online

Users browsing this forum: No registered users and 2 guests