Re: Passwords: length vs. complexity

[Ansgar -59cobalt- Wiechers <bugtraq () planetcobalt net>]

On 2008-07-18 Rivest, Philippe wrote:
> 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
[...]
> 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.

I already addressed this point in my previous mail. The strength of your
password or passphrase isn't necessarily determined by the number of
characters in it, but by the number of tokens. If your 35 character
passphrase consists of 7 words, then its strength isn't

  26^35   = 33424673908950949331177317694374493243220087013376

but rather

  50000^7 = 781250000000000000000000000000000

or maybe even

  300^7   = 218700000000000000

if we consider this estimate from the page you mentioned:

| Let's assume pass phrases are based on a set of only 300 words. That
| is probably a very conservative estimation, but on the other hand,
| most of those words only make sense when strung together in a
| particular way, significantly decreasing the randomness of the pass
| phrase.

Although that probably still is secure enough, it's significantly less
secure than you make it sound.

By using word-based passphrases instead of character-based passwords you
don't actually increase the length of your password (the length is still
less then 10 tokens), but rather increase the number of tokens to choose
from (300..50000 words > 85..95 characters).

> > 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]

Yes, when users choose bad passwords, entropy will decrease. How does
that affect *random* passwords?

[...]
> > 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:
> §äöüÄÖÜ@µ]

Read again.

With a French, or Spanish, or American layout there'll be different
special characters, but the number will still be somewhere between 25
and 35.

> 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.

Yes, length affects the total number of possible password. Tell news.

> 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.

Nonsense. Of course you can enforce that a password must contain
characters from particular groups. All you need is a frontend that
checks the password before storing its hash.

> Also those would have to be randomly chosen,

Ummm... yes, a good password should be randomly chosen, otherwise it
wouldn't have much entropy in it. Duh.

> 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 ;)

For some reason our users here seem to be able to memorize strong
passwords (10+ characters, mixed case, digits, special characters). We
must've be hiring only geniuses. Or, it could be because we explain to
our users why random passwords are important. Take your pick.

> > 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.

Really? Can you say "dictionary"? Or "rainbow tables"? Mine would most
certainly contain same-character passwords.

> > 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.

I'm not blaming anyone but trying to explain why merely enforcing
password length will not solve the problem. Not to mention that your
approach effectively increases the complexity rather than the length.

[...]
> > 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.

Of course I do. Security measures are only secure if they can also ward
off an attacker who has inside knowledge.

> And a cracker shouldn't assume that off the bat.

Why?

> 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!) ...

Most of these are simple variations that can be implemented most easily.
#4 isn't a variation, but a whole different passphrase, and #5 is error-
prone and thus unlikely to be used (at least by those users we are
talking about).

[...]
> 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.
[...]
> Per NIST, adding 2 characters to the password length (for user-chosen
> passwords) is about as effective as adding complexity requirements.

Look, my original statement was that complexity and length of passwords
are equivalent (mathematically), meaning that you can replace length
with complexity and vice versa. Nothing more, nothing less.

If you don't trust my words on that, here's the math:

           (n + x)^k = n^(k + y)
  <=>  k * ln(n + x) = (k + y) * ln(n)
  <=>  k * ln(n + x) = k * ln(n) + y * ln(n)
  <=>      ln(n + x) = ln(n) + y * ln(n)/k
  <=>      ln(n + x) = ln(n) * (1 + y/k)
  <=>          n + x = e^(ln(n) * (1 + y/k))
  <=>              x = e^(ln(n) * (1 + y/k)) - n

Yes, merely enforcing complexity requirements won't necessarily lead to
secure passwords, but that's a different story. As long as users don't
understand why they need strong passwords, they'll circumvent the policy
by making trivial changes. The same goes for length requirements,
because unless users understand why their passwords need to be strong,
they'll still chose weak ones (e.g. name + birth date or something).

The key to secure passwords is (and will be) user education, not
enforcing requirements.

  "If you think technology can solve your security problems, then
  you don't understand the problems and you don't understand the
  technology."
  --Bruce Schneier

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