12 ms·
Entropy isn't sufficient to measure password strength
- pmw 5y agoThis is a good place to advertise https://phrase.shop https://phrase.shop - a webapp I wrote that makes secure yet memorable passphrases. It makes entropy requirements explicit, and you can even roll your own dice to supply the required entropy to generate your passphrase. Try it, it's fun!
- bell-cot 5y agoMaybe I just don't have trendy-enough coworkers or friends...but I know of no one who actually analyzes password strength in terms of Shannon entropy. Cripes, the very first sentence of the Wikipedia page for Shannon entropy tells us that it's an average. Simple analogy - if the goal was to protect your house from a 9-foot-deep flood, would a dike with an average height of 10 feet do the job?
- dcl 5y agoYep one of those cases, where an ensemble average is not at all relevant for describing the situation.
- benwr 5y agoI've done a fair bit of research into this, and as far as I can tell, the entire internet does this thing you've never seen. For example, https://en.wikipedia.org/wiki/Password_strength#Entropy_as_a_measure_of_password_strength https://en.wikipedia.org/wiki/Password_strength#Entropy_as_a... implies the use of Shannon entropy.
- bell-cot 5y ago[sigh...] +1, though you're making me feel d*mn old. I won't tell you what decade it was, when I found that some "bright" user had picked his/her own office phone # (10 digits, 2 hyphens) to use as a "high security" password. My own mental model - with a decent compression algorithm, and compression dictionary pre-loaded with popular passwords and personal information, how many bits would the specific password in question compress to? That also catches the clever folks who pick stuff like "abcdabcdabcdabcd" or "3.1415926535".
- adgjlsfhk1 5y agoThe real question here is if there are any actually used password strategies where this distinction matters? In practice, no one would ever use the type of password strategy described.
- benwr 5y agoThis is a fair question; I've been thinking about "weird" password choice strategies recently, for which it can matter. For example, if you want your password to be an English sentence, choosing sentences based on random parse trees will produce duplicated sentences with ambiguous parses.
- iflp 5y agoKolmogorov complexity/entropy is more suitable for this purpose, under the implicit assumption that password crackers don't have tailored prior knowledge and are just enumerating "simple" sequences. It only agrees with Shannon entropy on long ergodic sequences. The author basically constructed an example where the two notions don't agree.
- canjobear 5y agoHow would you estimate the Kolmogorov complexity for the author's example?
- iflp 5y agoKolmogorov complexity is only unambiguously defined asymptotically, and "asymptotics is merely a heuristic". It is also uncomputable. So, to use entropy arguments for passwords, the only correct way I could think of is to generate long and (elementwise) random passwords.
- canjobear 5y agoYou asserted that Kolmogorov complexity will disagree with Shannon entropy in this example, so how do you know what the Kolmogorov complexity of this example is?
- iflp 5y agoIt is a random variable in this setting, as it is a function of the randomly generated password. Given a deterministic sequence, you find the definition of its Kolmogorov complexity in textbooks/Wikipedia/etc. By saying the Kolmogorov complexity will disagree with Shannon entropy, I meant the former, which is a random variable here, does not converge to the latter, contrary to the standard asymptotic setting which probably gives people the idea of using entropy to characterize password (I don't know, don't work in security). The point of my original post is that the asymptotics break down here, and this phenomenon is not poorly understood, at least in some other communities. It is not meant to provide an alternative that is always well-defined and useful, although as I said in the grandparent comment, there is the useful implication that you can stay safe by sticking to the asymptotic regime.
- Bolkan 5y agohttps://xkcd.com/936/ https://xkcd.com/936/
- voiper1 5y agoInstructions unclear, password on all sites is now "correct horse battery staple". Inspired by this, there's a package https://github.com/dropbox/zxcvbn https://github.com/dropbox/zxcvbn to estimate entropy and give suggestions.
- BoiledCabbage 5y agoFundamentally is there any flaw with this method? Or a reason why it isn't better than general password approach?
- kbart 5y agoIt's vulnerable to the dictionary-based attacks that are very common.
- rini17 5y agoThat is a sadly too often repeated lie. If you know otherwise please explain/link how the attack works, how can you guess the 4 words? Effectively, that would mean requiring much less than 2^44 attempts as xkcd explains.
- willis936 5y agoDiceware is designed to make passwords against dictionary attacks. Estimates of diceware entropy begin with the assumption that an attacker has the dictionary. A dictionary with 6^5 entries would take 6^5^N guesses to exhaust (assuming the entries are randomly chosen). 6^5^4 = 2^52.
- throwawayffffas 5y agoYou can only remember a limited number of passwords regardless of whether it's a sequence of words or a sequence of random characters. The main flaw in all these schemes is that you have to remember them. The only viable option is to use a password manager.
- BeefWellington 5y agoThere's a bit of a logical flaw here in that the argument is made against average entropy of a set of passwords, rather than individual entropy of each chosen password. This is an argument I can't find anyone making: an aggregate average entropy of the set of all passwords you use is fine for password security, rather than the entropy of each individual password. As far as I can tell this seems to be a (possibly intentional?) misunderstanding on the author's part.
- less_less 5y agoEntropy and min-entropy are properties of distributions, not of individual samples from those distributions. So there's no meaning to "the entropy of each chosen password".
- dbaupp 5y agoDespite that slight misuse of terminology, the point stands: the article talks about estimating the entropy of a distribution used for generating a password, but the important thing is the “distribution” an attacker is using for guessing the password. A single password should instead be treated as a sample from a (plausible) attacker’s distribution, and the complexity of that password can be used to estimate the size of the sample space required for that plausible attacker (as in, how many guesses/how much work they’ll have to do). This is, AIUI, the approached used by libraries like https://zxcvbn-ts.github.io/zxcvbn/ https://zxcvbn-ts.github.io/zxcvbn/ The entropy of a distribution for generating passwords matters when generating them in bulk, such as OTPs or implementing a password manager. This doesn’t seem to be the situation being discussed in the article, which is more about rating a user-provided password.
- less_less 5y agoZxcvbn is also a good idea, but it's a complementary approach. The user or password manager should generate secure passwords (using a high-min-entropy distribution), and the website or application should check that they're secure (using zxcvbn or similar). Of these two approaches, a high-entropy generation method gives more confidence. It gives a mathematical strength "guarantee": if you design and follow the method correctly, then an attacker, whether or not they know the generation method, is mathematically unlikely to guess your password quickly no matter what order they guess in. "Guarantee" is in quotes because of course the attacker could get very lucky or the user could get unlucky (eg generate a uniformly random 8-character string and it happens to be "password"), and also if there's eg an implementation flaw then your guarantee isn't worth the pixels it's printed on. By contrast, zxcvbn has no guarantee, because it doesn't use a huge curated dictionary and generation mechanism that the attacker is likely to use. So in addition to missing well-known passwords like "correct horse battery staple", it will miss bad passwords related to current events.
- teeray 5y agoIt’s important to remember that attackers get no information on how close they are (assuming good hashing practices). It is unknowable to them if you went with the correcthorsebatterystaple approach or placed your cat on the keyboard for a few minutes. Given that, a simpler alphabet with longer strings > more complexity with shorter strings.
- bigiain 5y ago> Because choosing good passwords is about memorableness as well as sheer strength That's not been true ever since the development of good password managers. There are fewer than 10 passwords I remember. One of them is my password manager's master passphrase (5 misspelled-and-with-random-punctuation words). The others include stuff like my work and home laptop/disk passwords, which I can't autofill, my 3 important banking passwords which I do not even entrust to my password manager, and my AppleID password because iOS is annoying enough at asking for that that I'm using one I can remember. The other ~600 entries in my password manager are 25 random characters (or whatever the upper limit if password length is for sites/services that are 'doin it wrong').
- omegalulw 5y ago> That's not been true ever since the development of good password managers. A lot of people (do not trust password managers, case in point the recent last pass scare. You want passwords to your key accounts to be 1) memorable 2) strong 3) only in your head. For these, I think the article is fairly relevant.
- awelxtr 5y ago> A lot of people (do not trust password managers, case in point the recent last pass scare. That's no excuse. KeePass allows having the database file locally where it's you duty to manage it. It might be less convenient, maybe. But I don't see valid excuses for people to not start using a password manager, even less the less tech savvy people.
- shepherdjerred 5y agoIt’s completely valid to distrust password managers. No software is free from bugs, or accidentally exposing your passwords. It might take a lot of work, but it’s certainly possible. There’s also the possibility of mismanaging your password database and losing all of your data.
- 5y ago
- canjobear 5y agoCool example. An attacker will take 2^234 guesses on average to guess the password, but that's an average of 19 1's and one enormous number. So the attacker will usually guess the answer quickly. It's kind of like the St. Petersburg paradox in that the expectation value doesn't reflect typical behavior. Seems like this might be a use case for "dispersion" (the second moment of entropy) [1]. [1] https://math.stackexchange.com/questions/1626522/higher-moments-of-entropy-does-the-variance-of-log-x-have-any-operationa https://math.stackexchange.com/questions/1626522/higher-mome...
- krupan 5y agoWhen will we stop using passwords?! They are an elementary school kid “secret club” game taken way, way too far. They are totally broken. Nobody can come up with and remember good passwords. Nobody can store passwords securely. 100% busted. Instead of continuing to debate what makes a good password, we need to put our energy into better techniques altogether! No more shared secrets! Let’s talk about one-time codes, asymmetric key cryptography, hardware tokens, anything but passwords!!
- rkeene2 5y agoThe US Government thought they were bad, and got rid of them. In 2004 (Thanks George W. Bush!)
- mojuba 5y agoIn one of my current web-based projects I decided to experiment with magic links sent via email. They are pretty convenient (and secure enough) but turns out there's a problem with mobile email clients: they tend to open links in isolated embedded browsers and then forget the cookies. For most non-technical people this is a show stopper unfortunately. I then went with one-time 6-digit sign in codes that are emailed to the user. These are secure enough if done right, but now I'm wondering if they will feel secure to the users. P.S. I might change it to a one-time alphanumeric code, which should feel more secure.
- voiper1 5y agoSometimes the magic links or codes expires in X minutes. That helps them feel secure. But like password resets, you're hosed if your email is hacked (unless you have 2FA).
- mojuba 5y agoNot only expiration, you also limit the number of attempts, the IP address, you verify an additional nonce token generated for the specific request, etc. The security of your email is typically taken care of by a more sophisticated system like GMail, that will do captcha, they remember your geographic region, your habits, etc. Given the above, I'd say alphanumeric one-time codes are better in terms of entropy and feel. They look like passwords but you don't need to remember them.
- deleted 5y ago[deleted]
- croes 5y agoI thought it's the entropy of the chosen password not about the entropy of the possibilities of password you could choose
- benwr 5y agoEntropy of a single password isn't actually a well-defined concept; entropy is always about a distribution. "Entropy calculators" that look at your password and tell you "its entropy" are making assumptions about how you chose the password. We care about the distribution from which you drew the password, because that lets us analyze how difficult it would be for an attacker who knew your password selection process to brute-force the password. Just knowing the password itself isn't enough information to determine that (though of course you can judge how hard it would be for an attacker once you know their brute forcing strategy).
- khana 5y ago
- iechoz6H 5y agoI typically use a phrase from my life e.g. MathsDegree@StamfordWasABigWin [1] RanThroughAPlateGlassDoorWhenTen [2] with some esoteric obfuscation rules. 1. I don't have a maths degree from Stamford. 2. Did happen, not one of my passwords.
- MattPalmer1086 5y agoThe argument feels like a straw man. He seems to be saying, if your password selection strategy skews towards really weak passwords, and you measure the Shannon entropy of the distribution, it won't reveal that this is a bad strategy. I don't know anyone who would actually do this and declare a win "because Shannon". At best, it's mildy interesting that Shannon entropy on its own isn't going to give you a useful answer if you have a weak strategy.
- willis936 5y agoHasn't this problem been solved for decades by diceware? Use words as your characters with a dictionary of a few thousand words. Assume an attacker knows the dictionary. Make passwords that are too long to brute force (40+ characters). Use enough words that a dictionary attack is also infeasible (4+). Add a salt if you're feeling extra spicy. Entropy is sufficient if you use the right language model.
- DarylZero 5y agoIt seems like it is still sufficient for passwords that are generated in a normal way.