[cryptography] is there an interation-incremental version of PBKDF2?

Chris Palmer chris at noncombatant.org
Sat Sep 11 02:15:50 EDT 2010

travis+ml-rbcryptography at subspacefield.org writes:

> Your implication is, "don't try, don't even discuss trying".

No, I mean that we should do better by taking into account the whole system,
including the capabilities of the developers and users, and the business
requirements and realities. We should also not lose sight of bedrock
software engineering principles (what few of those we have).

For example, Jack Lloyd suggested crypto-function-internal ways to achieve
your goal, such as

"""even if your PRF is invertible, that would seem to require keeping the
key (ie, password) or the key schedule [...] It occurs to me that you could
actually re-stretch a PBKDF2 hash based on HMAC if you kept around the
chaining variables resulting from H(k ^ ipad) and H(k ^ opad); this would be
sufficient to allow continuing the chaining. Of course, if someone can get
these chaining variables, it would be a much easier target for cracking than
going after PBKDF2"""

This is fine and good, and might even work. I certainly don't know one way
or the other --- and that's kind of the point. No longer are we talking
about the understandable (albeit shaky) interface of a hash or KDF function
("string in, fixed-size string out, and the mapping appears random but
really isn't, and how random it isn't is hard to pin down and degrades over
time"). Suddenly now we have to understand the internals of a specific
function in order to use the password storage system correctly. And what
shall we do when it turns out the function we chose is broken? By breaking
the abstraction, we've tied ourselves to a particular implementation. "We
can't migrate to scrypt because we assumed we'd always have chaining
variables resulting from H(k ^ ipad) and H(k ^ opad)!"

But that's sort of beside the point because what really matters is the
business reality. For example, you point out that we are in trouble if 25%
of our users never log in again. Well, do we care about those users? From a
pure business perspective, possibly not. We expend engineering effort to
satisfy active customers. From a social perspective, we'd still like to
protect them by obscuring their passwords as best we can, since they
probably used the same password on other sites. 

So we have some options:

1. Erase their obscured passwords, and if they ever do log in again, tell
them sorry and direct them to the account recovery flow. "Becasue it's been
so long since you last visited us, we'd like to verify your account..." The
feasibility of this depends on several data-decidable factors: what
percentage of users are inactive? what percentage of them ever log in again
after N months, and what percentage of those are actually fraudulent account
take-overs vs. real re-activations? how many users hate our account recovery
flow so bad they give up? are there things we can do to smooth the account
recovery flow?

2. Use a password obfuscation function that is just a simple iterated hash
or otherwise blindly upgradable. That way you can increase the number of
iterations without knowing the original password. As other posters pointed
out, you lose more or less "entropy" in doing so. Well, ok. Use a big hash,
so that the relative loss is less significant?

"""And, you will never get below                           

  ( ( pi*(2^n) )/2 )^0.5
where 'n' is the number of bits in the hash you iterate over. This is
about 128.3 bits for SHA-256."""

Given that this is a best-effort, make-them-buy-more-FPGAs game and not a
hard and fast we-can-win game, maybe that is good enough?

3. Don't worry about it, since this whole password obfuscation thing is a
losing battle in the long term anyway. Pick a decent obfuscation function
with "unnecessarily" large safety factors, and then dedicate the rest of
your time to ensuring that attackers have a real hard time actually getting
the obfuscated passwords in the first place. After all, you were going to
exert tremendous effort to stop SQL injection and backup tape theft anyway,
right? Right.

4. Dedicate your R&D cycles and dollars to solving the password problem
rather than the somewhat-better-password-obfuscation problem.

I'm not saying these are the only or even the best possibilities; they are
just illustrations of my point of view that we should consider the whole
problem. Even though this is the cryptography list and not the
secure-engineering list, I suspect based on occasional posts that people
tend to conflate the two and to treat the cryptography lists as secure
engineering resources. As a security engineer, I tend to pick up crypto out
of my toolbox last, not first, because it's such a fickle and wacky tool.


More information about the cryptography mailing list