Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Mon, 29 Apr 2013 11:39:39 -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 10:40 AM, Matt Weir <cweir@...edu> wrote:

> To address your question on how to figure out:
> 
>    C(X, 'Password1') < C(X, '2n8PGUoPeb')
> 
> Ideally you'd want to develop an "ideal" cracking strategy, and then figure out where each password falls into that strategy. [...]

Let me make it clear that I am not expecting an operational definition. First because it is really really hard to get a grasp on X. The best we can do is look at leaks and a few experimental results. We just don't know the underlying function that humans use when asked to create a password.

But then, even if we do know (or have a good approximation) for X we have your two questions.

> The two problems of course are A) What's an ideal cracking strategy,

I don't know on whether finding an ideal cracking strategy for a given arbitrary X is tractable.

> 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!"

Right. I absolutely agree. And I don't hold out hope for good password strength meters (though I do think that we may be able to improve upon them). I've always wanted to write an article for the AgileBits blog titled "All Password Strength Meters Suck, Include Ours".

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

Thanks.

> This is a slightly different question than the original one though, since you're looking for a password strength metric,

Again, let me clarify that I'm not asking for a metric that will give us an efficient and effective way to calculate it. I'm looking for a metric that just gives us a way to talk about these things. The concept that I'm after describes what actual strength meters are trying to approximate.

> vs the strength of a generic password creation policy.

As we discussed in the Twitter discussion, if a password creation policy expects (but doesn't enforce) a uniform (or other desirable) distribution of passwords, it doesn't give us much information about the strength of passwords that humans actually create when following the policy.

That is, if the policy merely defines a set of strings, but assumes that people will pick uniformly from that set, it will suck at telling us how strong any given password is. In this, Matt and I have been in perfect agreement. (I had just been confused about other stuff.)

Again, I would like my (abstract) strength concept to be commensurable to Shannon Entropy so that we can say that when X is a uniform distribution C(X, k) == H(X) for all k in X.  We can then talk about how much the average C(X, k) differs from H(X). This really isn't necessary, as it should always be easy to calculate C(X, k) from when X is uniform, so I can always put them in the same terms when I want to.

But if I'm the only one who thinks that such a definition would be useful, that's fine too.

Cheers,

-j

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.