0936: "Password Strength"

[gmalivuk]

What's the advantage of this over KeePass? Easier to audit the code?

That, and the fact that in a pinch I can use it on someone else's computer if I need to. If I trust that person and re-skim through the source to verify that it's not phishing, it's equally easy to use on any machine running Firefox (since that particular implementation is, unfortunately, browser specific).

The main problem is that the comparison is wrong. It is much better if your password is not a word. That is what the strictest security advice suggests.

That is the advice because 1) you can fit more entropy into fewer characters that way, and some sites limit the size of the password you can use, and 2) it is unlikely that a person allowed to choose their own words will pick something with sufficiently high entropy, because we're bad and randomness.

In any case, correcthorsebatterystaple is *not* a word. It's four of them, chosen randomly. Which means that the total entropy is four times the entropy of each individual word.

The "logic" people keep using to criticize Randall's suggestion as being vulnerable to a dictionary attack is just as ridiculous as the following:
Your password obviously should not be just a 1 or a 0, as those passwords are stupidly easy to break. Therefore, your password should not consist of a concatenated string of random choices (with replacement) from the set {0,1}.

1,000 guesses per second is also a drastic underestimate when pretty much anyone can easily buy the hardware and software to do almost 3,000,000 guesses per second.

True. But of course if you'd read even just the most recent page or so of this thread, you'd see that the estimate wasn't intended for the scenario where you have your own machine on which to brute force a password at your leisure.

[holocron]

I showed this comic to my advisor and he suggested we change our password generation program at the university.

Here's what I came up with

Enjoy,
Vance

Code: Select all

#!/usr/bin/python
# Date: 23Aug2011
# Author: Vance Morris
# Email: vance<dot>morris<at>gmail<dot>com
# This program generates a file of 100 random passwords, ready to use.
# The format for each password is <Word><Word><Word><Number><SpecChar>
# An example would be YellowElephantCounting3@
# The default output file is named passwords.txt


"""
    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
"""
import os, re, random

DICTIONARY = "/usr/share/dict/words"
PASSFILE   = "./passwords.txt"
CHARS      = "~!@#$%^&*()_+-={}[];:<>,./?"
WORDS      = []
REGEX      = re.compile('[a-z]{6,8}$')

def isValid(s):
  if REGEX.match(s):
    return True
  else: return False

def loadDictionary():
  with open(DICTIONARY,'rb') as f:
    while True:
      l = f.readline()
      if not l: break
      l = l.rstrip()
      if isValid(l):
        l = l.capitalize()
        WORDS.append(l)

def makePassword():
  w = ""
  num = random.randint(0,9)
  char = CHARS[random.randint(0,len(CHARS)-1)]
  for x in xrange(0,3):
    w += WORDS[random.randint(0,len(WORDS)-1)]
  return w + str(num) + char
 

def writeFile(s):
  with open(PASSFILE,'a') as f:
    f.write(s+"\n")

# main
if (os.path.isfile(DICTIONARY)):
  loadDictionary()
else:
  print "Dictionary file not found at "+DICTIONARY+"\n"

for x in xrange(0,100):
  writeFile(makePassword())


[gmalivuk]

I was going to say only using three words might be suboptimal, but I guess that with the 8 or so additional bits from the number-character combination at the end and the fact that /usr/share/dict/words is rather bigger than 2000 words, it probably works out to similar entropy.

[holocron]

I am only using words that contain a through z and are between 6 and 8 characters in length.
This gives me 27,975 words to work with.
The number of 6 character words is 7351.
The number of 7 character words is 10036.
The number of 8 character words is 10588.

Let's assume that each character is 8 bits, including the appended number and special character, this gives between 64 and 80 bits of entropy.

EDIT: Fixed that, thank you.

[gmalivuk]

Let's assume that each character is 8 bits

That's an overestimate, even correcting the byte/bit error, because characters in English words have far fewer than 8 bits of entropy. Even completely random letters are only about 4.7, because you're choosing from just 26 instead of the full 256 ASCII set.

And with the word count, we can just figure it out directly: Your method gives 27975^3*10*27 possible passwords, or 52.4 bits of entropy. Which is still pretty good, but definitely not as high as even the lower bound of your estimate.

It is, coincidentally, quite close to the amount of entropy Randall's method would give if, like yours, it added a digit and special character to the end. The number of ways to pick 3 words with replacement from 27,975 is only slightly more than the number of ways to pick 4 from 2000. So I guess it comes down to whether you find it easier to remember 3 less common words or 4 more common ones.

[Eebster the Great]

The main problem is that the comparison is wrong. It is much better if your password is not a word.

Round and round and round we go . . .

[scarletmanuka]

Yeah, someone has already mentioned in this thread how easy it would be to set up a "free password generation" website and then store all the passwords to hack people's accounts at random.

I'm sure I must have read that, but with several hundred posts on this thread it's easy to forget what has been brought up.

There's also "Password Reuse".

[Vash]

That is the advice because 1) you can fit more entropy into fewer characters that way, and some sites limit the size of the password you can use, and 2) it is unlikely that a person allowed to choose their own words will pick something with sufficiently high entropy, because we're bad and randomness.

In any case, correcthorsebatterystaple is *not* a word. It's four of them, chosen randomly. Which means that the total entropy is four times the entropy of each individual word.

The "logic" people keep using to criticize Randall's suggestion as being vulnerable to a dictionary attack is just as ridiculous as the following:
Your password obviously should not be just a 1 or a 0, as those passwords are stupidly easy to break. Therefore, your password should not consist of a concatenated string of random choices (with replacement) from the set {0,1}.

Well, that's all valid.

True. But of course if you'd read even just the most recent page or so of this thread, you'd see that the estimate wasn't intended for the scenario where you have your own machine on which to brute force a password at your leisure.

I can't read. That's why I use the internet.

[Stacey]

Best password ever: 00000001

ROFL

[superluser]

Still, it would be foolish to get your password from a server-side program just based on the trust you give an anonymous person on the Internet.

If I were listening to that advice, I'd probably never have gotten my Mr T name. (note for the humor impaired: I do not recommend using real data to generate your Mr T name)

[holocron]

And with the word count, we can just figure it out directly: Your method gives 27975^3*10*27 possible passwords, or 52.4 bits of entropy. Which is still pretty good, but definitely not as high as even the lower bound of your estimate.

Thank you for that bit of information.
With social engineering, a skilled hacker could determine the pattern and crack these passwords very quickly. Without the pattern knowledge, wouldn't the amount of entropy jump to 4.7^20 for three 6-char words or 4.7^26 for three 8-char words?

[holocron]

I agree with the strip that ordinary words give more entropy per unit of memorization effort. But I'd be curious what other people here think. The following 10 passwords each have exactly 64 bits of entropy, if you know the algorithm generating each one:

1. y#WK6qAFUct
2. JIb Varb cOF jiW
3. 2a01 e073 862c 2a5e
4. 10753 57459 34348 10846
5. cap ion take wow kudo irk
6. gyb beec mov bog fup geec
7. (215) 253-7163, (319) 137-9466 x537
8. Alaska amen breast crust reward hectic
9. May 2, 1885 1:21:7, August 2, 1934 18:16:14
10. 0010101000000001111000000111001110000110001011000010101001011110

So which is the easiest to memorize? Which is the hardest? For me, number 8 is the easiest, and number 10 is the hardest. I could memorize 8 in just a few minutes, by breaking them into two sentences, each of which uses 3 of the words, and visualizing a bizarre picture for each sentence. And I'd probably remember it for years. I think number 1 would take a LOT more effort, and I'd have to review it frequently or I'd forget it.

But what do all of you think?

This. I posted before reading through a good number of posts. Thanks!

[gmalivuk]

With social engineering, a skilled hacker could determine the pattern and crack these passwords very quickly.

No, not if it's a remotely good random number generator. It's got 52 bits of entropy, even if the attacker does determine the method and the exact list of words.

If it could be cracked very quickly by someone who knows the pattern, then it's a shitty algorithm. Relying on security through obscurity is generally not a good idea.

[TheInsomniac]

So many thoughts on this subject:

1) I work at a very big company, on a large team. I saw our adminstrative assistant open up a Rolodex of passwords, off her desk, the other day. I know she also has passwords for managers and the like.
2) "Surely you're joking, Mr. Feynman!" has some great stories about the "security" at Los Alamos during the Manhattan Project. In those days it was combo locks on file cabinets that were the issue. The situation in #1 demonstrates that not much has changed in security.
3) I had to sign up for a password at the account page of a major company recently. It had one of those "password strength" raters. It refused all of my standard passwords, mostly because of character issues or because the number string was 4 digits. I think it barged on 4-digit strings,because those so often are things like years that are easy to guess. Regardless, I ended up only being able to use the weakest of all of my standard passwords, which I came up with in the '90s when I was a teenager.

ITs are failing us.

[AndyClaw]

Thanks, Randall, for bringing this to more people's attention. Super annoying password policy at work: not allowed to have any more than two letters or numbers in a row, not allowed to have two of the same character in a row, and must use at least one letter, number, and special character. The result is probably a bunch of short passwords that would be easy to crack.

[gmalivuk]

Is it also limited by length? Because if not, just stick a ! or something between each character of an actually secure password.

[Isil`Zha]

Insert random unicode into your passwords, it significantly increases the keyspace, and I know of no brute-force cracker that even attempts to search higher than the ASCII keyspace. Meaning it will literally never brute force your password.

At one point at my previous job we pulled the SAM database and ran l0phtcrack against it. Every single password was broken within a week. Except mine. Mine was unbreakable.

[gmalivuk]

Insert random unicode into your passwords

Sure, and then be unable to login quickly and securely on another computer.

[Jorpho]

Well, ALT+[four numpad characters] can pop up something outside of the ASCII keyspace, right? That's an interesting idea.

[gmalivuk]

How is that more effective than just including "alt0151" or whatever at that point in your password? With the added benefit that it'll still work for password fields that don't accept full unicode input.

[Jorpho]

As Mr. Isil`Zha just suggested, if there are characters outside the ASCII character range that are not used by brute force crackers, then actually using ALT+0151 will make a password unbreakable by such crackers.

[gmalivuk]

It seems rather foolish to rely on the assumption that attackers will never use the characters you're using.

Once again, the entropy values that have been discussed through most of this thread refer to the difficulty of cracking a password *after* knowing the algorithm used to generated it. And knowing someone has a unicode character in their password means we *will* include those in our search. At which point it turns out this method isn't any more secure than just typing the code for the same character.

[mric]

"I needed a password 8 characters long so I picked Snow White and the Seven Dwarves."

(Recently voted funniest joke of the 2011 Edinburgh Fringe)

[gmalivuk]

Recently told in this thread, too.

[Splarka]

Thomas Baekdal's take on password usability. From 2007. Sure looks familiar. (@twitter)

I hate it when people steal ideas from Randall without crediting him. Stupid time travelers!

[TheGrammarBolshevik]

Yes, I'm sure that Randall read that article in 2007 and then sat on it for four years in order to plagiarize that god-awful explanation of a well-understood idea.

[Katifer Dragonite]

Just out of interest, what would be the strength of a password made of four random Latin words? I bet that they don't do dictionary attacks on dead languages.

[scarletmanuka]

Just out of interest, what would be the strength of a password made of four random Latin words?

The same as for English words, assuming a similarly sized word list. Once again - the strength is determined by assuming that the attacker knows the system you are using to choose your password. So for that system, we do in fact have to assume the attacker is doing a dictionary search with Latin words.

[alokito]

I was thinking, it may be better to use 4 random names for two reasons,

1) Names are easier to remember than common words, particularly when in a sequence
2) There are a whole lot of them. Apparently there are books with up to 100k available on Amazon

Assuming you could get a text file with all of them, you would get over 16 bits of entropy per word, and over 66 bits total for only 4.
A random string with mixed-case letters, numbers and symbols only has about 77 chars, or over 6 bits of entropy per character, which means you would need a totally random string of 10 characters to equal the entropy in four random names. That seems a lot harder to remember.

BTW, I wrote a java implementation of the comic with a GUI program that includes some stats to make it easy to play with these ideas for less technical people than xkcd readers, you can check it out by searching for alokito on github (I'm still a no-link noob here).

[bigjeff5]

I was thinking, it may be better to use 4 random names for two reasons,

1) Names are easier to remember than common words, particularly when in a sequence
2) There are a whole lot of them. Apparently there are books with up to 100k available on Amazon

The problem with that is that unfamiliar names are not easy to remember at all. For most people the list of familiar names is probably in the neighborhood of 200-300, tops (and I think I am being very generous there - I don't think I know that many myself). Most names people are familiar with are the names they hear repeated over and over again - that's why they are easier to remember than all the words in the English language - there aren't many of them that you have to remember!

So if you are only using names you are familiar with (to make it easier to remember) the hacker just needs to take into account the region of the world you live in and he can chop his list down to the 1,000 or so most common names for the area. This leaves you significantly worse off than Randall's list of the top 2000 most common words. If he knows more about where you are from he can cut it down even more, completely destroying the entropy (and obviously, the security) of your system.

[Vash]

Yes, I'm sure that Randall read that article in 2007 and then sat on it for four years in order to plagiarize that god-awful explanation of a well-understood idea.

I don't know if that's the only place it has been explained. It is always possible for someone to read something, forget about reading it, and then use the idea years later. I almost didn't want to say it, though. It might be pretty unlikely. I don't know how accessible that website is. That would help to clarify.

[TheGrammarBolshevik]

Ahh, fuck. Yeah, I totally retract that completely serious and not ironic post.

[Vash]

Ahh, fuck. Yeah, I totally retract that completely serious and not ironic post.

I was contesting the point you seemed to be making with sarcasm, but if you were making no point, then I suppose I stand corrected.

[TheGrammarBolshevik]

I was making a point with sarcasm, but whatever you were trying to contest wasn't it.

[Vash]

I was making a point with sarcasm, but whatever you were trying to contest wasn't it.

Yeah, I wanted to correct that. I think I know your point now.

[superluser]

The problem with that is that unfamiliar names are not easy to remember at all. For most people the list of familiar names is probably in the neighborhood of 200-300, tops (and I think I am being very generous there - I don't think I know that many myself). Most names people are familiar with are the names they hear repeated over and over again - that's why they are easier to remember than all the words in the English language - there aren't many of them that you have to remember!

So if you are only using names you are familiar with (to make it easier to remember) the hacker just needs to take into account the region of the world you live in and he can chop his list down to the 1,000 or so most common names for the area. This leaves you significantly worse off than Randall's list of the top 2000 most common words. If he knows more about where you are from he can cut it down even more, completely destroying the entropy (and obviously, the security) of your system.

Just use names from Pynchon novels. You'll probably top 2000, and it would be very difficult to forget Cherrycoke Oedipa Eggslap Chunko.

[gmalivuk]

Perhaps, though I suspect still much easier to misremember that than something from a list of actual common words, like "correct horse battery staple".

[jpk]

So one of my passwords expired towards the end of last week, and I thought I'd give this a try. Did the reset, used four common words, had to insert a digit to keep the algorithm happy, so I used digits as separators.

I remembered the digits, but the words themselves were completely gone by the time the system prompted me for a refresher.
I'm not playing that game again. It was embarrassing having to ask for a reset after just a few hours.

[Isaac5]

How does one calculate this?

[Eebster the Great]

How does one calculate this?

The entropy of a password-generating scheme is the binary log of the total number of passwords it can generate.