0936: "Password Strength"

[wingsofwrath]

Right, all the more reason to keep the subject matter of a password as far removed from your usual interests and as secret as possible.

And of course, "Bild88.1936BoschReglerSSM72" has three actual words, one random string of alphanumeric symbols, one date, a number and a non-numeric symbol, so in the worst case scenario the attacker knows the exact constituents, they could still combine for a given value of 52 bits of entropy, which I believe is quite sufficient for a medium security password.

[FoolishOwl]

The point of the comic was that a pass phrase composed of four words randomly selected from a list of common words is sufficient for a medium security password, so we don't need all these cryptic techniques for selecting a password. If you prefer your method, that's fine, but it's not intrinsically better.

[gmalivuk]

one random string of alphanumeric symbols

Is it really random, though?

[wingsofwrath]

Is it really random, though?

Probably not for the original designer, but since it's meaning has been lost to time (it doesn't help that said designer is most likely dead) and even someone who knows the object being referenced can't make heads or tails of it, it might as well be.

The point of the comic was that a pass phrase composed of four words randomly selected from a list of common words is sufficient for a medium security password, so we don't need all these cryptic techniques for selecting a password. If you prefer your method, that's fine, but it's not intrinsically better.

Perhaps. It's a matter of personal preference, really. I developed the method as a way to make quick easy to remember alphanumeric passwords long ago, and for me it worked so far. The switch to fictional words was recent, and I still thinks gives the best results for a high-security password outside of random character selection, which is very hard for a human to remember.

[Eebster the Great]

If your password does indeed have 52 bits of entropy, I imagine that is plenty for almost all purposes.

I do find it to be quite a bit harder to remember than the four-common-word passphrase though, personally. And even a word list of 8000 words (giving 52 total bits of entropy) can include only fairly common words.

[Vash]

Looks like Randall Munroe doesn't know a lot about breaking passwords.

[gmalivuk]

Do you have an actual point to contribute?

---

On the topic of other password-generation methods that are easy to remember but hard to crack, a sequence of 8 playing cards (taken from a well-shuffled deck of 52) also provides 44 bits of entropy. Like other suggestions, this may be just as hard for some people to remember as 44 bits of random characters, but I imagine it would be easier for people who spend a lot of time playing cards already.

[Kartoffelkopf]

My passwords nowadays generally consist of a historical battle and the year it was fought in. This is easy for me to remember and helps with remembering dates too.

To come up with a new password:
Pick a battle, say, Waterloo
Look up the year it was fought in (even if you think you know, do it just to double-check)
Your new password is the capitalised name and the year.

Waterloo1815

Right, all the more reason to keep the subject matter of a password as far removed from your usual interests and as secret as possible.

And of course, "Bild88.1936BoschReglerSSM72" has three actual words, one random string of alphanumeric symbols, one date, a number and a non-numeric symbol, so in the worst case scenario the attacker knows the exact constituents, they could still combine for a given value of 52 bits of entropy, which I believe is quite sufficient for a medium security password.

I don't use non-alpha-numeric symbols in my passwords since I am bound to forget them.
Using your example though:
88BlutundEhre.1933BundesarkivBildT3R
is what I came up with. The main problem is remembering in what order everything goes in.

[gmalivuk]

My passwords nowadays generally consist of a historical battle and the year it was fought in. This is easy for me to remember and helps with remembering dates too.

This is an astoundingly weak way of generating passwords.

[Iranon]

What about using the tool your're most likely to have at hand, your keyboard? Pick whatever weaksauce password generation method you find easiest to remember, then shift at least one hand by one key in a direction of your choice before typing.
You don't even have know your own password until you have to tell it to someone or use an unfamiliar keyboard layout, at which time you should be able to figure it out.

[wingsofwrath]

This is an astoundingly weak way of generating passwords.

I second that opinion. Not only is the resulting password short, but it's also extremely vulnerable to dictionary attacks, and, worst of al, completely predictable.

I don't use non-alpha-numeric symbols in my passwords since I am bound to forget them.
Using your example though:
88BlutundEhre.1933BundesarkivBildT3R
is what I came up with. The main problem is remembering in what order everything goes in.

This is definitely better and keeping (somewhat - the words could use some more randomising) within the bounds of my system, but the base constituents have me raise an eyebrow (as well as several hairs from the back of my neck) as to why you decided to use the the Hitlerjugend salute as your subject matter.

What about using the tool you're most likely to have at hand, your keyboard? Pick whatever weaksauce password generation method you find easiest to remember, then shift at least one hand by one key in a direction of your choice before typing.
You don't even have know your own password until you have to tell it to someone or use an unfamiliar keyboard layout, at which time you should be able to figure it out.

Awesome but impractical in my opinion. While one can argue that a substitution cypher is an effective way of making a password appear random, it will only be as strong as the base being used. If I start with the word "fish" and I decide to shift right I will get "godj" which, although immune to a dictionary attack is no better in terms of entropy.
Even worse, it felt completely unnatural to do that so I doubt anyone can effectively apply this method daily to a 20 character passphrase.
In fact, using the same system on "correcthorsebatterystaple" yielded "vpttrvyjptdrnsyyrtudys[;r" but I had to type the characters one at a time and I'm not even sure I haven't made mistakes.
In my opinion, the meagre raise in entropy is not worth the extra effort.

[mishad]

My passwords nowadays generally consist of a historical battle and the year it was fought in. This is easy for me to remember and helps with remembering dates too.

This is an astoundingly weak way of generating passwords.

The pet password-generation algorithms that have been proposed here have been ... eye-opening, certainly.

If we are looking for 40+ bits of security (a bare minimum, really, and we probably want more [1]) then our algorithm has to be able to generate more than 2^40 (1 trillion) different passwords. (We can make some allowance for there being many different potential algorithms, but there are really only a few major variations, so that's probably only a few thousand combinations, and we still need our algorithm to be able to generate billions of passwords.)

We aren't very good at estimating very large and very small numbers, but surely its clear even to those that use them that these algorithms don't give that variety?

Humans are a warmongering species, but I don't think there have been more than a few thousand "historical battles". Ditto aircraft models.
There are only a few million choices of 5 to 10 word phrases from the bible. Ditto song lyrics.

And remember, this is just to hit the bare minimum security. If we "nearly" get there -- perhaps achieving 35 bits of entropy with our algorithm -- then the time-to-crack will be <1yr.

M

[1] Based on an maximum attempt rate by the attacker of 1000/sec, e.g. for an online attack by a botnet attacking multiple accounts in parallel via a rate-limited web service, or an offline multi-GPU attack against an bcrypt-based hash , this gives a time-to-crack of a few years for a 40-bit search-space. With a weak (e.g. MD5/sha1) hash an offline GPU attempt rate might reach 1^10 per second (~ 2^30) which means we need nearly 65-70 bits of entropy to maintain similar expected time-to-crack.

[wingsofwrath]

The pet password-generation algorithms that have been proposed here have been ... eye-opening, certainly.

We aren't very good at estimating very large and very small numbers, but surely its clear even to those that use them that these algorithms don't give that variety?

That's why I'm such a big advocate of using the brain's ability to correlate seemingly unrelated data for password creation. Whereas my earlier examples were low end medium-security passwords good for forums and stuff, let's see if we can come up with a higher security one (fit for email) using the same system.

First, let's set some base parameters: I need at least 30 characters, ideally over 40. The password should also contain at least four words, three numerals and at least two non-numerical symbols for a theoretical entropy of 100 bits, but at the same time must be easy to remember.

Before I start, I need a unifying theme which will help me remember the password, and this must be chosen randomly, as far away from my usual interests as possible. Let's say, "walrus", and let's choose Wikipedia as the main source of information. ideally I would like to gain my constituents from several Wiki articles loosely relating to my chosen theme, but for illustration purposes I will keep to the main article.

For starters I need 4-5 common words taken from the article and which will serve as a base for the lot. I won't be as predictable as to choose the Latin name of the creature or make any reference to the Beatles, so instead I will have: "mursu" (Finnish for "walrus", uncommon but not invulnerable to a dictionary attack) "whiskered" (because a walrus has whiskers, duh, and it's a nice common adjective), "sea cucumber" (two common words, the whole found in the diet of the above mentioned animal) and "carpenter" (common word, reference to Alice through the Looking-Glass).

I also need a few numerals, so I will choose 1785 (date the walrus was first described by Linnaeus), 880 (weight of a female walrus in lbs) and 260 (depth of deepest measured dive)

Then I can take all this data and find a suitable combination that is easy to remember: "880wiskeredmursu1785&carpenter.seacucumber260"which can be rendered inside one's brain as the idea that a "880lb whiskered Finnish walrus described in 1785 is diving with a carpenter to find sea cucumbers in 260 feet of water".

The resulting password is very long (45 characters), draws from a character set of 66 different symbols and contains very diverse elements designed to hamper a straight dictionary attack - one of the words is foreign (automatically meaning a wider dictionary, thus a lot more possibilities), one is an adjective while three are common, of the three numerals only one is a date, the rest can be seen as "random" in the absence of the unifying element, the animal, and, finally, there are two non-numerical symbols, which, although make sense in context, can't be placed unless the attacker already knows the theme and the general meaning of the phrase (which, I should't be telling you this, need to be kept absolutely secret. If you feel like bragging at the pub about your new "unbreakable" password, you deserve to have it broken).

With so much resting on the knowledge of both the theme and the meaning of the passphrase, and at such hefty length, we can safely assume that both a brute force and a dictionary attack will take a reasonably long time, likely more than a year (I'm sure no hacker will spend that amount of time just to read your email).

By the way, I'm too lazy to calculate actual entropy, but I'm pretty confident it's somewhere around 100 bits, so I'll call my goal reached. Feel free to signal any mistakes I might have made in my reasoning.

[gmalivuk]

What about using the tool your're most likely to have at hand, your keyboard? Pick whatever weaksauce password generation method you find easiest to remember, then shift at least one hand by one key in a direction of your choice before typing.

That adds a total of 4 bits of entropy (each hand can move any of 4 directions, for a total of 16 ways to mangle). If your password was weak before, it's still pretty weak.

[Vash]

Do you have an actual point to contribute?

I have no additional points to contribute.

[Eebster the Great]

What about using the tool your're most likely to have at hand, your keyboard? Pick whatever weaksauce password generation method you find easiest to remember, then shift at least one hand by one key in a direction of your choice before typing.

That adds a total of 4 bits of entropy (each hand can move any of 4 directions, for a total of 16 ways to mangle). If your password was weak before, it's still pretty weak.

Well, each hand can probably move in six directions on a typical keyboard with rows offset. So you're really adding more like seven bits.

And let's face it, adding seven bits of entropy can be pretty useful sometimes.

[wingsofwrath]

And let's face it, adding seven bits of entropy can be pretty useful sometimes.

But as I said earlier, it feels unnatural, it's slow and imprecise. Certainly not worth the effort for 7 bits of entropy.

[gmalivuk]

By the way, I'm too lazy to calculate actual entropy, but I'm pretty confident it's somewhere around 100 bits, so I'll call my goal reached. Feel free to signal any mistakes I might have made in my reasoning.

My own rule of thumb (which I just made up on the spot) is, if I really don't know how to calculate the entropy exactly, but I suspect it is N bits, I should only use it for applications requiring N/2 bits or less of entropy, just to be on the super duper safe side. In your case, N/2 is still 50 bits, which is a pretty strong password, so go for it. Just don't depend on it's being 100 bits if you really need 100 bits, because in that unlikely case the attacker is also more likely to be exceptionally clever and might try a search method that is far better than brute force, even if you or I can't think of what such a method might entail.

(For example, Tr0ub4dor&3 is 11 characters, apparently from 94, which might look like it's got 72 bits of entropy, but which should be treated as having at most 36 bits by someone who doesn't actually know how to calculate the entropy of their not-really-random password.)

[Eebster the Great]

Especially since any situation where you "really need" 100 bits is probably one where you need to be on the extreme edge of "safe," not just on the "safe side." After all, that is one hell of a strong password.

[mishad]

By the way, I'm too lazy to calculate actual entropy, but I'm pretty confident it's somewhere around 100 bits, so I'll call my goal reached. Feel free to signal any mistakes I might have made in my reasoning.

Well, there are ~4M articles on wikipedia, which would be 22 bits of entropy, except that "walrus" is probably a lot more popular than "Sint-Stevens-Woluwe". ("Lol, I'm so random -- Penguin!") So instead lets just use Wikipedia's "random page" instead, so we get the full 22 bits of randomness.[1]

Each page has perhaps a few thousand "words" (whether words or numbers), and you are choosing 6 or 7 words from that list. But the number of "significant" words (meaningful/memorable -- exclude connectives, many verbs, many adjectives and adverbs, half the nouns) is probably only a few hundred per article -- lets say 7 or 8 bits per selected word. So the entropy from the choice of words is ~40-50. You lose some (hard to quantify) amount because different people will tend to see similar sets of words in the text as "memorable".[2]

Then you have a bit more entropy from how those words are joined together -- perhaps another 5-10 bits? And a bit more for the choice of this algorithm in the first place -- another 5-10.

That gives you a total of perhaps 80-90 bits of entropy, very roughly.

As an approach, its probably fine. The 6-word diceware method gives equivalent security (6 words from list of 8K is ~78 bits of entropy) in a similar number of characters with easier typing (particularly on mobile touchscreens with auto-correct). The wikipedia approach may result in easier-to-remember phrases, I suppose, due to the common theme.

M

[1] Unless Wikipedia don't use a crytpographically secure PRNG, of course... Which they almost don't, as they have no reason to, but lets not get too worried about that.

[2] Some Wikipedia pages won't have enough content to be usable with this method, so we will have to select another page. We lose some randomness/entropy from that too, but only a few bits, I think.

[gmalivuk]

(particularly on mobile touchscreens with auto-correct)

If your device auto-corrects your password entry, it's doing it wrong.

[slid3r]

CharonPDX wrote:
A co-worker has created an xkcd-compliant password generator:
http://slid3r.com/passGen

Enjoy.


fingerboards aroused panhandlers petroleum

I like the idea, but I agree that it might work better if it had a "Simple English Wiki" option for the words.

Fixed, now with words 5 to 7 characters long. Thanks for the feedback!

http://slid3r.com/passGen -- Enjoy!

[TheGrammarBolshevik]

My passwords nowadays generally consist of a historical battle and the year it was fought in. This is easy for me to remember and helps with remembering dates too.

This is an astoundingly weak way of generating passwords.

Yeah, but as long as nobody figures out that Kartoffelkopf of the xkcd forums uses this method, it shouldn't be a problem…

Fixed, now with words 5 to 7 characters long. Thanks for the feedback!

http://slid3r.com/passGen -- Enjoy!

"1646 passwords generated so far" tells me that such passwords have about 10 bits of entropy.

[gmalivuk]

It tells me 1646 people have used that website so far.

[slid3r]

slid3r wrote:
Fixed, now with words 5 to 7 characters long. Thanks for the feedback!

http://slid3r.com/passGen -- Enjoy!

"1646 passwords generated so far" tells me that such passwords have about 10 bits of entropy.

I am not sure how you get entropy, from a counter?

[mishad]

(particularly on mobile touchscreens with auto-correct)

If your device auto-corrects your password entry, it's doing it wrong.

That's an interesting assertion. Its probably an accurate statement of the facts for today, but would it always be true?

If passphrases (sequences of common words, rather than gobbledygook) were the norm, would it still be "doing it wrong" to do auto-correction?
What would the disadvantages be (of using auto-correct on passphrase entry fields)?

[gmalivuk]

For one thing, you would be forced to use passphrases made up of words your device recognizes as such. Even if such become common, I would strongly oppose any device that required it of me, just like I currently oppose rules that require exactly such-and-such number of characters.

[TheGrammarBolshevik]

It tells me 1646 people have used that website so far.

The issue is that the passwords appear to be generated server-side.

[gmalivuk]

Sure, that is an issue. But it has nothing whatsoever to do with how much entropy they have.

[Anonymously Famous]

Sure it does. If the server-side generated password is kept in the database along with identifying information about the person who requested said password (say, the IP address), the entropy, as far as the owner of the password-generating website is concerned, is very close to zero, if he knows that the person with that identifying information uses the password generator for their passwords.

Or, if you merely keep a list of the passwords that have been generated in the past, and you know that person x uses your particular password generator, you only need to go through the list of 1646 passwords that have been generated, giving it the stated "about 10" bits of entropy.

Using someone's website as a password generator is not a very good idea...

[slid3r]

I would be glad to post the source code, it is small and pretty efficient. It tracks neither words used, nor unique IPs. It simply reads in a list of words I parsed from a public dictionary text file, pics 4 of them at random, and prints them to the screen. Literally no more than that. The counter is a text file that gets +1 on load.

In fact:

Code: Select all

<?php

//  XKCD Inspired Password Generator
//  Author:  Slid3r
//
//  Use freely, but please leave comments intact.


// Function to select and return a random word from text file
function randWords() {
        $wordsFile = "/path/to/shortWordList.txt";
        $handle = fopen($wordsFile, "r");
        $contents = fread($handle, filesize($wordsFile));
        $txtArray = explode("\n",$contents);
        $max = sizeof($txtArray) - 1;
        $randex = rand(0,$max);
        $returnWord = $txtArray[$randex];
        fclose($handle);
        return $returnWord;
}

// Function to increment counter text file by one
function simpleCounter() {
        $countFile = "/path/to/counterFile.txt";
        $handle = fopen($countFile, "r");
        $contents = fread($handle, filesize($countFile));
        $returnCount = $contents+1;
        fclose($handle);
        $handle = fopen($countFile, "w");
        fwrite($handle, $returnCount);
        fclose($handle);
        return $returnCount;
}


// Loop the randWords() function 4 times, and concatenate into one string
for ($i = 0; $i < 4; $i++) {
        $sentence .= randWords() . " ";
}

// Print string of words to screen
echo "<br><center><h2>$sentence</h2><br>";

// Credit XKCD
echo "<h3>Inspired by:</h3>";
echo "<a href = \"http://xkcd.com/936/\"><img src=\"http://i.imgur.com/s2oQ9.png\" title=\"Credit to XKCD\" border=\"0\" \/></a><br><br>";

// Increment counter
$count = simpleCounter();
echo "<center>$count passwords generated so far.</center>";

?>


[TheGrammarBolshevik]

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.

[slid3r]

The point of giving you the source, was so that you can run it yourself. You really need to lighten up. I am no hacker, nor do I have interest in malicious or intrusive acts. I just threw together a fun script in honor of this great comic. Please ... just enjoy it for what it is, and stop making it out to be some elaborate phishing scheme.

[Anonymously Famous]

Thanks for that source code. I haven't looked at PHP for a while, and this will give me an excuse to play around with it again.

I agree that it's fun, and is a great way to see the kinds of pass phrases that might develop. I'm sure that you did this just for fun, that you would never use the generated passwords for ill, but the interwebs are full of people who make security necessary in the first place, so you just can't trust a web-based password generator. Unless it's your own and you can keep the passwords secure during transmission.

[slid3r]

Unless it's your own and you can keep the passwords secure during transmission.

https is a good point. When I have some time I really should hook that up. Good feedback.

[gmalivuk]

the interwebs are full of people who make security necessary in the first place, so you just can't trust a web-based password generator. Unless it's your own and you can keep the passwords secure during transmission.

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 don't know if I already mentioned it here or in one of the math forum threads about passwords, but I personally use PassHash, the html file for which I saved locally after verifying in the source code that it doesn't transmit any data anywhere off my computer.

[Anonymously Famous]

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.

The local file thing is a good idea, and what I was thinking of doing with slid3r's code. Now all I need to do is find a sufficiently large word list that I like.

[slid3r]

Now all I need to do is find a sufficiently large word list that I like.

Here, use this perl script like this:

wordParser.pl > myWordList.txt

Find a plain old dictionary text file, and feed it to this script. It will go through it and select only the words that are 5 to 7 characters long. Worked pretty nice for me.

http://wordlist.sourceforge.net/ is a good source for some text files. /usr/share/dict/words will often already be populated for spelling purposes on a *nix machine

Code: Select all

#!/usr/bin/perl

use strict;

local ($/,@ARGV) = ("\n","/usr/share/dict/words");
my @words = <>;
chomp(@words);

for my $i (@words) {
        if ( $i =~ m/^[a-z]{5,7}$/ ) {
                print "$i\n";
        }
}


TA DA!

[TheGrammarBolshevik]

The point of giving you the source, was so that you can run it yourself. You really need to lighten up. I am no hacker, nor do I have interest in malicious or intrusive acts. I just threw together a fun script in honor of this great comic. Please ... just enjoy it for what it is, and stop making it out to be some elaborate phishing scheme.

I'm not at all suggesting that you're phishing; just saying that it's probably worth not assuming that you aren't on a rough-and-tumble place like the Internet, especially when there are simple client-side alternatives.

I don't know if I already mentioned it here or in one of the math forum threads about passwords, but I personally use PassHash, the html file for which I saved locally after verifying in the source code that it doesn't transmit any data anywhere off my computer.

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

[Vash]

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. 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. It is a fun comic, though.

Also, p0l0n1uhm210 I thought it would show up as stars?