Message-ID: <20140226091413.GB6224@openwall.com>
Date: Wed, 26 Feb 2014 13:14:13 +0400
From: Solar Designer <solar@...nwall.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Should we care about "parameter influence" attacks against PBKDF2?

On Wed, Feb 26, 2014 at 12:31:21AM -0500, Bill Cox wrote:
> This is probably a case of my being ignorant because I'm new to
> password hashing.

No, it's not that.  This is a fine question to bring up, by anyone.

> I read this paper because there's a link to it from the PHC FAQ:
> 
> Design and Analysis of Password-Based Key Derivation Functions
> http://palms.ee.princeton.edu/PALMSopen/yao05design.pdf
> 
> There's some very cool stuff there, and the attack on PBKDF2 based on
> the ability to have the user re-enter his password while an attacker
> chooses a number of hash rounds is brilliant, and belongs in a paper,
> but should we take action to defend against this attack, or simply
> enjoy it's novelty?
> 
> In particular, this attack assumes the attacker can choose input
> parameters other than the password, and then have the user use those
> parameters and reenter the password.  The hashing then takes place
> where the attacker can see the resulting hash value, but not the
> password.  I have difficulty finding the motivation to upgrade my KDF
> to defend against this scenario.  Is it even remotely possible?
> 
> In particular, if an attacker can chose inputs other than the
> password, why not just make the salt 0 so he can do a dictionary
> attack?  How does hashing all the input parameters defend against
> attacker chosen salt?  I read code where the salt length is hashed
> in... am I being daft (which I often am), or is that as useless as it
> seems at face value?

The paper uses the word "chosen" for the iteration count, which does
appear to make the attack a lot less useful in practice, but I think the
attack also matters when the iteration count is not attacker-chosen, but
rather when multiple different iteration counts just happened to be used
by the defender, and those multiple hashes happened to leak.  The paper
shows that for PBKDF1 and PBKDF2 the leak of 2 or 3 such hashes may
allow for significantly faster offline attacks.  This is important.

As to attacker-chosen iteration counts, this is not absurd either.  For
example, a program might be adjusting the iteration count based on the
system's measured performance, and the performance may vary depending on
other system load (and on many other factors).  So an attacker with
access to another account or VM on the same machine as the defender may
affect the iteration count being used on a given occasion.  If the same
password is reused to derive multiple keys - or, to make attack more
likely and relevant, separate hashes to be used for authentication, e.g.
on separate pseudo-user accounts of the person - then the system may
happen to store a combination of derived keys or hashes that together
may be offline-attacked quicker (to crack the reused password) than any
one of them would be attacked individually.

> Which is more likely of these two possibilities? 1) the KDF designer
> messed up and has a way to attack his algorithm because he didn't hash
> in all the input parameters, and 2) a random implementer messed up the
> hashing of all the input parameters, creating a weakness.

I don't know which is more likely.

As you probably realize, hashing of all the input parameters is not the
only way to prevent this attack.  A final step may (or may not,
depending on how it's chosen) also prevent the attack.  (Arguably, this
translates into hashing of the iteration count anyway, via the iteration
count indirectly affecting the input to this final crypto hash step.)
Would this fall under "the KDF designer messed up" (if such a final step
is missing or does not prevent the attack)?  As a side-effect, having a
final step like this also prevents hash upgrades to higher iteration
count, which brings us right to:

If we do support hash upgrades to higher m_cost and/or t_cost, we're
susceptible to a variation of this attack, almost by definition.  Given
a pre-upgrade and a post-upgrade hash, the attacker only needs to
perform the upgrade for each candidate password to test that candidate.
The attacker does not need to compute either hash fully.

This means that upgrades should be at least by the AT cost of the
pre-upgrade hash, thus at least doubling that cost for the upgraded
hash.  If this is not true, then an attacker having obtained both a
pre-upgrade and a post-upgrade hash gains advantage, compared to them
having only the pre-upgrade hash.  Then the upgrade is actually a
tradeoff, making the post-upgrade hash stronger as it should, but also
making the combination of two hashes weaker than the original.  We'll
probably want to avoid the possibility of this situation (don't support
too small upgrades, which we have another good reason not to anyway, as
previously discussed).

Another observation is that not-yet-upgraded hashes should preferably
not have any upgrade points in their computation.  This was already
preferable in order to maximize their effective memory cost, but now
we're reminded of an extra reason for that.

> Can I just ignore this case?

No, let's keep the above things in mind.

Thank you for bringing this up!

Alexander

Powered by blists - more mailing lists