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

Jon Callas jon at callas.org
Wed Sep 8 17:21:18 EDT 2010

On Sep 8, 2010, at 11:53 AM, travis+ml-rbcryptography at subspacefield.org wrote:

> * PGP Signed by an unknown key
> So PBKDF2 is pretty cool in many ways, but it has been a while since I
> looked at it.
> One thing about it that kinda bothers me is that, when examining it, I
> couldn't immediately see a way for a system to increment the iteration
> count without having the user re-enter a password, since U_x seems
> to depend on P.
> So, let's say you have a web site with, say, 250M users.  Over time,
> compute power increases, and you want to increase the iteration count
> of all the hashes in the database, but getting them all to enter their
> password again is untenable; there will always be people who logged in
> once and never again.
> Is there something similar to PBKDF2 that has this property?  Could
> there be, or is this a fundamental limitation of the constraints we
> want regarding security against offline attacks?

Not really. PBKDF2 has the advantage that you can use any PRF in it. The most common PRF is some HMAC, which is a one-way function. You could use a two-way function like AES in it, and get the property you want. But if you use a two-way function, that means you can reverse the derived key to get the password that the key is derived from. This, in fact, is exactly what you need to be able to change the iteration count. But you lose the fact that with a one-way function, the derived keys are just binary and there's no way to learn your 250M users' passwords. Someone who stole the file of derived keys would therefore have the passwords. That's an undesirable property of a KDF -- one-wayness is a good thing.

So you just have to wait for the users to type their password in again. You can in software update their derived key the next time they unlock. But you have to wait for them to unlock.


More information about the cryptography mailing list