How Does Imposing Restrictions on Passwords Affect their Keyspace?

[kenewbie]

Ok, I want to make the argument that putting restrictions on passwords are not exclusively a good thing.

There are normally rules you need to follow when you create one, which are there to prevent dictionary-attacks. IE, You need at least 1 capital letter, at least one numeric and at least one non-capitalized letter.

If we say that there are 120 writable characters in a password, and the maximum number of characters you can have is 8, then the keyspace of the password should be 8^120.

I can see that the keyspace would be reduced when you impose limits on it, but by how much? How do I calculate the new keyspace given the restrictions I wrote above?

This is sort of an attempt at that:

There are 120 - 26 writable characters if you remove all capital letters. This gives 8^94 combinations which you can remove from the original keyspace? So with the only restriction being at least 1 captial letter, the new keyspace is 8^120 -8^94? That is a pretty hefty reduction on a brute force attack.

So hefty, in fact, that my logic must be flawed somewhere?

Anyone able to help me out and show how to remove all instances without a captial letter, a small letter and a number from the keyspace?

k

 

[CRGreathouse]

There are normally rules you need to follow when you create one, which are there to prevent dictionary-attacks. IE, You need at least 1 capital letter, at least one numeric and at least one non-capitalized letter.

Assuming there are 26 capital, 26 non-capital, 10 numeric, and 58 other:

There are 120^8 8-character passwords. (Thus there are less than 120^8 restricted passwords.) Of these there are 94^8 without any capitals, 94^8 without any non-capitals, and 110^8 without any numerics. (Thus there are more than 120^8 - 94^8 - 94^8 - 110^8 restricted passwords.)

The unrestricted passwords have about 55 bits of entropy. By the inequalities above, the restricted passwords have 53 to 55 bits of entropy.

Of course, the real point is not to weaken the password strength by 2 bits, but to prevent a dictionary attack on passwords that (because they're in a dictionary, or close) has only ~30 bits of entropy.

 

[CRGreathouse]

Oh, and in your problem most of the strength loss was from the numeric requirement. If it was changed to "one non-letter", the strength loss would be less than half a bit.

 

[esbo]

Ok, I want to make the argument that putting restrictions on passwords are not exclusively a good thing.

There are normally rules you need to follow when you create one, which are there to prevent dictionary-attacks. IE, You need at least 1 capital letter, at least one numeric and at least one non-capitalized letter.

If we say that there are 120 writable characters in a password, and the maximum number of characters you can have is 8, then the keyspace of the password should be 8^120.

I can see that the keyspace would be reduced when you impose limits on it, but by how much? How do I calculate the new keyspace given the restrictions I wrote above?

This is sort of an attempt at that:

There are 120 - 26 writable characters if you remove all capital letters. This gives 8^94 combinations which you can remove from the original keyspace? So with the only restriction being at least 1 captial letter, the new keyspace is 8^120 -8^94? That is a pretty hefty reduction on a brute force attack.

So hefty, in fact, that my logic must be flawed somewhere?

Anyone able to help me out and show how to remove all instances without a captial letter, a small letter and a number from the keyspace?

k

You can prevent dictionary attacks by using words which are not in the dictionary
such as kiygkdksh. Even 5 characters is 12 million combinations.
Nobody but a fool or a lottery player would try to crack that!

And look at it this way, the more complicated you make it the more likely a person
is to write it down somewhere. Thus sites which require complicated passwords
actually make it more likely that someone will discover your password!

 

[kenewbie]

CRGreathouse, thanks a lot for the help!

I re-did the problem with a total keyspace of the printable ascii-characters (non-extended) and this is what I got:

Total keyspace 94^8 = 6 095 689 385 410 816 = 6.095 * 10^15
Keys without numerics 84^8 = 2 478 758 911 082 496 = 2.478 * 10^15
Keys without capitals 68^8 = 457 163 239 653 376 = 4.571 * 10^14
Keys without noncapital 68^8 = 457 163 239 653 376 = 4.571 * 10^14

Restricted keyspace = 2 702 603 995 021 568 = 2.702 * 10^15

Assuming 100 ms latency on a web-attack.

Time to guaranteed compromize of total keyspace : 6.0905 * 10^14 seconds
Time to guaranteed compromize of restricted space: 2.7026 * 10^14 seconds

10^14 seconds is about as long as homo sapiens have existed, so you are **** out of luck either way.

Given a password-file and a Pentium 4 2.8 GHz, John the ripper does 272 234 attempts each second on a traditional DES encryption.

Time to compromize of total keyspace: 6.0905 * 10^15 / 272 234 = 22 391 359 585 seconds (727 years)
Time to compromize of restricted space: 2.7026 * 10^15 / 272 234 = 9 927 593 526 seconds (322 years)

I guess that given a cluster of fast computers you can bring the second scenario down to a manageable timeframe, and in that case the "at least one numeric" would cut the effective time needed in half or so.

I imagined the impact would be greater, shows how hard it is (for me at least) to appreciate how big the difference between 10^9 and 10^10 really is.

k