Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Entropy isn't sufficient to measure password strength

benwr.net

Post reply on HN
Print view View original

21–30 of 124 posts

Re: Entropy isn't sufficient to measure password strength

#21

Post by iflp »

canjobear wrote: post #15
iflp wrote: post #14

Earlier quoted context omitted.

Kolmogorov 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.

You 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?

It 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.

Re: Entropy isn't sufficient to measure password strength

#22

Post by taeric »

bigiain wrote: post #12

> 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 ba…

I'm curious if you have a rotation/audit practice for those? With 600 odd passwords, I'm not even sure how I would keep track of access to the items being protected.

Re: Entropy isn't sufficient to measure password strength

#23

Post by mojuba »

krupan wrote: post #18

When 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, a…

In 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.

Re: Entropy isn't sufficient to measure password strength

#25

Post by Aerroon »

krupan wrote: post #18

When 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, a…

Hopefully never. Or at least not in the near future. Almost every other method is going to have privacy implications because they will rely on something you have or something you are. You can't compel passwords in a similar way that you can compel people to give physical tokens or fingerprints or retina scans.

Re: Entropy isn't sufficient to measure password strength

#26

Post by taeric »

krupan wrote: post #18

When 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, a…

I'm curious how you think these other items work. They ultimately boil down to a shared secret that is beyond what you can remember. Which... isn't the best thing, necessarily.

Consider, if I leave my hardware token at home when I go on vacation, I'm basically locked out of all of my accounts. This is fine, as I typically plan for this to be the case. But it is an attack vector. I can't even audit my protected assets while away.

Re: Entropy isn't sufficient to measure password strength

#27

Post by nextaccountic »

bigiain wrote: post #12

> 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 ba…

> 5 misspelled-and-with-random-punctuation words

Why misspell and add random punctuation?

Re: Entropy isn't sufficient to measure password strength

#28

Post by lmm »

canjobear wrote: post #15
iflp wrote: post #14

Earlier quoted context omitted.

Kolmogorov 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.

You 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?

It's easy to calculate an upper bound on the Kolmogorov complexity of a given value (you just have to exhibit a Turing machine that computes it), but very hard to prove a lower bound (you would have to prove something about all possible Turing machines).

Re: Entropy isn't sufficient to measure password strength

#29

Post by Biganon »

nextaccountic wrote: post #27
bigiain wrote: post #12

> 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 ba…

> 5 misspelled-and-with-random-punctuation words Why misspell and add random punctuation?

So that they can't be found in a dictionary

Granted, 5 words chosen truly randomly from an English dictionary is already insanely strong, but why not make it slightly stronger?

Re: Entropy isn't sufficient to measure password strength

#30

Post by c0balt »

nextaccountic wrote: post #27
bigiain wrote: post #12

> 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 ba…

> 5 misspelled-and-with-random-punctuation words Why misspell and add random punctuation?

Most likely to make dictionary attacks against the password(s) ineffective.
Post reply on HN