0936: "Password Strength"

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

Moderators: Moderators General, Prelates, Magistrates

bigjeff5
Posts: 127
Joined: Tue Nov 10, 2009 3:59 am UTC

Re: 0936: "Password Strength"

Postby bigjeff5 » Thu Aug 11, 2011 9:48 pm UTC

Oracle wrote:So why are so many posts about single word passwords when we just learned that aBc@r9U3% is not nearly as strong as "correct horse battery staple"?


Actually, unless I'm just not getting it aBc@r9U3% looks like gibberish, and would have 2^45 bits of entropy (the maximum for a 9 digit password and 90 possible characters) - twice as good as the passphrase's 2^44.

If it's not pure gibberish, though, you're absolutely right.

FoolishOwl
Posts: 52
Joined: Mon Jun 29, 2009 8:36 pm UTC
Location: San Francisco, California
Contact:

Re: 0936: "Password Strength"

Postby FoolishOwl » Thu Aug 11, 2011 10:34 pm UTC

bigjeff5 wrote:
Oracle wrote:So why are so many posts about single word passwords when we just learned that aBc@r9U3% is not nearly as strong as "correct horse battery staple"?


Actually, unless I'm just not getting it aBc@r9U3% looks like gibberish, and would have 2^45 bits of entropy (the maximum for a 9 digit password and 90 possible characters) - twice as good as the passphrase's 2^44.

If it's not pure gibberish, though, you're absolutely right.

Lots of posts were about passwords that people invented using some scheme involving taking some word or phrase and distorting it, like Randall's 'Tr0ub4dor&3' example, and thus don't have as much entropy as 'correct horse battery staple'. I've seen lots of textbooks recommend schemes similar to the 'Tr0ub4dor&3' example. Using a totally random string of characters would be stronger, but harder to remember.

The key thing is that a passphrase like 'correct horse battery staple' is sufficiently strong, but much easier to remember, and to persuade regular people to use.

User avatar
bitwiseshiftleft
Posts: 295
Joined: Tue Jan 09, 2007 9:07 am UTC
Location: Stanford
Contact:

Re: 0936: "Password Strength"

Postby bitwiseshiftleft » Thu Aug 11, 2011 10:52 pm UTC

FoolishOwl wrote:The goal isn't perfect security, which is impossible. It's more like harm reduction -- or vulnerability reduction, to be more accurate. Lots of people use ridiculously obvious passwords -- look at an analysis of hacked password databases. I've read several, and they're all similar. You could just create a list of the most common few passwords, and try every known user name with that short list until you found one the user whose password is "123456" or "password". It wouldn't take long.

The point of this comic is, if you're giving advice to someone who is "not a computer person" about choosing a password, suggesting Randall's passphrase method, and assuring them that the math behind it is good, is good advice that's likely to be accepted. I may use 'tr -dc "[:alnum:]" < /dev/urandom | fold -b15 | head' to generate a password for the root account on a server (thanks for that suggestion, by the way), but someone who is "not a computer person" is not going to do that, and will instead use "mynameYYYY" on every message board and email account they use. And, I think Randall's passphrase method may work well for me in most cases that don't have strict rules about case, symbols, etc.

Oh, incidentally, someone mentioned four digit bank PIN codes. Those have bothered me, but I've noticed banks have started allowing longer PIN codes. More importantly, the PIN is used together with a bank card -- that's two-factor authentication, so it's more secure than just a password.

Here's my shell script, by the way. Tested on Ubuntu 11.04.

Code: Select all

#! /bin/bash

# RandomWord
# Randomly select words from the system spelling dictionary. Possessive nouns,
# i.e., words ending with "'s", are culled. If an integer is supplied as an
# argument, that number of random words will be selected; the default is to
# select one random word.
#
# FoolishOwl
# 2011 August 11

if echo "$1" | /bin/grep -Eq '^[[:digit:]]+$' ; then
   COUNT="$1"
else
   COUNT=1
fi

while [[ COUNT -gt 0 ]] ; do
   if /usr/bin/shuf -n 1 /usr/share/dict/words | /bin/grep -v "'s$" ; then
      (( --COUNT ))
   fi
done


You're gonna want to use --random-source=/dev/urandom on that. Also, I'd use a dictionary that's shorter than /usr/share/dict/words. For example, get 12dict and run

Code: Select all

perl -ne  'print if /^[a-z]{1,6}\s*$/' 6of12.txt
on it; you should get 8257 words, 1-6 characters in length, that are relatively common. The list will still contain obscurities like "zebu" though. Or just get the diceware wordlist, but the 12dict one is probably better.

User avatar
Eebster the Great
Posts: 3460
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: 0936: "Password Strength"

Postby Eebster the Great » Fri Aug 12, 2011 12:45 am UTC

bigjeff5 wrote:
Oracle wrote:So why are so many posts about single word passwords when we just learned that aBc@r9U3% is not nearly as strong as "correct horse battery staple"?


Actually, unless I'm just not getting it aBc@r9U3% looks like gibberish, and would have 2^45 bits of entropy (the maximum for a 9 digit password and 90 possible characters) - twice as good as the passphrase's 2^44.

If it's not pure gibberish, though, you're absolutely right.

If we interpret it as a three-letter word with random capitalization then five random printable ASCII characters, the sample space is something like 1000 * 23 * 965 = 6 * 1013. And it is quite reasonable to expect cracking software to try this pattern at some point.

60 trillion might sound large, but at the above quoted rate of 4 billion guesses per second (on a single machine), it would take about four hours max to be found (well, max four hours into checking that particular pattern). With a more powerful machine or multiple machines, it could be done much more quickly.

Also, you are misusing the term "bit." Passwords coming from sample spaces of 244 and 245 have entropy of 44 and 45 bits, respectively.

ibutton77
Posts: 5
Joined: Thu Oct 04, 2007 2:02 am UTC

Re: 0936: "Password Strength"

Postby ibutton77 » Fri Aug 12, 2011 12:50 am UTC

7 pages of comments, and not one mention of "Crimson Eleven Delight Petrichor".

Whyyyyyyyyy? D:

User avatar
MathGirl
Posts: 13
Joined: Mon Dec 20, 2010 5:31 pm UTC

Re: 0936: "Password Strength"

Postby MathGirl » Fri Aug 12, 2011 12:54 am UTC

This was a dangerous comic to read after a few drinks.

laddiebuck
Posts: 2
Joined: Thu Aug 11, 2011 6:25 pm UTC

Re: 0936: "Password Strength"

Postby laddiebuck » Fri Aug 12, 2011 5:22 am UTC

ibutton77 wrote:7 pages of comments, and not one mention of "Crimson Eleven Delight Petrichor".

Whyyyyyyyyy? D:


I know! And Petrichor is probably not even in the top 100k by frequency (I checked a couple of corpuses). Let's go with a 200k word list. That would be about 70 bits of entropy, a staggeringly large number. The Doctor certainly knew his stuff...

User avatar
darkspork
Posts: 532
Joined: Tue Sep 23, 2008 12:43 am UTC
Location: Land of Trains and Suburbs

Re: 0936: "Password Strength"

Postby darkspork » Fri Aug 12, 2011 5:49 am UTC

I'd argue pronounceable gibberish words are best, especially if they're hilarious.

flajjdadjery394
yebderbasch752
zygmuftyllix311

Maybe it's just me, but I could come up with a gibberish word and its spelling, forget it, hear it in my mind six years later, and spell it the same way. I find my brain tends to treat syllables on the same level as individual characters, too.
Shameless Website Promotion: Gamma Energy
My new esoteric programming language: GLOBOL
An experiment to mess with Google Search results: HARDCORE PORNOGRAPHY HARDCORE PORNOGRAPHY

cryptographer
Posts: 1
Joined: Fri Aug 12, 2011 5:45 am UTC

Re: 0936: "Password Strength"

Postby cryptographer » Fri Aug 12, 2011 5:57 am UTC

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?

User avatar
Pfhorrest
Posts: 5444
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 0936: "Password Strength"

Postby Pfhorrest » Fri Aug 12, 2011 7:08 am UTC

Maybe I'm missing something, but it seems that everyone here is discussing the strength of passwords of a given pattern, against an attacker who knows to try that pattern; yet as this thread shows, people have many different patterns they use. Each of them has a varying strength against an attacker who is trying just that pattern, but how does an attacker know what pattern you chose your password according to? A random attacker trying to brute-force a password chosen by unknown means will have to try every pattern by which the password might have been chosen, and so will still have to eventually try every possible password of that length in that character set.

Of course, I suppose a smart attacker would try more-commonly-used patterns first and less-commonly-used patterns (minus those already tried) last. So the strength of your password is a function not only of the length and depth (character set) of your password space, nor only of the analogous complexity of the pattern from which you choose passwords from that space, but also of the commonality of use of that pattern. I'm going to go out on a limb and say easier-to-remember patterns are more commonly used and harder-to-remember patterns are less commonly used, so there really is a trade-off between ease of use and strength for passwords in a given space of possibilities. For passwords of a given length and character set, the strongest ones are going to be the ones for which there simply is no mnemonic or other aid, ones that you just have to straight up memorize.

The last thing a smart attacker would try, after trying all known patterns, would be simply randomly trying everything in that password space that does not fit any known pattern; accordingly, the strongest password you could choose would be something randomly chosen from the set of passwords that don't match any known pattern. Because, e.g., if my true randomness generator by improbable chance spits out "12345", that doesn't magically make "12345" a secure password; the randomness is useful for avoiding falling back on any known patterns, but things that fall into known patterns by chance are just as insecure as those chosen by those patterns, because they're the first things that attackers are going to try. Yes, the space of possible passwords that don't fit any known patterns is smaller than that of all possible passwords, but an attacker is going to have to try the entire space eventually anyway, and that is going to be the part of that space a smart attacker tries last, because, due to its inherent difficulty to use, it will be the one used the least, even though it is the strongest.

Randall's point in the comic may still stand, however, as a passphrase of a couple common words is both much longer than a short password and so part of a much larger total space, and though the analogous "length" of passphrases fitting the pattern you choose by is much shorter (four "characters", i.e. words), the "depth" of them is deeper by an order of magnitude or two (thousands, maybe tens of thousands of words, vs a few hundred 8-bit characters). So although this is likely to be one of the first patterns tried by an attacker for passwords of this length, being an easy-to-use pattern, the space of all possible passwords of this length is huge, and passwords chosen according to this pattern still fill a sizable fraction of that huge space, allowing you to afford the ease of use of that pattern without compromising the strength of your password compared to shorter passwords chosen by harder-to-use patterns.
Forrest Cameranesi, Geek of All Trades
"I am Sam. Sam I am. I do not like trolls, flames, or spam."
The Codex Quaerendae (my philosophy) - The Chronicles of Quelouva (my fiction)

campboy
Posts: 52
Joined: Wed Jun 18, 2008 1:54 am UTC

Re: 0936: "Password Strength"

Postby campboy » Fri Aug 12, 2011 8:24 am UTC

Pfhorrest wrote:Maybe I'm missing something, but it seems that everyone here is discussing the strength of passwords of a given pattern, against an attacker who knows to try that pattern; yet as this thread shows, people have many different patterns they use. Each of them has a varying strength against an attacker who is trying just that pattern, but how does an attacker know what pattern you chose your password according to? A random attacker trying to brute-force a password chosen by unknown means will have to try every pattern by which the password might have been chosen, and so will still have to eventually try every possible password of that length in that character set.

Of course, I suppose a smart attacker would try more-commonly-used patterns first and less-commonly-used patterns (minus those already tried) last.

No, he wouldn't. A smart attacker would more likely try the patterns which are quickest to try first. According to Randall's figures, the four words protocol takes about 65000 times as long to check as the Troubadour protocol; even if four words is significantly more common, you save time on average by checking the Troubadours first -- at least until practically everyone stops using them.

User avatar
MisterH
Posts: 31
Joined: Thu Jul 21, 2011 11:02 am UTC

Re: 0936: "Password Strength"

Postby MisterH » Fri Aug 12, 2011 9:04 am UTC

Um, only one problem with this strategy - horses can't talk.

smorrey
Posts: 1
Joined: Fri Aug 12, 2011 8:15 am UTC

Re: 0936: "Password Strength"

Postby smorrey » Fri Aug 12, 2011 9:26 am UTC

Ummm the method he is proposing isn't nearly as secure as he thinks.
This is because of the english language usage as well as the possibility of hash collisions.

2 things to remember here.
Most website software that is in the wild doesn't actually store your password, it stores a hash (usually MD5) of the password.
Each MD5 hash is comprised of exactly 16 bytes stored as a 32 plain text character string.
Therefore the hash can only contain 0-9 and a-f

Lets look at the example given.
correct horse battery staple

This produces an MD5 hash of
9cc2ae8a1ba7a93da39b46fc1019c481

So your password , no matter how long is actually converted to something 16 bytes long and won't have any "special" characters, the hash itself is not case sensitive either (however the algorithm will produce different output with different letter cases).

But don't forget, you don't actually need the original password, since it's now been converted to a fixed length string all you need is something that computes to that same fixed length string. For those who don't know, this is called a hash collision.
Since the string is a fixed length of 16 bytes stored as 32 characters, this leaves us with 16^32 possible combinations without a collision. So in a way you can think of this as a slot machine with 16 wheel stops and 32 wheels.

That may sound like a lot and on a single core computer generating 1 hash per microsecond (pretty slow by today's standards) you are talking 584,554.531 years before you are guaranteed a collision.
Forgetting for a moment that storing all possible MD5 hashes ought to consume a minimum of 16^32 bytes of storage; on a quad core computer, running that same algorithm, the collision time is only 764.561659 years.
Take 4 quad core computers (or a single 16 core unit) and that drops to 27
Still a pretty long time but if you had 32 cores at your disposal it drops to 5
At 64 cores it's 2
Throw 128 cores at it and you're only talking 1 year.

Theoretically as you double the number of cores the time to a collision goes down by the square root of the previous time. This assumes a perfectly distributed algorithm and 0 time used for communications and storage.

Therefore if you were a person with sinister motives in control of a small botnet with say 16,000 cores and you maxed out all cores you should be able to generate a password that will match any MD5 hash within just a few minutes.

Hellmaw
Posts: 1
Joined: Fri Aug 12, 2011 10:46 am UTC

Re: 0936: "Password Strength"

Postby Hellmaw » Fri Aug 12, 2011 10:47 am UTC

My password is CPE1704TKS because I like to play chess.

correct horse battery staple
Posts: 1
Joined: Fri Aug 12, 2011 12:25 pm UTC

Re: 0936: "Password Strength"

Postby correct horse battery staple » Fri Aug 12, 2011 12:41 pm UTC

@smorrey: a few problems with your analysis:

1) Randall already says in the comic that the "time to crack" is potentially much faster with a stolen hash.
2) If all you're doing is attacking by searching for a hash collision then it doesn't matter how the password was generated. Your attack is a brute force attack against the space of possible hashes.
3) Doubling the number of cores halves the time to crack: your example number reflects this but you claim it reduces the time by the square root.
4) The space of possible hashes is much larger than the space of possible combinations of four common dictionary words. It's still faster to attack the password than try to generate a hash collision. Your example only becomes faster because of massive paralellization.

At any rate, I think I might recommend this scheme to my security-challenged mother-in-law. She currently uses a scheme which generates passwords with a maximum of maybe three bits of entropy (if an attacker knows the scheme). It turns out her passwords are also very easy to remember.

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

Re: 0936: "Password Strength"

Postby Jorpho » Fri Aug 12, 2011 12:50 pm UTC

1) He mentions that cracking a stolen hash is faster. (That method, of course, requires stealing the hash first.)
2) Do secure sites really still use MD5? I thought people switched to SHA-1 for the very reasons you describe.
3) Good luck coming up with a convenient way to max out 16,000 cores "in a few minutes".

kasmeneo
Posts: 51
Joined: Mon Dec 20, 2010 9:07 am UTC
Location: 50° 6′ 26″ N, 8° 39′ 52″ E

Re: 0936: "Password Strength"

Postby kasmeneo » Fri Aug 12, 2011 12:54 pm UTC



I like how some of the lines of that table make somewhat sense...
"121212 hooters london hotdog time"
"ginger fucking internet extreme magnum"
"yellow smokey monster ford dreams"
"william blowme boobs fucked paul"
It's cooler up here.

Spoe
Posts: 23
Joined: Fri Dec 11, 2009 4:28 pm UTC

Re: 0936: "Password Strength"

Postby Spoe » Fri Aug 12, 2011 2:47 pm UTC

tahrey wrote:So your 4 words come out to the same as a 12-character "normal" one. Merely more memorable... possibly.


Almost certainly more memorable since the 12 character "normal" one would need to include passwords like A&..;he|7"9w. 12 unrelated items to remember rather than 4.

Army1987
Posts: 8
Joined: Fri Aug 12, 2011 2:49 pm UTC

Re: 0936: "Password Strength"

Postby Army1987 » Fri Aug 12, 2011 2:52 pm UTC

The only significant disadvantages of this approach, compared with a password made up of (say) seven random printable ASCII characters, is that it's much slower to type without typos and might be longer than allowed, but this can be mitigated using *short* words. My email password cannot be longer than 20 chars and cannot include spaces and some special characters; so, I used the British National Corpus to get a list of the 1024 most common three-or-four-letter words, chose five of them at random, and concatenated them with CamelCase (e.g. CapFoolGladWhomBay). That's 50 bits of entropy: not terribly much, but there's nothing worth millions of dollars in my email. (And still the security method says this is a “mediocre” password; under those constraints, how the *hell* am I supposed to make a stronger one?)
Another bonus of such passwords compared to random ASCII characters is that they are easier to type on a keyboard layout other than the one you're used to (provided at least the letters are in the same place). Having to search for each punctuation character would slow me by more than a factor of 3. (OK, I know using a password on a shared computer isn't a terribly great idea, but I always clear the browser cache and everything before logging out.)

gavin
Posts: 113
Joined: Wed Aug 10, 2011 1:24 pm UTC

Re: 0936: "Password Strength"

Postby gavin » Fri Aug 12, 2011 2:58 pm UTC

I have been known to combine a couple phone numbers and holding down the shift key in various patterns that change for different places. So, as an example, say one number is 555-555-5555, I may just do: %%%-%55-%%%% and then follow on the pattern with the next number too. My pattern is usually different from something that basic though (4 shifts, 2 non-shifts)

TheEngineer
Posts: 49
Joined: Wed Nov 24, 2010 2:40 pm UTC

Re: 0936: "Password Strength"

Postby TheEngineer » Fri Aug 12, 2011 3:07 pm UTC

For improved security, run your passphrases through Google Translate set to Latin.

"Correct Horse Battery Staple" => "Donec solidis emendet equum" => "Solid until the correct horse"

Hmmm ... Not exactly symmetrical encryption but the result makes so much more sense.

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

Re: 0936: "Password Strength"

Postby gmalivuk » Fri Aug 12, 2011 3:15 pm UTC

Army1987 wrote:That's 50 bits of entropy: not terribly much, but there's nothing worth millions of dollars in my email.
Then again, access to your email potentially means access to every other website where you have an account, as well, since password resets are done through your registered email address.

(And still the security method says this is a “mediocre” password; under those constraints, how the *hell* am I supposed to make a stronger one?)
Well doubling the size of the word list adds one bit per word, for one thing. As would picking random letters to capitalize. (That might be harder to remember, but with the benefit of adding another bit 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
MisterH
Posts: 31
Joined: Thu Jul 21, 2011 11:02 am UTC

Re: 0936: "Password Strength"

Postby MisterH » Fri Aug 12, 2011 3:55 pm UTC

Talking of training humans to use hard to remember passwords;

http://www.nakedpassword.com/

I forget what mine is as soon as her bra comes off!

Spoe
Posts: 23
Joined: Fri Dec 11, 2009 4:28 pm UTC

Re: 0936: "Password Strength"

Postby Spoe » Fri Aug 12, 2011 4:22 pm UTC

smorrey wrote:Most website software that is in the wild doesn't actually store your password, it stores a hash (usually MD5) of the password.
Each MD5 hash is comprised of exactly 16 bytes stored as a 32 plain text character string.
Therefore the hash can only contain 0-9 and a-f

Lets look at the example given.
correct horse battery staple

This produces an MD5 hash of
9cc2ae8a1ba7a93da39b46fc1019c481

So your password , no matter how long is actually converted to something 16 bytes long and won't have any "special" characters, the hash itself is not case sensitive either (however the algorithm will produce different output with different letter cases).


It's converted to something 16 bytes long, yes. But that's enough to store 19 characters of the 94 easily accessible on a US keyboard. Looking at just the English alphabet, case-sensitive, 22 characters. And case-insensitive, 27 characters.

A random 32 digit hex number has 128 bits of entropy, more than any of the password creation methods mentioned. However, MD5 isn't perfect and, IIRC, provides about 123 bits of protection, not 128, in this context.

DanielC
Posts: 2
Joined: Fri Aug 12, 2011 4:40 pm UTC

Re: 0936: "Password Strength"

Postby DanielC » Fri Aug 12, 2011 5:12 pm UTC

smorrey wrote:Each MD5 hash is comprised of exactly 16 bytes stored as a 32 plain text character string.
Therefore the hash can only contain 0-9 and a-f


This is just a choice of representation. There is absolutely nothing fundamental about 0-9, a-f. It is popular to represent hashes as hexadecimal values, but if you wanted you could express them as octal, decimal, binary and anything else that strikes your fancy.


This produces an MD5 hash of
9cc2ae8a1ba7a93da39b46fc1019c481

So your password , no matter how long is actually converted to something 16 bytes long and won't have any "special" characters, the hash itself is not case sensitive either (however the algorithm will produce different output with different letter cases).


*Sigh*... Hexadecimal is just a choice of number system. An MD5 has 16 bytes of *DATA*. By your line of reasoning I could express the hash as binary and then claim a hash doesn't contain anything other than 0 or 1 as if that meant anything. Incidentally, 16 bytes is 128 bits, which is much more space than any of the passwords that have been discussed in this thread.


But don't forget, you don't actually need the original password, since it's now been converted to a fixed length string all you need is something that computes to that same fixed length string. For those who don't know, this is called a hash collision.


This is not what a collision is. Finding a text that corresponds to a given hash is a "pre-image". There are three main properties that a cryptographic hash should have: Pre-image resistance, Second pre-image resistance and Collision resistance. These are different things. In particular, finding collisions is much easier than finding a pre-image.

Since the string is a fixed length of 16 bytes stored as 32 characters, this leaves us with 16^32 possible combinations without a collision.


This is nonsense and it gives the correct value entirely by chance. The only reason 16^32 is correct is because each hexadecimal digit has 16 options (from "0" to "f"), not because the hash has 16 bytes. Just try doing the same calculation for a different hash, like SHA-1, which has 20 bytes and a hexadecimal representation of 40 characters.

What you have done in your calculation is take the length of the hash in one unit (bytes) and raise it to the length of the hash in a different unit (hex).

That may sound like a lot and on a single core computer generating 1 hash per microsecond (pretty slow by today's standards) you are talking 584,554.531 years before you are guaranteed a collision.
Forgetting for a moment that storing all possible MD5 hashes ought to consume a minimum of 16^32 bytes of storage;


How do you figure that MD5 hashes consume 16^32 bytes of storage? Each hash requires 16 bytes to store (32 if you store it as ASCII hex) and there are 2^160 possible MD5 hashes. That works out to 68.7 billion times more storage than you suggested. Anyway, all you have done here is describe a brute force attack. I think everyone here is familiar with brute force attacks. Whether you have access to the hashes or not, a brute force attack is the slowest type of attack possible.

Therefore if you were a person with sinister motives in control of a small botnet with say 16,000 cores and you maxed out all cores you should be able to generate a password that will match any MD5 hash within just a few minutes.


Provided that they have access to the hash so they can attack offsite, and provided that the company used MD5 instead of something like PBKDF2.

FoolishOwl
Posts: 52
Joined: Mon Jun 29, 2009 8:36 pm UTC
Location: San Francisco, California
Contact:

Re: 0936: "Password Strength"

Postby FoolishOwl » Fri Aug 12, 2011 5:33 pm UTC

bitwiseshiftleft wrote:You're gonna want to use --random-source=/dev/urandom on that. Also, I'd use a dictionary that's shorter than /usr/share/dict/words. For example, get 12dict and run

Code: Select all

perl -ne  'print if /^[a-z]{1,6}\s*$/' 6of12.txt
on it; you should get 8257 words, 1-6 characters in length, that are relatively common. The list will still contain obscurities like "zebu" though. Or just get the diceware wordlist, but the 12dict one is probably better.

I poked around a bit, and found Kevin's Word List Page, which led me to the SCOWL package, which is used to generate custom versions of /usr/share/dict/words. The 'scowl' package is in the Ubuntu repositories, so I installed it, and modified my script to use the short list of ordinary words common to US, British, and Canadian English:
Before:

Code: Select all

if /usr/bin/shuf -n 1 /usr/share/dict/words | /bin/grep -v "'s$" ; then

After:

Code: Select all

if /usr/bin/shuf -n 1 --random-source=/dev/urandom /usr/share/dict/scowl/english-words.10 | /bin/grep -v '[^[:alpha:]]' ; then

The 'grep' filters out the annoying words ending with {apostrophe s} . There's one word ending with {accented-e s}, so I could produce a slightly more efficient filter by searching for {not-alpha s} at the end of a word. Or, I could just produce a filtered list and avoid filtering with grep at runtime at all. I was aiming for relative simplicity, though, with a little future-proofing: I can post this on Ubuntu Forums, and the instructions are simply to install 'scowl' and use this script. Currently, you end up with a word list of 3930 words, which is a bit better than Randall's example, and I think the sample output shows reasonable results:

Code: Select all

foolishowl@example.org:~$ RandomWord 12
leads
invalid
proved
disturb
loss
useless
pint
harmless
turned
massive
examine
trapped

Bounsy
Posts: 9
Joined: Wed Jan 26, 2011 5:33 pm UTC

Re: 0936: "Password Strength"

Postby Bounsy » Fri Aug 12, 2011 6:22 pm UTC

Another fairly easy to remember way to add nonsense words to your passwords is to misspell regular words. You do have to remember how you misspelled the words, of course, so use the idea at your own risk. If you do something consistent like drop the first, last, or nth character of each word or transpose two specific charcters, that makes it easier to remember. There's also pig latin, dropping duplicate letters in words with duplicate letters (e.g., bookkeeper => bokeper), doubling each character, etc., etc., etc.

There are so many possible ways to obfuscate your words that, if you pick a method that eliminates dictionary words and includes some additional random characters (numbers, symbols, etc.) in random locations, you quickly force the attacker to use a brute force algorithm to crack your password. Telling others which specific method you use is a good way to weaken attacks against your accounts, but I doubt many of us will be targetted so specifically, so it's probably a non-issue.

fagricipni
Posts: 41
Joined: Thu Nov 04, 2010 7:32 pm UTC

Re: 0936: "Password Strength"

Postby fagricipni » Fri Aug 12, 2011 6:32 pm UTC

MisterH wrote:Talking of training humans to use hard to remember passwords;

http://www.nakedpassword.com/

I forget what mine is as soon as her bra comes off!


Now they just need to get a model named Sammy to add a parallel path to the one implemented by the model named Sally -- not all computer users are male, nor are all male computer users heterosexual.

doggitydogs
Posts: 38
Joined: Sun Apr 24, 2011 5:52 pm UTC
Location: 42.39561°, -71.13051°

Re: 0936: "Password Strength"

Postby doggitydogs » Fri Aug 12, 2011 6:41 pm UTC

But my computer can crack that password in 300 milliseconds...

Code: Select all

test_password("correcthorsebatterystaple");

Bounsy
Posts: 9
Joined: Wed Jan 26, 2011 5:33 pm UTC

Re: 0936: "Password Strength"

Postby Bounsy » Fri Aug 12, 2011 6:49 pm UTC

I've worked where the password had to be exactly 8 characters long, containing at least one number, one uppercase, one lowercase, and one symbol (with many common symbols forbidden due to possible problems if they are used as part of scripts, etc.) The password had to start with a letter as well. The number of possible passwords is amazingly low once all of the restrictions were in place and especially considering how many users will use common dictionary words as part of their password.

Here's an idea for a simple formula to evaluate password strength:
1. The length (1 character = +1)
2. The variety (+1 each for a least one uppercase, lowercase, number, symbol, and unusual (not on a normal keyboard)--meaning a total of +5 if you have all five)
3. The lack of dictionary words (-1 for each character that is the start of at least one dictionary word--probably have to exclude 1-2 letter words like "a" and "an" in order to not penalize too much)
4. Unicode (+1 for each unicode character)

Other factors could be added to further reward/penalize certain patterns, such as having an extremely long password (reward) or alternating letters and numbers (penalty). The exact weighting of each factor is debatable, but you get the idea.

Once such a formula is established, you can then have a password policy that is something like: All passwords must be at least 8 characters long and have a password strength of at least 12. (Note: That policy is almost the same as saying, "All passwords must be at least 8 characters with one uppercase, one lowercase, one number, and one symbol." However, more variety is allowed and bad behaviors are discouraged, which should make for stronger passwords overall.)

FoolishOwl
Posts: 52
Joined: Mon Jun 29, 2009 8:36 pm UTC
Location: San Francisco, California
Contact:

Re: 0936: "Password Strength"

Postby FoolishOwl » Fri Aug 12, 2011 6:53 pm UTC

Bounsy wrote:Telling others which specific method you use is a good way to weaken attacks against your accounts, but I doubt many of us will be targetted so specifically, so it's probably a non-issue.

Kerckhoff's Principle: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge. Most of the clever obscuring devices people suggest are more predictable than random generation. Again, this was the point of Randall's comic.

But, as you say, it's really a matter of coming up with a good enough method that people will actually use. Very few people are going to have the NSA come at them with all their resources; most people just need to worry about spambots, which go after the low-hanging fruit.

Spoe
Posts: 23
Joined: Fri Dec 11, 2009 4:28 pm UTC

Re: 0936: "Password Strength"

Postby Spoe » Fri Aug 12, 2011 7:52 pm UTC

DanielC wrote:How do you figure that MD5 hashes consume 16^32 bytes of storage? Each hash requires 16 bytes to store (32 if you store it as ASCII hex) and there are 2^160 possible MD5 hashes.


Just a minor quibble: 2^128. 2^160 is (most commonly) SHA-1 in context of hashes.

DanielC
Posts: 2
Joined: Fri Aug 12, 2011 4:40 pm UTC

Re: 0936: "Password Strength"

Postby DanielC » Fri Aug 12, 2011 8:55 pm UTC

Spoe wrote:
DanielC wrote:How do you figure that MD5 hashes consume 16^32 bytes of storage? Each hash requires 16 bytes to store (32 if you store it as ASCII hex) and there are 2^160 possible MD5 hashes.


Just a minor quibble: 2^128. 2^160 is (most commonly) SHA-1 in context of hashes.


Indeed. I mistyped.

User avatar
Pfhorrest
Posts: 5444
Joined: Fri Oct 30, 2009 6:11 am UTC
Contact:

Re: 0936: "Password Strength"

Postby Pfhorrest » Sat Aug 13, 2011 12:35 am UTC

campboy wrote:No, he wouldn't. A smart attacker would more likely try the patterns which are quickest to try first. According to Randall's figures, the four words protocol takes about 65000 times as long to check as the Troubadour protocol; even if four words is significantly more common, you save time on average by checking the Troubadours first -- at least until practically everyone stops using them.

Even if there are many uncommonly-used but quick-to-try patterns?

E.g. say there is a pattern which 5% of possible passwords (of a given length and character set) match. 20% of users use this pattern because it is very easy to remember. Then there are ten other patterns which only 0.5% of passwords (of the given length and character set) match, each used by 1% of users.

Let T be the time it would take to brute-force the entire space of possible passwords of the given length and character set randomly. It takes you 0.005T to search each of the latter patterns, and 0.05T to search the former pattern. If you search all the easy ones first, as you suggest, you spend 0.05T (since there are ten of them), and cover 10% of use cases. If you search the harder but more commonly used one first, you also spend 0.05T, but you cover 20% of use cases. In other words, for the same amount of search time, you're twice as likely to find the right password searching the one harder-to-search-but-more-commonly-used pattern first than if you searched the ten easier-to-search-but-less-commonly-used ones, under these circumstances.

Of course these circumstances might not obtain, but my point is that "how hard is it to search the set of passwords matching this pattern?" is not the only important question; "how often are passwords matching this pattern used?" is just as important. One is the cost and one is the value, and both must be considered to make a rational decision about the expected payoff.
Forrest Cameranesi, Geek of All Trades
"I am Sam. Sam I am. I do not like trolls, flames, or spam."
The Codex Quaerendae (my philosophy) - The Chronicles of Quelouva (my fiction)

User avatar
Eebster the Great
Posts: 3460
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: 0936: "Password Strength"

Postby Eebster the Great » Sat Aug 13, 2011 2:53 am UTC

The important thing to realize is that the search spaces of two different password schema will likely differ by several orders of magnitude, making the relatively small differences in usage irrelevant. A 44-bit password will almost always be superior to a 28-bit one.

User avatar
cjquines
Posts: 61
Joined: Thu Jul 21, 2011 5:30 am UTC

Re: 0936: "Password Strength"

Postby cjquines » Sat Aug 13, 2011 5:14 am UTC

I calculate password strength with:
Number of characters>Mixed cases>Numbers and symbols.

campboy
Posts: 52
Joined: Wed Jun 18, 2008 1:54 am UTC

Re: 0936: "Password Strength"

Postby campboy » Sat Aug 13, 2011 10:16 am UTC

Pfhorrest wrote:Of course these circumstances might not obtain, but my point is that "how hard is it to search the set of passwords matching this pattern?" is not the only important question; "how often are passwords matching this pattern used?" is just as important. One is the cost and one is the value, and both must be considered to make a rational decision about the expected payoff.

They're both relevant, but certainly not equally important. The issue is, as Eebster says, that the costs tend to be much more widely distributed than the values. This is because small changes to the method translate exponentially into changes in the number of possible passwords. The value, also, can only be estimated; the cost can be calculated exactly.

starfyredragon
Posts: 4
Joined: Wed Jul 15, 2009 6:02 pm UTC

Re: 0936: "Password Strength"

Postby starfyredragon » Sat Aug 13, 2011 5:30 pm UTC

Rephistorch wrote:
jpk wrote:
jpk wrote: Hell if you make random passwords that are 8 characters long and take the time to memorize them, you're way ahead of the game. Truly random (or close enough) upper and lower case passwords with numbers, and your choice of any 5 symbols (your choice!), gives you a password with a strength of 67^8 which is ~23x better protection than four random common words.


If by "random enough" you mean generated with a good random number generator, yes, you can get random enough for password-sized objects. If you mean "picking random letters" then no, there's no such thing as "random enough" in that case - people can't do random.


Which is of course what I meant. It's pretty easy to memorize if you type it often enough and maybe even create a mnemonic for yourself. I actually don't think anything can ever be truly random, but possibly so improbable to predict as to be as close as you're gonna get.


Actually, to paraphrase a study I saw awhile back, you can cause people to pick randomly. There was a study done on randomness and human interaction done as an algorithmic situation. Basically, to cause human-generated randomness, you need to remove two things: capability for repetition and defining points.

For example, a method to do this would be to mark a ball's surface in a coordinate plane and tell them to choose a point on it, assigning the number to the position they choose (mark the coordinates via magnetic strips or sum such to avoid defining points. Then later hand them the ball again and have them choose a point on the ball once more. Generates a nice random number setup.

starfyredragon
Posts: 4
Joined: Wed Jul 15, 2009 6:02 pm UTC

Re: 0936: "Password Strength"

Postby starfyredragon » Sat Aug 13, 2011 6:31 pm UTC

gmalivuk wrote:
PowerJoe wrote:My method: Pick a Hebrew word, and type the corresponding keys, so the English password appears random. For complying with non-alphanumeric requirements, choose words with ת, ץ, or ף, which are on the ',', '.' and ';' keys respectively.

Con: Need to speak Hebrew, which I do!
Con: Now everyone with access to a Hebrew word list and some basic programming skills can brute-force your passwords...
---
Regarding the comic itself, I think this is a pretty damn good technique as long as the system you're using lets you use it. As someone else already pointed out, a random four-word phrase from among the few thousand most common English words gets you a password as hard to brute-force (even for someone who knows exactly how you picked your password) as a 10-character long completely random alphanumeric string.


Solution ver. 2: Set your keyboard to Hebrew, and type as if the keyboard were in English, to generate a seemingly random string in hebrew.

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

Re: 0936: "Password Strength"

Postby gmalivuk » Sat Aug 13, 2011 6:48 pm UTC

Which is just as susceptible to a dictionary attack, upon knowing that's how a password was generated.
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 90 guests