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

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

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