Message-ID: <20140120164454.GA26832@openwall.com>
Date: Mon, 20 Jan 2014 20:44:54 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: scope and focus (Re: [PHC] Native server relief support for password hashing in browsers)

On Mon, Jan 20, 2014 at 03:05:38PM +0000, Peter Maxwell wrote:
> So far I've seen a *massive* amount of discussion on memory-hardness and
> what processors can fill memory the quickest, without addressing the more
> fundamental question of what we're considering to be our threat model

All of these:

http://www.openwall.com/presentations/Passwords12-The-Future-Of-Hashing/mgp00064.html

(This slide lists a mix of threats and their mitigations.)

However, the focus of PHC is on providing a better password hash type to
mitigate offline attacks.

> and what we consider secure in that model.

Nothing.  Or, under a more limited definition of "secure", the current
state-of-the-art password hashing, which PHC is meant to advance.

We're merely trying to mitigate offline attacks to a greater extent.

So far, for attacks that are known to have actually occurred, bcrypt
works almost as well as a password hashing scheme could, but we expect
that this might not remain the case far enough into the future, and we
have started to care about attackers with ASICs more.

Also, there's still some demand for a scripting language friendly
password hashing scheme, for setups where a call to native bcrypt is not
yet available.  For those cases, we need and can design a fallback
algorithm much more attack-resistant than phpass' current last resort
fallback is.

Then, there are use cases for large-memory KDFs (gigabytes), and there
bcrypt is not a serious competitor.  So PHC is also about improving upon
scrypt for such use cases (e.g., for use in TrueCrypt).

> At the moment, we can probably compare algorithm against algorithm

And this may be just good enough for the above needs, except with
special cases like:

> but that assumption would not be valid
> if someone presents a candidate algorithm that adjusts hardness based on
> password complexity (which can be done but there are problems with the
> approach).

Yes, there are major problems with this approach, which will probably be
enough to bring it out of consideration.

> We also cannot answer more fundamental questions like: for a standard
> password db of say 1m passwords, how many more passwords will be protected
> against an adversary with $x resources compared to using bcrypt.  Without
> being able to answer those types of question, how do can you justify the
> winning PHC algorithm?

I agree that more research in this area is welcome, but beyond/outside
of PHC.  For specific (expected) password distributions and assuming
optimal attacks (or unoptimal to some specific extent, since attackers
will usually not be able to exactly predict the distribution), you can
arrive at percentages cracked using $T time and $X resources, given
amortized $t time and $x cost to test a candidate password for a given
hash type.  From the PHC, you'll only need estimates for the $t and $x
figures for the different PHC candidates/winners/whatever, as well as
how they differ by the password hashing scheme's cost settings, type of
attack hardware, and attacker's total budget.  Yes, it'd be nice to have
such info on PHC candidates, and obtaining and documenting such info is
within scope of PHC.

In PHC, we can compare PHC candidates based on these per-candidate
figures, without translating them to percentages cracked under specific
scenarios.  The tough part is comparing one PHC candidate with higher
attack costs vs. another with slightly lower attack costs but also e.g.
lower complexity and/or extra functionality.  Similarly, it may be tough
to compare PHC candidates where one has higher costs for some types of
attackers and the other has higher costs for other types.  (To me, there
are no potential practical use winners among the native-code PHC
candidates discussed so far, because none are consistently no-weaker
than bcrypt.  I hope this will change.)

Would being able to compare percentages cracked under certain budgets
given certain database sizes, rather than only estimated time and dollar
costs to test N candidates, be of help in choosing PHC winner(s)?
I think not.  If anything, it could be helpful in choosing no winners at
all (or to keep them as academic-only), if the reduction in percentages
cracked for realistic scenarios would turn out to be negligible.

> For someone charged with securing passwords, would
> it be more cost-effective to enforce a strong password policy instead of
> the extra hardware needed for the PHC algorithm?

This is tough.  To me, it is clear that it should be a combination of
both, and if only one has to be chosen, then I'd focus on at least
minimally stretched password hashing first rather than on password
policy, because:

http://www.openwall.com/presentations/Passwords12-The-Future-Of-Hashing/mgp00029.html

Yes, it is unclear what the best balance is, and this may be subject to
further research.  Cost of stricter password policy is hard to estimate
with reasonable accuracy.

> If my own experience in
> security is anything to go by, risk is the governing factor and I'm not
> seeing any sufficient justification on why a company or institution should
> spend increased hardware resources for storing passwords when you cannot
> measure projected risk reduction.

It may be difficult to justify a password hashing cost increase, yes.
Yet the PHC is not only about costlier password hashing.  It is mostly
about better efficiency, in terms of attack cost per defense cost.  For
that, relative comparisons may be sufficient, and no hardware costs
justification is needed.  A better password hashing scheme should ideally
be better than current state-of-the-art even when scaled down to low
configurable cost settings, such as to match currently deployed hardware.

> Anyway, to cut to the chase - we should be able to model performance of
> candidates using a suitably small number of variables and making some
> reasonable assumptions (I'd already started on this last year and if I can
> get a good run of spare time might actually be able to finish it).

Sounds good.

> > I think this is mostly beyond scope of PHC (although these things may
> > reasonably be worked on by the same people).  The only portion under
> > scope is "per-{password, account} costs for certain kinds of attackers"
> > for different defender's cost settings, similar to info included in the
> > scrypt paper, but expanded to cover not only ASICs, but also relevant
> > pre-existing hardware (that some attackers are likely to use).
> 
> On the contrary, I think these questions are absolutely core to the PHC:
> how can you justify using the winning PHC algorithm otherwise?

I've tried to explain this above.  To reiterate:

We need to justify PHC itself, for which there needs to be significant
improvement upon current state-of-the-art.  We need to pick winner(s),
for which we need to be able to compare relative qualities of the
candidates.  Once we've done that, yes, we'll also have the task(s) of
justifying moving to the PHC winning algorithm(s) if and where
appropriate.  Such justification may proceed after PHC concludes,
because it does not affect whether we can justify PHC to ourselves[1]
and which candidates we choose as winner(s).[2]

[1] We want to try to advance the field, and to come up with password
hashing schemes that are better for practical use as well.  I think this
is reason enough to try, and we should allow for PHC to conclude with no
winner(s) or with academic-only winner(s) (which we won't recommend for
practical use, then), although I hope there will be candidates we could
actually recommend for practical use.

[2] We should consider relative ease of justification for actual use
when deciding on the winner(s), though.  For example, simplicity and
dependency on fewer and on well-regarded crypto primitives are
advantages and may be reason to choose one candidate over another, in
part because these properties ease justification.

Alexander

Powered by blists - more mailing lists