[cryptography] hashed passwords, iteration counts, and PBKDF2

Jon Callas jon at callas.org
Wed Oct 31 18:05:43 EDT 2012


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


On Oct 31, 2012, at 1:58 PM, travis+ml-rbcryptography at subspacefield.org wrote:

> * PGP Signed by an unknown key
> 
> Thinking out loud;
> 
> 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.
> 
> 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?

Almost certainly not. There aren't proofs of security, but I can wave my hand at some.

This basic technique is something that a number of modern (SHA-3 etc.) hash functions do. It's more or less what Skein does.

Consider what you're doing as creating a hash function with a compression function that is your base hash function (which is likely to actually be a keyed HMAC), and then you chain it with a counter that provides uniqueness per iteration.

Skein takes the Threefish tweakable cipher as its compression function and uses a counter and other stuff in the tweak to create the UBI chaining mode which has per-chunk uniqueness to get some security guarantees.

There's a handwave. If you are indeed using HMAC with a small quantity of smarts, you can almost certainly chain the HMAC proofs into a proof of security.

It's trivially no weaker than the base PRF/compression-function, which if it's an HMAC is not bad, security-wise. I can think of some ways to screw it up, but I think those imply a drastic weakness in either the underlying base hash function or HMAC itself. Even those can probably be papered over with a Luby-Rackoff argument that enough rounds covers all sins. If you're doing a few tens of thousands of rounds (which is just a good idea with PBKDF2), I'm sure that you can end up with a security floor that is much greater than the entropy in the password itself (which is going to have lots of suck -- you're lucky to *ever* get over 32 bits, and only an insane person would be much over 64, and even those are likely to be illusory).

In short, it sounds okay to me. I'm sure you can screw it up if you try, but it sounds okay to me.

	Jon


-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 3.2.0 (Build 1672)
Charset: us-ascii

wj8DBQFQkaC1sTedWZOD3gYRAtSmAKCuQSeeeq2uwuVDx9S7T/6wQquW7QCeJwH0
Tox5gJds6vvt/PmIY7GwkbE=
=6f0G
-----END PGP SIGNATURE-----



More information about the cryptography mailing list