Fog Creek Software
Discussion Board




Why does "salt" make it harder?

Everytime somebody asks how to store username/passwords. Somebody always jumps in and says "make sure to use salt!".

Well I am looking to encrypt some passwords for something I am doing here.

My plan was to use the following process:

1. Generate Password for user - i.e. "dog"
2. Encrypt that password with a one way encryption and store that in the database - i.e. "sdafsdsdf"
3. Email the generated password to the user so they can login.

To login the user has to enter their email and password on the site. it follows this process:

1. Retrieve entered email and password
2. Encrypt the entered password
3. See if there is a row in the user list that has email and encrypted password the same.

Now that is how past projects I have done di it and is how I was going to do it this time.

But a site on the net said that people can then once they have a email address of one of your users go to your site and
enter that email address with 1,000,000 different passwords and eventually guess it.

So to "stop" this they say to change the process to:

1. Generate Password for user - i.e. "dog"
1a. Append a random string to the end of that password - i.e. "dogadasdasd"
2. Encrypt that password with a one way encryption - i.e. "sdafsdsdretretf"
2a. Store the encrypted data AND the random string ("adasdasd") in the database in 2 fields.
3. Email the generated password ("dog") to the user so they can login.

Now to login the user has to enter their email and password on the site. it follows this process:

1. Retrieve entered email and password
2. Retrieve the "salt" value from the database that corresponds with that email address
2a. Encrypt the entered password+salt
3. See if there is a row in the user list that has email and encrypted password+salt the same.


Now my question, how does the second route actually make it harder to hack the system using the "try a million passwords until it works approach"?

Wouldn't this "salt" thing only help if the hacker was actually looking at the database directly? and if the hacker could do that why wouldn't he just download the "bankdetails" table rather than the "usernames" table?

So isn't the "salt" just extra effort for no gain?

Chris Ormerod
Wednesday, April 28, 2004

The salt prevents having a dictionary of pre-generated passwords on hand when trying to break encryption.

For example, if you use a five alpha-numeric character salt, then one dictionary word has over 916 million different possible values (one for each valid salt... 62^5).

Brad Wilson (dotnetguy.techieswithcats.com)
Thursday, April 29, 2004

Another thing a salt does is prevent someone from knowing if two passwords are the same (different salt means different encrypted value for the same password).

Brad Wilson (dotnetguy.techieswithcats.com)
Thursday, April 29, 2004

So it does only help if they have access to your backend?

It doesn't stop a dictionary attack if somebody wrote a vbscript that sat there submitting our login form until it got in. Or does it?

Chris Ormerod
Thursday, April 29, 2004

I don't commonly work with encryption (I should <grin>!), but here's my understanding:

(1) With a random attack -- generating random passwords, adding the salt simply makes the password longer and that much harder to guess. If you simply add a 5 character, alphanumeric (case sensitive), that gives you about a billion more values to guess: (26 lower case + 26 upper case + 10 numeric digits) = 62 total. A 5 character salt, in this case, is 916,132,832 -- just shy of a billion.

Now, if the original password is 5 digits, add a 5 digit salt, and you've got about a billion times about a billion ( (916,132,832)^2) which is about 839,299,365,868,340,224

Add to that non alphanumerics: `-=~!@#$%^&*()_+[]{};:'",.<>/?\| -- 32 extra characters, and with the same 5 digit password with a 5 digit salt, you've got this many guesses:

53,861,511,409,489,970,176

(somebody check my math)

for a simple random password hack. You can see why admin type folks always tell you to add non-alphanumeric characters to your password.

Assuming you could guess a million of them a second, you're going to be guessing for over a trillion years. Let me know when you've guessed my password <grin> -- I'll be anxiously awaiting.

(2) In the case of a dictionary attack, it simply helps ensures that the password is not in the dictionary. You've added your own trailing characters that will likely (a) make the dictionary attack fail -- the password with your salt added won't be in the dictionary, or (b) require that the dictionary be so large and consume so much space, that the trillion years of guessing above for a random attack will look better.

Again, I don't work in crypto. This is just my understanding.

Sgt. Sausage
Thursday, April 29, 2004

"It doesn't stop a dictionary attack if somebody wrote a vbscript that sat there submitting our login form until it got in. Or does it? "

That's how I understand it, too, since the user doesn't type the "salt" part anyway.

Antti Kurenniemi
Thursday, April 29, 2004

Salt is necessary when attackers can get access to encrypted passwords. Without salt, an attacker could carry around a small "generic" dictionary containing the encrypted versions of common passwords, and use them to break into any system that used the same encryption algorithm. With salt, a "generic" dictionary becomes useless because salt makes each password encrypt to something different.

Dan Maas
Thursday, April 29, 2004

Salt does not make it harder to "guess" a user password as the hacker will use the same interface as the user and only have to write "dog" together with the email address.

The only place that will make it harder is when the hacker has guessed the database password and already has access to everything in there and that is something you should be more concerned about (ie. it could be very wise to encrypt everything in the db if it's sensitive data you have in there).

Peter Monsson
Thursday, April 29, 2004

Peter -- I stand corrected. It makes sense.

Oops. Ignore my previous post.

Sgt. Sausage
Thursday, April 29, 2004

How does the salt really help to protect the password database? Is not it reasonable / safe to assume that the intruder with access to the password database also has gained access to the salt database? Moreover the front end is still the same, so a dictionary attack is still possibe. Bandwidth limitations come to mind to avoid this, but they make the system vulnerable to DOS-attacks.

Requiring that users must include punctuation, digits or upper and lower case characters really is a bad idea from a human factors point of view. Such passwords are very hard to remember, our visual memory is much weaker than our auditive memory (for meaningful words). Require this from your users and users solve the problem with sticky notes under their keyboards or along the top of their monitors. This is a techie's solution that does not work.

Of course the requirement to include punctuation etc. adds bits and makes guessing and dictionary attacks more difficult, but there are better ways to do the same: use long passwords of two or three meaningful words, e.g. 'pendeskroof'  (pen, desk, roof).

Karel Thönissen (www.garabit.nl)
Thursday, April 29, 2004

The scenario assumes the attacker has access to the security DB (otherwise, why hash in the first place), so he has the salt and the hash of the password+salt. That last point is important: he does not have access to the hash of the password without the salt. This is never stored, since it would negate the whole salting process to nothing.

The dictionary attack is a reverse lookup. Lets say we have an 8bit password. this gives us 256 possible passwords. If I have made a dictionary of all possible passwords and their corresponding hashes, the size of dictionary needed to to a hash->password lookup is exactly 256 entries.
If I add an 8bit random salt, a same functionality dictionary (given a hash give me the password) now needs 65536 entries. It is important to realize here that taking the salt separately and taking its hash gives me no help in discovering the hash of the password+salt. That is a property of a good hashing function.

That leaves us with why a salt instead of just longer passwords? Well, not taking human nature into account, both would be the same. If we all take passwords such as "ygf33%*(BSgd4$3", dictionaries would have to grow to impractical size to have a chance of containing even one password. Unfortunately, 50% of humans seem to select "sexg0d" as their password, so we add a decent size salt to that.

Just me (Sir to you)
Thursday, April 29, 2004

"It doesn't stop a dictionary attack if somebody wrote a vbscript that sat there submitting our login form until it got in. Or does it?"

It doesn't. Presumably you already have a system in place to prevent such an attack from being realistically possibly, like locking an account out after m number of tries, for n minutes.

Brad Wilson (dotnetguy.techieswithcats.com)
Thursday, April 29, 2004

Instead of making your password scheme able to withstand brute-force attacks, why not simply eliminate brute-force attacks?

Keep track of the login attempts for a given account, and if there are more than X login attempts in Y minutes, you need to 1) deny the login attempts and 2) raise some sort of flag for the admin, because something fishy is obviously going on.

To me that makes more sense than simply strengthening yourself against brute-force attacks so that a cracking attempt takes 994383948443248394803 tries instead of 23983734332323.

(of course, that means logging all login attempts to a table, which will need to be cleaned out periodically)

John Rose
Thursday, April 29, 2004

To me, the least-secure part of a Internet-based login scheme has been *e-mailing them a lost password via plaintext*, anyway.

I don't do "cracking", but if I did, I'd write a piece of spyware that would search common mailbox formats (Outlook, Outlook Express) on the victim's computer for "lost password" emails from common sources such as Yahoo, Hotmail, etc, and forward them to me. 

Again, I've never done this for moral reasons.  And even if I were immoral, I'd be far too lazy to do it anyway. :P

John Rose
Thursday, April 29, 2004

John, in this case the hash+salt is only a defense agianst bruteforcing the passwords when the attacker has read access to a copy of the security db (e.g. from a backup). It is orthogonal to any other protection you wish to employ.

Just me (Sir to you)
Thursday, April 29, 2004

Salt helps limit the damage caused by a compromise of the password database.

Let's say I get hold of a Unix password file from an old system that does not use salt.  I now encrypt every word in the dictionary, and check the resulting encrypted hashes against the password file.  Chances are I will find some passwords.

Medieval Unix uses a 12-bit salt for passwords. The salt is stored unencrypted, and is used to modify the plaintext password.  There are 4096 possible salts.

Now when I do my dictionary attack, I must do it 4096 times, once for each salt.  Each time, I can break only those passwords that happen to be encrypted with that salt. Actually, if I have the password file, it's even easier. If there are 80 entries in the password file, then there are at most 80 salts, and I need encrypt my dictionary at most 80 times.

The medieval Unix password encryption algorithm was chosen to take about 1/2 second to encrypt a password on a VAX 11/780. That's tolerable for the computer checking a password, but it makes dictionary attacks pretty hard. Of course, modern processors are a little faster than the 11/780, so dictionary attacks are very real today.

The "modern" solution would be to choose an encryption system that takes 1/2 second of modern CPU time.  Say, RSA with an 8192-bit modulus.  Of course, that's only good for a few more years.  Even better would be to combine secrets, so the password file is encrypted with a token stored on the authentication server somehow, and if the password file is taken without the token, then it is useless.

David Jones
Thursday, April 29, 2004

For security there are many items that you need to look at:
  client, channel, business tier, database tier.

Lets work through them backwards.  These details are specific to a 2-tier project that I was responsible for in the distant past.  Improvements could be made.

Database:
  - we used one way hashes (MD5 as I recall) to store our passwords
  - to ensure that 2 passwords do not hash to the same value we ensured that UCase(user id) was included in the hash, we could also have used a salt or nonce value for more security since user id was known to the client.
  - the hashed data was stored in a separate table with select only access to a known db user id/password, along with the real database user id and password encrypted with a key derived from the user id, password and hashed password.

Business Tier/Client
  - we had a security object that knew how to access the single table with the encoded data
  - during login we would perform the same one way hash of the password.  If it matched the database version of the hash, we decrypted the database credential and reopened the database connection.

For a n-tier project we would have had to consider the Channel and the Client.
Channel
  - data would need to be encrypted against packet watching

Client
  - for a smart client you would want to do the hashing on the client using a nonce and a timestamp (the nonce and timestamp would have to travel to the server which would use this allow with the one way password hash it currently has)
  - the nonce and timestamp guard against simply using the hashed value in a replay since without it the one way hash would always be the same.
  - the timestamp is further used to ensure that the packets are not replayed by limiting the lifetime
  - further enhancements include using the size of the datapackage in the hash.

Billy Boy
Thursday, April 29, 2004

Another reason for a salt can be to prevent "internal attacks".  let's say you have an SQL based accounting system that uses a user/password table for security.  Potentially several people in your IT department (dba, it admin, backup guy) have access to read all the tables. 

It's probably possible to reverse engineer the proper way to make changes to the accounting system back end so that a nefarious change can be made without anyone knowing.  But that takes a lot of work.  How much easier would it be to simply look up the CFO/Head of HR/(insert powerful person here) password and sign in as her through the front end and make the changes.

Salted passwords prevent this from being possible.

Jason (www.mesacanyon.com)
Thursday, April 29, 2004

Billy Boy,

I don't really see clear in your smart client scenario. Why would you do the hashing on the client? If you are worried about snooping on the wire, use SSL. Now it looks like you are trying to come up with elements of a homebrew Kerberos facility.

Just me (Sir to you)
Thursday, April 29, 2004

Yes I agree that securing the channel with SSL is a good idea in general.

We don't have access to SSL on our internal network cause it costs money to buy certificate, time to setup maintain the internal web server.

Once we deploy, we need to run over port 80 exclusively -- most sites will allow 443 but not all.

Billy Boy
Thursday, April 29, 2004

And yes, we did base alot of this design on Kerberos and on the WSE security provider.

Billy Boy
Thursday, April 29, 2004

Problem I would see is that since you are going ouside, you're probably not going to have synchronized clocks to rely on (not even reasonably synchronized in the wild). This means your timestamping will have to be pretty course grained to avoid having to try too many intervals. But increasing the interval also increases your nonce window, with all the probems ascociated with that if the traffic is high.

Of course this might in practice not be a problem for your particular app.

Just me (Sir to you)
Thursday, April 29, 2004

We run ntp on our local network so our machines are reasonably accurate wrt one another.

It is also handled in the protocol.  If ts is out of range we return an error in validation with the current server time.  The time delta between client and server is used from then on to calculate the ts.  It is a pain...

Billy Boy
Thursday, April 29, 2004

I know, I know -- I say this every single time it comes up on JOS, but that's because it is important.

The fact that you are asking these questions at all tells me that you should not be writing your own authentication system.  YOU WILL GET IT WRONG.  Buy an existing, off-the-shelf authentication system written by trained professionals.

Let me put it this way -- I've written books on security, I wrote the code signing tools for WSH, and I would not consider _myself_ competent to implement the kind of system you're describing.  Authentication is one of those things that you have to get absolutely positively perfectly correct, and there are a zillion ways to get it wrong, so don't even try.

Eric Lippert
Thursday, April 29, 2004

Billy Boy,

I agree with Eric 100%. You are heading for disaster.

Just me (Sir to you)
Thursday, April 29, 2004

"Buy an existing, off-the-shelf authentication system written by trained professionals"

Could you suggest a good one?

specifics
Thursday, April 29, 2004

Eric:

You say you'd get it wrong and then you want me to get one from the professionals?  WTF are you then if you wrote it for WSH?

Do you have anything productive to add to the conversation?

Billy Boy
Thursday, April 29, 2004

Wow, what a nonsensical flame.

He said he's done a lot of security work, but even he wouldn't feel competent writing that type of authentication system since he doesn't specialize in them. There are professionals who do specialize in authentication systems - he wants you to buy from one of them.

Reading for comprehension is  a useful skill to develop.

Jimmy Jo-jo
Thursday, April 29, 2004

As an aside, a few years ago I took a graduate-level course in cryptography.  Every homework assignment included a few questions in which we were asked to break a well-known cryptographic system that had been innocently misused. These were not obvious blunders -  they were subtle errors in protocol that could easily have been introduced by any developer.  As an example, we saw no fewer than four simple mistakes in the use of RSA that allowed students to produce a total break.

If there's one thing I learned from that class, it's that I'd never attempt to build an authentication or crypto system without involving a few specialists - it's just too easy to get wrong.

Jimmy Jo-jo
Thursday, April 29, 2004

Eric & Jimmy

You are correct, my reply was inappropriate.  I just get somewhat tired of defending my employer's 'not invented here' point of view.  I would have prefered greatly to get a packaged solution for authentication, as well as a packaged UI components -- we have custom button, menus, listviews and we have implemented our own model view controller...

Billy Boy
Thursday, April 29, 2004

> You say you'd get it wrong and then you want me to get one from the professionals?  WTF are you then if you wrote it for WSH?

No, no apology needed -- that is a totally fair question.

When I wrote the code signing tools for WSH, I essentially deferred all the cryptographic heavy lifting to the existing code signing infrastructure provided by the operating system -- the CryptoAPI and the new Software Restrictions Policy API.  Of course, I needed to understand how those things worked so that my threat modelling would make sense, but I did not need to do any of the actual cryptography myself except for identifying which portions of the document need to be passed through the hash algorithm.

That sounds pretty easy, right?  No math at all, just figure out what portions of the document need to be hashed, and then call the MD5 or SHA1 library function, done.  Trivial, right?

Except that the first time I implemented it -- the SIMPLEST task in cryptography -- I got it wrong.  And that's not because I'm some kind of bozo who doesn't understand crypto -- my math fu is still reasonably good.  And the code looked perfectly correct, and the crypto experts I showed it to didn't catch the bug right away either. 

Fortunately, (a) the worst-case of the bug was that someone could take a signed file and munge it so that it would no longer run correctly but would still register as signed -- which is a pretty good worst case compared to, say, allowing arbitrary code to execute.  There was a denial of service possibility, but no escalation of privilege.  And (b), we caught the bug before WSH shipped, thank goodness, so the only code I broke was our own test team's.

I hope that adds a little more value.

Eric Lippert
Friday, April 30, 2004

The encryption Scheme used for UNIX passwords is one way: it is not possible to reverse it. Therefore, would it be accurate to say that this is, in fact, a hash code rather than an encryption of the password?

It was stated that the inclusion of the Salt in the UNIX passwords scheme increases the difficulty of guessing by a factor of 4096. But the salt is stored in plain text in the same entry as the corresponding cipher-text password. Therefore, those two characters are known to the attacker and need not be guessed. Why is it asserted that the salt increases security?

senthil
Friday, June 18, 2004

*  Recent Topics

*  Fog Creek Home