crypt-dev - Re: Representing the crack resistance of a password.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Mon, 29 Apr 2013 09:38:14 -0500
From: Jeffrey Goldberg <jeffrey@...dmark.org>
To: crypt-dev@...ts.openwall.com
Subject: Re: Representing the crack resistance of a password.

On 2013-04-29, at 7:26 AM, Solar Designer <solar@...nwall.com> wrote:

> On Mon, Apr 29, 2013 at 01:05:30AM -0500, Jeffrey Goldberg wrote:

>> I asked how we should characterize, or even name, this notion. I tossed out
>> 
>>  C(X, k) = 2 log_2 G(0.5, X, k)

And now that I've had a few hours sleep, I see that even if that is the right concept, I got the math wrong.

Should be

  C(X, k) = log_2 G(0.5, X, k) +1 (or log_2(2G(0.5, X, k))

Maybe I'll do even better if I get coffee.

> Regarding your G() above, see:
> 
> http://www.lysator.liu.se/~jc/mthesis/4_Entropy.html#SECTION00430000000000000000
> 
> for a formal definition of "Guessing entropy" and some discussion.

Thank you! I would have gotten there eventually as I was starting to work through "Testing Metrics for Password Creation Policies
by Attacking Large Sets of Revealed Passwords" (Weir et al.)

  http://goo.gl/YxRk

Using Guessing Entropy, then my C (crack resistance) would be C(X) = log_2 (2G(X)). So here if X is a uniform distribution, C(X) == H(X).

But I am looking for something more (and so maybe "entropy" isn't the right analogy). I want to be able to talk about the crack resistance of a particular password given a distribution. 

Suppose that a password policy is "at least 8 characters, at least one uppercase letter, at least one digit" but X is the actual distribution of what humans do when told to create a password under that policy. I would want

  C(X, 'Password1') < C(X, '2n8PGUoPeb')

So instead of having G be the average number of guesses needed for a random x in X; I'd like to be able to talk about the strength of a particular password (with respect to a particular distribution of passwords). 

Cheers,

-j