[cryptography] hashed passwords, iteration counts, and PBKDF2

Solar Designer solar at openwall.com
Sun Nov 4 09:09:27 EST 2012


On Wed, Oct 31, 2012 at 01:58:00PM -0700, travis+ml-rbcryptography at subspacefield.org wrote:
> One reason why PBKDF2 requires the original password is so that you don't repeatedly
> hash the same thing, and end up a "short cycle", where e.g. hash(x) = x.  At that
> point, repeated iterations don't do anything.

Even when this does happen for a given password, it is of almost no help
for the attacker.  The attacker won't know in advance which of the
candidate passwords produce such short cycles, so the attacker won't be
able to try those cheaper candidate passwords before other passwords.
Thus, I think this becomes a practically relevant problem only if it
occurs for a large percentage of passwords.

> I just realized, you don't necessarily need to put the original password in; you
> could just hash something else that varies to keep it out of a short cycle; for
> example, the round number.
> 
> This would allow you to update an iteration count post-facto without knowing the
> original password.  Would it break any security goals?

A relevant topic is entropy loss with multiple iterations (perhaps
without reaching a short cycle).  I "bookmarked" and summarized some
cryptography list postings from 2010 here:

http://www.openwall.com/lists/crypt-dev/2011/07/14/1

I might not be aware of all security goals there were, but your proposed
approach sounds fine to me (yes, we'll accept the very slight entropy
loss).  Being able to upgrade an existing hash to a higher iteration
count is a desirable property.  [ A much trickier task: support upgrades
to a higher memory cost for the already-computed iterations.  Sounds
impossible at first?  Not quite.  This would probably require initial
use of some secret component (allowing for a lower-memory shortcut) and
then dropping it at upgrade time. ]

Another reason to avoid including the original password on each
iteration is to have the running time a function of iteration count,
but mostly not of password length (for sane password lengths).
Otherwise we may have to use a lower iteration count to allow for the
maximum password length allowed by the system (have such longest
passwords processed in a sane amount of time, especially if they're
potentially attacker-chosen), which results in hashes of shorter
passwords being unnecessarily too quick to compute.

Alexander



More information about the cryptography mailing list