RE: Passwords: length vs. complexity

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

> 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

How can one know what kind of tokens were used? I mean beside the fact that
you may have enough storage space and processing to store and use a rainbow
table for 15+ token, how would you identify if a password is
1- Character only
2- Complexity
3- Length
4- Tokens are words or single alpha/num/special

If I were to get a hashed password (maybe I'm weak in this area) I wouldn't
be able to identify what was used to create it. So I would have to choose the
technique to best crack it. Brute forcing it, rainbow table or even a
dictionary attack.

I could with a lengthy password bypass most of these, unless I'm mistaking. 

Brute forcing would have to test every permutation possible, with length you
would have a lot, that would be (without knowledge) length^tokens_used (15^94
for exemple or 15^300). This could take too much time.

Rainbow table, you would have to get the full range of possible hash and this
would take a lot of space and time to compute & process as you would have to
get all the possible hash for all the lengths. And where would you stop? I
mean if you have a rainbow table for up to 8 char/tokens, if I have 9 your
attack wont work. So the longer I go the more I can resist.

And for dictionary attack, well a bit of complexity would get thru that one.

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

Well, I rarely see *random* passwords. I usually see user chosen password and
you then know they are weaker. 


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

I don't know where you work; seriously where I have worked b4 even sys admin
had a hard time remembering the password for all the resources they used. We
had to use tools that would store & encrypt them, which is by far what normal
user would do. Not to place any bad mouth, but we don't all work with
scientist with 200 of IQ that are able to remember 24 token long password for
all there appz and resources.

I don't know if you are in my reality, but I see different stuff (with
respect to all the genius you seem to hire)

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

I know that encryption and hash should to be able to withstand any attack
even if all knowledge about the system and process is known beside the key
used. 
(I don't remember the name of the guy who said that for encryption)


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

> #5 is error- prone and thus unlikely to be used (at least by those users we
are talking about).

#5 is not more or less prone to errors then $8a£l|
It is a normal phrase, and each words gets + 1 space. If you don't like my
example you may find something that suits you better. But I can remember to
hit my space bar +1 time for a 5 (only 4 words counts space wise) word
sentence.


And for the record, I do want to stress out that user training should be the
first thing you think when you talk about strength of a password. 

I'll take this with one last example; security is a trade off to between what
is possible and its cost. Strong password thru complexity is possible, but at
higher cost then length (user cost (mental or training), policy cost and so
on).


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é : 18 juillet 2008 16:22
À : security-basics () securityfocus com
Objet : Re: Passwords: length vs. complexity

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