Hacker News Reader

Comment by Olscore | Hacker News Reader

Question: From my understanding bcrypt is designed for security even when the hashed data is leaked. Each piece of data is uniquely salted and hashed to perhaps varying degrees of difficulty. So for a thought experiment, let's say a site made the password column of their user database public. Given an entirely public password column, even with associated usernames, would this have any use or decrease the security of those user accounts at all, aside from the obvious that their username is known?

View on HN

It would allow you to bruteforce the passwords without any sort of rate limiting. So, if you used a dictionary, you probably could get quite a few weak passwords in a short amount of time relative to a system that had proper rate limiting to prevent these kinds of attacks.

Ah derp. Totally forgot about rate limiting. Thank you.

I thought bcrypt was a deliberately slow algorithm so it cant necessarily be brute forced.

But still much faster than an HTTP request to an Auth API that allows only, say, 5 requests per minute.

Right, but you would still bypass the rate limiting of the server whether that be login attempts, http requests per second, firewall rules, latency or whatever when checking.

That's another rate limiting that has nothing to do with the hash strength.

Good password hashing functions have internal rate limits that reduce the likelihood of anyone being able to break the hashes easily because they will be expensive even when fully implemented in hardware.

For how long are they resilient it's another question but bcrypt is pretty good, it's quite slow, and is expensive to implement in ASIC/FPGA.

This is what I was thinking about. Thanks.

You'd still need the salt though, right?

Bcrypt salts are ordinarily colocated with the hashes and the number of rounds used to compute them.

The salt is typically stored with the hashed value. Its purpose is simply to prevent you from being able to use a single dictionary attack on all users.

The salt is usually stored with the hash. It prevents using pre-calculated rainbow tables. Without a salt you can check a password guess against all passwords. With a salt you can only test the guess against a single password.

Depends what you mean by short amount of time. Depending on the strength selected with bcrypt, it can easily take a second to check a hash. On a 30m password database, this will take a year on one machine to check just who is using "monkey" as a password.

> it can easily take a second to check a hash

On what hardware?

An i7 laptop. But even if you use an 18 cores server, it doesn't really change the point. It might take a month instead of a year. But it still doesn't scale, even to only check the most common passwords.

How can you say it doesn't scale? You just need to spin up a cluster that is powerful enough to get down to let's say a week. The cost of this would be a joke for a company / institution of a certain size.

1 week only tests 1 password. It would have to run for years to get a decent set of results. I don't see how a company can afford all that hardware and power to do something that is illegal to begin with. How do they monetize it to get a return?

You just need to target certain accounts, no need for all.

And don't forget, that every 18 months, the amount of processing power you get for a modest price, doubles.

Still?

Not anymore.

It's hard to get specific numbers about a trend that just changed. But the double every 18 months is now clearly wrong.

We've got a couple of approximately 27 months doubling, but that is past too. My bet is that we won't get a fixed number ever again.

I'm not sure the fastest per core speed for the last 5 years in CPUs is significantly faster.. more cores, more caches for some operations, but not nearly the growth we used to see.

Well, I was surprised by these benchmarks: http://www.anandtech.com/show/10404/asrock-deskmini-110-mini... When you compare the skull canyon CPU and the i5 6500: http://ark.intel.com/compare/93341,88184 The i5 has better specs on pretty much any aspect, but the skull canyon does way better in those benchmarks. I am told the impact is the 128MB eDRAM which acts as a L4 cache.

So maybe that's the way for computers to become much faster, making everything around the CPU go faster. Integrate the RAM and the GPU on the chip. Superfast SSDs. Etc.

Let's say that were true, so in a year and half you will only have to spend 20 years cracking the passwords? Bcrypt is designed for this exact situation and performs pretty well.

I am not saying bcrypt is bad. But thruth is, we have to be constantly challenging our assumptions about security and avoid feeling like the battle is "won".

> I don't see how a company can afford all that hardware and power to do something that is illegal to begin with.

An evildoer would use stolen credentials, stolen credit cards, or stolen hardware (botnets).

It does technically scale, just like everything else :)

But I think the parent's point was that this compute time only lets you check one password against one account. All you can do, after this compute time, is state that "'monkey' is/ is not the correct password for @iagooar's account".

Those results can't be used to check other accounts (because they're salted) so this approach doesn't really scale well at all. It might, for a huge adversary (state-scale) allow a single password to be cracked in a reasonable timeframe, iff it's relatively simple password.

https://gist.github.com/epixoip/a83d38f412b4737e99bbef804a27...

107 kHashes/second/machine for bcrypt in default settings (which probably many sites will use).

In the comment at the bottom it says: bcrypt work factor is 5, scrypt work factor is N=1024 r=1, and PBKDF2 rounds are set to 1,000.

If they did indeed use a work factor of 5 then this analysis is pretty much meaningless for bcrypt. The default is 10 and I usually use 12 myself.

With bcrypt you can set a parameter which determines how slow it is. So if hardware gets faster, you can change the parameter. (brcrypt uses 2^n iterations where n is the parameter.)

So it doesn't matter on what hardware, if you want bcrypt to take 1 second on modern hardware (for any value of "modern"), you can.

But 1 second of CPU time on your Web server is a lot different than 1 second of CPU time on a supercomputer.

Or 1 second of GPU time. Or 1 second of time running on an ASIC.

Chances are that you can't afford the most modern hardware. An attacker at least temporarily can probably afford more than you can. If you configure bcrypt so that an attacker spends 1s, it will be to slow to be practical for you.

Yes, but even if you allow it to only take 1ms per check for an attacker, it's still practical for you and will take an attacker 4 minutes per account to check all of /usr/share/dict/words (to say nothing of the "add a 1 or a ! at the end"), so long as you are using random per-account salt (which bcrypt basically guides you towards).

Make it 15ms for an attacker and it becomes an hour per account just for the dictionary.

True but in reality an attacker won't just use any dictionary. They look at password leaks, figure out what passwords people are actually using and what the most popular ones are.

You also can't assume that all accounts are equally valueable. An attacker might very well prioritize some of them.

This doesn't render all of this useless but I think you shouldn't consider even best solutions out there to be anything else than a temporary barrier. It's a good one and you probably will have enough time to change your password after a leak but you really do need to change your password within a week or so.

It seems like implementing a security strength which is a function of the current practical CPU speed is a recipe which could lead to disaster in the future, mainly because of how reluctant some companies are to change existing systems once they are in place.

The concept actually makes sense, but it kind of assumes that the strength of the security will be increased at the same rate of which technology progresses, which I don’t think will always be the case. This is especially true when you consider potential “bursts” in computation speed progression.

That being said, I’m not implying that I have a better idea. Running algorithms that take 30 seconds to execute isn’t going to work for logging into your Twitter account either.

Depends on how you design your password system... once upgraded a password system by putting a marker with the pwd for newer encoding... this way it can be upgraded as users login.. after n% of users have rolled to the new system, or x days, you can disable the other accounts and require they reset/recover their password for use.

You're massively overestimating the strength of bcrypt here. olcHashcat on a single modern GPU will do several thousand hashes per second, depending on work factor and GPU speed.

Then why even bother with bcrypt?

Because something with a cryptographic hash, like sha256, you can do millions (or in some cases billions) of hashes per second on the same GPU.

Password hashes, like bcrypt, PBKDF2 and scrypt, are massively slower. That doesn't mean they're uncrackable, it just means they are expensive to crack, so a strong password in a well implemented password hash will take a long time (and cost a lot of money) to crack, by which time the user has hopefully noticed and had time to change their password.

Additionally, there's a new player in town called Argon2 that attempts to solve the problems with bcrypt and scrypt. It's the most recent winner of the password hashing competition.

https://github.com/P-H-C/phc-winner-argon2

What problems with bcrypt/scrypt does argon2 solve?

bcrypt is limited to 72 characters (admittedly this is not that big a practical limitation), and scrypt is an excellent KDF, but wasn't designed as a password hash, and thus doesn't have great GPU defence. In practice, they're still both great, but that doesn't mean we should stop trying to do even better.

Argon2 looks really interesting, but it is still relatively new.

If someone isn't ready to go with Argon2 and truncating past 72 characters is an issue, Django (and possibly other implementations that I'm not aware of) overcome that by first hashing the password with SHA256 before passing it to bcrypt.

> scrypt is an excellent KDF, but wasn't designed as a password hash, and thus doesn't have great GPU defence

Last time I heard of scrypt, it was being used in Litecoin, a fork of bitcoin, because it was preventing GPU based crackers.

I don't know if it has anything to do with GPUs, I had thought it was due to memory, as referenced on the wiki page for Litecoin: "Litecoin uses scrypt in its proof-of-work algorithm, a sequential memory-hard function requiring asymptotically more memory than an algorithm which is not memory-hard."

It rate limits via IO (specifically memory IO) rather than processing power (CPU/GPU).

Ah, that's interesting enough to be worth looking into.

Yes if your password looks like: z1c4KzC*ITtt4Ka%vVDeei!aFSuEOTiDFCJ2NXc8Z7Jz then we are looking at enough time for you as a user to not care.

When you have a massive leak, it's better to have under 10 angry users about that they have been hacked (increasing at a slow pace) than most of your userbase raging at you and leaving your service.

> depending on work factor

Right, but therein lies the strength of bcrypt. You can set it so it will be several thousand per second, or several seconds per thousand. This comment seems a little like saying "I can run faster than a car, depending on how hard you press the accellertor."

The work factor also increases the work the server has to do to handle users logging on, which is a big cost both in UX and hosting fees. In practice, reasonable work factors for bcrypt are between 10 and 12. What application could tolerate a full second of delay (and 100% usage of a server core) just to hash the users password?

Also, a few thousand hashes per second (and that's on a GPU, and bcrypt is decidedly GPU unfriendly due to memory allocation patterns) won't allow you to do much more than a dictionary / rule + dictionary attack, so in the short term you're only going to get weak passwords.

I don't think anyone has any expectation that a login should be as fast as any other page load. Same thing for authorising a payment. I don't think a 1 sec delay when authenticating is unreasonable.

To me the risk with using bcrypt is DOS. If you have a high work factor, all an attacker has to do is to run a lot of logon (no need to be successful, they just need to relate to real users) to sink your servers.

No matter what you do, you always need to have a rate limiter / DOS mitigation for your login APIs / pages.

> The work factor also increases the work the server has to do to handle users logging on, which is a big cost both in UX and hosting fees. In practice, reasonable work factors for bcrypt are between 10 and 12. What application could tolerate a full second of delay (and 100% usage of a server core) just to hash the users password?

Is there a way client side processing power could be leveraged to help calculate the final hash value so that the computational cost could be practically increased?

I'm aware that having the client calculate and send the final hash value by themselves is a bad idea though.

"a second to check a hash" is a long time, but that's 3,600 attempts per hour. With rate limiting you can bring that down to 10 attempts per hour.

Presumably your users don't want to wait 6 minutes to log in, and nor do you want to tie up a full core for 6 minutes running the hash. That's the problem with increasing bcrypt's work factor - you have to deal with the increased difficulty too.

If you're doing salting properly (a unique CSPRNG-generated salt for every user) then 3600 attempts per hour really isn't enough to get anything except the lowest of low-hanging fruit.

If you're not trying to crack the 30m passwords, but focused on one, and especially if you might have some other clues about what that password might be, it could take a very short amount of time.

wouldn't the slowness of bcrpyt be a hindrance enough? Of course rate limiting is a much greater barrier, but I thought the whole point of using bcrypt is that its naturally slow and prevents checking several passwords in a short time

You can set the work factor (log rounds). Bcrypt is also cool because it doesn't scale well to GPUs, so it's still pretty slow even if you have decent hardware.

The rounds are a trade off between how long your users will wait to login and how strong the hashes will be. The current recommendation is between 8 and 12 depending where you look. The best practice is to just check on the system you are running, I usually aim for the number of rounds nearest a half a second.

It's an interesting thought, but it would be a catastrophe. Even if you can't brute force strong passwords due to many rounds of hashing, you can still check the hashes/salts against common passwords. You can't do a rainbow table attack, but you can do a dictionary attack.

I suppose the main danger is the possibility that someone might, at some point in the future if processing power should suddenly take a leap forward, come up with a way to crack them.

Would something like an ASIC help the attacker, I wonder?

Or some curious, thousands-of-computers strong grid-based cracking enterprise. I suppose, even constrained by the current state of tech, cracking bcrypt with some kind of massively parallel dictionary attack isn't entirely unfeasible.

eventually at least on PBKDF2 you could also increase the number of rounds taken. So if somebody logs in you could recalculate the PBKDF2 hash.

Indeed, though I suppose you've got to hope that the keeper of the passwords gets their hands on a similar level of processing power as the attackers do, with which they can increase the encryption work factor.

You can upgrade hashes offline as well. You just hash the existing hash with the new algorithm/configuration and remember algorithm, salt and any other parameters for all previously used algorithms. If you have all that information you can take the same path to verify the password and replace the chained hash with a simple hash that's faster to calculate.

It would substantially reduce the security of the system.

A large percentage of passwords are on the top-10000 password list, and for such passwords it is easy to reverse the hash using brute force

bcrypt and other modern hashing algorithms allow strengthening your hashes (by computing more iterations) at a later date should technological advances make your current number of rounds too weak. This allows you to 'upgrade' your password hashes from 20 rounds to 20,000 without needing the user to re-enter their password. If you publish your hashes at any point, you lose the benefits of this, if your hashes become weakened by technological progress you need to reset your users' passwords.

> would this have any use or decrease the security of those user accounts at all

Yes:

http://www.pxdojo.net/2015/08/what-i-learned-from-cracking-4...

Now, this assumes typical storage, that "leaking the password column" means leaking hashed password+salt. Without the salt, things would go slower - but it's sort of an artificial constraint - what you're talking about, is leaking the stuff the server needs to have to check a valid password. And that generally means the hash and the salt.

More generally, there's an upper bound on how difficult it can be made for the server to verify a password; conceptually this is: ((the amount of time a user is willing to wait to be logged in) - overhead) / (resources available on the server for checking the password)

Ok. You don't actually divide the time by the resources, but the point is that if you have 10.000 (valid) logins a minute, you probably can't dedicate 4 high-end GPUs on max throttle for 1 second to check every login attempt.

But an attacker might have those kind of resources. Which means, there's a very real practical limit to how hard it can be made to validate a password guess (a cracking attempt) -- and it will be some small fraction of the time your server takes to validate a login.

Which means that no "easy" passwords (eg: dictionary words) are ever "safe" passwords (safe against an off-line attack).

My guesstimate (mostly pulled out of thin air, and late night napkin "calculations") are that for any password to be "secure" it would need ~64 bits of entropy. Maybe that's a high estimate, given a solid work factor, but I don't think so.

The problem is, that 64 bits is actually quite a lot of information to memorize. In short: you'll likely only remember one or two such passwords. Use them to lock your password manager, and have machine generated random passwords for the rest (because what you don't want is to ever re-use passwords, as passwords are generally always susceptible to sniffing, shoulder-surfing, being filmed, keylogged or otherwise captured in plain text).

For a little more about some of my thoughts on generating passwords that are secure, friendly to current systems ("password rules"), friendly to humans (feasible to remember and type from memory without visual feedback), see these comments: https://news.ycombinator.com/item?id=11772700

(I keep coming back to this idea, but so far I've concluded that 64, 96 and 128 bits is rather a lot to type in, almost no matter how it's encoded. So I'm not sure how useful such a system will end up being. But maybe I'll finally just prototype it, and ask for help in testing it (the "security" part is intentionally trivial, but the usability part is the interesting bit -- will it actually help us in using secure, machine generated passwords, or will we still have trouble remembering them?)

I thought this was from a phishing attack - eg, plaintext, not bcrypt hashes?

How can a salt change on every encoding?

There has to be a reference point, no?

You can hash a fixed salt + password + some other user info like surname or email address. That way if you have the salt you can't just compute the hash of salt+"123456" to see who had that, you have to compute separately for each user.

What? No. Don't use a fixed salt.

Each record should have a unique, random salt. You then store salt:hash(salt+password).

There are numerous guides on how to do this properly, for example https://www.owasp.org/index.php/Password_Storage_Cheat_Sheet

Though of coure you don't actually do that, you use something like bcrypt that does this for you.

Yes absolutely this - I was just trying to explain how salts should implemented - in the real world always use something like bcrypt or scrypt that does all this for you.

OK, I think I got my terminology wrong. But my thinking was that as well as using bcrypt or whatever on the info in the database you can add some random value stored in code rather than in the database so if your database is compromised it's still a job for them to crack it. Not quite sure what you call that.

A pepper.

https://en.wikipedia.org/wiki/Pepper_%28cryptography%29

Using a site-specific constant combined with the user's e-mail as the salt isn't too horrible.

The owasp link you provided explains the two goals of using a salt:

1) Not being able to tell two passwords are identical based on the resulting hash. The e-mail is unique per user, so even if a bunch of users have "password" as their password, the hashes will all be different. Yes, if a user changes their password from "password" to "password" then the hash remains the same, but this is a very minor problem.

2) Prevent rainbow attacks. The constant part of the salt is enough to demand a site-specific rainbow table, and the e-mail takes this even further to a site + e-mail combo. Thus rainbow attacks would only have value in targeted attacks against a known site constant & e-mail combo. Once a good table is complete, it won't matter if the user changes their password.

Using a unique random salt would solve these two issues, however they can also be solved by adding a simple timestamp of the password's initial hashing time to the salt.

site-specific content (or formulaic derivations based on other columns likely to be in the same DB dump) suffer from internal (or former internal) bad actor problems as well. Disgruntled (or just loose-lipped) ex-employees can leak the formula or constant and you have a false sense of security.

(I'm not arguing it's "too horrible", but I am saying that it's worse than other schemes that aren't significantly more burdensome.)

A site specific constant is often called a "Pepper" as an aside. Just helps people google it if they want more information.

Several implementations utilise a Salt + Papper (unique per user value and single per site value). A Pepper is particularly useful when it is NOT stored in the database (e.g. stored in an environmental variable or even code). That way if someone steals your database via SQL Injection or a database backup file, they'd have to break the Pepper to recover passwords.

Peppers only make sense when they're almost "free" to implement. A slow hashing scheme is the most important thing, then unique salting, and finally a pepper last (since a pepper adds the least security wise).

You store the user's salt in a database column just like the hash. Optionally, when they change their password, you update the salt.

If you accept the premise of a secure hash, then there's no predictable effect on the output when you change hash('mypass') to hash('onetimesalt' + 'mypass'). Knowing that the user's salt is 'onetimesalt' does not get the attacker any closer to figuring out which password was used with that salt. Therefore there is no harm to storing the salt unencrypted in the database.

The advantage of doing this is that an attacker can't just make a single hashing run against common passwords using a single serverwide salt - they actually have to check the password list using every single user's salt. So if you have a million users (caveat: and your attacker is just scanning them all rather than going after a specific user), you've increased the complexity of an attack by a factor of a million.

Reply on news.ycombinator.com