[article draft] Password hashing howto and hownotto

Discussions of secure PHP coding. Security in software is important, so don't be afraid to ask. And when answering: be anal. Nitpick. No security vulnerability is too small.

Moderator: General Moderators

[article draft] Password hashing howto and hownotto

Postby Mordred » Sun Jan 28, 2007 5:03 am

(Okay, the actual title is not this, but it's too long for the input field ;) )

Questions about this have been asked too many times, and I've always felt unsatisfied by the popular answers, but lacked the time to clearly explain the rationale behind using "salt and pepper". This tries to amend the situation by going over the popular choices and discussing security problems with them. I've seen bad examples with the listed schemes "used in the wild" (discussing them here might be a bit against the forum rules) and almost every time the system would have been secure had it used proper hashing and a trick or two from the "paranoia" section. I cannot stress enough how important those steps are in terms of increasing the security, and since they are quite painless to implement, I don't see a reason not to.

Comments, thoughts, fact and grammar nitpicks are very much welcomed.
I plan to add links explaining some of the concepts mentioned and also to articles and real projects advocating this or that technique.
Maybe a chart crossing attack and defense techniques will be useful too, what do you think?
Do you think this needs expanding (or shrinking) in some direction?

-------------------
Risk mitigation strategies for storing login credentials

Abstract:

When storing sensitive data it is never enough to rely on the security of the storage environment alone. While developing and deploying of 100% secure software is a nice dream to have, any security-aware developer should have contingency plans for when the security is compromised. In this article we will examine some well-known solutions and will propose some additional steps for hardening the security of stored login credentials.



1. Secrets and security layers.

Passwords (or rather username/password pairs) as means of authentication are the proverbial "something you know" in Information Security. The level of security they provide is considered enough for most of the current web applications. Passwords are essentially a shared secret between the user and the web application. The problem with "something you know" is that one wouldn't want someone else to know it as well, but on the other hand the user MUST send his password to the server, and the server MUST somehow store it so it can check later if Bob-the-user provided the right password. A good mechanism of secure transport of login credentials is the https protocol, which ensures that only Bob and the server ever see the plaintext of the password.

We must note that there are good passwords and bad passwords, and that the security of a login is as much in danger from an SQL injection vulnerability as well as from a weak password. We will not discuss password strength policies, but it must be noted that enforcing some at least basic password rules is an essential step in securing the login system.

For brevity we will talk about usernames and passwords, but do not forget that there might be more components to an authentication system, for example the "forgotten password" secret question/answer combo, password reminder texts, etc. Whatever security measures you take against disclosure of username/password combos, you must take against such "peripheral" data as well.

Applications in general work in layers, and web applications have the additional strata of web and database servers, underlying OSes with their specific file systems, etc. Each of these layers bears security burdens on its own and may prove to be the security point of failure in case of a malicious attack. This does not mean that the other layers must not try to reduce the impact of a security breach.

If an attacker gains shell access to the server he has quite a huge level of control over the system, and there is very little to be done to mitigate the damage. On the bright side though, usually attacks penetrate the much "lighter" layers of defense, and the damage they cause are limited.

In this article we will generally assume the worst, Mallory, a skilled malicious attacker, has access to one or all login credential records in the database, and possibly to other resources on the system. We will also assume that the most precious information on the server are the said login credentials, and that our primary objective is to protect them. We will now assess the levels of security breaching Mallory is capable of and how to further limit his options.

We must not forget that even in the mythical 100% secure system, which Mallory cannot exploit, Adam the admin also has full access to the database, and Bob the user would very much like that his secret will not be shared with Adam.


2. Plain text passwords

Also known as the "quadruple XOR encryption", this is the zero point in secure storage, and should generally never be done. Apart from Mallory, the passwords are visible to Adam the admin and Isabella the ISP. Now Bob the user is well aware that his private messages can be read by Adam and Isabella, but he totally wouldn't like that they also know his most precious password. The problem with Adam and Isabella also lies in the choice of a secure password transport mechanism, which is outside the scope of this article, so we won't discuss it futher.

3. Encrypted passwords

Encrypted passwords have the benefit of not being obvious to the naked eye, but also the intrinsic weakness that encryption is reversible. If not Mallory, then at least Adam can easily learn the plaintext, as he knows the encryption key. Moreover, since the attacker may have control over the plaintext of a password by either registering his own account or by guessing or online bruteforcing of the password of a single existing account, he may use a known plaintext attack to reveal the key that is being used.

4. Hashed passwords

Hashes are one-way functions. Given a plaintext password they produce a hash value that cannot computationally be reversed into the original password. By storing the hashes in the database, we can then check Bob's credentials by hashing his supplied password and comparing it to the hash of his real password we keep in the database. Since no plain text password is ever recorded in the database, this seems like a better solution than keeping the plaintext. And so it is, but still this solution has some unpleasant properties.

First, if Bob and Cindy both choose 123456 as their password, Adam the admin can easily see that their passwords match, because the hashes in the database are the same.

Moreover, if Mallory has Bob's hash, he can check it against a precomputed rainbow table for the hash function which will most probably easily give him the plaintext, Bob's password.

Third, if Mallory manages to obtain the entire table with login credentials, he can efficiently reveal the passwords of many users by simultaneously checking them in a rainbow table.

Apart from a rainbow table, Mallory can also try a dictionary attack and of course the plain oldschool bruteforce. Note that these attacks will be carried offline, at the leisure of Mallory's distributed password cracking botnet.

This is the currently most popular method, and only recently do existing open source projects try to migrate to salted passwords.

5. Salted hashed passwords

This is the method most authors advice for, and the rationale behind it is quite sound.

The reason bruteforce works (and rainbow tables and dictionary attacks are just optimisations of the bruteforce attack) is because users tend to choose bad passwords, ones which are short and found in a common dictionary. A good way to circumvent this, apart from enforcing fashist password policies, is to add a piece of "good" data to the password before hashing it. By "good" we mean that it is long enough and built of diverse character sets. This is like magically making the password "better" without actually making the user remember 30 characters of line noise. This technique is known as "salting the hash".

This is the point where authors stop agreeing and start moving in three main directions:

I. The school of doublehashing

The reasoning is that there are precomputed dictionaries for HASH(password), but not ones for HASH(HASH(password)), so here's an easy way to defeat password stealers. While this is true, the method still has the unpleasant property that Bob's and Cindy's doubly hashed passwords are still the same.

Apart from that, from a cryptological point of view, double hashing is considered insecure, although I suspect that in reality this would not impact anyone but an enemy of the NSA or something. I am not a cryptologist though, so I listen to what the experts are saying, which is not to do it. You may use this mantra in your daily meditations: Never never ever ever double double hash.

II. The school of constant salts

They propose keeping HASH(const_salt + password), where the salt is the same for every user. The hashes are again safe from rainbow table lookups, but the "same password" = "same hash" problem with Bob and Cindy persists.

III. The school of personal salts

If we generate a salt value for every user, HASH(user_salt + password) will be different for Bob and Cindy even if their passwords match. Lookups in rainbow tables will not work, so this seems the best strategy. We must keep the generated user_salt in the login table though, while with the first two methods no additional info was needed.

We must note that mixed strategies like HASH(const_salt + HASH(password)) and HASH(user_salt + HASH(password)), apart from maybe going going against against the aforementioned mantra, are essentially not different from schools II and III.

All of these strategies prevent precomputed attacks, but are still vulnerable to offline dictionary and bruteforce attacks, depending on the level of access Mallory has to the system. Assuming the exact hashing scheme is known (as is the case with the popular open source applications), Mallory has a range of options:

For example with II, Mallory may expect that Adam the admin was lazy and didn't change the default salt while configuring the application. He may also carry a known plaintext attack in order to bruteforce the salt value. Thirdly, if he manages to get read access to the server's filesystem, he can examine the application sources and reveal the salt value.

With III, if Mallory has access to the credentials in the database, he can also read the stored user_salt and carry a dictionary or a bruteforce attack against the account.

6. The advanced gourmet course: using salt and pepper

Since both schools of personal and constant salts have different strengths and weaknesses, it is only logical to combine them in hope that the result will be better. Let's examine a system that uses something like HASH(const_salt + password + user_salt):

1. The double-salted (or salted and peppered if you so prefer) hash is safe from rainbow table lookups.
2. Bob's and Cindy's hashes will be different, even if their passwords are the same.
3. Even if Mallory has full read access to the database, he will not be able to launch a dictionary or a bruteforce attack against the hashes, as he will be missing the const_salt, which is not kept in the database.
4. Even with all salts in hand, Mallory can bruteforce only one account at a time.

Mallory's only options now are to try a know plaintext attack agains the const_salt (which is easily thwarted by choosing a long and "ugly" salt) or by obtaining a read access to the sources.

With a sufficiently "good" const_salt, we may skip the special user_salt column, and use an already existing column as the username or the email column without affecting the security. Still, database space is free, so we might as well use it.

To put things in perspective, by using salt and pepper, the credentials can be stolen only if Mallory has read access to the database AND the filesystem AND bruteforce power (requiring N (number of users) times more processing power for dictionary or bruteforce attacks against all accounts)

7. 123456 Paranoia Lane, Gotham city

There are a few easy steps we may take in order to protect the login credentials better, and they lay in hardening the "nearby" security layers. We will not reiterate the well known recommendations for secure coding (validate and escape everything that comes from the user, simple, eh ;) and look for some additional non-kosher techniques. Remember, the best way with security is to be as paranoid as possible!

1. Choose good long salt (and pepper!) values. This is quite obvious, but still there are authors and coders out there that put artificial limits like CHAR( 8 ) columns for user salts, containing only alphanumeric characters. Database space is free, don't economize the cheap forsaking the expensive.

2. Use better hash functions. Although the recent "breaks" of MD5 and SHA1 do not seem to affect their usage as password hashes, better attacks may appear any moment now, so use another one for your new applications. SHA256 is the currently suggested hashing algorithm.

3. Use a "quirky" hashing technique - hash the first two chars of the user_salt and concat this hash to the whole salt'n'pepa'n'password before hashing it again with ANOTHER hash function - you get the idea. Be creative, this will require Mallory to have read access to the hashing code in order to see the exact hashing scheme, and then write custom password cracking code instead of using an already existing one.

4. "Don't do security through obscurity" is actually a misquote. Don't do security ONLY through obscurity. Use obscurity as another security layer when appropriate. Give "ugly" names to the columns and tables used in the login process. Even if Mallory finds an SQL injection vulnerability, he must yet guess those ugly names or at least use many additional steps in learning them if the database system has means of querying for table metadata. If possible, deny your database user access to the metadata tables.

5. Usernames are one half of the username/password combo required for login. I haven't yet seen a security system that readily displays a user's password, but many of those I've seen happily show usernames to the public in forum threads, private messages, member profiles, etc. Do you know which is the most popular password? No, not 123456, it comes a distant second. The most popular choice is to have your username as a password. Of course you need to display some id of the user to the other users of the system, so use a separate "Display name" column, and either strongly warn or enforce the user to choose a display name different from his username.
Things need not have happened to be true. Tales and dreams are the shadow-truths that will endure when mere facts are dust and ashes, and forgot.
Image
My security blog. (not updated lately)
The Unexpected SQL Injection (article) (.txt, cause the .html version is broken)
Password hashing howto (and how not to) (article)
Salt strengths (article)
User avatar
Mordred
DevNet Resident
 
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Postby feyd » Sun Jan 28, 2007 10:01 am

Seems okay, overall. There's at least one noted (unintended) double word set: "going going against against" in
We must note that mixed strategies like HASH(const_salt + HASH(password)) and HASH(user_salt + HASH(password)), apart from maybe going going against against the aforementioned mantra, are essentially not different from schools II and III.


Not sure if that was intended or not.
User avatar
feyd
Neighborhood Spidermoddy
 
Posts: 31559
Joined: Mon Mar 29, 2004 4:24 pm
Location: Bothell, Washington, USA

Postby Mordred » Sun Jan 28, 2007 11:49 am

Not sure if that was intended or not.


Just a silly attempt at making fun of double hashing. Since the "mantra" also uses doubled words ...
Okay, I get it, not funny... :)
Things need not have happened to be true. Tales and dreams are the shadow-truths that will endure when mere facts are dust and ashes, and forgot.
Image
My security blog. (not updated lately)
The Unexpected SQL Injection (article) (.txt, cause the .html version is broken)
Password hashing howto (and how not to) (article)
Salt strengths (article)
User avatar
Mordred
DevNet Resident
 
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Re: [article draft] Password hashing howto and hownotto

Postby Oren » Sun Jan 28, 2007 3:38 pm

Mordred wrote:Do you think this needs expanding (or shrinking) in some direction?

Expanding - in all directions :wink:

Great article Mordred, seriously, very "deep" if you know what I mean.
We really needed such a topic and I really hope this whole topic would grow to something which is even more serious and detailed - yes it was long, but... it's short... :P I'll explain... Yes it was long relative to most of the posts we see here, but yet it was short since each sub-topic wasn't covered in full.

P.S I'm in no way suggest that Mordred didn't make a good work, the opposite - you did a GREAT work Mordred and I would like to thank you personally and hope this topic would grow to something more serious with tons of links to external resources and aticles. If this happens, it'd be great if the mods would mark this topic as Sticky for a more quick reference in the future. Keep on the great work Mordred and all the other good people here :wink:
User avatar
Oren
DevNet Resident
 
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Postby Kieran Huggins » Sun Jan 28, 2007 3:45 pm

I really enjoyed this article -I encourage you to write more! Thanks!

I just wish you'd written it a few days previous, since we had to do decide this very thing during the throwdown ;-)
User avatar
Kieran Huggins
DevNet Master
 
Posts: 3635
Joined: Wed Dec 06, 2006 5:14 pm
Location: Toronto, Canada

Postby Oren » Sun Jan 28, 2007 3:49 pm

Kieran Huggins wrote:I really enjoyed this article -I encourage you to write more! Thanks!

I'll second that :wink:
User avatar
Oren
DevNet Resident
 
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Postby Ollie Saunders » Sun Jan 28, 2007 5:05 pm

Ohh yes I like that article. Particularly the stuff on pepper as well as salt and straightening out that obscurity misquote. You might want to also highlight that minimizing exposure isn't really the same as obscurity and should also be respected.
User avatar
Ollie Saunders
DevNet Master
 
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Postby Oren » Sun Jan 28, 2007 6:03 pm

User avatar
Oren
DevNet Resident
 
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Postby WaldoMonster » Mon Jan 29, 2007 6:28 am

After reading the first part I printed a hard copy to read the rest of it.
Thanks for this very interesting article Mordred,

I hope you have the time to expand this article with:
  • What you already suggested, "defence techniques"
  • Secure (relative secure) login system without SSL.
    I use a login system based on the "Alternative System" from Paj’s site for that.
    http://www.pajhome.org.uk/crypt/md5/auth.html
  • What does "Chart crossing attack" mean?
    Maybe interesting to ;-)
User avatar
WaldoMonster
Forum Contributor
 
Posts: 225
Joined: Mon Apr 19, 2004 6:19 pm

Postby Mordred » Tue Jan 30, 2007 6:57 am

Thanks for the kind words, people!

I'm not sure I want to repeat the basics on hashing, there's lots of articles on that, and I can't add anything to them apart from the section on "salt and pepper", so I'll maybe just point to some good articles and leave it at that.

Secure (relative secure) login system without SSL.

I'm hardly an expert on that, and besides my topic here is storage, not transport.
Anyway, as I see that "alternative system", I don't think it will stop replay attacks, if someone sniffs hex_md5(hex_hmac_md5(password, random2)), he can login with that the next time. I might be wrong, I haven't put much thought into that (no time right now)

What does "Chart crossing attack" mean?

This is a vulnerability in the parser for the English language ;) Next time I'll write it in lojban :P

Should be like this:
Maybe a (chart) (crossing) (attack and defense) (techniques) will be useful too, what do you think?
Sorry, English is not my mother tongue.

I meant a chart where one dimension covers possible attacks, and the second dimension covers defensive steps, so I can better illustrate the effectiveness of this or that strategy. I will definitely write one, but no sooner than the next weekend :/
Things need not have happened to be true. Tales and dreams are the shadow-truths that will endure when mere facts are dust and ashes, and forgot.
Image
My security blog. (not updated lately)
The Unexpected SQL Injection (article) (.txt, cause the .html version is broken)
Password hashing howto (and how not to) (article)
Salt strengths (article)
User avatar
Mordred
DevNet Resident
 
Posts: 1579
Joined: Sun Sep 03, 2006 5:19 am
Location: Sofia, Bulgaria

Postby Maugrim_The_Reaper » Tue Jan 30, 2007 11:08 am

Good read - I found pieces a bit obscure (but look who's talking!) but mainly that's an overview effect - a little more detail or graphics would bump that up. Overall it's solid and hits all the main angles - nice work. Main issues with MD5 and SHA1 is how little computing power is needed by recent approaches - it's still usable for some basic purposes but should be phased out for hashing where security is a major concern (or simply to get in the habit ;)).

For "password transfer" techniques, the most common reliable is SSL. Failing SSL, the password needs to be hashed before sending, and in a way which cannot be replayed. I wrote a tutorial on the Challenge/Response approach a while back: http://forums.devnetwork.net/viewtopic.php?t=38810 , consider it complementary reading, it's main failing is that client processing relies on the presence of Javascript. The working example falls back gracefully to plain text transfers of passwords if JS is disabled.
Pádraic Brady

http://blog.astrumfutura.com
http://www.survivethedeepend.com
Zend Framework Community Review Team
Zend Framework PHP-FIG Representative
User avatar
Maugrim_The_Reaper
DevNet Master
 
Posts: 2704
Joined: Tue Nov 02, 2004 6:43 am
Location: Ireland

Postby The Phoenix » Tue Jan 30, 2007 1:08 pm

Points:

- "Note that these attacks will be carried offline, at the leisure of Mallory's distributed password cracking botnet" - An offline distributed botnet? Unlikely at best. Perhaps reword it to either offline, or on a distributed botnet.

- "Apart from that, from a cryptological point of view, double hashing is considered insecure, although I suspect that in reality this would not impact anyone but an enemy of the NSA or something. I am not a cryptologist though, so I listen to what the experts are saying, which is not to do it. You may use this mantra in your daily meditations: Never never ever ever double double hash. "
This is somewhat misleading. Its insecure because it reduces the entropy, which in turn makes it easier to do a brute force attack. Less combinations = faster cracking. You can realistically cycle through most common md5 passwords in under a week on common hardware available today: http://www.timwarriner.com/software/md5brute.html

Thats certainly not the level of 'enemy of the NSA'. Its script-kiddie level. Thats why its a very good idea to move to the SHA2 class of hashes - as the government is now requiring for all new implementations.

- "Use obscurity as another security layer where appropriate": Many people misunderstand this concept. Obscurity != Security, even for large values of Obscurity. It doesn't ever add security. Here's an example that illustrates it. If I have a million dollars, and hide it in my house, given sufficient search time & resources, you will locate it, and take it.

If however, I put it inside a safe (fireproof, axeproof, etc), it is *secured*. Not *obscured*. Thats why we trust safes and vaults, and treasure maps went out of style long ago.

In fact, having obscure/difficult names for tables and the like make it likely the programmer will make mistakes, lowering the security by accident. Security withstands attack - it doesn't avoid it.

Even if you are married to the idea, and want to plead the case for obscurity as a positive add to overall security, it belongs in a separate thread. One likely to generate flames, and a ton of misinformed posts. :)

- Hashing (Salt & Pepper): You left out the most secure, and most widely recommended approach: One-time pads. By sending a unique salt that is generated per-request, you can avoid all of the attacks listed.

I think you've done a great job with the overall topic, but had some key items that aren't as accurate as they could be (either in meaning or fact). You could reduce the variations in salt/hash choices, as many don't add much value. One-time pads/salts however should be given explicit call-out, as they solve almost all the issues cited.

Nice work!
User avatar
The Phoenix
Forum Contributor
 
Posts: 294
Joined: Fri Oct 06, 2006 8:12 pm

Postby Oren » Sat Feb 03, 2007 3:47 pm

The Phoenix wrote:If however, I put it inside a safe (fireproof, axeproof, etc), it is *secured*. Not *obscured*. Thats why we trust safes and vaults, and treasure maps went out of style long ago.

With the "given sufficient search time & resources", the safe can be cracked as well!

Let me clarify first that I'm not pro security through obscurity and not against. With that said, in the specific examples that Mordred mentioned, obscurity might be a good idea since (and you said it yourself The Phoenix), you need time. By giving your tables/fields less common names, the hacker may need more time - which might make the difference between a successful attack and a failure.
User avatar
Oren
DevNet Resident
 
Posts: 1640
Joined: Fri Apr 07, 2006 5:13 am
Location: Israel

Postby GameMusic » Thu Jul 12, 2007 8:52 pm

The Phoenix wrote:- Hashing (Salt & Pepper): You left out the most secure, and most widely recommended approach: One-time pads. By sending a unique salt that is generated per-request, you can avoid all of the attacks listed.


How would you do that?
GameMusic
Forum Newbie
 
Posts: 24
Joined: Fri Oct 28, 2005 8:33 pm

Postby feyd » Thu Jul 12, 2007 8:54 pm

uniqid() among other random number generation sources.
User avatar
feyd
Neighborhood Spidermoddy
 
Posts: 31559
Joined: Mon Mar 29, 2004 4:24 pm
Location: Bothell, Washington, USA

Next

Return to PHP - Security

Who is online

Users browsing this forum: No registered users and 4 guests