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

Marsh Ray marsh at extendedsubset.com
Thu Sep 9 14:28:29 EDT 2010

On 09/08/2010 05:06 PM, travis+ml-rbcryptography at subspacefield.org wrote:
> On Wed, Sep 08, 2010 at 02:21:18PM -0700, Jon Callas wrote:
>> 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...
> one-wayness is a good thing.
>  [...]
> IIRC, OpenBSD used to repeatedly iterate a OWF on the user's
> password for crypt(3).  This only required the plaintext password for
> the first iteration; to increase the iteration count, I just OWF the
> stored value again - no user interaction required.

 > But is there a reason to require
 > the password as input to every round of iteration of a KDF?

Here's a reason:

> On 09/08/2010 11:29 AM, mheyman at gmail.com wrote:
>> On Fri, Sep 3, 2010 at 10:29 AM, Jack Lloyd<lloyd at randombit.net>
>> wrote:
>>> On Fri, Sep 03, 2010 at 09:45:20AM +0100, Ben Laurie wrote:
>>> ...narrow-pipe designs have a huge null space for messages which
>>> are exactly as big as the compression function input size. For
>>> instance hashing inputs that are multiples of 512 bits, SHA-256
>>> will only produce about 63% of the possible 2^256 outputs.
>> So we deal with SHA-255.33 instead of SHA-256. Not a big enough
>> difference to worry about.

But without a fresh injection of entropy, the effective entropy in the
resulting hash is reduced more than half a bit per log2
of the iteration count.

Looking at OpenBSD's configuration format:
> Possible values are: ``old'', ``newsalt,<rounds>'',
> ``md5'', and ``blowfish,<rounds>'' where ``old'' means classic
> 56-bit DES.  For ``newsalt'' the value of rounds is a 24-bit integer
> with a minimum of 7250 rounds. For ``blowfish'' the value can be
> between 4 and 31.  It specifies the base 2 logarithm of the number of
> rounds.

It interprets the parameter as the log2 of the target iteration count, 
so in a sense the entropy loss is linear. The default is 6 or 8.

7250 rounds could be losing 9 or 10 bits of entropy. I haven't looked at 
that particular algorithm, it could be losing more or none at all 
depending on how its done.

I glanced at the MD5crypt code, it looks like it uses 1000 iterations, 
so it probably loses 7 or more bits.

OpenBSD's bcrypt seems to have a generous amount of internal state so 
probably isn't losing anything measurable.

But when it comes to simple iterations applied to a narrow 64-bit hash 
like the traditional crypt(3), it seems that "more is less". It may or 
may not be significant in any given setup, but it's something to be 
aware of.

- Marsh

More information about the cryptography mailing list