Page 8 of 23

Re: 0936: "Password Strength"

Posted: Thu Aug 11, 2011 9:48 pm UTC
by bigjeff5
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.

Re: 0936: "Password Strength"

Posted: Thu Aug 11, 2011 10:34 pm UTC
by FoolishOwl
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.

Re: 0936: "Password Strength"

Posted: Thu Aug 11, 2011 10:52 pm UTC
by bitwiseshiftleft
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 12:45 am UTC
by Eebster the Great
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 12:50 am UTC
by ibutton77
7 pages of comments, and not one mention of "Crimson Eleven Delight Petrichor".

Whyyyyyyyyy? D:

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 12:54 am UTC
by MathGirl
This was a dangerous comic to read after a few drinks.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 5:22 am UTC
by laddiebuck
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...

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 5:49 am UTC
by darkspork
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 5:57 am UTC
by cryptographer
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?

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 7:08 am UTC
by Pfhorrest
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 8:24 am UTC
by campboy
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 9:04 am UTC
by MisterH
Um, only one problem with this strategy - horses can't talk.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 9:26 am UTC
by smorrey
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 10:47 am UTC
by Hellmaw
My password is CPE1704TKS because I like to play chess.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 12:41 pm UTC
by correct horse battery staple
@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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 12:50 pm UTC
by Jorpho
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".

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 12:54 pm UTC
by kasmeneo


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"

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 2:47 pm UTC
by Spoe
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 2:52 pm UTC
by Army1987
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.)

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 2:58 pm UTC
by gavin
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)

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 3:07 pm UTC
by TheEngineer
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 3:15 pm UTC
by gmalivuk
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.)

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 3:55 pm UTC
by MisterH
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!

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 4:22 pm UTC
by Spoe
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 5:12 pm UTC
by DanielC
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 5:33 pm UTC
by FoolishOwl
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

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 6:22 pm UTC
by Bounsy
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 6:32 pm UTC
by fagricipni
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 6:41 pm UTC
by doggitydogs
But my computer can crack that password in 300 milliseconds...

Code: Select all

test_password("correcthorsebatterystaple");

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 6:49 pm UTC
by Bounsy
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.)

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 6:53 pm UTC
by FoolishOwl
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 7:52 pm UTC
by Spoe
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.

Re: 0936: "Password Strength"

Posted: Fri Aug 12, 2011 8:55 pm UTC
by DanielC
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.

Re: 0936: "Password Strength"

Posted: Sat Aug 13, 2011 12:35 am UTC
by Pfhorrest
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.

Re: 0936: "Password Strength"

Posted: Sat Aug 13, 2011 2:53 am UTC
by Eebster the Great
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.

Re: 0936: "Password Strength"

Posted: Sat Aug 13, 2011 5:14 am UTC
by cjquines
I calculate password strength with:
Number of characters>Mixed cases>Numbers and symbols.

Re: 0936: "Password Strength"

Posted: Sat Aug 13, 2011 10:16 am UTC
by campboy
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.

Re: 0936: "Password Strength"

Posted: Sat Aug 13, 2011 5:30 pm UTC
by starfyredragon
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.

Re: 0936: "Password Strength"

Posted: Sat Aug 13, 2011 6:31 pm UTC
by starfyredragon
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.

Re: 0936: "Password Strength"

Posted: Sat Aug 13, 2011 6:48 pm UTC
by gmalivuk
Which is just as susceptible to a dictionary attack, upon knowing that's how a password was generated.