RE: Passwords: length vs. complexity (was: How does the Cain and Abel SAM dump works?)

["Rivest, Philippe" <PRivest () transforce ca>]

DISCLAIMER: My math is NOT what it used to be :) and it never was that
awesome anyhow ;)
---------------------------------------------------------------------

Let me the "advantage" to link a few sites that I have found b4 I entered
this post and that I have shared with a few of the members.
(for those who think Wikipedia and all are not "good" I also posted a
Microsoft one who, I hope, did a good enough research AND a NIST link!)


I would like to get back to the fact that a pass-phrase would contain a LOT
more then a single character more then a normal password. As identified in
this web site, a normal English word has about 5 characters, so using 2 words
would yield (on average) a 10 character password.

http://technet.microsoft.com/fr-ca/library/cc512609(en-us).aspx
->In a pass phrase, each word is a chunk. The average length of an English
-word is five characters


Here are the few lines that I think everyone should read up:
 (website start)
http://technet.microsoft.com/fr-ca/library/cc512609(en-us).aspx


A famous paper that I love to quote is Miller's 1956 classic "The Magical
Number Seven, Plus or Minus Two: Some Limits On Our Capacity For Processing
Information." The premise of the paper, which is one of those great papers
where it is enough to just read the title, is that humans have limited
information processing capability. We can remember 7 plus or minus 2 chunks
of information at a time.

If we assume users can remember 7 chunks, words, or symbols, then the longest
password they could use would be limited to 9 characters

In a pass phrase, each word is a chunk. The average length of an English word
is five characters

Returning to Miller, a user remembering a 7-word sentence can have a
41-character password. There are several caveats with this reasoning. First,
it is unlikely that a real pass phrase is that long. For instance, my current
pass phrase (yes, I do use them) is only 35 characters long, and I already
think it is cumbersome. Also, Reinhold found that the median pass phrase
contained only 4 words

The 32 common symbols are, in order of occurrence:
ea1oirn0st2lud!m3hcyg94kSbpM758B. Even more interesting, 10% of passwords
were composed solely from these 32 symbols.
(web site end)

--END OF ARTICLE--
(my own text)

SO by the fact that the human mind can hardly remember a 10 digit/character
password like : /"1d(&3`d# but can very easily remember 7 chunks of 5 words
(about 35 char + spaces) the future of a password length has to go with
chunks of words or a similar principle.

> Care to explain why e, I or 1 would have less entropy in a randomly chosen
password?

To answer the question:

http://technet.microsoft.com/fr-ca/library/cc512609(en-us).aspx
(web site text)
The 32 common symbols are, in order of occurrence:
ea1oirn0st2lud!m3hcyg94kSbpM758B. Even more interesting, 10% of passwords
were composed solely from these 32 symbols.

http://en.wikipedia.org/wiki/Password_strength
(web site text)
In one analysis of over 3 million eight-character passwords, the letter "e"
was used over 1.5 million times, while the letter "f" was only used 250,000
times. True entropy would have had each character being used about 200,000
times. The most common number used is "1", whereas the most common letters
are a, e, o, and r.[9]

http://technet.microsoft.com/fr-ca/library/cc512624(en-us).aspx
(web site text)
There is one more way to estimate the additional strength created by
substitutions. http://www.ukradioamateur.org/extra/morse/html/c28.htm gives
estimates of letter frequencies in the English language. It shows that we
might have 21 different letters in our 25-character phrase, not counting
spaces, and that the most common are E (3.25), T (2.3), N (1.98), R (1.9),
and O (1.88).


> With a German keyboard layout I have at least the following usable
> characters:

> [a-z]: 26
> [A-Z]: 26
> [0-9]: 10
> [°!"§$%&/()=?ß*+#-_.:,;<>äöüÄÖÜ@µ]: 32

> Total: 94

(my own text)
True and I agree, but seriously these I can accept:
[a-z]: 26
[A-Z]: 26
[0-9]: 10

But these I will probably NEVER see in use:
§äöüÄÖÜ@µ]

http://www.infoworld.com/article/06/07/21/30OPsecadvise_1.html
(website text)
The problem with this analysis is that complexity cannot be guaranteed, and
for the most part will be circumvented by your end-users. Whether you give
them 94 characters or 65,000 characters to choose from, most will choose to
include the same 32 characters (several studies have discussed this,
including this Microsoft debate
http://www.microsoft.com/technet/community/columns/secmgmt/sm1104.mspx
).

--END OF ARTICLE--

So a normal user would choose from 32 characters, so it would go to 32^8 or
32^9 (max from the Miller's research that a normal user cant remember more
then 7 +/- 2 chunks of information(stated b4).
32^5 =         33,554,432
32^6 =      1,073,741,824
32^7 =     34,359,738,368
32^8 =   109,951,1627,776
32^9 = 35,184,372,088,832

As you can see, normal user chosen character are affected a lot by length.
Again, I know that if we do the ^94 we get bigger numbers, but this can't be
enforced and user just can remember it. Also those would have to be randomly
chosen, and belive me I did that with SAP once and I got a lot of 
"WTF is that password you just gave me"

Well I gave that user a SAP generated password. I don't know if you ever saw
that, but OMG they are hardcore. Seriously even the 10-12 length passwords
randomly chosen with 94 or 74 (don't really know) are freakish at best
#\31*!say
(10 char long)

YEAH SURE I'll remember that, NO I won't post it on my screen or under my
keyboard ;)

> Merely enforcing password length will gain you nothing. Example:
> "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" is a pretty long password, but I think
> you'll agree that it still isn't a very good password. Enforcing long
> passwords also may lead to notes with passwords left under keyboards or on
> monitors.

Well the password you state is not strong for a few reasons, mainly because
you know how long it is, and how many characters are in it and what type
(letters, lower case). If I was to be a stupid cracker and just go brute
forcing it, I would'nt test that password in the first few tries for sure.

The password you took has 31 characters, so 
26^31 = 7,3143171433403393900724146770015e+43

So I would guess that knowing nothing about that password, I wouldn't be able
to crack it b4 very long. Btw, I wouldn't recommend that password any how.

A 31 character long pass phrase would how ever, be a lot stronger. Even if
you just input the space into it it would gain a lot of strength.

26^31 = 7,3143171433403393900724146770015e+43
(Let's add a possible character to the entire alphabet, let's add " ")
27^31 = 2,3565501633836823549906773194587e+44
(Let's add length)
26^32 = 1,9017224572684882414188278160204e+45

This is as far as my math are going, I don't know which of the 2 last numbers
are the bigger. My collegue says the e+44, I would be tempted to say e+45
(pls correct us)


> Enforcing password length, however, won't change much about this. If users
> don't understand why it's bad to use a word as the major part of their
> password, you'll get passwords like "Password11111" instead of "Password1".
> Which is somewhat better, but still weak.


It is true that the users are the weak link. But if we remember that user
can't remember more then 7 +/- 2 characters, we can't really blame them. We
have to enforce as best we can and train them. It is far easier to ask the
system to enforce a minimum of 15 characters then a very good complexity. You
had 5 examples that were saying that length was as good as complexity, here's
a simple policy that could enforce stronger password and put less burden on
our dear users:

1) 0 complexity enforce (but very well welcomed) OR very limited complexity,
like upper case (which would double the key space possible, even if the user
would put it at the first character of the password)
2) 15 char minimum for every account (for admin get to 20-25)
3) Keep history of the last 5-10 password
4) Max password length: 45 (7 chunks of 5 words with 5 char + space would be
around 41-45) I know you don't REALLY need to specify a limit.




> I disagree. For someone knowing you choose your passwords that way, the
> password would consist of 5 tokens rather than 26 characters. If we assume
> that the words are taken from a dictionary with 50,000 words, the number of
> passwords would become

Again, you start with knowledge of the way the password was built. And a
cracker shouldn't assume that off the bat.

I could easily fool that "attack" by using very known mistakes
Password 1) My password is very strong
Password 2) Mypasswordiseverystrong
Password 3) my pasword is verry strong
Password 4) My very strong password
Password 5) My  password   is very     strong
Password 6) My PaSsWoRd Is VeRy StRoNg (I had a friend (RBF_GIRL) who would
always type like this. Sup rbf!)
...

Go guess what password used space, double space, all upper, all lower, strong
vs str0ng (I know easy) or strong vs $7r0ng


And the final link would be this one where they talk about randomly generated
password VS user chosen. I would like to take your attention to the last 2
lines.


According to:
http://main.blogs.encompassus.org/?p=50
(web site)

According to NIST SP 800-63, an 8-character randomly generated password using
a 94-character alphabet has 52.7 bits of entropy. If you let users pick their
own 8-character passwords, you're down to 18 bits of entropy, the equivalent
of about 3 randomly generated characters. This means a random password is
about 28 billion times better than a user-chosen password. If you add in a
complexity requirement, you're up to 24 bits of entropy, which is not quite
as good as 4 randomly generated characters. The "do the math" crowd acts like
you've got 8 random characters, when it's more like 4. They're off by a
factor of about half a billion.

Per NIST, adding 2 characters to the password length (for user-chosen
passwords) is about as effective as adding complexity requirements.


--End of Article--






Hoping my post was "clear" in a format way. I'm also hoping my maths aren't
too off lol :)

Btw thx for the replies!

Merci / Thanks
Philippe Rivest, CEH
Vérificateur interne en sécurité de l'information
Courriel: Privest () transforce ca
Téléphone: (514) 331-4417
www.transforce.ca

Vous pourriez imprimer ce courriel, mais faire pousser un arbre c'est long.
You could print this email, but it does takes a long time to grow trees.
 

-----Message d'origine-----
De : listbounce () securityfocus com [mailto:listbounce () securityfocus com] De la
part de Ansgar -59cobalt- Wiechers
Envoyé : 17 juillet 2008 12:22
À : security-basics () securityfocus com
Objet : Passwords: length vs. complexity (was: How does the Cain and Abel SAM
dump works?)

On 2008-07-17 Rivest, Philippe wrote:
> > Nope. Length and complexity are equivalent. Increase length and you
> > need less complexity, increase complexity and you need less length.
> > It's just easier to increase the length, because keyboards tend to
> > limit the number of available characters.
>
> That's not technically true. Size (of a password ;) ) does matter more
> then complexity.
>
> The fact is, for character to character, if you add 1 key space (add
> one length) or add complexity, you would get more security for the
> added character.
>
> 8 length : 208827064576
> 9 length :5429503678976
> This is the added number of password possible from an 8 to 9 char
> password: 5220676614400
>
> Let's do the same thing for complexity
> 26 char for 8 key space length:  208827064576
> 32 char for 8 key space length: 1099511627776
> Here we see how many more possible password you get: 890684563200
>
> 5,220,676,614,400 > 890,684,563,200
> So if you add 1 key space (8-> 9 char) you get a lot more possible
> password then if you add 6 possible characters to your password. 

Yes. So?

Let's take a closer look at your example:

26^8 =  208827064576
26^9 = 5429503678976
39^8 = 5352009260481

Result: Increase the number of characters by 13 characters for an 8
character password, and you get roughly the same number of passwords
that increasing password length by 1 will get you.

Example 2:

26^9  =   5429503678976
26^10 = 141167095653376
37^9  = 129961739795077

Result: Increase the number of characters by 11 characters for a 9
character password, and you get roughly the same number of passwords
that increasing password length by 1 will get you.

Example 3:

26^10 =  141167095653376
26^11 = 3670344486987776
36^10 = 3656158440062976

Result: Increase the number of characters by 10 characters for a 10 
character password, and you get roughly the same number of passwords
that increasing password length by 1 will get you.

Example 4:

36^9  =  101559956668416
36^10 = 3656158440062976
54^9  = 3904305912313344

Result: Increase the number of characters by 18 characters for a 9
character password, and you get roughly the same number of passwords
that increasing password length by 1 will get you.

Example 5:

36^10 =   3656158440062976
36^11 = 131621703842267136
52^10 = 144555105949057024

Result: Increase the number of characters by 16 characters for a 10 
character password, and you get roughly the same number of passwords
that increasing password length by 1 will get you.

Bottom line: You can always substitute length by number of characters
and vice versa. The relation isn't linear, but existing nonetheless.
Which is what I said.

> Also, If you go about adding complexity, how do you really control it?
> Entropy on char has it that e, I, 1 and so on will be chosen a lot
> more then ?????????, so you don't really calculate 92 possible char on
> you 101 keyboard but you would calculate around 72 or even 32 for the
> most chosen passwords.

Care to explain why e, I or 1 would have less entropy in a randomly
chosen password?

> 72^8 =  722,204,136,308,736 possible password
> 26^11=3,670,344,486,987,776 possible password

With a German keyboard layout I have at least the following usable
characters:

[a-z]: 26
[A-Z]: 26
[0-9]: 10
[°!"§$%&/()=?ß*+#-_.:,;<>äöüÄÖÜ@µ]: 32

Total: 94

94^8  = 6095689385410816
26^11 = 3670344486987776

> So, even with only 26 character (only lower char) an eleven key
> password would be stronger then a fully complex password with only 8
> key.

No.

> Please, note that it is also FAR easier for IT to enforce key length
> then good password complexity.

Merely enforcing password length will gain you nothing. Example:
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" is a pretty long password, but I think
you'll agree that it still isn't a very good password. Enforcing long
passwords also may lead to notes with passwords left under keyboards or
on monitors.

> Password1 would be a good password complexity wise. But a very poor
> password due to the fact that everything is NOT random. A capital
> letter on the first character, a digit on the last and a word as the
> prime key.. very usual

Enforcing password length, however, won't change much about this. If
users don't understand why it's bad to use a word as the major part of
their password, you'll get passwords like "Password11111" instead of
"Password1". Which is somewhat better, but still weak.

> How ever, mypasswordisverystrong is a very strong password, that would
> totally fail the complexity test, but it has 22 character, its easy as
> hell to remember and if you just add the normal space "my password is
> very strong" you get a 26 character long password.

I disagree. For someone knowing you choose your passwords that way, the
password would consist of 5 tokens rather than 26 characters. If we
assume that the words are taken from a dictionary with 50,000 words,
the number of passwords would become

  50000^5 =         312500000000000000000000

instead of

  26^22   = 13471428653161560586981973426176

Not to mention that with this approach particular characters actually do
have less entropy than others.

The strength of a password should not rely on that the way how it's
chosen remains secret.

> FYI 26 char long password with only spaces as special char would yield
> this much possible passwords:
> 1,6423203268260658146231467800709e+37
>
> I don't know how much exactly this is, but it looks to be more then
> enough :)
>
> Hence, complexity < length

Non sequitur, as explained above.

Regards
Ansgar Wiechers
-- 
"All vulnerabilities deserve a public fear period prior to patches
becoming available."
--Jason Coombs on Bugtraq