A better way to think about passwords

Grant Olson kgo at grant-olson.net
Mon Apr 18 04:50:17 CEST 2011


On 04/17/2011 09:31 PM, Doug Barton wrote:
> I agree that the description of baekdal's use case is pretty limited,
> and his math may be optimistic. OTOH this page seems to cast doubt on
> the idea that even comparatively simple passwords can be cracked in very
> short time periods, and more importantly that length is more important
> than complexity in any case:
> 
> http://blogs.mcafee.com/mcafee-labs/password-policy-length-vs-complexity
> 
> On the other other hand, if passwords are so easy to crack, why use them
> at all? :)
> 
> 

That's back-of-the-envelope math, based on having to resort to a brute
force attack.  If you're using English words, then ask yourself how many
letters can follow the letter q.  There's obviously only one, and that's
u.  Now those two characters that should have 26^2 possibilities
according to the back-of-the-envelope math really only be 26^1
possibilities.

Allow me to digress for a little bit.  I've been reading a book on Game
Theory.  It explained the best possible strategy for winning
rock-paper-scissors.  If you don't already know the answer, take a
second and try come up with an ideal strategy for the game.

It turns out the perfect strategy is to make real random selections.  If
you do this, over time you'll end up with a 50% win rate against any
opposing strategy.

If you attempt to use any strategy other than that, your opponent can
develop a counter-strategy that beats you.  And then you can develop a
counter-counter-strategy to beat them.  And they can... Well it's like
that scene in the Princess Bride where the villain analyzes the hero's
strategy to determine which cup is poisoned.  You can't win.

Back to passwords.

If you develop a completely random string consisting of nothing but a-z
and a minimum length of 15, then yes it will take on average half the
total time listed in that article to crack the password.  And yes, that
is better than the eight digit "p at ssw0rd".

But if you don't, and you use a dictionary word, or a dictionary word
with l33t-sp34k, or two dictionary words, your opponent can develop a
strategy that beats the average case brute force time.  And your
opponent actually does this now.  The McAfee article conveniently
ignores that the Cane & Abel can do dictionary attacks, and it can do
rainbow table lookups.

Given how much I've seen the original article you posted in the last few
weeks, I'm sure the people who write password crackers are coming up
with multiple-dictionary-word strategies, assuming they haven't already.

And the kicker is, even if they run through all of these strategies and
must eventually fall back on a brute-force attack, it's not much more
computationally expensive to do so.  All these strategies might account
for something like 1% of the total search space.  They'll still
ultimately get the totally random password in about the same average
time, but they'll get many not-so-random passwords out of the way much
much more quickly.

The seventeen character "imtoosexyformycar" may be much much easier to
hack than the seventeen character "qkgfnroefdsoeyhzz" depending on your
opponent's strategy, and it may not, but it'll never be significantly
slower.

-- 
-Grant

"Look around! Can you construct some sort of rudimentary lathe?"

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 565 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20110417/acdf070f/attachment.pgp>


More information about the Gnupg-users mailing list