5 ms·

Password hashing functions are very useful, but can cause operational issues. A common advice is to allocate as much memory as possible, and as much CPU as pos

Password hashing functions are very useful, but can cause operational issues. A common advice is to allocate as much memory as possible, and as much CPU as possible, to make bruteforce attacks as long as possible. Unfortunately, it only makes sense if a each user is assigned a dedicated server. Which is almost never the case in APIs and web applications. Doing all the stretching work on a server scales poorly. And predicting how many users will try to log in is impossible, unless you set up drastic limits. One way or the other, this makes the whole service vulnerable to very cheap denial of service attacks. There are a lot of discussions about password hashing functions and their parameters, but almost none about server relief, which is far more important IMHO. The idea is to delegate most of the work to the client. The server just provides the salt. It's acceptable to use as much resources as possible for a short time on the client, since it's unlikely to do anything else important at the same time. The stretched password is sent to the server instead of the actual password, so that it's acceptable for the server to keep the stretching work down to a minimum before storing the password. This also has the advantage that the server doesn't see the actual password. This solves scalability issues, and drastically reduces to ability to perform cheap resources exhaustion attacks on the servers. In a webapp, this can be efficiently achieved using WebAssembly, or with WebCrypto's PBKDF2 implementation. Obviously not an issue in native apps either. Legacy protocols such as FTP and IMAP don't have that luxury, though. There's no way to run a password stretching function on the client. So, while it's nice to see software like Dovecot adopt functions like Argon2 to store passwords, this can actually do more harm than good. Finally, while password hashing functions are typically described as suitable for storing passwords, they have other usages as well. Password-authenticated key exchange mechanisms such as SPAKE2 don't get the attention they deserve. They can be extremely useful to add a strong security layer on top of another authentication mechanism, using a simple password. And they also usually leverage password stretching functions.

ricardobeat 9y ago
Doesn't sending the salt to the client void a whole layer of security?
- eropple 9y ago
  I don't see how that'd be the case. An attacker who has visibility into the client that has the salt can already see the plaintext password. And an attacker on the service side of things can see the salt anyway, it's in the database.
  - jedisct1 9y ago
    An attacker that would have the ability to impersonate the server could precompute a rainbow table for a given salt, and send that salt to the client. OTOH, without client-side prehashing, an attacker that has the ability to impersonate the server doesn't have to precompute anything in order to collect all passwords.
    - Franciscouzo 9y ago
      If an attacker is able to impersonate the server, then it is also able to ask the client for the password by modifying the Javascript sent.
      - jedisct1 9y ago
        All clients are not web browsers, but sure.
  - Buge 9y ago
    >An attacker who has visibility into the client that has the salt can already see the plaintext password. There is no way for the server to distinguish a legitimate user trying to login from an attacker trying to hack someone. So if the salt is sent to a legitimate client, the salt will also be sent to attackers. I'm not sure if sending the salt to attackers is really a vulnerability though.
- jedisct1 9y ago
  Certainly not, especially if it is sent over an authenticated channel.
eropple 9y ago
> Doing all the stretching work on a server scales poorly. And predicting how many users will try to log in is impossible, unless you set up drastic limits. One way or the other, this makes the whole service vulnerable to very cheap denial of service attacks. Can you point to an example of a (nontrivial) site where a DoS attack against the password hashing service was the primary point of failure? I'm sure it's happened, but it strikes me that most systems will go down hardest and first from pressure on other parts of that system. > This also has the advantage that the server doesn't see the actual password. This is the more compelling thing, to me, about this approach. Doesn't play super nicely with the established API tooling out there, but it's something to consider.
- jedisct1 9y ago
  > Can you point to an example of a (nontrivial) site where a DoS attack against the password hashing service was the primary point of failure? Reformulating the question from a different angle: why did all the large sites whose password database got leaked (Yahoo, LinkedIn...) still use regular hash functions? > This also has the advantage that the server doesn't see the actual password. Other schemes with that property include augmented PAKEs such as SPAKE2+ (example implementation: https://github.com/jedisct1/spake2-ee https://github.com/jedisct1/spake2-ee) and Tabby PAKE (https://github.com/catid/tabby/blob/master/PASSWORD.md https://github.com/catid/tabby/blob/master/PASSWORD.md)
  - tjoff 9y ago
    > Reformulating the question from a different angle: why did all the large sites whose password database got leaked (Yahoo, LinkedIn...) still use regular hash functions? Incompetence.
  - eropple 9y ago
    > why did all the large sites whose password database got leaked (Yahoo, LinkedIn...) still use regular hash functions? Inertia? Stuff I built in 2001 probably still uses MD5+salt today because nobody's maintained it in over a decade. Fear of breakage? Going down because of an "unnecessary" change probably reads worse to management than getting owned does (before it happens)--and besides, it's not our data, just users. I dunno, man. Obviously I have a ton of respect for your crypto work (I mean that, seriously, thank you). Your other points make total sense, this one just feels like overreach > Other schemes with that property Well outside my weight class, but you've given me some stuff to read about. No idea how it ends up integrating with existing API tooling, but worth examining for sure.
jameskegel 9y ago
These types of memory hard operations also have other popular uses; Keccak and other modern variants like Wild Keccak in proof of work operations which favor consumer hardware for example.
- dchest 9y ago
  Keccak is certainly not optimized for current consumer hardware, it's much faster in hardware implementations, and none of the currently available consumer hardware contains one (which means that when using it as proof-of-work or password hash it benefits miners/attackers with ASICs). Also, Keccak is not memory-hard. "Wild Keccak" is not a "modern variant of Keccak". I'm not familiar with it, but it looks like an attempt to build a PoW scheme with ROM/RAM hardness using Keccak permutation.
xnyhps 9y ago
> Legacy protocols such as FTP and IMAP don't have that luxury, though. There's no way to run a password stretching function on the client. IMAP uses SASL, which can do client-side stretching by using SCRAM-SHA-1. I don't know how common they are, but there must be some servers and clients that support it. Downside is that upgrading the mechanism becomes hard, and it's difficult to integrate it with an existing user database with hashed passwords.
tuxxy 9y ago
Building such schemes just widens your attack surface by a margin of 10. There's a reason we have stuck with server side hashing.
tptacek 9y ago
Server relief is an old idea that hasn't been widely deployed for, I think, good reason. It's something that makes sense to deploy in a new design, where you control the protocol, the client, and the server. It makes less sense as something to retrofit into a web application. DoS sttacks on slow password hashes are a phenomenon more heard about than ever seen. Concern about them was raised back in the "salted hash" days, when people resisted deploying bcrypt in favor of "secret salts". In the 10 years since, virtually every major site has switched to some kind of stretched password hash. Many of these companies are (or were) clients. The number of in-reality DoS attacks against password hashes I've heard attributed to these companies: 0. My guess at why: it's trivial to DoS a typical SaaS application anyways, applications don't run hashes on nonexistent accounts, and have to lock out repeated login attempts on existing accounts for other reasons anyways. Which means, unlike every other vector for application-level DoS, to conduct this attack you need a continuous supply of fresh valid accounts on a continuous supply of untainted IP addresses. Why bother? There's almost certainly a preauth endpoint somewhere that accomplishes the same thing anonymously. You observe that the server doesn't have to see the password in server-relieved schemes. This is true, in the limited sense that there's no point that the server is required to have the plaintext password resident in memory. But there's two caveats to that benefit: first, that's not how passwords are generally taken from compromised applications (what really happens is that the database of password authenticators is stolen, and that remains the case in server relief designs), second, the assurance that passwords will never appear in server memory vanishes when you stipulate that server relief is implemented in content-controlled code, which can simply arrange to have the password sent on the attacker's behalf. Of course, the content-controlled language we're talking about here (Javascript) is the classic objection to server-relief, and it's worth recalling the reason why: not that browser Javascript is bad for implementing crypto (though: it is), but that it's the slowest of all the computing parties involved in an attack on passwords. By running adaptive hashes clientside, you reduce the security of those hashes to the lowest common denominator of the servers, attackers, and clients --- in most applications, you'll have to reduce it to the strength of outdated smartphone Javascript. In serious designs, there are already good reasons to isolate authentication into its own service. More large applications should design and implement auth services, and more and more are. Once you've factored auth out of your monolith app server, it's much easier to scale password hash compute, and do it in ways that allow service providers to take advantage of resources that clients don't have. Again: I think server relief makes sense in new designs, just like I think PAKEs do. But people read comment threads like these and get it into their head that they should get a PAKE set up for their Django application. That's a terrible idea. I think I'm on pretty good footing, cryptographically speaking, with everything I've written to this point. This last point I'll make, I acknowledge I sound (to everyone) like a crank. But here goes: This is my problem with the Password Hashing Competition. In reality, bcrypt turned out to be a uniquely strong, well-designed password hash for the purposes it was most typically being applied for (SaaS app login). For every other application --- particularly general-purpose KDFs --- scrypt got you to something like 99.9% of the optimal outcome. But then, for reasons I don't fully comprehend, we had a giant contest to determine "the best password hash" (the one Argon2 won). The world wasn't asking for it, nothing was really threatening the mainstream password hashes we had before... and now we have a "new" king of password hashes that for most purposes is not materially better than scrypt, and a whole lot of new mechanism being proposed to find reasons to deploy it. Generally the point I would want to make is that on mainstream platforms, like Django and Rails, the platform defaults are pretty good, and probably all you'll need for the whole lifespan of your application. If you don't know what you're doing, and are mostly going off comments on Reddit and HN, it is possible to do more harm than good by departing from those defaults.

ricardobeat 9y ago

Doesn't sending the salt to the client void a whole layer of security?

eropple 9y ago
I don't see how that'd be the case. An attacker who has visibility into the client that has the salt can already see the plaintext password. And an attacker on the service side of things can see the salt anyway, it's in the database.
- jedisct1 9y ago
  An attacker that would have the ability to impersonate the server could precompute a rainbow table for a given salt, and send that salt to the client. OTOH, without client-side prehashing, an attacker that has the ability to impersonate the server doesn't have to precompute anything in order to collect all passwords.
  - Franciscouzo 9y ago
    If an attacker is able to impersonate the server, then it is also able to ask the client for the password by modifying the Javascript sent.
    - jedisct1 9y ago
      All clients are not web browsers, but sure.
- Buge 9y ago
  >An attacker who has visibility into the client that has the salt can already see the plaintext password. There is no way for the server to distinguish a legitimate user trying to login from an attacker trying to hack someone. So if the salt is sent to a legitimate client, the salt will also be sent to attackers. I'm not sure if sending the salt to attackers is really a vulnerability though.
jedisct1 9y ago
Certainly not, especially if it is sent over an authenticated channel.

eropple 9y ago

> Doing all the stretching work on a server scales poorly. And predicting how many users will try to log in is impossible, unless you set up drastic limits. One way or the other, this makes the whole service vulnerable to very cheap denial of service attacks. Can you point to an example of a (nontrivial) site where a DoS attack against the password hashing service was the primary point of failure? I'm sure it's happened, but it strikes me that most systems will go down hardest and first from pressure on other parts of that system. > This also has the advantage that the server doesn't see the actual password. This is the more compelling thing, to me, about this approach. Doesn't play super nicely with the established API tooling out there, but it's something to consider.

jedisct1 9y ago
> Can you point to an example of a (nontrivial) site where a DoS attack against the password hashing service was the primary point of failure? Reformulating the question from a different angle: why did all the large sites whose password database got leaked (Yahoo, LinkedIn...) still use regular hash functions? > This also has the advantage that the server doesn't see the actual password. Other schemes with that property include augmented PAKEs such as SPAKE2+ (example implementation: https://github.com/jedisct1/spake2-ee https://github.com/jedisct1/spake2-ee) and Tabby PAKE (https://github.com/catid/tabby/blob/master/PASSWORD.md https://github.com/catid/tabby/blob/master/PASSWORD.md)
- tjoff 9y ago
  > Reformulating the question from a different angle: why did all the large sites whose password database got leaked (Yahoo, LinkedIn...) still use regular hash functions? Incompetence.
- eropple 9y ago
  > why did all the large sites whose password database got leaked (Yahoo, LinkedIn...) still use regular hash functions? Inertia? Stuff I built in 2001 probably still uses MD5+salt today because nobody's maintained it in over a decade. Fear of breakage? Going down because of an "unnecessary" change probably reads worse to management than getting owned does (before it happens)--and besides, it's not our data, just users. I dunno, man. Obviously I have a ton of respect for your crypto work (I mean that, seriously, thank you). Your other points make total sense, this one just feels like overreach > Other schemes with that property Well outside my weight class, but you've given me some stuff to read about. No idea how it ends up integrating with existing API tooling, but worth examining for sure.

jameskegel 9y ago

These types of memory hard operations also have other popular uses; Keccak and other modern variants like Wild Keccak in proof of work operations which favor consumer hardware for example.

dchest 9y ago
Keccak is certainly not optimized for current consumer hardware, it's much faster in hardware implementations, and none of the currently available consumer hardware contains one (which means that when using it as proof-of-work or password hash it benefits miners/attackers with ASICs). Also, Keccak is not memory-hard. "Wild Keccak" is not a "modern variant of Keccak". I'm not familiar with it, but it looks like an attempt to build a PoW scheme with ROM/RAM hardness using Keccak permutation.

xnyhps 9y ago

> Legacy protocols such as FTP and IMAP don't have that luxury, though. There's no way to run a password stretching function on the client. IMAP uses SASL, which can do client-side stretching by using SCRAM-SHA-1. I don't know how common they are, but there must be some servers and clients that support it. Downside is that upgrading the mechanism becomes hard, and it's difficult to integrate it with an existing user database with hashed passwords.

tuxxy 9y ago

Building such schemes just widens your attack surface by a margin of 10. There's a reason we have stuck with server side hashing.

tptacek 9y ago

Server relief is an old idea that hasn't been widely deployed for, I think, good reason. It's something that makes sense to deploy in a new design, where you control the protocol, the client, and the server. It makes less sense as something to retrofit into a web application. DoS sttacks on slow password hashes are a phenomenon more heard about than ever seen. Concern about them was raised back in the "salted hash" days, when people resisted deploying bcrypt in favor of "secret salts". In the 10 years since, virtually every major site has switched to some kind of stretched password hash. Many of these companies are (or were) clients. The number of in-reality DoS attacks against password hashes I've heard attributed to these companies: 0. My guess at why: it's trivial to DoS a typical SaaS application anyways, applications don't run hashes on nonexistent accounts, and have to lock out repeated login attempts on existing accounts for other reasons anyways. Which means, unlike every other vector for application-level DoS, to conduct this attack you need a continuous supply of fresh valid accounts on a continuous supply of untainted IP addresses. Why bother? There's almost certainly a preauth endpoint somewhere that accomplishes the same thing anonymously. You observe that the server doesn't have to see the password in server-relieved schemes. This is true, in the limited sense that there's no point that the server is required to have the plaintext password resident in memory. But there's two caveats to that benefit: first, that's not how passwords are generally taken from compromised applications (what really happens is that the database of password authenticators is stolen, and that remains the case in server relief designs), second, the assurance that passwords will never appear in server memory vanishes when you stipulate that server relief is implemented in content-controlled code, which can simply arrange to have the password sent on the attacker's behalf. Of course, the content-controlled language we're talking about here (Javascript) is the classic objection to server-relief, and it's worth recalling the reason why: not that browser Javascript is bad for implementing crypto (though: it is), but that it's the slowest of all the computing parties involved in an attack on passwords. By running adaptive hashes clientside, you reduce the security of those hashes to the lowest common denominator of the servers, attackers, and clients --- in most applications, you'll have to reduce it to the strength of outdated smartphone Javascript. In serious designs, there are already good reasons to isolate authentication into its own service. More large applications should design and implement auth services, and more and more are. Once you've factored auth out of your monolith app server, it's much easier to scale password hash compute, and do it in ways that allow service providers to take advantage of resources that clients don't have. Again: I think server relief makes sense in new designs, just like I think PAKEs do. But people read comment threads like these and get it into their head that they should get a PAKE set up for their Django application. That's a terrible idea. I think I'm on pretty good footing, cryptographically speaking, with everything I've written to this point. This last point I'll make, I acknowledge I sound (to everyone) like a crank. But here goes: This is my problem with the Password Hashing Competition. In reality, bcrypt turned out to be a uniquely strong, well-designed password hash for the purposes it was most typically being applied for (SaaS app login). For every other application --- particularly general-purpose KDFs --- scrypt got you to something like 99.9% of the optimal outcome. But then, for reasons I don't fully comprehend, we had a giant contest to determine "the best password hash" (the one Argon2 won). The world wasn't asking for it, nothing was really threatening the mainstream password hashes we had before... and now we have a "new" king of password hashes that for most purposes is not materially better than scrypt, and a whole lot of new mechanism being proposed to find reasons to deploy it. Generally the point I would want to make is that on mainstream platforms, like Django and Rails, the platform defaults are pretty good, and probably all you'll need for the whole lifespan of your application. If you don't know what you're doing, and are mostly going off comments on Reddit and HN, it is possible to do more harm than good by departing from those defaults.