It's easy to say "use bcrypt" or "use scrypt," but I think it's important to acknowledge the challenges of deploying those functions in large scale high performance environments.
It's straightforward and effective when password hashing happens client-side (like local encryption for a bitcoin wallet), but using scrypt or bcrypt server-side at effective difficulty levels will either destroy your L1/L2 cache or exceed your CPU budget.
In practice, from what I've seen, this means scrypt is never used, and bcrypt is used with a work factor that's tuned low. I think this is just a fundamental asymmetry, and that at the end of the day people use bcrypt so that they can say "we used bcrypt!" and get a nod when their entire user database is compromised, even though it provides very little value the way it's deployed.
Actually the Password Hashing Competition has shown this asymmetry can be exploited to the server's advantage: one of the ideas being studied is called server relief.
For example instead of storing the scrypt hash on the server you store the SHA256 hash of the scrypt hash (and the salt alongside), and ask the client to send the scrypt hash to authenticate. This way the per authentication cost to the client is expensive (one scrypt hash) but the cost to the server is cheap (only one SHA256 hash).
Attackers cannot take shortcuts. They cannot send random scrypt hashes to the server while skipping the scrypt computation step, because the space of possible scrypt hashes is just too large to brute force.
The only downside of server relief is that you need custom code on the client-side to do the computation. So it works with javascript in browsers, but not with traditional clients like an IMAP or POP3 mail app.
Edit: @__david__: yes you could SHA256() only the hash part of the scrypt hash, as opposed to the hash & salt parts. It is an implementation detail --not really important. And regardless of how you do it, if the DB get stolen the SHA256 hashes are useless to authenticate.
Edit: @espadrine: no, breaking a SHA256(scrypt()) hash is no easier than breaking a scrypt() hash. Server relief with SHA256 introduces no weaknesses. It is strictly more secure than standard scrypt hashes.
Edit: @plantbased: I recommend against MD5(scrypt()), because it is likely preimage attacks will be found on MD5 in the near future, so someone stealing your database of MD5(scrypt()) hashes will be capable of computing an arbitrary scrypt hash that authenticates to a given user. But you could certainly do MD5-crypt(scrypt()) with MD5-crypt being the salted & iterated version by PHK.
I see, so basically it's like forcing users to make long, un-dictionary-attackable passwords, without requiring users to remember long, un-dictionary-attackable passwords.
I like that idea. But why do you store the salted SHA256 of the scrypt hash and not the scrypt hash directly?
Edit: Thinking about it more, I'm guessing it is for the case where your DB gets stolen. With the salted hashes, attackers can't just send the direct scrypt hash down to the server to get authenticated.
Correct. If you store the scrypt hash directly, it effectively becomes a plaintext password and a compromise of your database lets the attacker login to any account.
The whole idea of salts is to prevent rainbow table attacks i.e. you can't use precomputed hashes.
In this case you'd need to precompute an SHA256 of a dictionary of scrypt hashes which would have been computed from a dictionary of english words.
In practical terms, if you steal the DB and wanted to reverse passwords, you'd need to scrypt lets say 100 million words, then SHA256 them, then compare them to what's in the DB.
The original blog entry argues (or maybe it was the post on the same site that linked to) that we should use more compute intensive hashing algorithms, rather than relying on salts. scrypt is definitely more compute intensive.
So if you didn't use a salt and wanted to throw a 100M word dict at this, how long would that take on decent hardware to create the rainbow table of 100M words which could be used repeatedly against stolen dictionaries? On a decent GPU you can do around 1.2 billion SHA256 hashes per second. So the SHA256 step is trivial.
So you could create your rainbow table to attack the non-salted version of this in around 25 seconds.
A salted version of this same system would need the scrypt to be salted because SHA256 is so fast. If you just salted the SHA256 you'd be able to use a precomputed scrypt rainbow table and then you only have to compute the salted SHA256's which as you can tell from my benchmark above is very fast.
So clearly the salt is needed and you need to compute scrypt(salt + password) -->> send to server and then SHA256(scryptHash). Note that you don't need to add the salt on the SHA256 side because you've already defeated a rainbow table attack by your initial salting.
So how fast could you attack a salted system like this using GPU's for your SHA256 and ASICS for your scrypt based on the benchmarks above?
You can pretty much ignore the SHA256 step because it's so fast, so you'd get around 4.5 million guesses per second using ASICS doing scrypt.
Compared to 1.2 billion guesses using a GPU for SHA256, that's not too bad.
Cryptocurrency mining ASICs cannot be used for password cracking because they are not designed to hash arbitrary strings, and do not support arbitrary scrypt parameterization. They are designed to take in a block template of some sort, and then internally handle iterating the nonce to minimize load on the communication bus and the host processor.
An interesting thing about GPU password cracking that many people don't realize is that the GPU is responsible for not only hashing candidate passwords, but also generating those candidate passwords. The bus bandwidth isn't enough and the CPU isn't fast enough to keep it fed with candidate passwords otherwise.
You could, of course, build password cracking ASICs that have internal processors for generating candidate passwords, but I'm not convinced that it doesn't make more sense to stick with GPUs or maybe FPGAs there.
You'd be better off with FPGA which are available in significantly smaller process sizes (and therefor lower running costs) than ASICs you roll yourself. There's also a certain level of reusability that you don't get with SHA256 etched into silicon.
Not true re GPU bandwidth/dictionaries. see cudahashcat - we're using it on a switched PCIe bus feeding dictionaries with plenty of bandwidth. You're not limited to mask attacks, which is what you're describing.
Are you sure about that? I'm more familiar with oclhashcat, and it certainly can't keep the GPU busy with a pure dictionary attack. It'll feed the GPU with a dictionary, then apply rules on GPU to generate variants.
The problem with the approach you mention is that clientside bugs can evilly break things. If the clientside code silently gives wrong results, not only will you not know, but, assuming they run it from the start (i.e. when they register), it will actually "work" - until the client moves to another machine or updates. That's not a good situation.
You may be able to detect this with testing, but not necessarily. And yes, it'll probably happen sooner or later, given the nature of JS compilers.
I don't know if there's a method that avoids this problem that still has the advantages that you mention.
This is brilliant. But since we are often told that composing cryptographic promitives can turn out to be unexpectedly dangerous, can you point me to some articles where this technique is studied in more detail? Preferably by experts such as yourself.
mrb, this is awesome, thanks for sharing. Can you comment on storing the scrypt as an md5 hash and how that would impact security? [Asking because I'm confined to server side systems that only support md5]
IMHO While MD5 has a fraction of the keyspace of SHA2, it's still a very hard problem to reverse it and intuitively it seems this might provide a huge improvement over salted and stretched (multiple rounds) of md5 on the server.
> The only downside of server relief is that you need custom code on the client-side
That, and the major reason we do hashes even over TLS: if the server gets cracked and the attacker has access to the stored hashes, breaking a SHA256 is trivial (ie, brute-forcing b when knowing s = SHA256(b)). Then, the attacker can assume the identity of any individual whose SHA256 s got broken, by sending the bcrypt b directly from a crafted client, without having to find p where b = bcrypt(p).
People have odd ideas about how serious the vulnerabilities in hashes are. These hashes, even old and obsolete ones, are still entirely secure for password like hashing if the password is random enough, which scrypt output is.
Even MD5 is still (AFAIK) effectively unbreakable in this use case (finding md5 collisions is possible, finding the input given an md5 is not). According to http://en.wikipedia.org/wiki/MD5#Preimage_vulnerability finding input to generate a given md5 has a complexity of 2^123.4 - i.e. never going to happen. And that's Md5, an obsolete hash!
Sha1, also considered obsolete, has a bad rep because there are scary theoretical collision attacks. This isn't good news, certainly, but for a sense of perspective: nobody, not even with lots of distributed computing power, has ever actually managed to find a collision since that would take around 2^60 attempts. I don't think anyone has ever found even a theoretical weakness in its preimage resistance.
And you're talking about sha2 - there have been no published reports on any attacks, even theoretical, on the full sha2 (they have found weaknesses on reduced versions, suggesting room for improvement - but that's largely of academic interest).
Collision attacks are another matter. If you're using a hash to sign potentially hostile content rather than recognize friendly content, md5 is clearly dangerous, and sha1 may well become so. But that's relevant to things like certificate authorities, not message authentication.
Yeah - brute forcing is really only a relevant attack if the number of possibilities is fairly limited (even with a really fast hash). Scrypt output is likely to be effectively random (if salted) - and without salt, you'd need to build an expensive (but potentially feasible) rainbow table of possible scrypt output.
> you'd need to build an expensive (but potentially feasible) rainbow table of possible scrypt output
I don't think that's feasible. "Expensive" is an understatement. To compute the rainbow table you need to do the work of actually calculating the scrypt output for each password, even though you don't have to store it. The space is just too big, therefore the time cost.
It's a question of size - clearly a rainbow table of 1 is feasible. I'm guessing a rainbow table of a million won't be too expensive either, and with a million common passwords, you'd likely crack something.
But yeah, it's not likely to be a major threat. In any case, salting makes it irrelevant.
Good point - it is implemented with a salt! However, the way that's done depends on the implemetation. The underlying KDF doesn't require nor generate a salt, so if you're implementing it client side, you'd need to ensure salting works.
Re-read that comment, particularly the part about the difference between a collision attack and a preimage attack.
MD5 is (currently) vulnerable to collisions, but not to preimages. So you can find two inputs that have the same hash, but not an input that hashes to some particular value in a database.
@teraflop - Oh, so does that just mean basically that you can, e.g. generate a bunch of MD5 hashes and some will be the same? But if you have a target you're basically SOL finding a collision for that? That would make sense if that's what it means.
More specifically: if you just hash a bunch of arbitrary strings that aren't specially-constructed for the purpose of colliding, then collisions are basically random, and extremely improbable. But you can fairly easily generate two files, differing only in a small number of bits, with the same MD5 hash by taking advantage of the structure of the algorithm.
Another consequence of that is that even MD5 collisions aren't at all trivial to exploit in general. An attacker can create a collision, but it's a slow process, and the colliding content is pretty constrained. You'd probably need to be very well informed, and invest quite some creativity to find two messages that are "valid" to whatever system is processing those and have sufficiently different meanings to be useful to you.
Clearly doable in specific instances, but it's not going to be an addition to the script-kiddie attack handbook anytime soon.
well breaking SHA256 by brute force is only trivial when your input space is small. presumably scrypt has 256 bit output so bruteforcing to find the scrypt output would be difficult.
1. Empirically: most of the applications I reviewed that used bcrypt simply used the defaults.
2. Even with a lower work factor, bcrypt is drastically better than salted SHA.
3. Companies with auth loads so high that they really need to tune bcrypt should also be using dedicated auth servers, which (a) improve security in other ways and (b) allow for a lot of flexibility in handling work factors.
> 1. Empirically: most of the applications I reviewed that used bcrypt simply used the defaults.
Isn't that a security risk of it's own though? Wouldn't creating a rainbow table for (non-salted) passwords hashed with the default bcrypt settings then make sense again?
Because bcrypt automatically generates and adds a salt every time it's invoked. Every bcrypt hash has a different salt. Hashing the same plaintext ten times will produce ten different hashes.
One of the things that make these password hashing threads astonishingly tedious is that somebody who has never so much as googled "bcrypt" always chimes in with "but what about the rainbow tables???".
As far as I'm concerned bcrypt took the term for a concept that is generally understood to be deterministic (hashing) and redefined it by adding the randomness in by default.
That was probably a better call than trying to introduce a new term and a new hashing algorithm at the same time; but it's also asking for the exact long-term confusion you're complaining about here.
That XKCD doesn't really apply here since you could have easily asked for an explanation without the snark in the first place. There's also a difference between making fun of someone for not knowing something and choosing not to engage with them.
> That was probably a better call than trying to introduce a new term and a new hashing algorithm at the same time; but it's also asking for the exact long-term confusion you're complaining about here
To be fair, besides a basic search for information on the subject, this was also covered in the linked article...
What term? The paper that introduced bcrypt was titled "A Future-Adaptable Password Scheme". The first result, Wikipedia, calls it "a key derivation function for passwords".
The purpose of a password hash is to protect the password authenticators in the event the database is compromised. If you define away the possibility of a database compromise, just store them in plaintext.
I'm not trying to define away the possibility of a database compromise, I'm integrating a secure element into the hashing scheme that can compute an HMAC without exposing its key.
You're right, authentication rates are low. But Moxies point of concern with regard to requiring a heavier CPU and memory commitment on the server is still valid, particularly when faced with malicious traffic.
You need to make sure your login system can handle malicious clients, brute-force attempts from individual IPs, or against particular accounts, dropping back to CAPCTHAs or some other means of resource control when things look bad. This isn't a particularly easy problem to solve, and if you do it incorrectly you open yourself and your users up to a denial-of-service.
IMHO, some of the new fancy password-based authentication protocols, like AugPAKE, which do hashing client-side, might ease this problem... but they're still stateful (SYN floods anyone?) and therefore still depend upon good DoS protection.
> Moxies point of concern with regard to requiring a heavier CPU and memory commitment on the server is still valid, particularly when faced with malicious traffic.h
How about this: Save two hashes, one low cost, one high cost--both must pass for login. Don't run the high cost unless the low cost one works first.
Note: not a security guy, so I'm probably overlooking something silly.
Edit: the two responses below (thus far) are reasons you should not do this. Duh on my part.
If you have a high cost and low cost hash, someone getting the password database can just crack against the low cost hash. Even if the low cost hash is short so that it frequently returns a false okay (say a nice round number like 1/256 FP rate), you're still reducing the amount of "hard" hashes the attacker has to computer by a factor of that false positive rate.
You can, however, do the high-cost hash on the client, then do a low-cost hash comparison of the result on the server.
So you do a cheap SHA256 hash comparison on the server, but because the input to that comes out of, say scrypt, it has 256 bits of entropy (or near), making cracking infeasible. (scrypt has variable length output, so you could use other hash sizes).
This is only done when checking; when setting the password, both the slow and fast hashes are done on the server (to stop someone just hashing 'password123' with SHA256 and sending that).
This is called server relief. There's a discussion of it elsewhere in this comment thread, it is well known, e.g. [1], though doesn't google particularly well.
The downside, of course, is that someone with a disabled or borked javascript can't login to your site.
That's a neat idea. What do you put in both? I see two options:
1) You copy the whole password, and use the whole password for both. Then an adversary can just attack the weaker, faster one.
2) You split the password; half goes in one and half in the other. Now user passwords have doubled in length---or they haven't, and you have 4-10 character half-passwords instead of 8-20 character passwords.
There are separate concerns of brute-force mitigation that people should look into regardless of their hashing technology. Things like exponential-growth cooldowns per IP/user account (with lots of caveats to prevent cooldown-DDoS) should be used.
>This isn't a particularly easy problem to solve, and if you do it incorrectly you open yourself and your users up to a denial-of-service.
When there is a choice between making dealing with denial of service mitigation more difficult or making it easier for user passwords to be discovered after a breach, you should definitely choose dealing with denial of service mitigation. Not saying you might disagree with that sentiment but I would have very little sympathy about a company trying to make excuses like that to validate increasing the risk of user passwords being exposed.
Think infrastructure rather than appliances like Facebook. What do you think happens if certain state keeping big authentication servers or routers reboot? We have a customer that has more than one million users on a GGSN (which is a glorified router). If that happen to restart every single customer will immediately and automatically try to reconnect.
The systems involved actually doesn't tend to handle this many in reality (the ISP in question restrict it to some 20-30k/s to our system). These systems are starting to be better at supporting keeping state through restarts, but there can still be pretty impressive spikes of authentication traffic if the wrong system is rebooted (or crashes!).
But its a non-obvious (imo) attack vector opened simply by switching to scrypt / bcrypt.
In a perfect world, quality web apps have rate limiting built into their auth schemes. But it's important to acknowledge these two algorithms will put a much heavier burden on your CPU.
If you're authenticating with a username and password on every request you're doing something wrong. Once a user is logged in you should be setting a cookie, session, or some other token to identify the user.
Authenticate once, generate a token, and use the token for auth from that point. I can't think of a case where you'd need to send the u/p on each request.
If you're writing http headers out to your apache logs on your production server, you're doing it _severely_ wrong.
edit: I'm specifically talking about http basic auth with a precomputed "Authentication: base64($username + $passwd)" header, not a GET of "/foobar?api_key=12345abcd". The latter is obvious in it's failures and is not related to http basic auth.
No, of course not. The CS problem behind a password hash (or KDF) is to exploit time and memory to convert a low-entropy secret into something with the strength of a high-entropy secret. But when you're securing individual HTTP requests with session tokens, you simply use high-entropy secrets, and thus don't have the password hash problem.
If users picked 128 bit random numbers as their passwords, any hash function would suffice to store authenticators for them. You'd still want to hash them, because presumably users will re-use the same 128-bit random number on several machines. But it would be infeasible to brute force them, so MD4 would do just fine.
There is no reason to hash a secure cookie, because they aren't used across several machines. The compromise of a stored session key implies that every system where that cookie is valuable is also compromised.
A reason to hash cookies/tokens on the server side is so you don't have to reset them if your server database is compromised. A fast cryptographically secure hash with digest size equal to the token size is a good choice.
This also has the benefit of defending against timing attacks, for example, if you don't completely trust your code or the compiler / interpreter to not optimize your "constant time" comparison.
It would be good practice to reset your auth tokens in the event of a database compromise anyway. In most cases that's a low-cost operation. The advantage is that it rescues you from the possibility that the attacker logged auth tokens when they were passing through one of your servers.
I agree, of course there is nothing stopping you from resetting if and when you want to, and on your own schedule. That's not a reason not to run a hash on the input token. I think there's no possible reason not to run 'token = sha256(token)'.
> In most cases that's a low-cost operation
But resetting API tokens is not necessarily low cost, as it's literally pulling the plug on all your persistent connections, and requiring manual intervention to bring them back online. There are many cases where you can't simply pull the plug on all your clients.
Also, as a byproduct it enforces all sorts of best practices, like ensuring the token is just a token, and doesn't have data piggybacking on it.
So what are your cookies/tokens if hashing them makes a difference? Seems like cookies should be CSPRNG values, and it is unclear what hashing one of those gets you.
The tokens are CS-PRNG, e.g. 32-bytes or larger. The preimage is stored on the client as the token. The token value received by the server is sent through a hash or HMAC before being compared against the persisted value on your backend database.
If the backend database is compromised/leaked whatever, the attacker sees the result of the Hash/HMAC, but cannot generate a preimage, so your tokens stored by clients do not need to be reset. Otherwise, a leak of the backend token database grants full access to the attacker.
This is particularly useful for long-lived tokens, like API tokens, but can also be used for short-lived sessions alike.
This is not currently considered a must-have / expected best practice, but I believe it will evolve into one, because it's hard to get wrong, and it protects against a reasonably common attack vector. Guaranteed timing attack resistance is a bonus add-on which is valuable in its own right.
The backend has been so invasively compromised that attackers have dumped the session token store. The thing that the session tokens protect essentially belongs to the attackers. Even if, as a result of crazy overengineering, they can't read the original "seed" secret the store holds authenticators for, they can simply overwrite them.
There is no point to hashing cookies and session keys. Don't bother. It's not just not a best practice. It's something a smart auditor would file a sev:info bug against.
Writing a new token will make a lot of noise in the system, exposing the breach. Using a stolen token from a new IP, perhaps much less so, although that too should set off warning bells. Appeal to authority aside, I can't see a downside.
What I like most about 'token = sha256(token)' is that it expresses a significant part of the design in a single, obvious line of code; we don't store tokens, we can't provide tokens after the fact, we can't display tokens on our god-mode UI, if you lose your token a new one much be regenerated because we simply don't have it anymore, the token must not encode data beyond being a unique random value, we cannot be socially engineered into sharing your token with an attacker, the token will never be disclosed through a timing side-channel, insider threats cannot access your token, etc.
> Writing a new token will make a lot of noise in the system
Simply doing a hash of the token won't get you the desired "noise" in the system. That is, you need to do something else besides what you have said here. For example, writing a new token, whether produced by an attacker or a legitimate user, will produce the same some "noise", no? Unclear how, when the attacker owns your database and any triggers, you are going to tell if it is an attacker.
Similarly, the single obvious elegant line of code is not going to deter an attacker. Oh, I imagine that there are attackers that enjoy the beauty of code in a hacked system and put it on pastebin, possibly slowing them down.
And what are the chances if the attacker is that deep into your system, that they aren't reading the tokens before they are hashed?
The downside that I see, and I would flag this scheme, is that it doesn't provide the protection that the developer is led to believe.
An attacker can't change a token without locking out the valid client, that's the "noise" I was speaking of. If my requests suddenly start failing because my token is no longer valid, the attacker has shown their hand and we now have proof of a compromise. There are many attack vectors which could provide read or even read/write access to the token database without memory access or code execution. To name one from last week, how about Slack?
Nothing, literally, nothing, can provide protection against the attack vector you're saying this does not help against. Sure, and of course I agree. But obviously we don't give up and do nothing because sometimes exploits grant root. We add layers of defense and expect that some will hold, and some will not. Some will act to contain a breach across certain vectors, and some will be run over. Some will simply slow an attacker down, or prevent them from walking away with 100% of your data, and only get a percentage based on the time they were able to maintain the compromise.
I don't know what you mean that the line is "not going to deter an attacker". Surely you understand the difference between a short-lived attack which can only target persisted data, and a persistent attack with full memory access, and surely your threat model allows for one without the other in many cases? So green boxes in those cases for this technique, and N/A for the other boxes. What am I missing?
There are attacks it does not withstand, the same attacks that make password hashing useless by-the-way, and there are attacks that it certainly does withstand. There are also several attack vectors which it eliminates completely, and various follow-on benefits which I listed as well.
On the whole it is a large positive in a simple obvious package with no possible downside (except perhaps auditors flagging it as a bug). I never said it was a magic bullet which protects you from full persistent system compromise. I understand exactly what protections it provides and beneficial policy restrictions it imposes.
I find the resistance to such a simple defense-in-depth perplexing. It not being perfect is not a reason not to do it. Neither is password hashing, but we still do that. I really am shocked that token hashing would be at all controversial. I do it, and I think everyone else should too.
"It doesn't provide the protection that the developer is led to believe." Well this is much more true of bcrypt than it is of token hashing! What percentage of passwords does bcrypt protect, and for how many minutes after the database is popped? It's impossible to answer. What percentage of tokens does token hashing protect? If you can answer a) describe the access level granted by the compromise, and b) describe the time when the compromise began, then I can definitively answer that question.
The answer cannot be, assume the attacker had full root access to all systems. Because we are under attack every single day, and some of those attacks succeed in some limited measure. There are laws on the books today, and new ones coming, which require rapid disclosure of the actual extent of data breaches, so this isn't academic.
Of course the exact extent of a compromise is not always know, but likewise there are cases where the extent of a compromise is precisely known, and in a subset of those cases, a hashed token prevents an attacker impersonating your clients.
I mean, sha256(token) is child's play, to be arguing about it is just odd. I'd like to see homomorphic encryption stop even a memory-sniffing attacker from ever intercepting my tokens. Lets get serious! What, you'd rather just trust TLS? :-/
This makes sense, but--forgive my ignorance--what site needs to process millions of password authentications per second? Don't most sites hash/compare the password once at login, then issue an ephemeral token to maintain the authenticated state? Is Facebook, for example, hashing my actual password for every HTTP request that my Facebook mobile app makes?
I think if the most efficient way to attack the hashes is to buy the same hardware you use to process logins than in some sense you've already won. It's where the attacker can buy GPUs or program an FPGA and dollar for dollar make orders of magnitude more guesses per second than you do verifications per second that you want to avoid.
To the larger point, I do agree that some of this starts to look to be a bit of security theater. If a user picks a laughably weak password, and the server is completely compromised, it doesn't much matter what password storage scheme you used, and on the other hand if the user picks a great password, especially if he never reuses it, the consequences of losing that hash is limited.
I think maybe you missed it a bit. If attackers can spend a bunch of money to guess enough passwords to be useful in, say, weeks, then if you make it take 100 times as long, now it's years.
And using scrypt with a decent work factor isn't 100 times harder, its tens or hundreds of thousands of times harder.
Additionally, I think one of the benefits of scrypt is that it is specfically designed to deter GPU or FPGA attacks because it is memory intensive instead of just CPU.
Moxie hit the nail on the head. It's absolutely a fundamental asymmetry. Slow hashes can protect strong passwords, and not much else. And if you use a password manager to generate strong passwords, then you are going to throw that password out anyway.
In the time it takes for your users to give up on the hourglass, assume their login request is hung, and start double-clicking submit, you have now DDoS'd yourself. That's about 750ms I think...
Also, try this sometime -- clear your cookies and try to login to Google, or Twitter, or Facebook. Time how long it takes before you see the first byte of a session cookie. Hint: Not Long Enough.
Password hashing is embarrassingly parallel. The botnets don't cost the attackers anything to hash your password on 100,000 CPUs all at once, after they've decided to target you. Moore's law? Also not helping.
We need something better. I'm working on just that, I'm sure it will have more than it's share of naysayers, but I'm giving it my best.
You raise a good point, but one that's probably an issue to a minority of those implementing applications that require an authentication component. Sure, the Twitbooks, GooSofts and FaceLinks of the world that deal with large numbers of concurrent authentications have to think a bit more about this, and that's fine; I would expect that they would be well equipped to do so, and likely also run dedicated authentication servers and carefully considered systems.
I can probably count on one hand the number of times I've seen an application use bcrypt or scrypt and define their work factors. The common case seems to be sticking to the defaults that their chosen library ships with. While these may be somewhat less than ideal, it's universally true that these schemes are stronger than salted passwords fed to a fast cryptographic hash.
>>but using scrypt or bcrypt server-side at effective difficulty levels will either destroy your L1/L2 cache or exceed your CPU budget.
Perhaps this is the real issue: lack of sufficient budget for CPUs that can reliably get the job done is a reflection on the priority organizations place on information security.
For an attacker, a great way to cripple an organization that uses scrypt/bcrypt easily is just to attack logins. If each login takes 1 second of work, then it's easy to overwhelm any system system using a host of bots on distributed hosting systems. Say an attacker can hit with a mere 1 req/s from 100 hosts (very easy with aws/digitalocean/hetzner/etc), then that's 100 CPU-seconds of work just for logins.
Comparatively, if they hit with 100 req/s for normal front-end data, caches can easily handle that. So really, adding these types of login checks to any publicly available login page ends up creating an on-demand DDOS target.
From the password cracking side, the asymmetry comes from the fact that an organization has to have X amount of server resources to service Y number of requests, but an attacker can utilize the same X amount of server resources to service just one thing, breaking the exact password they are looking for. This is further exaggerated by the fact that generally for an organization those X server resources also need to more than just service logins (like actually serve content or API data).
I specifically set a request number that would be below most thresholds.
That said, a one-time request from 100 hosts would still use 100 CPU-seconds of work. Other than preemptively blocking hosts (such as all of AWS), there is no way that a "per-ip attempt throttle" is going to catch a single request from 100 different hosts.
If you had a server with maxed out with 8 intel E7-8870V2 CPUs (15 cores @ 8 CPUs = 120, $32k server cost just in CPUs), and set for a work factor that gave a normal "1 second" work factor, then someone just DOS'd you for most of a second. On a more reasonable 8 core server, that DOS would last 12.5 seconds (actual CPU time, not including the fact that they are stacked on top of each other). And on a dual core system that's almost 2 minutes.
If there was any other part of a website that could be DOS'd for so long with so few requests, then most people would also suggest the application had "far more gaping holes in it." Moxie's point above is that the advice presented is to just put bcrypt/scrypt/PBKDF2 in place, and no advice is given at all on how to deal with these issues that come up, or even that they exist at all, and thus systems end up being misconfigured or work factors relaxed to a point where only a false sense of security is gained.
> I specifically set a request number that would be below most thresholds.
No legitimate user will be logging in once per second. If you're specifically throttling logins and don't set it higher, you're so incompetent you shouldn't be writing production code in the first place.
> That said, a one-time request from 100 hosts would still use 100 CPU-seconds of work. Other than preemptively blocking hosts (such as all of AWS), there is no way that a "per-ip attempt throttle" is going to catch a single request from 100 different hosts.
So you've successfully DDoS'd an application for the few seconds that it takes a couple dozen cores to chew through 100 CPU seconds. Um, congratulations? I don't think there's a reward for "most pathetic DDoS attempt in history", but it should go to this.
> And on a dual core system that's almost 2 minutes.
You're very confused. When we say "1 CPU second", we're speaking of a single CPU core. 100 CPU seconds on a dual-core system takes ~50 real seconds. Your hypothetical 120-core server would be theoretically capable of processing nearly 120 logins per second at a 1-second work factor. bcrypt et. al are not multi-threaded.
There are botnets with hundreds of thousands of hosts in them. There are proxies and NATs with hundreds or thousands of users behind them. How do you balance those out?
> There are botnets with hundreds of thousands of hosts in them.
Which have a wide array of other mechanisms by which to DDoS your application. If that level of force is being directed at you, you need professional DDoS mitigation assistance. The CPU time cost of your login mechanism is immaterial.
> There are proxies and NATs with hundreds or thousands of users behind them.
You do not need to throttle an IP if it is not the source of an attack. But it remains inevitable that a serious DDoS will sometimes break legitimate users, even with intelligent mitigation strategies. Welcome to the real world, it ain't pretty!
Which have a wide array of other mechanisms by which to DDoS your application.
Why use any of those other mechanisms, which might require a few thousand hosts, when a method exists where a hundred hosts can do just as much damage by getting the server to punch itself in the face.
Because a method does not exist where a hundred hosts can do just as much damage. It is utterly trivial to detect and block anomalous login activity from 100 hosts.
- Some people run NoScript or have niche devices that mangle JavaScript (no login for you!)
- The client now has to generate the salt. So you'll want the client to be using a modern browser which supports window.crypto.getRandomValues(); (so IE 11 or newer)
- Low power (either electrically or performance wise) might struggle with the work factor and that might reduce the user experience (the browser might become unresponsive)
- Changing the crypto function is now quite annoying/work intensive. Effectively the client will now need to generate the old hash and the new hash, and send both. You'll need to check the old, check the new, and store the new if either are correct.
- There are some cross-site-scripting and forged request concerns. But those exist for all login pages frankly.
- You'll still need to do SOME work on the server to convert the raw client hash into a storable version (in case of compromise) so they cannot just re-send what is in the database for login (essentially the hash would be a plain text password for all intents and purposes). You could reduce the work factor, but not remove it entirely.
Essentially trusting a browser is a bad bet because too many browsers suck. I'd prefer to put my trust in a more known quantity, the web-server, even if it costs me a few cent in usage than do the extra dev', extra testing, and extra tech' support required to get browsers to do it.
Unfortunately there are still a lot of IE 6-8, Android 2.xx, and so on users who drag everyone down.
Minor nitpick, why would the client need to generate the salt to do authentication? I thought the salt is generated once when the password is first set, which can be generated at server side, and stored along with the salted hash. The salt would need to be retrieved from the server to the client and combined with the user entered password to compute the authenticating hash.
As a minor quibble (or am I missing something?) - the salt doesn't really need lots of entropy and you could send it to the client too; so lack of window.crypto isn't a major factor.
Of course, that doesn't really undermine your conclusion in any way - as you say, enough browsers "suck" that doing this client side may well negatively impact quite a few users.
> As a minor quibble (or am I missing something?) - the salt doesn't really need lots of entropy and you could send it to the client too; so lack of window.crypto isn't a major factor.
The KDF (bcrypt, scrypt) certainly needs a suitable CSPRNG though, which you aren't able to get across all browsers/clients right now.
I'm not sure I quite follow the point you're making. Perhaps I've misunderstood what you're saying, but bcrypt only uses a CSPRNG for generating the salt.
If you generate the salt on the server and pass it to the client, then the client only needs to be able to implement the deterministic part of bcrypt.
This fact should also be an intuitive deduction - after you've performed and stored the initial bcrypt derivation (with a fresh salt) all future executions need to be deterministic, because they need to product the exact same output (for comparison purposes). bcrypt wouldn't be much use to you if it generated new hash output each time you ran it (with the same password+salt).
Correct me if I'm wrong (I'm no crypto expert), but doesn't client-side hashing take away the main point of hashing passwords in the first place? If a password database is compromised, the hashes don't even need to be cracked, they can just be sent straight to the server for authentication. The only thing it seems to help with for the client<->server case is password reuse between websites, and that's only if they don't use the same client-side hashing scheme.
Moxie seemed to hint at this problem by mentioning local bitcoin wallets--client-side hashing only makes sense if you're not sending the hash anywhere.
This is covered in a little more details in other comments [1] but the basic idea is:
- The user generates a password. That password can be assumed to have relatively low randomness (entropy). It's normally going to be 6-12 ascii characters which isn't a particularly large input space. Expecting users to remember something substantially larger is not realistic.
- Because the input space is so small, good password hashing solutions need to have a high work factor, so that is it computationally infeasible to do a dictionary attack on the database.
- If the input space was larger [but everything else stayed the same] then we could reduce the work factor, because the size of the dictionary would increase, automatically making dictionary attacks harder to do.
- That "everything else stayed the same" is important. We still need our hash to be one-way, but it means (in overly simple terms) if we increase our input space by 1000 times, then we can decrease our work factor by the same magnitude.
- If you can increase the input space enough, then eventually you get to the point where a standard hash like SHA2 has a high enough "work factor" (CPU/GPU load)
And the missing piece is that it is argued (and is potentially true, but I haven't done the analysis, so don't take this as a recommendation or endorsement) that scrypt (used appropriately, with random salting) is an effective means of converting that small input space into a larger one.
The main problem (barring some fancy and probably patented new techniques) is that whatever gets sent over the wire from the client is a de facto cleartext password. If your system does the hashing client side and then stores that, an attacker with the login database can just submit the pre-hashed values.
To prevent this, you still need some transformation on the server between the login form and the database, which means you're back where you started.
There may be other downsides, but the one that immediately comes to mind is that some of your client's devices may well be extremely resource constrained. The obvious type of device that comes to mind is mobile phones but there's also set top boxes and many other non-full-blown-PC web clients around.
What ever work factor downtuning you need to do to conserve server resources may well be dwarfed by the downtuning you need to do to get bcrypt to run in a reasonable amount of time on a mid range smartphone.
Is this still true? I see some articles suggesting it from around the time that Android 2.1 or lower was a "mid range" smartphone.
It doesn't seem like it ought to be true. Running bcrypt in Ruby with default settings takes small fractions of a second on a few-years-old Macbook Pro. Even if the smartphone is 100x slower, it should be within the realm of reason to run a process that might take 1-2s once every thirty minutes or so.
Now, I'll buy that if your target device is not a mid-range smartphone, but "the very bottom of the smartphone market," bcrypt might be too expensive.
JS's bcrypt/scrypt performance will be pitiful. If it takes the client 1s in JS to bcrypt a password, a server will be able to do it in a 10th the time with a more efficient implementation. That makes client-side bcrypt have to use an artificially low difficulty factor due to the inefficient implementation language.
It's been said before in previous discussions, but have not seen it here: Just make your own 'password cracking cluster' to make sure you can handle the auth workload with ease.
Examples of sites where this is an issue? Serious question, where does scrypt/bcrypt overhead get to be important enough compared to the rest of the traffic the site has to handle?
It's straightforward and effective when password hashing happens client-side (like local encryption for a bitcoin wallet), but using scrypt or bcrypt server-side at effective difficulty levels will either destroy your L1/L2 cache or exceed your CPU budget.
In practice, from what I've seen, this means scrypt is never used, and bcrypt is used with a work factor that's tuned low. I think this is just a fundamental asymmetry, and that at the end of the day people use bcrypt so that they can say "we used bcrypt!" and get a nod when their entire user database is compromised, even though it provides very little value the way it's deployed.