0936: "Password Strength"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

User avatar
ahammel
My Little Cabbage
Posts: 2135
Joined: Mon Jan 30, 2012 12:46 am UTC
Location: Vancouver BC
Contact:

Re: 0936: "Password Strength"

Postby ahammel » Mon Feb 25, 2013 7:25 pm UTC

exoren22 wrote:That's why they have one-time use backup codes. Just don't ALSO get THOSE stolen, and you're fine. Otherwise, Google does have another recovery system, but it involves personal, identifying documents and several days' wait.

You can also give them an emergency backup cell number.
He/Him/His/Alex
God damn these electric sex pants!

User avatar
Jorpho
Posts: 6108
Joined: Wed Dec 12, 2007 5:31 am UTC
Location: Canada

Re: 0936: "Password Strength"

Postby Jorpho » Wed Feb 27, 2013 6:51 am UTC

exoren22 wrote:
Jorpho wrote:I don't even bother with a cell, and paying $20 a month so I can authenticate passwords seems a bit steep.

Just print out the "backup" codes, or have the system call you with a code each time, if you have google voice you can find a way to make it free. Keep the codes (ten at a time) in your wallet and regenerate them as you run out. Not as secure, sure, but you can always regenerate them from your "trusted" computer should the current list ever be compromised.
I don't understand. Google asks me for a number that can accept SMS, and I have no such number.

User avatar
Jorpho
Posts: 6108
Joined: Wed Dec 12, 2007 5:31 am UTC
Location: Canada

Re: 0936: "Password Strength"

Postby Jorpho » Thu Mar 28, 2013 2:04 am UTC

All right, I finally had a look at this today and it turns out Google does allow verification by voice now.

Except the way it establishes a computer as trusted is with a cookie – so if you don't have cookies, you have to verify every single time you log in! I guess I don't really know exactly how they would do it otherwise – some combination of heuristics and geographic or IP tracking, maybe, but cookies don't strike me as a particularly secure way of doing things. Besides, I don't see how this method would protect against XSS exploits, which are probably as likely as getting one's password stolen in most situations, I would think.

User avatar
Sakutarou
Posts: 6
Joined: Thu Mar 28, 2013 2:53 pm UTC
Location: Meta-World

Re: 0936: "Password Strength"

Postby Sakutarou » Thu Mar 28, 2013 11:55 pm UTC

So... I should make my password longer. That's what this comic is about, right?
When you don't know, the answer is a witch did it. With magic.

User avatar
vodka.cobra
Posts: 370
Joined: Thu Mar 27, 2008 6:50 pm UTC
Location: Florida
Contact:

Re: 0936: "Password Strength"

Postby vodka.cobra » Fri Mar 29, 2013 7:24 pm UTC

I tried to change my password and it won't let me use one longer than 30 characters. :(
If the above comment has anything to do with hacking or cryptography, note that I work for a PHP security company and might know what I'm talking about.

mishka
Posts: 48
Joined: Mon Mar 28, 2011 3:47 am UTC

Re: 0936: "Password Strength"

Postby mishka » Thu Apr 25, 2013 12:05 am UTC

The worst case scenario is that someone hacks into your website, and figures out a way to have the login script save passwords to a file. It happened to a web site I use.


Ways to make Randall's proposal more secure: run your password phrase through Vigenerre's cipher, it will give the appearance that it is a bunch of randomly generated text.
batteryhorsestaple with the key of correct will generate: dokkitrjcijiumcdcv
Run your password phrase through SHA-1 will generate: bf16d84515397ea643be89509f02a7af6b23ceb6 (arguably the more secure option)


I don't understand. Google asks me for a number that can accept SMS, and I have no such number.

Google also allows for a phone call that tells you a verification code, so unless you're deaf and don't have a cell phone, you're still in luck.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Thu Apr 25, 2013 1:37 am UTC

mishka wrote:Ways to make Randall's proposal more secure: run your password phrase through Vigenerre's cipher, it will give the appearance that it is a bunch of randomly generated text.
batteryhorsestaple with the key of correct will generate: dokkitrjcijiumcdcv
Run your password phrase through SHA-1 will generate: bf16d84515397ea643be89509f02a7af6b23ceb6 (arguably the more secure option)
Running it through a hash doesn't make it more secure, because it's not like the hash adds additional random information. All it does in this case, like Vigenerre, is make it more difficult to remember, which goes against the whole point of the comic in the first place.

You don't care if your password "looks" random, because if someone actually gets hold of it, then they know your password, period. You just care if it actually *is* sufficiently random to be secure from a brute-force attack by someone who knows the whole algorithm you used.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

mishka
Posts: 48
Joined: Mon Mar 28, 2011 3:47 am UTC

Re: 0936: "Password Strength"

Postby mishka » Thu Apr 25, 2013 1:52 am UTC

If the point is having a long character length and high entropy, then have a forty character hash generated through SHA-1 will add a lot.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Thu Apr 25, 2013 3:07 am UTC

The point is having high entropy in an easy-to-remember form. Eight random alphanumeric characters will have the same entropy as Randall's method, but will typically be far harder to remember.

A hash of a password, on the other hand, adds no security on top of the original password, assuming (as we should) the worst case where the attacker knows your algorithm.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Eebster the Great
Posts: 2739
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 0936: "Password Strength"

Postby Eebster the Great » Thu Apr 25, 2013 4:01 am UTC

mishka wrote:The worst case scenario is that someone hacks into your website, and figures out a way to have the login script save passwords to a file. It happened to a web site I use.

It's called "phishing," and in some cases it can be done via cross-site scripting without needing to "hack" the host site at all.

elasto
Posts: 3102
Joined: Mon May 10, 2010 1:53 am UTC

Re: 0936: "Password Strength"

Postby elasto » Thu Apr 25, 2013 4:05 am UTC

gmalivuk wrote:The point is having high entropy in an easy-to-remember form. Eight random alphanumeric characters will have the same entropy as Randall's method, but will typically be far harder to remember.

A hash of a password, on the other hand, adds no security on top of the original password, assuming (as we should) the worst case where the attacker knows your algorithm.

Aye. If the attacker doesn't know how you generated your password, choosing four random words is good enough. And if he does, then hashing those four words doesn't add any entropy. So either way it's not worth doing.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Thu Apr 25, 2013 4:13 am UTC

Especially since, as previously discussed in this thread, hashing carries with it the (admittedly minuscule) risk that the hash of your super seekrit password will collide with the hash of something like "password". So it won't add any security, but has a small chance of pretty much eliminating it entirely. (This of course is the same reason you should reject certain passwords even if they are generated completely randomly, such as using Randall's method and ending up with "password password password password".)
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11045
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: 0936: "Password Strength"

Postby Yakk » Thu Apr 25, 2013 4:26 am UTC

If Randall's method returns "password password password password" or something similar, don't reject it and try again.

What almost certainly happened is that your random password generator is broken. This is far, far, far more likely than a functioning random password generator with that many bits of entropy at its command would return something like that.

This remains true even if you have personally proven that every line of the random password generator is correct, and it correctly generates random passwords. It may even be true if you are using a peer-reviewed password generator that the world's experts in password generation have validated as being a solid implementation. The odds are so far in favor of the password generator having a fundamental flaw that caused it to generate "password password password password" rather than something uniform and random that it would be hard to imagine the stacks of evidence required to tip the scales the other way.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Thu Apr 25, 2013 4:49 am UTC

The probability of having the same word 4 times in a row is about 2^-33, or 1 in 8 billion. The chance of this word being "password" (assuming it's one of your 2k) is 2^-11, giving 2^-44 (1 in 16 trillion). Neither of those probabilities are so astronomically low that I'd assume there must be a mistake somewhere else in a robust, heavily vetted system.

Sure, once you're in the neighborhood of hundreds of bits of entropy, the story is different, but that's not what I was talking about in this case.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
addams
Posts: 9417
Joined: Sun Sep 12, 2010 4:44 am UTC
Location: Gold Beach, OR; 97444

Re: 0936: "Password Strength"

Postby addams » Thu Apr 25, 2013 5:13 am UTC

Yakk wrote:If Randall's method returns "password password password password" or something similar, don't reject it and try again.

What almost certainly happened is that your random password generator is broken. This is far, far, far more likely than a functioning random password generator with that many bits of entropy at its command would return something like that.

This remains true even if you have personally proven that every line of the random password generator is correct, and it correctly generates random passwords. It may even be true if you are using a peer-reviewed password generator that the world's experts in password generation have validated as being a solid implementation. The odds are so far in favor of the password generator having a fundamental flaw that caused it to generate "password password password password" rather than something uniform and random that it would be hard to imagine the stacks of evidence required to tip the scales the other way.

That was good.
What happens when the Random Generator is Generating Non-Randoms?

Is That like Hell Freezing Over?
Spoiler:
I watched a Screen with a sweet story.
Inside the Sweet Story it was Explained.

There is a prayer for Everything.
One minor Character's Profession was Praying.
Well; Sort of;

The people would come to him with Problems.
How do we pray for This?
What Prayer can we Honestly say for that?

The Characters spoken lines were, "There is a Prayer for That."
He said those words over and over.
He was comic relief? The whole thing was a comedy.

There were some Deep Serous moments.
Like comic relief, Upside Down.

I think in This Forum.
We have an equation for That.

We could mix the two.
An equasion that will hold back the Uncertinty.
And, A Prayer that takes it out of Our Hands and Puts it in God's Hands.

What did That Man Pray? Mr. Peabody's way back.

"May God Bless The (fill in the blank.)
And; Keep The (fill in the blank.)
Far From Us."


Great Little Prayer.

I also like, "Let them that love me, love me.
Them that do not love me; May God turn their Hearts.
Those that have Hearts that will not turn;
May God turn their ankle;
That I may know them by their Limping.


I like that one, too.

ok. Who's been praying?!
Stop it! I am tired of Limping and I don't want to change my Heart.
If I don't Love you, there must be a Damn Good reason!
Life is, just, an exchange of electrons; It is up to us to give it meaning.

We are all in The Gutter.
Some of us see The Gutter.
Some of us see The Stars.
by mr. Oscar Wilde.

Those that want to Know; Know.
Those that do not Know; Don't tell them.
They do terrible things to people that Tell Them.

mishka
Posts: 48
Joined: Mon Mar 28, 2011 3:47 am UTC

Re: 0936: "Password Strength"

Postby mishka » Thu Apr 25, 2013 7:10 am UTC

gmalivuk wrote:The point is having high entropy in an easy-to-remember form. Eight random alphanumeric characters will have the same entropy as Randall's method, but will typically be far harder to remember.

A hash of a password, on the other hand, adds no security on top of the original password, assuming (as we should) the worst case where the attacker knows your algorithm.

However, if you use a hash as your password, you only have to remember the input.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Thu Apr 25, 2013 7:19 am UTC

But it still doesn't add any security the input didn't have to begin with, at least for a single independent password.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Eebster the Great
Posts: 2739
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 0936: "Password Strength"

Postby Eebster the Great » Thu Apr 25, 2013 10:23 pm UTC

gmalivuk wrote:Especially since, as previously discussed in this thread, hashing carries with it the (admittedly minuscule) risk that the hash of your super seekrit password will collide with the hash of something like "password".

But as was also already pointed out, this is still far lower than the probability of an attacker happening upon your password by brute force anyway, so I don't know why it keeps getting brought up. It's a nonexistent problem.

Amarpal
Posts: 6
Joined: Tue Apr 23, 2013 10:21 am UTC

Re: 0936: "Password Strength"

Postby Amarpal » Sat Jun 08, 2013 11:23 am UTC

Interesting development: http://www.schneier.com/blog/archives/2013/06/a_really_good_a.html

"This is an answer to the batteryhorsestaple thing."

User avatar
Eebster the Great
Posts: 2739
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: 0936: "Password Strength"

Postby Eebster the Great » Sat Jun 08, 2013 4:38 pm UTC

Amarpal wrote:Interesting development: http://www.schneier.com/blog/archives/2013/06/a_really_good_a.html

"This is an answer to the batteryhorsestaple thing."

Randall is well aware of combinators. But his password scheme has sufficient entropy so any attack, no matter how well-devised, is unlikely to recover your password quickly enough.

Actually though, if the attacker can accomplish a billion guesses per second and knows exactly the scheme Randall used, it will only hold up for about 5 hours. So if you really want a secure password, you should choose each of the four words from a 4000-word dictionary, not a 2000-word dictionary.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Sat Jun 08, 2013 7:13 pm UTC

I don't think it was meant to be a counter to the comic, but rather a confirmation of the point made therein. A lot of the "hard" ones these guys cracked were of the mangled "trebuchet" variety; none were like "correcthorsebatterystaple".

Also, using a 4000-word list increases the entropy by 8 bits, while adding one more word from the 2k list adds 11. Though I suppose it's easier to remember fewer words, even if each word is a bit less common on average.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

WriteBrainedJR
Posts: 79
Joined: Tue Apr 16, 2013 3:08 pm UTC
Location: Right Behind You
Contact:

Re: 0936: "Password Strength"

Postby WriteBrainedJR » Sat Jun 08, 2013 10:11 pm UTC

gmalivuk wrote:I don't think it was meant to be a counter to the comic, but rather a confirmation of the point made therein. A lot of the "hard" ones these guys cracked were of the mangled "trebuchet" variety; none were like "correcthorsebatterystaple".

Also, using a 4000-word list increases the entropy by 8 bits, while adding one more word from the 2k list adds 11. Though I suppose it's easier to remember fewer words, even if each word is a bit less common on average.

I suspect the main problem with adding another word is that you start to run into issues with a lot of sites' maximum password lengths.

User avatar
cjmcjmcjmcjm
Posts: 1158
Joined: Tue Jan 05, 2010 5:15 am UTC
Location: Anywhere the internet is strong

Re: 0936: "Password Strength"

Postby cjmcjmcjmcjm » Sun Jun 09, 2013 8:44 pm UTC

WriteBrainedJR wrote:
gmalivuk wrote:I don't think it was meant to be a counter to the comic, but rather a confirmation of the point made therein. A lot of the "hard" ones these guys cracked were of the mangled "trebuchet" variety; none were like "correcthorsebatterystaple".

Also, using a 4000-word list increases the entropy by 8 bits, while adding one more word from the 2k list adds 11. Though I suppose it's easier to remember fewer words, even if each word is a bit less common on average.

I suspect the main problem with adding another word is that you start to run into issues with a lot of sites' maximum password lengths.

A site with a maximum password length is a warning to me that the password might be transmitted in plaintext.
frezik wrote:Anti-photons move at the speed of dark

DemonDeluxe wrote:Paying to have laws written that allow you to do what you want, is a lot cheaper than paying off the judge every time you want to get away with something shady.

User avatar
Copper Bezel
Posts: 2416
Joined: Wed Oct 12, 2011 6:35 am UTC
Location: Web exclusive!

Re: 0936: "Password Strength"

Postby Copper Bezel » Sun Jun 09, 2013 9:41 pm UTC

The Scrabble dictionary lists 1,500 three-letter words. Just sayin'. = ) (Not that many of them are really any more familiar than a random string of three letters, but knowing that it's a word with a meaning would still make it easier to remember.)
So much depends upon a red wheel barrow (>= XXII) but it is not going to be installed.

she / her / her

User avatar
ucim
Posts: 5564
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 0936: "Password Strength"

Postby ucim » Mon Jun 10, 2013 2:02 pm UTC

cjmcjmcjmcjm wrote:A site with a maximum password length is a warning to me that the password might be transmitted in plaintext.
No, it is an indication that after a certain point (based on the size of the resulting hash), longer passwords do not provide more security, they just increase the number of collisions.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11045
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: 0936: "Password Strength"

Postby Yakk » Mon Jun 10, 2013 7:06 pm UTC

ucim wrote:
cjmcjmcjmcjm wrote:A site with a maximum password length is a warning to me that the password might be transmitted in plaintext.
No, it is an indication that after a certain point (based on the size of the resulting hash), longer passwords do not provide more security, they just increase the number of collisions.
What?

No.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Mon Jun 10, 2013 7:23 pm UTC

ucim wrote:
cjmcjmcjmcjm wrote:A site with a maximum password length is a warning to me that the password might be transmitted in plaintext.
No, it is an indication that after a certain point (based on the size of the resulting hash), longer passwords do not provide more security, they just increase the number of collisions.

Jose
Even if that's true, it's a stupid policy. There is far more entropy in an average 100-character English sentence than there is in an average attempt at making a good 12-character password.

Also, you're completely wrong about how collisions work in any hashing algorithm I know of.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

WriteBrainedJR
Posts: 79
Joined: Tue Apr 16, 2013 3:08 pm UTC
Location: Right Behind You
Contact:

Re: 0936: "Password Strength"

Postby WriteBrainedJR » Mon Jun 10, 2013 7:31 pm UTC

gmalivuk wrote:
ucim wrote:
cjmcjmcjmcjm wrote:A site with a maximum password length is a warning to me that the password might be transmitted in plaintext.
No, it is an indication that after a certain point (based on the size of the resulting hash), longer passwords do not provide more security, they just increase the number of collisions.

Jose
Even if that's true, it's a stupid policy. There is far more entropy in an average 100-character English sentence than there is in an average attempt at making a good 12-character password.

This is why the password to my computer is a 100 character sentence with punctuation.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Mon Jun 10, 2013 7:35 pm UTC

Which has as much entropy (and is as likely to collide with any other given hash, assuming you're not using a shitty algorithm with less than 110 bits of possible outputs), as an 18-character completely random alphanumeric (upper and lower case) password.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Copper Bezel
Posts: 2416
Joined: Wed Oct 12, 2011 6:35 am UTC
Location: Web exclusive!

Re: 0936: "Password Strength"

Postby Copper Bezel » Tue Jun 11, 2013 7:51 am UTC

How do you get that? I mean, I'm not arguing - I don't really understand this stuff, but I'm curious. I get 107 bits of entropy out of the alphanumeric string. A string of 100 characters of truly random words is roughly 16 words, if spaces are included (so that the average length is 6.1 characters,) which makes it an average-length sentence and leaves two characters for punctuation, or three if I remove that last space character (and the punctuation is determined by grammar, so those characters don't normally add any entropy, regardless of what pandas might be eating or shooting.) You started from a 2000-word dictionary, so I made that assumption, and with 16 "characters" and 2000 possibilities each, I get 175 bits of entropy, which is much more than the alphanumeric string, but assumes random words in a random order.

Obviously, though, a real sentence isn't random words in random order, and treating it as one also assumes a lexical density of nearly 1, which is nonsense (and the sentence would be, too.) That makes me think that you're accounting for those factors somehow.

Just assuming that non-lexical words also have an average length of 5.1 characters + a space and leaving them out as if they're determined absolutely by grammar gets me 88, but of course, non-lexical words are typically shorter, and they're not totally determined by the other words in the sentence. So I can give myself a lower bound, too, and your 107 is in between the two bounds I'd found.

So how did you do that? = )
So much depends upon a red wheel barrow (>= XXII) but it is not going to be installed.

she / her / her

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Tue Jun 11, 2013 11:49 am UTC

I did that by remembering that written English has an entropy of about 1.1 bits per character.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
Yakk
Poster with most posts but no title.
Posts: 11045
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: 0936: "Password Strength"

Postby Yakk » Tue Jun 11, 2013 12:02 pm UTC

gmalivuk wrote:I did that by remembering that written English has an entropy of about 1.1 bits per character.

This comes from a seminal work on communications entropy by Shannon.

Imagine a game where you take a sentence, and you randomly hide characters. How hard is it to guess the right character? What if more than one character is hidden?

Sometimes the character will be obvious. "S?e sells sea shells by the sea shore" (almost certainly 'h'). Sometimes it won't be. "That is a real d?g." ('o' and 'i' are both legal and roughly equally reasonable).

( Shannon, Claude E.: Prediction and entropy of printed English, The Bell System Technical Journal, 30:50–64, January 1951. )
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Jorpho
Posts: 6108
Joined: Wed Dec 12, 2007 5:31 am UTC
Location: Canada

Re: 0936: "Password Strength"

Postby Jorpho » Tue Jun 11, 2013 1:25 pm UTC

As cited in the recent Twitter What-If.
http://what-if.xkcd.com/34/

User avatar
ucim
Posts: 5564
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 0936: "Password Strength"

Postby ucim » Tue Jun 11, 2013 1:43 pm UTC

It's just the pigeonhole principle.

Whatever way a password is hashed, the resulting hash is of a certain (usually fixed) size, which means that there are only a certain number of possible (hash) results. SHA-1, for example, has a 160 bit hash size. The hash of a password the size of War and Peace will still be stored in that space, and will probably share that hash with many other, smaller inputs.

160 bits, at 4 bits per hex digit, is 40 hex digits, which at two nybbles per byte, can encode 20 (extended) ASCII characters. Anything longer than that will collide.

Of course, you could simply use a longer hash, but whatever length you choose, that's it.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Tue Jun 11, 2013 3:09 pm UTC

But if your 100-character natural language sentence collides with a totally random 20-character password, with the obviously huge benefit of actually being practical to remember, it is a better password than the random string, and it should be permitted.

If the hash cuts off entropy at 160 bits, that still permits about a full Twitter post in normal English. If you're going to cut it off to avoid excess collisions, then that should be the cutoff, since you know most passwords will never have maximum entropy for their character length.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
ucim
Posts: 5564
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 0936: "Password Strength"

Postby ucim » Tue Jun 11, 2013 3:51 pm UTC

gmalivuk wrote:But if your 100-character natural language sentence collides with a totally random 20-character password, with the obviously huge benefit of actually being practical to remember, it is a better password than the random string, and it should be permitted.
True, but it gives the illusion that that 100 character password is unique. Maybe that's a harmless illusion.

You do have a good point though. One must consider the attack method as well as the entropy. It's always a balance between security and convenience, merely spelled differently.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Tue Jun 11, 2013 5:53 pm UTC

Your 100-character passphrase is orders of magnitude more likely to be unique than some amateurish mangling of a common word. The illusion that tr36uC#E7 is unique is a more widely believed illusion which is at the same time far less likely to be true.

Collisions or not, how can a short (less than, say, 30 characters) limit ever *help* security?

Edit: and what do you mean by attack method? Entropy values discussed in this thread generally assume worst-case scenarios, in which the attacker knows exactly how you generated your password. If your hash can be one of 2^160 possibilities, said attacker is as likely to find a collision among 20-character random strings as among 140-character potential Twitter posts. Which is to say, far, *far* less likely than he or she is to find your human-generated 20-character password on a stupid site that limits passwords to that size.

(Of course, you can make good passwords for those sites if you hash your longer passphrase yourself first, and then just paste that into the form.)
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
ucim
Posts: 5564
Joined: Fri Sep 28, 2012 3:23 pm UTC
Location: The One True Thread

Re: 0936: "Password Strength"

Postby ucim » Tue Jun 11, 2013 8:32 pm UTC

gmalivuk wrote:Your 100-character passphrase is orders of magnitude more likely to be unique than some amateurish mangling of a common word.
... but the resulting hash isn't, and it's the resulting hash that counts.

gmalivuk wrote:Collisions or not, how can a short (less than, say, 30 characters) limit ever *help* security?
A limit that is too short never helps security. More annoying are sites that prohibit commonly used punctuation, so I can't even use "can't" in the (long) password. It becomes harder to remember whether I used "cant" or "cannot" in the passphrase, and it's too late by the time I remember that this isn't one of those sites, and I used "can't". I've already been locked out and am now a support burden as I get the password reset again, whereupon I discover that the quote is permitted, but the period is not. grrrrrr!

As the person creating a password, I need to consider that the attacker knows how I came up with it (i.e. choose four words in French and run them together). However, as a website designer, I need to consider all possible attack methods on the database. If I encourage my users to do one thing (come up with a long French sentence), I would expect that an attacker would expect that my database is best attacked along those lines (i.e. with a French dictionary).

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Please help addams if you can. She needs all of us.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11045
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: 0936: "Password Strength"

Postby Yakk » Tue Jun 11, 2013 8:51 pm UTC

ucim wrote:
gmalivuk wrote:Your 100-character passphrase is orders of magnitude more likely to be unique than some amateurish mangling of a common word.
... but the resulting hash isn't, and it's the resulting hash that counts.

No, the resulting hash of a 100 character passphrase is more likely to be unique than some amateurish mangling of a common word after hashing as well, for any reasonable (even pretty short) hashing output. And by "more likely to be unique", I mean "less likely to collide with the hashed output of someone guessing passwords at random, biased by that generator knowing the methods that people use to generate passwords".

Because that is what we care about.

Banning long passwords because there are going to be collisions with longer passwords *hurts security*, because the space of passwords that people will actually use is sparse in the space of strings of a certain length. The entropy of your password system is something like the probability weighted log of the number of hash password outputs your users actually use, and by restricting password length you massively reduce the number of likely hash outputs, and as such strip huge amounts of entropy out of your password system.

Now, with a ridiculous hash size (1 bit!), adding longer passwords won't help -- but with even a modest hash length (32 bits), pretty long passwords remain useful, and with serious hash lengths (128 bits), you'd only want to limit password length to discourage people from copy-pasting book chapters and thinking they are more secure due to length.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 25782
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: 0936: "Password Strength"

Postby gmalivuk » Tue Jun 11, 2013 8:56 pm UTC

ucim wrote:
gmalivuk wrote:Your 100-character passphrase is orders of magnitude more likely to be unique than some amateurish mangling of a common word.
... but the resulting hash isn't, and it's the resulting hash that counts.
If my Twitter post passphrase collides with the hash for 20 random ASCII characters, and yours is just a mangling of "trebuchet", then an attacker is orders of magnitude more likely to get your actual password than to hit upon either my Twitter post or any of the shorter strings that collide with it. Meaning my passphrase is orders of magnitude better than yours.

As the person creating a password, I need to consider that the attacker knows how I came up with it (i.e. choose four words in French and run them together). However, as a website designer, I need to consider all possible attack methods on the database. If I encourage my users to do one thing (come up with a long French sentence), I would expect that an attacker would expect that my database is best attacked along those lines (i.e. with a French dictionary).
The whole point of this comic is that that won't help an attacker. Knowing every word in French won't help you pick the 10 I strung together in a particular order. Sure, you'll be better off than if you tried to brute force every possible string of that length, but if French has similar entropy to English, 140 characters of it will be as hard to brute force, even knowing that I've written a French Twitter post, as it is to brute force a random 160-bit string of hex.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 32 guests