[cryptography] is there an interation-incremental version of PBKDF2?
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>
>>> 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
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
More information about the cryptography