search

FusionAuth / fusionauth-issues

FusionAuth issue submission project
https://fusionauth.io
92 stars 12 forks source link

Discussion: Entropy based password hashing #85

Open robotdan opened 5 years ago

robotdan commented 5 years ago

Entropy based password hashing

Problem

Password hashing at scale is very costly when using Bcrypt, PBKDF2, etc. The reason for these algorithms is to increase the time it takes to hash a password in order to make it infeasible to brute force.

If the end goal is to keep entropy high and ensure brute force attacks are infeasible, there may be a better than to just continue to increase the algorithm complexity to crush CPUs.

Solution

Build an entropy based solution to select an algorithm and load factor to reach a desired amount of entropy to keep the algorithm complexity to a minimum.

For example, a 16-20 character password hashed with SHA-256 or SHA-512 is quite difficult to brute force even with a large bit coin rig.

https://fusionauth.io/blog/2019/02/21/save-a-cpu-ditch-bcrypt-use-sha2-instead

Additional Reading

https://blog.benpri.me/blog/2019/03/02/reactive-hashing/ https://blog.benpri.me/blog/2019/01/13/why-you-shouldnt-be-using-bcrypt-and-scrypt/

How to vote

Please give us a thumbs up or thumbs down as a reaction to help us prioritize this feature. Feel free to comment if you have a particular need or comment on how this feature should work.

DistractionRectangle commented 5 years ago

Overview

Due to salting + configurable slowness, the method of cracking some entries in a reasonably configured database is taking the n most common passwords and attempting to brute forcing each entry. There is a balance to be found between the server cost to validate a hash and relative cost for a given dictionary size n selected by an attacker.

Security

Reactive hashing does two things:

This allows a more targeted attempt at brute forcing a given db entry. If we assume n is chosen as a function of cost, where cost scales as: cost ~ n*m/h where

For a fixed cost we can see n increases with any increase in h, and more importantly we have a better criterion for populating n for each partition in the reactive hashing scheme (which can be probed with chosen plaintext attack -i.e. they sign up multiple accounts with different password lengths to see how they appear in the db).

For example

So lets say we divide the database into two, passwords with length < 16 and those with length >= 16.

Brute forcing as described above doesn't really change for the first partition since the n most common passwords in general will likely all be less than 16 characters. For the second partition, we now actually have a shot at cracking a few entries since we can populate n for this partition only with the most popular passwords of length 16+ (and n for this partition can be extended due to the increased hash-rate from reactive hashing). If reactive hashing allows for more than 2 partitions, one can see how this only increases the expected number of entries cracked for a given fixed cost

One would have to dive into the data dumps of late to quantify the impact (if any) of this feature on security. It's probably marginal, but not something unworthy of consideration.

But let's throw all that out, as we can hand wave most of that off as parameter tuning. Let's look at utility.

What's the point of this feature? To reduce cpu overhead for password validation which in turn saves money and perhaps mitigate the potential for it to be used to DDOS your servers.

Does Reactive Hashing effectively facilitate this? The benefits of reactive hashing only come into play for the subset of users that have passwords that meet some criterion that above the minimum requirements. So really, its utility is a question of how many users actually meet said criterion. Users in general simply don't choose good passwords, opting to permute and stuff credentials to meet the minimum requirements.

TL;DR

The utility sought by this feature is only realized by just using the faster hashing scheme and changing the password requirements to match; it requires additional configuration (peppering, aka "in-memory salt modification" in the docs) in order to not introduce new weakness (however slight)

patrickfav commented 5 years ago

To be frank: this is a terrible idea.

Issues

Password Length != Password Quality

Password quality is not only determined by it's length. You are missing dictonary attacks and attacks wich use context info, such as account name, which also work effectively on longer passwords. For instance '1234567890qwerty' is a quite long but very low quality password (and has high entropy).

No Change in Performance

This would probably have very minor impact on performance as most users have passwords way smaller than the minimum entropy threshold for not using key stretching. See this analysis from the eHaromney password dump: only 384 of 1.2 million passwords had a length of 15 (or longer)

This is basically 'Roll your own Crypto'

Even if you are combining known hashes, you are essentially creating your own key derivation function which is never a good idea (if you are not a security/crypto researcher). My argument would be: if it would be a good idea to compromise brute force resistance on longer passwords, I guess there would be a password hash/KDF that would have that feature.

tl;dr Don't roll your own crypto

Increases Implementation Complexity

You make your clients more complex: Old user with long password, but used to have bcrypt? You want to change the password min length for SHA-256 from 16 to e.g. 20, how do you sync all your client code? How would you migrate such rule changes?

Leaks Password Information

You leak information about the password: maybe an attacker will only choose the SHA-256 hashed PW because she has more luck to find that in a pw dictonary?

CPU time is cheap, Memory is expensive

Further you are mixing CPU and memory demand of password hashing algorithms. CPU time is cheap and usually easily scalable, memory however is not. This is why bcrypt is still relevant (uses mainly CPU and only fixed amount of memory), while e.g. scrypt is not (scales CPU with memory and uses too much RAM in secure settings)

Do you really have a Problem with Performance?

Do you have any hard facts, statistics that proof that e.g. bcrypt is a significant contributer to reduced performance? Depending on your implementation I would guess that login is only done once per session (maximum couple of times per day per user). Are there other means to decrease that impact, e.g. longer sessions? Are there other means to reduce the risk of being DDOSed?

polarathene commented 3 years ago

https://blog.benpri.me/blog/2019/01/13/why-you-shouldnt-be-using-bcrypt-and-scrypt/

This is incredibly bad advice (ditching bcrypt/scrypt in favor of minimal SHA iterations). Using passphrases is good but the belief that length is relative to security strength is naive.

"correcthorsebatterystaple" will take about 20 minutes to exhaust 43 bits of entropy (average success rate is half of the keyspace, ie 1 bit less from the 44-bit passphrase) on a single current generation GPU. With a slow hash that can easily become >100 years, and that is less time to compute the hash than it takes for me to request a web page from the server and get a response.

Those are optimal attack times based on NVIDIA 3080 handling 7 billion SHA-256 per second and Kerckhoffs's principle.

If you want to offload server load, have the clients perform the hashing or a portion of it (always hash even if just SHA, the received client hash for validation without making a compromised leak of hashes usable passwords in themselves).

1Password has the benefit of providing users 128-bit keys that are part of their security policy, the app uses this to derive keys for decryption, it is not stored on the server thus any compromise even with simple passwords still have a 128-bit entropy key to crack (which requires more energy than it takes to boil all of the worlds oceans). That does pose it's own problems if the devices are lost as the service cannot recover/fix that, but additional fallbacks may be available (family/team plan) where the admin can assist with recovery.

voidmain commented 3 years ago

@polarathene - your math appears to be off. Entropy is a calculation based on length and pool size. In general, passwords are functions of ASCII characters as the pool size and the number of characters as the length. Then you apply a log base-2 in order to calculate entropy.

Here's a good article on password entropy for you to review:

https://generatepasswords.org/how-to-calculate-entropy/

According to the math, if you use a password like correcthorsebatterystaple which has 25 characters, the corresponding entropy using a pool size of 95 is:

log2(95^25) = 165 bits of entropy

Even using the largest GPUs in existence currently, this will require 2^30 years to brute force to a 50% probability or so (I'm rounding a lot but it doesn't matter given the numbers being so large). Even if computing power went up by orders of magnitude, it would still require millions of years to brute force a password of that length. Therefore, this password is secure using a SHA-512 hash with a single pass.

As an experiment, here is a SHA-512 hash of a password that has somewhere between 1 character and 48 characters. If anyone can reverse it and tell me the original value, I'll make it worth your while. :)

935ff37fb53d9bc30b5238e3523e9a79b68dec6209a3f7aa40f5af1fcbd6051ba319d7026b7a8b62acd2dfb8efc0ad1264209bcaa53e7dd9e9e94a7046b617d9
polarathene commented 3 years ago

your math appears to be off. Entropy is a calculation based on length and pool size.

My math is not off. This is the same mistake of the linked blog article I was quoting. That article references an XKCD article which very clearly states that "correcthorsebatterystaple" is 44 bits of entropy, while the author provided math of 117.5 bits (log2(26^25)).

So how did XKCD come up with 44 bits of entropy? Is the comic author wrong instead? Nope, and I mentioned why with this line:

Those are optimal attack times based on NVIDIA 3080 handling 7 billion SHA-256 per second and Kerckhoffs's principle.

Kerckhoffs's principle assesses entropy based on knowledge of how the password/passphrase was generated. So for "correcthorsebatterystaple" we have 4 words, and if they're randomly sampled from a set of 2048 words as our "alphabet" (as if it were a different language where a word is equivalent to a letter) we would have 44 bits (log2(2048^4)).

In that sense, a generator like getapassphrase.com can output two passphrases both of 44 bits of entropy like these:

Despite the difference in length and even words in this case, they are both 44 bits of entropy based on the generator rules. If you know the user you're attacking has generated a 44-bit passphrase from this site, you are able to perform an optimal attack at 7 billion guesses per second of SHA-256 and within 20-40 minutes (latter being full exhaustion of the key space), you'll have it cracked.

Therefore, this password is secure using a SHA-512 hash with a single pass.

It is only secure if the attacker couldn't possibly know more about your password and brute forced it in the manner you've calculated your entropy on 95^25. In general there are far better and more likely successful strategies that are used first to get any low hanging fruit (when a password hash dump has been leaked), but this differs from a targeted attack when the attacker is specifically interested in your account credentials and willing to focus all their efforts and time upon recovering that password.

If you are valuable enough to warrant that sort of attention, and your password is strong enough to withstand their computation power even when they know exactly how you generated your password... well they don't have to be that well funded to take more affordable low-tech approaches... (which while unpleasant, is often one of the only viable options). On the bright side, being immune to the majority of attackers around the world is a win.

Here's a 64-bit entropy passphrase btw, this would take about 4 years with 10 nvidia 3080 GPUs (( (((2^64) / (7e10)) / (60*60*24*365)) / 2 ) = ~ 4.178 years): "insane deer and comical boar remember rare raven in Jordan". Obviously that would take much longer without prior knowledge of how the password was generated, but the true entropy should be evaluated by if the attacker did know.

Even if computing power went up by orders of magnitude, it would still require millions of years to brute force a password of that length. As an experiment, here is a SHA-512 hash of a password that has somewhere between 1 character and 48 characters. If anyone can reverse it and tell me the original value, I'll make it worth your while. :)

Relevant XKCD ;) (joking obviously)

At best one might try leverage some dictionary attacks, but assuming you've generated a password randomly with equal possibility of each character being from the pool of 95 values, that would be enough to not bother.

If it's actually generated in a more memorable way such as words that reduces that entropy more, if we know those words are all lowercase or some other consistent pattern, if any punctuation/separator is used (space, hyphen, pascal case, etc), again we narrow that perceived entropy down closer to what Kerckhoffs's principle would evaluate the strength by.

One last mention for any visitors reading this.

A high entropy password as secure as it may seem cannot be re-used across services safely. There are various ways a service can be compromised and some even in 2021 that are far less reputable still store passwords in plaintext, all it takes is one of those being compromised to gain access if it can be re-used on more valuable targets.

Likewise, if you have some clever little pattern for extending the length with a shared prefix/suffix (eg a personal pepper if constant, or salt if it differs slightly), something some users feel more comfortable with when trusting a password manager to store the password without their secret portion, if one or more of those passwords are leaked from services and the plaintext is known, it is very likely that pattern becomes exposed weakening the perceived entropy and enabling an attacker to pull off a targeted attack more successfully. You'd be better off with something like LessPass (not without it's own drawbacks), or trusting the entropy of good generator from a password manager.

TL;DR

voidmain commented 3 years ago

Just a reminder that while we appreciate lively discussion, we also want it to be civil. We have a community code of conduct here: https://fusionauth.io/community/forum/topic/1000/code-of-conduct

Please think twice before mentioning violence, even when you are joking (I understand the context of the comment and the XKCD comment, but it may be interpreted differently by different readers).

@polarathene - please edit your comment when you have a second so that is not mentioning any type of violence.

Also, I'll be responding to the last comment at some point. It still appears to have some mixed messages and incorrect math. It will take me a bit to get to though so stay tuned.

polarathene commented 3 years ago

but it may be interpreted differently by different readers

Apologies, I thought given the linked content and emoji usage the context of not being serious about violence would be difficult to misinterpret (while that approach is very real, I don't endorse it obviously).

please edit your comment

I hope that's sufficient?

It still appears to have some mixed messages and incorrect math

I'd be glad to clarify any of that for you. I'm always open to being wrong and corrected myself, but I'm fairly confident in this math. If I have slipped up, do let me know! :)

64 bits of entropy:

FWIW, SHA-512 on the RTX 3080 is about a third of the SHA-256 hashrate slowing it down to approx 2.3 billion/sec (ie 2.3e12 from my earlier comment is 1000x 2.3e9 aka 2.3 billion), so bump that 4 years estimate to 12 years for average success rate.

I'm not sure where I've gone wrong with the math above, but perhaps the perceived approach of an attack? (eg a naive attack brute-forcing variable string length with an alphabet/dictionary of 95 values to permute through). No doubt that would take longer and be infeasible if the attacker has little information to go on, but that's not a good assumption to make in security AFAIK, especially if you value what those credentials provide access to.

If you were questioning the math from some of my facts, I felt I was already being too verbose in my response. Let me know if you'd like any more info on any of that.

voidmain commented 1 year ago

Well, it took me quite a while to finally get back to this, but I think the problem here is a misunderstanding of the core problem statement.

@polarathene is specifically talking about dictionary attacks only with a limited dictionary of 2048. This would reduce the entropy to a degree that makes the problem solvable (in a time-frame that make sense). His math is correct based solely on that premise and a weak hash such as SHA-256.

However, this is not what this discussion is about. Nor have I ever suggested that we limit this discuss to such constraints. In fact, I presented a password hash using 48 characters from a set of 100 options (Ascii), which makes the entropy much larger (336 bits if my math is correct). Just because the XKCD example uses 4 dictionary words does not mean the problem statement is limited as such. Anyone could change just one character in correcthorsebatterystaple such as corr$cthorsebatterystaple and the entropy instantly balloons. You can also repeat characters, reverse words, and many other tactics to increase entropy. And you'll never know what the rules are, so as an attacker, how could you possibly figure it out?

If we return to the original problem statement and limit our discussion to the domain presented, then the discussion is less about entropy solely and more about other aspects such as:

These questions remain in the correct domain but analyze the original problem statement to determine if it is viable.

polarathene commented 1 year ago

I seriously want to emphasize that as a security professional you really should take Kerckhoff's Principle into consideration when it comes to entropy.

TL;DR:

If you ignore Kerckhoff's Principle, then you consider this perfectly secure:

64 bits of entropy is fairly solid:

Apologies, I didn't read over the entire discussion and ended up repeating a fair amount that's been said already. I've tried to manage the verbosity of this response to accommodate that.

I think this response bridges any gaps in miscommunication.

Part 1

You are misunderstanding what I've said, here's a response summary:

Please clarify

  1. These rules to balloon entropy are from a password generation scheme or manual user intervention?
  2. The discussion is about being confident in entropy of a password that you can disregard protecting it with additional computation (PBKDF2, bcrypt, scrypt, argon2)?
  3. Given your answers to those two questions, how do you reliably assess entropy is a safe amount where Kerckhoff's Principle cannot benefit the attacker?
  4. Why do you think entropy is not reduced when the input is not uniformly random? (if you assume the attacker doesn't know any better, how do your modifiers balloon entropy when the naive attack pattern doesn't change?)
Full Response (click to view) > @polarathene is specifically talking about dictionary attacks only with a limited dictionary of 2048. Incorrect. - The "alphabet" is 2048 in size, as opposed to say a-z + A-Z + 0-9 being 62 values in an "alphabet". - Throw in 33 more special characters (eg: !@#$%) and you get your standard 95 ASCII "alphabet". - Instead of single characters, I referred to a set of 2048 words, a much larger set to mix from. A dictionary attack provides combinations of those individual items from the set, usually to bias input towards more probably patterns, like common passwords ("password", "Password1!", "P@$$w0rd", "JohnDoe42", "abc123", etc). So in this case the "limited" dictionary attack is a combination of words instead, but with proper random selection, there is no bias in patterns, so a dictionary isn't too useful vs brute force (_just assume [Kerckhoff's Principle](https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle)_). --- > This would reduce the entropy to a degree that makes the problem solvable (in a time-frame that make sense). Entropy is calculated from the keyspace (total permutations) which you can get from the set size ("alphabet") to the power of key length (_with the 2048 words, a length of 4 would be 4 words_). So no, the entropy here cannot be calculated from the input "alphabet" alone, you need to take into account length. --- > However, this is not what this discussion is about. Nor have I ever suggested that we limit this discuss to such constraints. > In fact, I presented a password hash using 48 characters from a set of 100 options (Ascii), which makes the entropy much larger (336 bits if my math is correct). Hopefully I've cleared things up now, and you can see that the discussion remains on topic. `log2(100^48) = 318.9` (bits of entropy). Your math is off a little, but as you can see, we've already had this discussion back in 2021, and I'm basically [citing back the same statements you relayed to me](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-847120427). Do note that there is a ceiling depending on the hash used. For SHA-256 or SHA-512, IIRC a collision is expected to be hit in half their size, so SHA-256 would be 128-bit, anything beyond that wouldn't add more entropy if you only need to reproduce the hash, and not the original input (depends on the attack). --- > Anyone could change just one character in `correcthorsebatterystaple` such as `corr$cthorsebatterystaple` and the entropy instantly balloons. > You can also repeat characters, reverse words, and many other tactics to increase entropy. And you'll never know what the rules are, so as an attacker, how could you possibly figure it out? I know I've brought this up to you multiple times, but you keep ignoring it... The attacker may not know, but you judge entropy by [Kerckhoff's Principle](https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle) as a worse case. Otherwise by your logic how would the attacker know any better, I could just use `mmmmzzzzmmmmzzzzmmmmzzz@mmmmzzzzmmmmzzzzmmmmzzzz` (48 chars). Despite the patterns, is the entropy really 318.9 bits? or is it more realistically 6 bits? (_`mmmmzzzz` or `mmmmzzz@` at a length of 6, aka `2^6`_). We could assume the 3 unique characters are not known from our pool of 26 lowercase letters and 1 special character, so our "alphabet" increases from just 2 "words" to mix and match to 22308 (`26^2 * 33`), which for a length of 6 is an entropy of 86.67 bits (`log2( ((26^2) * 33)^6 )`). In that sense, you're correct, entropy increased nicely even with the very basic password generator rules. That entropy would also apply to this compact version `mzmzm@mzmzmz` (12 chars), but it's no longer the minimal entropy, since 78.84 bits (`log2(95^12)`) without the fancy generation rules is lower now. Would it be more secure with emoji? `🎉🎉🎯🎉🎉🎉` The alphabet size is considerably larger, and the chance that the attacker would use emoji if we ignore Kerckhoff's Principle is low. In this case the `mz` and `m@` variations have been substituted with single emoji each reducing key length to 6. - The entropy becomes 70.96 bits (`log2(3633^6)`), if you knew the length and that it was only using emoji. - The entropy isn't really possible to calculate now for the typical attack assumption of ASCII only input, as no emoji would ever be tried. - Realistically, it's two emoji only, and only changing 1 - the entropy should be assessed as far lower and I'm sure most would agree that it's a bad idea (_besides the fact that you should not use emoji in passwords because they're unreliable as input_). We've established that: - Regardless of what the input "alphabet" is, key length alone does not equate to high entropy. - Knowing the rules behind the targets password generation allows us to better assess the actual entropy which could be significantly lower than naively assumed. --- > How do we determine if a password should use a weaker or stronger algorithm? > Does this make a significant difference considering most users use weak/short passwords? In both cases, if the time to process the password is minimal (500ms say) it'd barely affect the UX for the user, while significantly impacting the attacker. For weak entropy, users should be better educated but with decent 2FA and password generation that really becomes less of a problem. There are plenty of concerns here regarding users and security that we won't discuss, we're just focused on what we can do to secure against an attack. If weak entropy is a concern, add some in. Services like 1Password do this properly, but you also have pepper and salts. For offline attacks you have resources, where memory is an excellent bottleneck to scaling an attack. Your password KDF offsets entropy concerns, configure argon2id. > What energy and overhead is reduced by requiring fewer CPUs? > Are there any unforeseen threat vectors (does a leak of the hash provide information that is useful)? I'm not able to answer these well. It depends. With enough entropy in your password, you could store with a single SHA256 hash, nothing else as an attack would be infeasible (_128 bits is more than enough to require energy to boil all the oceans in the world_). If the attacker is motivated, they'll find another way. If the entropy is low, you are risking energy efficiency over security. You'd need to evaluate if the savings in energy are beneficial over the increased risk from low entropy. A leaked hash with proper practices should not leak information that is useful. You're more likely to have a threat vector elsewhere, often through the users being manipulated or careless.

Part 2

A quick glance over the discussion history seems it was about:

Discussion timeline / summary - Other users prior to my comments gave a great [overview of why that is a bad idea](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-473514765). - My [original contribution into the discussion](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-846949803) was to make you aware of the linked blog article assessing entropy poorly. - I tried to explain why it was lower but couldn't seem to communicate [Kerckhoff's Principle](https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle) properly? - I suggested one way to augment the entropy, describing what 1Password does (they have a whitepaper on it). It is a great way to protect users, but has a slight inconvenience granting access to a new device. For a password manager that is acceptable. - @voidmain [responds about my entropy calculation being off](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-847120427), not considering the "optimal attack" description. - [I respond and clarify that information](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-847334246) early into the comment. This time I link to **Kerckhoff's Principle**. - @voidman [briefly responds](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-848036794), not having the time to review (_in all fairness my response was excessively verbose_), but fairly certain that I was misunderstanding how to assess entropy. - I throw in some more information not long after, and roughly 18 months later [receive a response to again dismiss what I've said](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-1487469623).

Assessing Entropy - Kerckhoff's Principle

Kerckhoff's Principle was mentioned multiple times and ignored.

When you dismiss this measure of entropy via the argument "how could they possibly know?", you justify:

  1. Only length is relevant, just fill it with the same character (z), they'd be attempting 26^25 or worse right?
  2. The attacker would only use the ASCII as input, use a random emoji and call it a day :sunglasses:
  3. Best of both worlds, take your random letter z, fill the length and replace a random one with an emoji.
  4. So long as the attacker doesn't know your very basic rules, your low entropy password is super strong!

It's better to assess entropy by total permutations if you're able to generate a password with sufficient randomness (minimize bias).

I really hope that gets the message across better?

Click for some examples ### Examples Entropy based on **Kerckhoff's Principle** from passphrases generated at [`getapassphrase.com`](https://getapassphrase.com/generate/). This is an example of a high entropy password (64 bits): - _"insane deer and comical boar remember rare raven in jordan"_ - All lowercase with spaces (_easy to input manually_), while having some structure at the expense of length (_easy to remember_). - **Attack time (50% keyspace):** 2 years with single **SHA-256** (_against 10x RTX 4080 GPUs_). Likewise when we have proper KDF involved, (44 bits + hashing overhead): - _"dizzy pig keeps cute paper"_ - Reduced length while simple and secure (_but you must trust the service is augmenting your entropy via key stretching, like with `argon2id`_). - **Attack time (50% keyspace):** 7 years with **bcrypt** (work-factor 10) (_against 10x RTX 4080 GPUs_).

Choosing Pragmatic Entropy

Pragmatic amounts of entropy was shared, citing (at a SHA-256 hashrate to iterate through a given keyspace entropy):

More insights From this we can observe: - 64-bits of entropy is plenty for the majority (_but risky the more valuable and thus targeted you are, especially SHA-256_). - SHA-512 extends the time to attack by about 3x (_mentioned in linked comment_). - Proper password hashing with the common `bcrypt` can easily augment that by a million times in difficulty (_on the GPUs, which are not optimal for attacking `bcrypt`_). `argon2id` defends better by being memory-hard in difficulty. You need a lot more length/entropy to compensate for the cheaper processing of single SHA-256 / SHA-512: - Becomes impractical the more unique passwords you need as password re-use across services will expose more risk (_some less reputable services use plaintext - no hash at all; or your password may be compromised via other means_). - For these same reasons, due to **Kerckhoff's Principle**, you'd not want to rely on the same password with some variant pattern. The entropy decreases considerably when that pattern can be identified due to those vulnerabilities, a 2nd compromised password may be sufficient to establish the shared material and any pattern for the variants. - As a result, it mostly becomes useful for a master password and deferring password generation to most services via something that generates enough entropy, the text length can be shorter all that matters is sufficient entropy then. - If not delegating the growing number of passwords to a manager, either memory fails or the user weakens security by offloading that memory and storing them somewhere that is often accessible to a motivated attacker. Given the above, lets compare 48 bits of entropy: - _"CL@ni%8#"_ (`70^7.83 = 48 bit`, [8 chars + all options via bitwarden](https://bitwarden.com/password-generator/)) - _"detailed snail summons slim lab coat"_ (48-bit passphrase via [getapassphrase.com](https://getapassphrase.com/generate/)) The passphrase is easy to read, input manually and remember if necessary. If we throw in uppercase or specials we lose some of those benefits, similar to the shorter bitwarden generated password. Especially so for the memory factor as the number of services grows. For reference, here's how 48-bit entropy compares between SHA-256 and bcrypt, but this time with [10x Nvidia 4080 GPUs](https://gist.github.com/bigpick/cfa22947c884f7a3fc1431475e345427) (_almost double the hash rates_): - **SHA-256:** 18 minutes (`((2^48 / 130e9) / 60) / 2`) - **bcrypt (work-factor 10):** 111.57 years (`((2^48 / 40e3) / (60*60*24*365)) / 2`) That is the lowest entropy, if you shrug-off **Kerckhoff's Principle** then you can pretend that it'd take much longer. Just consider that the attacker is investing time and money: - Low value targets don't justify heavy use of resources. - Higher value targets will optimize the attack to justify that larger investment of resources.
voidmain commented 1 year ago

Thanks for the details response, I’m sure folks that read this thread in the future will get insight from it. I also think we are essentially saying the same thing, just in different ways.

I do want to clarify a couple of points though. A lot of your responses state I’m ignoring Kerckhoff. I want to be clear that I am not ignoring that. I fact, I’m assuming everyone understood that the question “How do we determine if a password should use a weaker or stronger algorithm?” must take into account Kerckhoff. And I want to rephrase from saying “weak or stronger” to “faster or slower”. I think those are more appropriate terms.

Second, your math appears to change. You mentioned 2048^4 as one set size (passphrase based on a dictionary) and then you mention 100 characters of varying lengths for other set sizes. Then it seems like you try to reduce both sets in some cases and then increase them in others. Like if you start introducing capital letters, emoji, or random characters into the passphrase, the set size increases. But if you take 48 Ascii characters the set size decreases based on weak combinations. It’s not completely clear what your point is, but I think we can agree that the size of the set and the length are how you compute complexity and also how you brute force attack the hash (up until a collision which is theoretically infeasible for 512 bits).

And finally, the problem statement hasn’t changed, but perhaps your understanding has. No one has ever stated that XKCD was reality or that we would limit passwords in any way. I mean users can type in whatever they want right?

Let me present some code for how this would work in practice and maybe we can move over into the concrete:

String hash;
if (passwordSucks(password)) {
  hash = hashWithBcyprt(password, 14); // Load factor 14
} else {
  hash = hashWithSHA512(password);
}

This is super simple code and the crux is the method passwordSucks. The algorithm should ensure that passwords cannot be brute forced in reasonable time. Here’s one implementation:

boolean passwordSucks(String password) {
  if (password.length() < 24) {
    return true;
  }

  if (pwnd(password)) {
    return true;
  }

  if (dictionaryAttackable(password)) {
    return true;
  }

  if (repeatsTooMuch(password)) {
    return true;
  }

  // More checks here?

  return false;
}

The other methods called here would exclude what would be “known generators” whereby an attacker could generate the entire sets in reasonable time (like the 2048 dictionary used for passphrase or repeat characters).

Okay, now let’s look at the math.

This function has a base set size of 100^24 (1e48). Each additional character adds an additional permutation set that multiplies the base set by 100. A 28 character password has a set size of 100^28 (1e56).

Each if-check after reduces the set size by some amount. If we assume breached sets contain 1e9 entries, we have reduced the total set size to 1e39 for 24 characters and 1e47 for 28 characters.

If we assume the additional checks reduce the set size by some amount, the final set is the attackable surface. For argument sake, let’s assume we design dictionaryAttackable and repeatsTooMuch to reduce our set by an additional 1e9. Our final sets would then be 1e30 and 1e38 respectively.

In order to brute force 1e30 combinations using SHA512, it would take 1e20 seconds. That’s 3 trillion years for the base length of 24 characters.

Let’s go nuts and bump the set reduction to a whopping 1e15. That’s a huge number, but let’s go with it. That would reduce our set sizes to 1e24 and 1e32. Using the same computational power, it would take 1e14 seconds to brute for the 24 character example. That’s 3 million years for 24 characters.

Okay, let’s drink a bottle of whiskey, punch through the Balmer Curve, and really get aggressive with our reduction. Let’s take it to 1e20. That’s massive and probably a mess of spaghetti code from our drunken coding session, but for argument sake, let’s roll with it. Once we sober up, we would find our set sizes have been reduced to 1e19 and 1e27. Using the same computational power, it would take 1e9 seconds for 24 characters. That’s STILL 31 years for 24 characters.

Basically, we want passwords generated by complex generators (secure random 24+ bytes works) to be hashed using SHA-512 and everything else to be hashed with BCrypt or Argon. This is the original problem statement.

Now, I’m willing to discuss a way that this implementation can be attacked, but I propose we talk about implementation details in code with hard numbers

polarathene commented 1 year ago

TL;DR

Basically, we want passwords generated by complex generators (secure random 24+ bytes works) to be hashed using SHA-512 and everything else to be hashed with BCrypt or Argon. This is the original problem statement.

I think you're making too many compromises for ensuring a reliable baseline of entropy to get away with a single SHA-512 hash. There are better ways to minimize resource usage when that is a priority.

In theory the SHA-512 approach sounds neat, but I just don't see it being pragmatic for real users (EDIT: When it comes to creating their own passwords + heuristics, not externally providing them from generators / managers).

Your proposed approach with heuristics is guesswork on how much lower the entropy actually could be, as opposed to the simpler rules of a generator where you have a far more reliable source of entropy (there's a good reason they're a thing) (EDIT: I seem to have misunderstood, and you're focus is not on heuristics for users creating new passwords via FusionAuth, but detecting eligibility for single SHA-512 hash of externally generated passwords that should have some acceptable entropy baseline_).

You'd still be salting the input into SHA-512 and storing the salt right?

How would the heuristics apply to the following?:

If you're unable to ensure that, false-negative is not too bad for decent passwords, but false-positive on the low entropy is risky. BTW, 36 years becomes 131 days with 100x the hashrate.

For an attack with a single RTX 4080, here's the difficulty:

I'm not sure if I can communicate this any better.

Most of my responses are correcting misunderstandings / misinformation from your end when making statements about what I've said. That is then followed by responses where I essentially rephrase my prior responses, presenting math + sources to back that up in different ways.

If you still believe this is worth pursuing as you've detailed, go for it. I've tried my best to express concerns and feel I have nothing more to contribute to the discussion.

I'll try respond briefly to any follow-up questions, but this should be my last detailed response :sweat_smile: (they soak up a fair amount of my time)

Original Response

Below I have clarified / corrected statements from your last response, while providing additional math / feedback and food for thought.

Click to view
Corrections / Clarificaiton > Second, your math appears to change. Just accommodating the context. It remains correct, but if you feel I've made any mistake I'm open to feedback :+1: > You mentioned `2048^4` as one set size (passphrase based on a dictionary) That was when discussing the blog article referencing the XKCD `correcthorsestaplebattery` comic. That uses `2048^4`. When I provide my own passphrase examples of a given entropy size, they're generated from `getapassphrase.com` which isn't as straight-forward in structure to calculate like XKCD, but does result in the mentioned entropy. > and then you mention 100 characters of varying lengths for other set sizes. No [that was introduced by you](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-1487469623), originally you [mentioned a 95 character set with lengths of 25 and 48](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-847120427). > Then it seems like you try to reduce both sets in some cases and then increase them in others. Like if you start introducing capital letters, emoji, or random characters into the passphrase, the set size increases. I believe you were the one to [first introduce random characters into a passphrase, and suggest other modifications](https://github.com/FusionAuth/fusionauth-issues/issues/85#issuecomment-1487469623) to raise entropy, while capital letters was already part of your original 95 ASCII charset? :man_shrugging: I just went along with it. The emoji were introduced to highlight some concerns I raised with what you were saying, but that didn't seem helpful to you, ignore it. I'm only concerned about entropy. Using words that are all lowercase as input (_instead of individual letters_) works great. > But if you take 48 Ascii characters the set size decreases based on weak combinations. Not really an issue? If you chose 48 random ASCII characters, and have a length of 23 with no bias in the sequence, you get over 128 bits of entropy (`log2(48^23)`).
> It’s not completely clear what your point is > I think we can agree that the size of the set and the length are how you compute complexity and also how you brute force attack the hash (up until a collision which is theoretically infeasible for 512 bits). You simply don't brute-force attack once it becomes pointless. - A naive attack would allocate some small resource on you and move on. - A targeted attack may invest some resources blindly (_but if they're not able to predict the cost required, it'll not go too far either_). - SHA-512 should roughly hit a collision before reaching 256-bit size IIRC. Not that anybody would bother to hunt a collision for that hash since it's not practical. - **128-bit is ridiculous for entropy already**, you can have the entire crypto mining network and not be successful (_approx 331 EH/s: `(((2^128) / (331e18)) / (60*60*24*365)) / 2) = ~16 billion years average success rate`_). We're talking all oceans in the world could be boiled away with that kind of energy requirement.. - If the attacker wants access, they're going to have to find an alternative option. ---
Collapsed as largely redundant now + my mistake for potentially misinterpreting primary intent for heuristics > I mean users can type in whatever they want right? I don't know? That is decided by how FusionAuth want to approach such a feature? (_I don't use the software, doesn't matter to me_) If you want to offer the user a way to have a secure password, give them a reliable password generator like `getapassphrase.com` or BitWarden offer. Something that ensures a solid baseline of entropy. The user will probably have some bias in selection, but the easier they are to remember or manage, the less of an issue that is. I think trying to support any input and assessing that by your own rules is more flawed, you'd probably be misleading some users and I doubt they'd care much between the two choices. Nothing is stopping you from offering both DIY and secure generator :man_shrugging: **EDIT:** While reading your response, I see you suggested heuristics that fallback on failed check to slow hashing. --- > The algorithm should ensure that passwords cannot be brute forced in reasonable time. Just offer generators that ensure that. It's not your job to attempt to assess entropy from untrusted inputs from users. You'll find plenty of resources where that has been attempted and has not proven to be reliable. > The other methods called here would exclude what would be “known generators” whereby an attacker could generate the entire sets in reasonable time (like the 2048 dictionary used for passphrase or repeat characters). If you want to support some heuristics for DIY inputs, go for it. Probably better to just use existing solutions already out there that have gone through this sort of thing for you already and done a best effort, but I wouldn't place trust in it personally for ensuring minimal level of entropy, only as a guideline to nudge users towards more secure passwords (_often though, it encourages the wrong approach anyway which ironically lowers security through other means_). A dictionary check is only as good as the dictionaries you have... Are you going to select words by some sort of ranking like frequency in literature, password leaks, accommodate for modifiers (especially common ones), other languages? What about legitimately secure passphrases, will you set off a false-positive accidentally? - **dizzy pig keeps cute paper** is an example of a 44-bit strong secret, pair that with a slow hash (_bcrypt work-factor 10_) and it'd take 7 years on average with 10 Nvidia RTX 4080 GPUs. That's assuming the attacker already knows the exact rule-set to match that 44 bits of entropy (_it's not just 5 words randomly sequenced from a single dictionary - it's multiple dictionaries to conform to a specific sentence structure_). If the attacker does not know that, the difficulty is higher. - **insane deer and comical boar remember rare raven in jordan**: 7 million years.. (64 bits of entropy) Just do something like that, or endorse password managers that generate unspeakable gibberish. Pair that with 2FA / MFA, job done :sunglasses: > Basically, we want passwords generated by complex generators (secure random 24+ bytes works) to be hashed using SHA-512 and everything else to be hashed with BCrypt or Argon. This is the original problem statement. Right.. so knowing how biased humans are for DIY input, (_despite accounting for all that entropy reduction in the process makes sense_)... you'd still not know some heuristics like _"is this totally secure looking password used anywhere else, just waiting for the user to get compromised on any of those platforms?"_ `qwerty12345UIOP67890asdf!` (24 chars) - Some pattern bias to workaround whatever requirements are enforced, typical placement and choice for a special char - Can you add rules to detect that... sure? But do you want to be maintaining such a thing...at what point does the user get frustrated (_or the feature lose it's relevance because the majority are just given the slow path fallback anyway_) Might as well just generate the randomized password?: - `Q%un!oQ5aKe@as&zzk29!KdX` (24 chars, 148-bit) - Alphanumeric, lower+upper case, 10 symbols, total 72 chars (_bitwarden generator charset_) - Your worse-case `1e19` size is approx 63-bit, which we can match approximate with this pattern at 10 char length (61.7-bit), or with 11 chars (67.9-bit). Reduced entropy representation: `Q%un!oQ5aK` (10 chars, 61.7 bits) - Using some light slow hashing can augment a 44-bit passphrase to a similar difficulty while being much easier to remember and input. --- > That’s STILL 31 years for 24 characters. Sorry, in your response you didn't mention how you're calculating that time. In my previous one, I cited previous mentions of 10x Nvidia RTX 3080 attacking SHA-256, and updated it with the newer 4080 generation. 1. Nvidia RTX 4080 hashrate for SHA-512 is `4460.2 MH/s` (4.46e9, or for 10x units: 44.6 billion / sec) 2. `log2(1e19) = 63.12-bit` (`100^24` reduced to `1e19`, aka 63-bit entropy) 3. `((2^63.12 / 44.6e9) / (60*60*24*365)) / 2` = **3.56 years** Looks like you were roughly basing that off 1 RTX 4080, is that correct? (_`35.63 years` to reach 50% of keyspace_) I'm not sure what an example of your 24 char secure password would look like, but it's probably somewhere between these two (_single RTX 4080 at 50% keyspace_): - `Q%un!oQ5aK` (61.7-bit): 13.32 years, add one more char to length for at least 67.9 bits and you have approx 979 years. - `dizzy pig keeps cute paper` (44-bit): 32.87 minutes (_SHA-512_) vs 69.73 years (_bcrypt work-factor 10: `((2^44 / 4e3) / (60*60*24*365)) / 2`_). - `detailed snail summons slim lab coat` (48-bit): 8.77 hours (_SHA-512_) vs 1115 years (_bcrypt `wf=10`, even at `wf=1` it's still over 1 year, and `wf=5` is almost 35 years_) Just look at the difference bcrypt is making there for 44-bit. If you're comfortable with a security level of 31 years, drop the work-factor by 1 and halves to approx 35 years. If you like, keep lowering the work-factor. Keep in mind that the security concern is with the targeted attack who has far better resources (_RTX 4080 are not the best hardware for bcrypt hashes to dollar ratio; so consider a decent amount of margin when the value to attack is high_). The great thing about the examples I've provided is that **Kerckhoff's Principle** is in full effect. No reduction needs to be accounted for - that is the best attack to optimize for, no false-positives to worry about. However passphrases like that are not as useful for a single SHA-512 hash, as the required length becomes less reasonable, but probably still better UX for manual input / recall.
--- Before writing any code, consider: - How these heuristics would be approached, look into existing solutions and their experiences, how well did they actually work. - How many users passwords would pass those heuristics or go to the fallback route if there is no feedback cycle with the user. - Realistically what is the load-level impact on a system like; what sort of resource / cost savings are you gaining with SHA-512 vs relaxing the slow hash settings to be less intensive when a baseline for entropy is guaranteed. - Are you harming UX (and thus security) with these heuristics for the users input to pass.