Idea: different approach to password hashing
Hi,
When storing user's passwords that you need to verify against (but not
use as plaintext) the current state of the art is:
- Hash the password
- Use a salt
- Use a slow hash function - bcrypt, scrypt, etc.
This provides the best possible protection against an attacker who has
stolen the password database. It does not solve other issues like
phishing, malware, password re-use, etc.
BUT there is one remaining problem: the slow hash function can allow a
denial of service attack. A single request burns a lot of CPU. In
practice I don't think this is a major problem, given defences like IP
throttling. But it does deter people from using a higher work factor, to
really get the benefit of slow hashing.
Given the improving performance of JavaScript in browsers, it may now
make sense to do this in the browser. I'm assuming here that the site is
using SSL, so the JavaScript is delivered securely. If you're not using
SSL, then using a slow hash function is unlikely to be a priority for
you. There is at least once JavaScript implementation of bcrypt
(https://code.google.com/p/javascript-bcrypt/). But using this in a
simple way would introduce two problems:
- The client needs to fetch the salt from the server. This introduces
latency on login and, unless care is taken, can reveal whether a
particular user account exists. - If hashing is done purely on the client then the benefits of storing
hashes are lost. At attacker who has stolen the password hashes can
simply login using the hashes.
However, I think there are acceptable solutions to both of those problems:
- The salt can be generated as hash(server_salt + user_name) - where
server_salt is a random number that is unique to the server, public, and
the same for all users. The resulting hash appears to have the required
properties of a salt. - The server should do a single, fast, hash operation on the hash it
receives. As an example: the server stores SHA-256(bcrypt(salt,
password)). The client sends bcrypt(password) then the server applies
SHA-256 and checks the hash. This does NOT allow an attacker to conduct
a fast offline brute force attack. They can do a fast brute force of
SHA-256(password) because password has a limited amount of entropy -
2^50 or 2^60 or so. But a 128-bit bcrypt(password) has entropy or 2^128,
so they cannot readily brute force it.
Now, perhaps this has already been thought of. Perhaps people are
actively using it (although I've never seen it). If so, apologies for
the line noise.
As some background on me, I was pushing JavaScript cryptography 15 years
back as a simple password defence for sites that do not use SSL
(http://pajhome.org.uk/crypt/md5/). This got a bit of a cult following,
but the world has moved on since then, and really any site with a login
should use SSL. But it seems a use for JavaScript password hashing has
returned! I knew it would all along :-)
Paul
--
Pentest - The Application Security Specialists
Paul Johnston - IT Security Consultant / Tiger SST
Office: +44 (0) 161 233 0100
Mobile: +44 (0) 7817 219 072
We're exhibiting at Infosecurity Europe!
Stand K97, Earl's Court London - 29th April - 1st May
Infosecurity Europe 2014
Email policy: http://www.pentest.co.uk/legal.shtml#emailpolicy
Registered Number: 4217114 England & Wales
Registered Office: 26a The Downs, Altrincham, Cheshire, WA14 2PU, UK
Accreditations: ISO 9001 (44/100/107029) / ISO 27001 (IS 558982) / Tiger
Scheme
Paul,
You are right on. bcrypt and the like are reasonable choices for low traffic websites, but can be abusive hits on CPU/L1/L2 caches and are problematic at scale. For bcrypt with work factor 10, it takes about 10 concurrent runs of bcrypt to pin a high performance CPU.
You have a few choices here.
-
Throw a lot of hardware at it. Lots. I've seen a few folks do this. It works but it's expensive.
-
Reduce the work factor and speed up the algorithm. Bad choice. It defeats the purpose of adaptive algorithms.
-
Use an HMAC, proper key storage and rotation, and cryptographic isolation of the HMAC process in a separate service or the like, so your main app server has no access to the HMAC private key.
Several folks critique these assertions. These ideas are backed by John Stevens extensive, nay, I dare say obsessive threat model on password storage. http://goo.gl/Spvzs
Until someone shows me something similar, I'm going with John's very detailed and well thought out advice.
Aloha,
Jim Manico
@Manicode
(808) 652-3805
On Jan 31, 2014, at 8:15 AM, Paul Johnston paul.johnston@pentest.co.uk wrote:
Hi,
When storing user's passwords that you need to verify against (but not use as plaintext) the current state of the art is:
- Hash the password
- Use a salt
- Use a slow hash function - bcrypt, scrypt, etc.
This provides the best possible protection against an attacker who has stolen the password database. It does not solve other issues like phishing, malware, password re-use, etc.
BUT there is one remaining problem: the slow hash function can allow a denial of service attack. A single request burns a lot of CPU. In practice I don't think this is a major problem, given defences like IP throttling. But it does deter people from using a higher work factor, to really get the benefit of slow hashing.
Given the improving performance of JavaScript in browsers, it may now make sense to do this in the browser. I'm assuming here that the site is using SSL, so the JavaScript is delivered securely. If you're not using SSL, then using a slow hash function is unlikely to be a priority for you. There is at least once JavaScript implementation of bcrypt (https://code.google.com/p/javascript-bcrypt/). But using this in a simple way would introduce two problems:
- The client needs to fetch the salt from the server. This introduces latency on login and, unless care is taken, can reveal whether a particular user account exists.
- If hashing is done purely on the client then the benefits of storing hashes are lost. At attacker who has stolen the password hashes can simply login using the hashes.
However, I think there are acceptable solutions to both of those problems:
- The salt can be generated as hash(server_salt + user_name) - where server_salt is a random number that is unique to the server, public, and the same for all users. The resulting hash appears to have the required properties of a salt.
- The server should do a single, fast, hash operation on the hash it receives. As an example: the server stores SHA-256(bcrypt(salt, password)). The client sends bcrypt(password) then the server applies SHA-256 and checks the hash. This does NOT allow an attacker to conduct a fast offline brute force attack. They can do a fast brute force of SHA-256(password) because password has a limited amount of entropy - 2^50 or 2^60 or so. But a 128-bit bcrypt(password) has entropy or 2^128, so they cannot readily brute force it.
Now, perhaps this has already been thought of. Perhaps people are actively using it (although I've never seen it). If so, apologies for the line noise.
As some background on me, I was pushing JavaScript cryptography 15 years back as a simple password defence for sites that do not use SSL (http://pajhome.org.uk/crypt/md5/). This got a bit of a cult following, but the world has moved on since then, and really any site with a login should use SSL. But it seems a use for JavaScript password hashing has returned! I knew it would all along :-)
Paul
--
Pentest - The Application Security Specialists
Paul Johnston - IT Security Consultant / Tiger SST
Office: +44 (0) 161 233 0100
Mobile: +44 (0) 7817 219 072
We're exhibiting at Infosecurity Europe!
Stand K97, Earl's Court London - 29th April - 1st May
Email policy: http://www.pentest.co.uk/legal.shtml#emailpolicy
Registered Number: 4217114 England & Wales
Registered Office: 26a The Downs, Altrincham, Cheshire, WA14 2PU, UK
Accreditations: ISO 9001 (44/100/107029) / ISO 27001 (IS 558982) / Tiger Scheme
The Web Security Mailing List
WebSecurity RSS Feed
http://www.webappsec.org/rss/websecurity.rss
Join WASC on LinkedIn http://www.linkedin.com/e/gis/83336/4B20E4374DBA
WASC on Twitter
http://twitter.com/wascupdates
websecurity@lists.webappsec.org
http://lists.webappsec.org/mailman/listinfo/websecurity_lists.webappsec.org
Hi Paul,
Hi All,
Another interesting and secure solution is adding a local parameter or
unreadable local parameter proposed by Solar Designer at
http://www.openwall.com/presentations/YaC2012-Password-Hashing-At-Scale/mgp00001.html
The main idea is using Hash (User_password+ salt+local_parameter),
where local parameter is the same for all users and stored on a
dedicated device (see slides 4 and 5).
By the way, mechanism hash(server_salt + user_name) has a weakness -
more right consruction is hash(user_name+server_salt).
Thanks.
Sincerely,
Denis Kolegov
@dnkolegov
Hi,
On 31/01/2014, at 13:15, Paul Johnston paul.johnston@pentest.co.uk wrote:
- Hash the password
- Use a salt
- Use a slow hash function - bcrypt, scrypt, etc.
This provides the best possible protection against an attacker who has stolen the password database. It does not solve other issues like phishing, malware, password re-use, etc.
I personally prefer the HMAC(secret, salt + password) approach. If an attacker finds a SQLi and gets the DB, he/she first needs to crack the secret (not really feasible today if you have a strong secret). If the site has a LFI then the strength of this approach kind of sucks, but it is the same as a normal hash+salt.
BUT there is one remaining problem: the slow hash function can allow a denial of service attack. A single request burns a lot of CPU. In practice I don't think this is a major problem, given defences like IP throttling. But it does deter people from using a higher work factor, to really get the benefit of slow hashing.
If you have throttling well implemented, taking into account different dimensions, then it looks a lot easier to DoS a site based on slow hash functions.
Given the improving performance of JavaScript in browsers, it may now make sense to do this in the browser. I'm assuming here that the site is using SSL, so the JavaScript is delivered securely. If you're not using SSL, then using a slow hash function is unlikely to be a priority for you. There is at least once JavaScript implementation of bcrypt (https://code.google.com/p/javascript-bcrypt/). But using this in a simple way would introduce two problems:
- The client needs to fetch the salt from the server. This introduces latency on login and, unless care is taken, can reveal whether a particular user account exists.
- If hashing is done purely on the client then the benefits of storing hashes are lost. At attacker who has stolen the password hashes can simply login using the hashes.
However, I think there are acceptable solutions to both of those problems:
- The salt can be generated as hash(server_salt + user_name) - where server_salt is a random number that is unique to the server, public, and the same for all users. The resulting hash appears to have the required properties of a salt.
- The server should do a single, fast, hash operation on the hash it receives. As an example: the server stores SHA-256(bcrypt(salt, password)). The client sends bcrypt(password) then the server applies SHA-256 and checks the hash. This does NOT allow an attacker to conduct a fast offline brute force attack. They can do a fast brute force of SHA-256(password) because password has a limited amount of entropy - 2^50 or 2^60 or so. But a 128-bit bcrypt(password) has entropy or 2^128, so they cannot readily brute force it.
Now, perhaps this has already been thought of. Perhaps people are actively using it (although I've never seen it). If so, apologies for the line noise.
As some background on me, I was pushing JavaScript cryptography 15 years back as a simple password defence for sites that do not use SSL (http://pajhome.org.uk/crypt/md5/). This got a bit of a cult following, but the world has moved on since then, and really any site with a login should use SSL. But it seems a use for JavaScript password hashing has returned! I knew it would all along :-)
The difference is that JS password hashing doesn't add any security per si, what makes the difference is SSL. :)
Paul
--
Pentest - The Application Security Specialists
Paul Johnston - IT Security Consultant / Tiger SST
Office: +44 (0) 161 233 0100
Mobile: +44 (0) 7817 219 072
We're exhibiting at Infosecurity Europe!
Stand K97, Earl's Court London - 29th April - 1st May
<ATT00001.html>
Email policy: http://www.pentest.co.uk/legal.shtml#emailpolicy
Registered Number: 4217114 England & Wales
Registered Office: 26a The Downs, Altrincham, Cheshire, WA14 2PU, UK
Accreditations: ISO 9001 (44/100/107029) / ISO 27001 (IS 558982) / Tiger Scheme
The Web Security Mailing List
WebSecurity RSS Feed
http://www.webappsec.org/rss/websecurity.rss
Join WASC on LinkedIn http://www.linkedin.com/e/gis/83336/4B20E4374DBA
WASC on Twitter
http://twitter.com/wascupdates
websecurity@lists.webappsec.org
http://lists.webappsec.org/mailman/listinfo/websecurity_lists.webappsec.org
Jim,
Stalwart AppSec educator—thanks for the nod. Paul,
Your problem characterization is thoughtful, considering different forms of attack and the various surfaces upon which they can occur. You’ve even re-considered the (informal) threat model applying your proposed control alternatives. Well-played. Since you’ve taken the problem one or two steps past where most have, it’s worth following up beyond what I’ve posted publicly.
[Adaptive One-way Functions]
I would not oppose an approach predicated solely on an adaptive one-way function. Research load characteristics and tune for effective results.
- Throw a lot of hardware at it. Lots.
You could throw iron at the problem (*1) using the standard adaptive one-way function formulations. Distributing the work from server to client is a natural response, yes, but not one I’ve seen in practice very often. You’re correct that doing so ‘inherits’ another problem: continued support for a user-specific salt (*2). You rightly indicate that it also inherits the problem of obscured credential replay by MitM.
In essence, this design leads down a slippery slope to a home-rolled challenges/response (C/R) protocol—something to be avoided. We see Existing C/R schemes, such as OAuth, protect plaintext credentials against MitM theft. Bearer tokens (application/end-point ‘passwords') used by these schemes can help designers limit the amount of CPU-intensive server-based credential verification. When designing systems, prefer these to home-rolled schemes; their limitations are well-understood (*3).
As a user, you’re probably familiar with organizations (like social media sites) that rely on PBKDF2 or bcrypt with high work factors to protect databased credentials but also use tokens to reduce the amount of bcrypt-driven password verification that occurs. If you’ve already forsaken OAuth, explore other fancy C/R protocols with Javascript support like SRP (*4).
[Keyed Macs]
- Use a [server-side] HMAC, … [and do it well]
I would suggest this approach and advise carefully solving knock-on problems.
As stated, I’m a fan of this approach, principally because it is both simple and because it forces the attacker into asymmetric (disadvantaged) warfare with the defender (*5). That is, the defender is subject to only nominal password verification effort whereas the attacker must pay to brute force (or steal) the secret key prior to enjoying the same ease of verification.
As Jim hedged, one inherits the ‘key protection’ problem with this scheme. Detractors rightly indicate organizations can easily screw key protection up. Within my own experience, it’s been easy to design solutions because the organizations with which I work enjoy benefits like a) separate of duties involved in generating, handling, and using key material, b) reasonable application server configuration, and c) broadly deployed HSM support. Though, even without fancy hardware, organizations often have existing regimes for production secret protection.
[Paul’s Proposed Design]
Paul, the approach you proposed (*6), as I understand it, may be represented as follows:
(0) Client C: uname —> Server S
(1) S: SHA2(server_salt + uname) —> C
(2) C: bcrypt(salt, pw) —> S
(3) S: verify(SHA2(<bcrypt result>))
My “brief” analysis of this approach places it (surprisingly?) in an equivalence class with bcrypt itself, once known to an attacker. For those interested in why, contact me offline.
This scheme does provide some additional protections to credentials in flight (during step (2)). if designers desire this effect, I’d recommend revisiting the C/R section and selecting from that family of approach.
-jOHN
John Steven
iCTO, Cigital
+1,703-727-4034 | @M1splacedsoul
https://google.com/+JohnStevenCigital
-
(2) - Some ascribe anti-reversing properties to salts beyond obscuring duplicate plaintext and raising space/time difficulty on targeted individual attack. This results in complaint about salts made public.
-
(3) - http://hueniverse.com/2012/07/oauth-2-0-and-the-road-to-hell/
-
(5) - http://goo.gl/Spvzs
-
(6) - Quoted from Paul’s mail:
- The salt can be generated as hash(server_salt + user_name) - where server_salt is a random number that is unique to the server, public, and the same for all users. The resulting hash appears to have the required properties of a salt.
- The server should do a single, fast, hash operation on the hash it receives. As an example: the server stores SHA-256(bcrypt(salt, password)). The client sends bcrypt(password) then the server applies SHA-256 and checks the hash.
- ():
John Stevens
...John Steven’s...
Jim,
Stalwart AppSec educator—thanks for the nod. Paul,
Your problem characterization is thoughtful, considering different forms of attack and the various surfaces upon which they can occur. You’ve even re-considered the (informal) threat model applying your proposed control alternatives. Well-played. Since you’ve taken the problem one or two steps past where most have, it’s worth following up beyond what I’ve posted publicly.
[Adaptive One-way Functions]
I would not oppose an approach predicated solely on an adaptive one-way function. Research load characteristics and tune for effective results.
- Throw a lot of hardware at it. Lots.
You could throw iron at the problem (*1) using the standard adaptive one-way function formulations. Distributing the work from server to client is a natural response, yes, but not one I’ve seen in practice very often. You’re correct that doing so ‘inherits’ another problem: continued support for a user-specific salt (*2). You rightly indicate that it also inherits the problem of obscured credential replay by MitM.
In essence, this design leads down a slippery slope to a home-rolled challenges/response (C/R) protocol—something to be avoided. We see Existing C/R schemes, such as OAuth, protect plaintext credentials against MitM theft. Bearer tokens (application/end-point ‘passwords') used by these schemes can help designers limit the amount of CPU-intensive server-based credential verification. When designing systems, prefer these to home-rolled schemes; their limitations are well-understood (*3).
As a user, you’re probably familiar with organizations (like social media sites) that rely on PBKDF2 or bcrypt with high work factors to protect databased credentials but also use tokens to reduce the amount of bcrypt-driven password verification that occurs. If you’ve already forsaken OAuth, explore other fancy C/R protocols with Javascript support like SRP (*4).
[Keyed Macs]
- Use a [server-side] HMAC, … [and do it well]
I would suggest this approach and advise carefully solving knock-on problems.
As stated, I’m a fan of this approach, principally because it is both simple and because it forces the attacker into asymmetric (disadvantaged) warfare with the defender (*5). That is, the defender is subject to only nominal password verification effort whereas the attacker must pay to brute force (or steal) the secret key prior to enjoying the same ease of verification.
As Jim hedged, one inherits the ‘key protection’ problem with this scheme. Detractors rightly indicate organizations can easily screw key protection up. Within my own experience, it’s been easy to design solutions because the organizations with which I work enjoy benefits like a) separate of duties involved in generating, handling, and using key material, b) reasonable application server configuration, and c) broadly deployed HSM support. Though, even without fancy hardware, organizations often have existing regimes for production secret protection.
[Paul’s Proposed Design]
Paul, the approach you proposed (*6), as I understand it, may be represented as follows:
(0) Client C: uname —> Server S
(1) S: SHA2(server_salt + uname) —> C
(2) C: bcrypt(salt, pw) —> S
(3) S: verify(SHA2(<bcrypt result>))
My “brief” analysis of this approach places it (surprisingly?) in an equivalence class with bcrypt itself, once known to an attacker. For those interested in why, contact me offline.
This scheme does provide some additional protections to credentials in flight (during step (2)). if designers desire this effect, I’d recommend revisiting the C/R section and selecting from that family of approach.
-jOHN
John Steven
iCTO, Cigital
+1,703-727-4034 | @M1splacedsoul
https://google.com/+JohnStevenCigital
-
(2) - Some ascribe anti-reversing properties to salts beyond obscuring duplicate plaintext and raising space/time difficulty on targeted individual attack. This results in complaint about salts made public.
-
(3) - http://hueniverse.com/2012/07/oauth-2-0-and-the-road-to-hell/
-
(5) - http://goo.gl/Spvzs
-
(6) - Quoted from Paul’s mail:
- The salt can be generated as hash(server_salt + user_name) - where server_salt is a random number that is unique to the server, public, and the same for all users. The resulting hash appears to have the required properties of a salt.
- The server should do a single, fast, hash operation on the hash it receives. As an example: the server stores SHA-256(bcrypt(salt, password)). The client sends bcrypt(password) then the server applies SHA-256 and checks the hash.
- ():
John Stevens
...John Steven’s...