```Date: Mon, 29 Apr 2013 11:40:06 -0400
From: Matt Weir <cweir@...edu>
To: crypt-dev@...ts.openwall.com
Subject: Re: Representing the crack resistance of a password.

Jeffrey,
That'll teach me to write my e-mails faster, (or at least check my inbox
before I hit send). To address your question on how to figure out:

Ideally you'd want to develop an "ideal" cracking strategy, and then figure
out where each password falls into that strategy. The two problems of
course are A) What's an ideal cracking strategy, and B) How do
you efficiently decide how long a password takes to crack? Point B is
important since you don't want to wait 3 months while running someone's
password through a GPU cracker to say "Yup, it's strong enough, you can use
it!"

I'd recommend checking out Shiva Houshmand Yazdi's and Dr. Sudhir
Aggarwal's paper on the subject available at:

This is a slightly different question than the original one though, since
you're looking for a password strength metric, vs the strength of a generic
That's pretty much what Shiva, Sudhir and I are arguing in our papers.

Matt

On Mon, Apr 29, 2013 at 10:38 AM, Jeffrey Goldberg <jeffrey@...dmark.org>wrote:

> 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