Show HN: Entropy Based Password Validation | Hacker News Reader

Show HN: Entropy Based Password Validation

github.com

31 pointswagslane32 comments

I don’t understand what is raw or no-bullshit about this, although it makes it sound very serious.

The entropy depends on how the password is generated. If I choose ten words from my own dictionary then the entropy depends on the size of the dictionary. But if I re-rolled 15 times until I got words that I liked then one would have to decrease the entropy accordingly. But someone else couldn’t distinguish those two cases if they knew nothing about me (modulo common human psychology).

The point is that entropy depends on how the agent generated the password and has nothing to do with character sets or length in itself. So sure, this could be said to be a certain approach to approximating entropy in the general case, but I see no reason to put adjectives in front of “entropy-based password validation” which somehow suggest that it’s the number one, objective way to do it.

That seems backwards to me. The entropy should be relative to how the password is guessed, not how it was generated.

It doesn't make any difference to the attacker if I pick "bluecheese" out of a dictionary or as a result of successive random letter draws.

It does make a difference because the attackers have comparable sophistication to the generators.

They don't have to brute force all 26^10 lowercase character sequences if they can instead look through 26^3 words in a dictionary. And optionally modifying those words to append "1!" to them, or capitalize the first character, or replace e with 3 or whatever doesn't take much.

Right; so we seem to agree entirely that the entropy is relative to the attacker's generator.

Sure, but the attackers you want to consider are the ones who have generators that can match your minimum entropy to generate the password - assume their dictionary is no longer than yours, their set of punctuation doesn't have any characters yours doesn't, etc.

It depends whether you want to determine an upper bound or a lower bound on #guesses needed.

The article's approach has no assumptions and provides an upper bound. Your approach makes several assumptions and gives a lower bound IFF those assumptions hold.

The upper bound is useful for the general case: no attacker will be worse.

You're trying to account for more sophisticated attackers, which is great! It is however not clear (without further motivation) whether your attacker model is realistic. That is: will their be an attacker who knows this much about your password generation approach, but does not know more?

If no realistic attacker would know this much, your approach gives an overapproximation (real bound is higher). If, otoh, there is an attacker who knows more (eg, seed of the PRNG, or first characters, etc.), it'll be an underapproximation (real bound will be lower).

So, the difference is that the result of the first approach can directly be interpreted, while the result of your approach needs context.

The upper bound is a best case analysis. In the best case, I can choose “1” to be my password, and no one will ever guess it.

In the worst case, we assume that the attacker has done their home work and knows the algorithm by which the password was generated, but not the content of this particular password. So, knowing the algorithm, what can the attacker exploit that would help them discover the contents of this password in the shortest possible time?

I submit that the worst case analysis is really the only one we care about.

My point is that that is not the worst case. Example of a worse case: the attacker knows that + the first 2 characters of your password (real-life example).

The worst case would probably be something like "attacker knows hash, passwd algorithm, full state of machine at passwd generation time incl. random seed and all characters of the password but one". It is clearly far worse than your case, though I find your case more relevant than this one.

But if you assume that the attacker knows the generation process then you can make a very strong case that the password is no weaker than the stated entropy[1], since the attacker would have to effectively brute force the password by generating all possible passwords using that generator.

[1] Although I guess there are caveats: what if your password _happened_ to be weak according to another generation method that you didn’t use but the attacker guessed?

Lets say that you use method such as `openssl rand -base64 6` and out comes "password". The odds of that happening would be crazy low for an individual user. However, if you deploy the same generator for a billion people it could realistically happen, and you might want to filter against outputs like that. Of course if all passwords are autogenerated (users cannot choose), the attacker gains no advantage from choosing "password" instead of "tlnNHJ4x".

I suppose it comes down to a worst-case best-case type of thing. If you're trying to prevent Alan Turing and Bletchley Park (new band name I call it) from guessing your password given spies and psych profiles, you care about the entropy of the generation. In principle the best password actually is whatever the last one your opponent's cracking software tries. In between is the real world, but you can't go wrong with real random generation.

This is the correct answer. Password security is not an absolute thing, it's rather the case that a password is secure or insecure relative to an attackers ability to guess it. Interestingly enough, it's also the motivation for zxcvbn, the open source library chrome uses to evaluate password strength!

https://github.com/dropbox/zxcvbn

Not quite, if you take the a priori assumption that the attacker will test dictionary words, you don't want your password to be a dictionary word.

However, it's so incredibly unlikely a high entropy generator would generate a dictionary word that you shouldn't even have to worry about it.

Yes, entropy can only be measured in relation to an expected probability distribution. You need to have an a priori model for how the password is generated (selected) to estimate its entropy. So the dichotomy you set up is IMO a false one, in that you are guessing about how the password was generated.

Haha, couldn't agree more. Not to mention the "hacks" they use to artificially lower entropy of repeated characters.

So the password 1010101010101011101101000000010111011011101001010001001101011011 is calculated as only having a length of "2" and a base of 10. So it would be about 6 bits according to this. But the generation method clearly is generating a binary string with length 64, for a total of 64 bits of entropy.

It's related to Qvault, the password manager written by someone who keeps making very fundamental mistakes about cryptography in their blog.

Heyoo I remember you from Reddit. Qvault is no longer a password manager, though that was a fun project. I think I've corrected the mistakes in my articles that you pointed out, if you have found anymore I'm all ears.

This is nifty but I don't think implemented the way you'd want it to be.

You say you're basing it -- or are inspired by -- the xkcd comic. But the xkcd comic gets this calculation more-or-less right. Entropy is not a property of the character set used to generate the password, it's a property of the rule-set used to generate the password. Look at the comic: the "Tr0ub4dor&3" password isn't 11 random characters chosen from a set of 72 possibilities, and "correct horse battery staple" isn't 28 characters chosen from lower alpha + space.

The difficulty in calculating password entropy is that it's unclear whether or not the rule set will be known to the attacker or not. So an attacker which attempts "arbitrary length lowercase characters" will have a much harder time with "correct horse battery staple" than one that knows "exactly four common english words in lowercase separated by spaces."

Or, put differently, if you know someone has a numeric four-character bank PIN and they submit 1979, do you think this was four randomly chosen digits or do you think the entropy is effectively reduced by an obvious ruleset used to generate it?

Because you rely on character set validation, except for your clever cheat to artificially reduce the entropy of repeated characters, you will nearly always overstate the entropy of the password.

A sort of very naive naive refinement of the problem is that you want an engine that, knowing a password, finds the feasible lowest entropy ruleset that could generate the password and is human reasonable. I include the qualifier "feasible" because via overfitting even random characters have a lowest entropy ruleset (e.g. if by chance the third character is capitalized and the 18th is not, we should not assume that the same rules applied again would generate this property) If you find this unsatisfying because the problem is open ended, I'd at least caution you that the entropy values as stated are at best an indication of how long it would take a brute-force character search to break the password, not how long it would take an even modestly informed adversary to do so.

Hope this guidance turns the cogs a little.

Yeah, complexity sets are a bad method to estimate password entropy. Wheeler et al. [1] published pretty sound methods for estimating password entropy at the lower end of the entropy scale.

https://www.usenix.org/conference/usenixsecurity16/technical...

It does turn the cogs. If I'm understanding you, then your criticism isn't that I'm doing it wrong (I am lowering the base in relation the the ruleset) it's that I don't have struct enough rulesets, right? I need to break them down further?

These numbers seem off

I think he overestimating the security of passphrases

For example, the odds of guessing the correct 6 words (in order) from a 2000-word dictionary is approx. 1/10^20 combinations . 1 trillion guesses/second for a year is 3x10^19 guesses, so it takes just three years to guess it, not 10,000 years.

It's good to see entropy being used as the metric to judge passwords instead of complexity rules.

As others have commented, this isn't sufficient though, and will over-estimate the complexity of worded passphrases or l33t-speak. Password crackers are wise to those generation techniques and will brute-force combinations of those with more direct generation methods instead of generating from the underlying character set at random.

Complexity rules backfire if the minimum is done to meet them, like capitalise the first letter, append a number 0 and exclamation mark. A tool like this could (and probably should) check for those special cases and discount them from entropy, assuming conservatively that it's a weak password, ie. "P4ssw0rd0!" ~= "p4ssw0rd" ~= "password" ~= 13 bits (a single English word at random).

I'd also add that while that's a cool graph, it's going to age poorly as FLOPs/Watt is still on an upward trend. I wrote a password generator* which takes into account GCloud/AWS GPU prices and wholesale energy costs, along with Hashcat metrics, to recommend the number of bits of entropy for passwords. Looking 20 years into the future you'd probably want something closer to 82 bits entropy than 76, based on my calculations.

* https://github.com/aliclark/pragmatic-password-generator

It's somewhat ironic that this readme quotes an image that argues how counting character classes gives an incredibly distorted view of how complex a password is but then goes on to somehow completely miss the point and basically just count the character classes and the password length (which then proves the point of the xkcd comic by overestimating the ~28 bits of entropy password to have over 65 bits of entropy).

And the fact that this gives 'password123' a whole 51 bits of entropy should be a sign that it's an oversimplification. In fact if it wasn't for the fact that repeated characters are eventually ignored it would at least be guaranteed to always overestimate the entropy, as it is now it just punishes the use of long passwords using a small set of characters (again going directly against the quoted xkcd comic).

I submit that your password has roughly zero bits of entropy, if it is found in the Pwned Passwords list, or any other well-known list of passwords.

Long fully-random passwords in a password manager is what I recommend to friends and family. Using 32 alpha-numeric is what I use by default, with exceptions when other requirements are needed (symbols, etc). This ensures compatibility with pretty much everything.

62^32 = = 2.27e57

I always say: "If you can remember your password, someone can guess it"

What matters is the key derivation algorithm and any info the hacker has on his victim. Using your pet's and parent's names may meet all the criteria of high entropy but be easy to guess by someone who knows you.. Using a poor key derivation function means more guesses. That is why you should always use scrypt or bcrypt. So you make a simple password you will not forget, but use scrypt to convert this into a very long string and then use that string for AES256 encryption of the data.

How does this compare with zxcvbn, which is available in a bunch of languages (meaning you should get consistent “score” values for eg client side and server side)

I'm seeing a ton of great comments here. I'm going to start logging them as issues on the repo, if you have additional concerns or suggestions please feel free to do so as well.

Please add checking the entered password against the Pwned Passwords list. If found there, then the password has zero entropy.

Entropy is a subjective value, in that it depends on the observer's statistical model. Quite weak passwords can look high-entropy to a system like this, e.g. it's not going to know that "Make America Great Again" is a common phrase, or that the user is a security-illiterate Trumpist and therefore likely to use such a passphrase.

If you're generating passwords for users from these statistical models, and forcing them to use the first paraphrase you give them, talking about "raw entropy" would make more sense. It's still subjective, in that someone who knows the full machine state at generation time would probably see a different entropy, but at least that information is relatively hard to access.

when it comes to password strength, the number you are really interested in is something like probability of the password being generated by a naive human. Measuring raw entropy basically assumes that the only one non-random thing a user can do is repeat a character.

for example, by the p*log(p) measure

`1234567890abcdef` and `936a0ce28b1d74f5` both have log(16!) bits of entropy, yet one of them is much easier to guess than the other.

I really enjoy projects inspired by XKCD comics! Always cool to see ideas materialized by the community.

Is anyone aware of an overview/list of XKCD-inspired projects?

Reply on news.ycombinator.com