[dm-crypt] [PATCH v1] luks1: fix pbkdf iteration estimation with sha1

Milan Broz gmazyland at gmail.com
Wed Sep 7 20:38:36 CEST 2016

On 09/07/2016 06:52 PM, Daniel P. Berrange wrote:
> On Wed, Sep 07, 2016 at 06:28:08PM +0200, Milan Broz wrote:
>> Hi Daniel,
>> On 09/07/2016 05:09 PM, Daniel P. Berrange wrote:
>>> A previous commit attempted to fix the pbkdf iteration
>>> estimation:
>>>   commit 4609fd87d7f3cbccf1ed6db257f01b18a1edcb55
>>>   Author: Milan Broz <gmazyland at gmail.com>
>>>   Date:   Thu Oct 29 11:52:18 2015 +0100
>>>     Fix PBKDF2 iteration benchmark for longer key sizes.
> BTW, I notice in that commit you also removed a bizarre
> /= 2 on the key slot iteration count
> -       PBKDF2_temp = (*PBKDF2_per_sec / 2) * (uint64_t)iteration_time_ms;
> +       PBKDF2_temp = *PBKDF2_per_sec * (uint64_t)iteration_time_ms;
> any background history on why this /2 was there in the first place ?

IIRC in the first version there was hardcoded sha1 code and the switch
to use crypto library was done so it produced exactly the same iteration
counts (that time we used always 128bit key, I think).
This was hidden (and unintentional) workaround to that
double pbkdf2 sha1 problem (that expected even particular key size)
that lived longer than it should...

The benchmark differs quite a lot for the various crypto backends
(OpenSSL vs gcrypt for example) anyway. Important is that the iteration count
is high enough, and increases for the new hardware. 

> It seems rather bizarre, as AFAICT it means that if you asked for
> 1 sec pbkdf time you only got 0.5sec. So IIUC the 0.7.0 release in
> fact quadrupled the pbkdf time, by fixing this and also bumping
> default iter time to 2 seconds.

You mean 1.7 release?
That part was benchmarked many times by the people writing the paper
reporting the problem
I think we discussed several options and this one was safest and
I added extra iteration time to provide us some more time until
we have better KDF in place.
The change should be balanced with the change of using real key length,
but there were some corner cases - and the decision was to
never generate lower iterations count after the fix.

> I don't see any point in going via the public API with just a couple
> of lines later we're directly using the internal crypt_pbkdf() call
> already, especially since the public API signature is fundamentally
> broken.

The reason of using that API is that there is one point
where we can benchmark various KDFs.

What is broken with API? That there is no multiple versions of the same symbols
after such a change, that is what you mean?

> Mostly I changed that so that future readers of the code don't look
> at it and wonder wtf.com it is doing, and then have to waste time
> trying to analyse whether it is safe usage or not. There's value
> in having the code clear.

And I just did not want that every cryptsetup release calculates
the value differently just because "it is more readable".

That code has a lot of wtf but it produces usable values.

>> The whole intention of dynamic iteration count for volume key fingerprint is just
>> countermeasure for the case that RNG was flawed (it generates just limited
>> keyspace) and to somehow slow down possible bruteforce using digest only.
>> So the iteration count here is not so important as for the keyslot.
> It might not be as important as the keyslot iterations, but IMHO we should
> still take care to calculate it correctly in case the safety net is actually
> needed some day.

It depends what we define as correctly - code generates high enough iteration count,
it is not exact *time* as expected though. IMHO I think the introducing
so high dynamic digest iteration count was a overkill (it was my idea though :).
(It repeats with every slot it tries to open, former idea was to increase time
to maximal 1 second if all slots are used but with all these changes that goal
was not met.)

>>>  	if (r < 0) {
>>>  		log_err(ctx, _("Not compatible PBKDF2 options (using hash algorithm %s).\n"),
>>>  			header->hashSpec);
>>> @@ -717,7 +720,7 @@ int LUKS_generate_phdr(struct luks_phdr *header,
>>>  	/* Compute master key digest */
>>>  	iteration_time_ms /= 8;
>>> -	header->mkDigestIterations = at_least((uint32_t)(*PBKDF2_per_sec/1024) * iteration_time_ms,
>>> +	header->mkDigestIterations = at_least((uint32_t)(*PBKDF2_per_sec/1000) * iteration_time_ms,
>>>  					      LUKS_MKD_ITERATIONS_MIN);
>> The 1000 vs 1024 is not in fact mistake, it was my (stupid) optimization in old code
>> and I just keep it in place - the effect is small, I really do not care here.
>> As said above, the mkDigestIterations is just additional countermeasure.
>> So the only real problem I see there is that for volume key fingerprint we
>> do not use 20 bytes output key size, so for SHA1 it generates double iteration count.
> s/double/half/

heh, yes, you are of course right. anyway, it does not really matter there.

>> So we add cca ~120ms more for check if keyslot iteration is set to 1s.
> No, the current buggy code is removing time, not adding time, by making
> iterations value too small for the mk digest.

So it is not a bug but a feature :-)

ok, now seriously, I understand that this code is full of magic constants, but it does
the job. I am still not sure it is worth to fix in stable release though.

>> In recent version the default hash is sha256 where the problem is not present...
>> Sorry, but I do not want to change this code again, this patch do not improve any security
>> problem, it just moves the baseline a little bit.
>> Or did I miss anything important there?
>> For new LUKS we will like to use some memory-hard KDF anyway and the whole benchmarking
>> will be done differently.
> Even once LUKSv2 arrives, LUKSv1 is realistically going to live on in
> active use for years, possibly even decades. So personally I think it
> is worth fixing this, since the change to do it all correctly is very
> simple and this code is the reference implementation other people look
> to for best practice guidance when implementing the LUKS format.

Yes, and the intention is to keep LUKS1 code stable and do not modify it if
it is not absolutely necessary. The problem is that we defined iteration time
that should take "exact" time. It in fact calculates some approximation.
(But systems that use fixed PBKDF2 iterations have far more serious issues now.)

But you are right that the damage by reading magic code and copying mistakes
elsewhere is a problem.

Maybe I should fix this in next major release but not touch stable branch, dunno yet.

Anyway, thanks for looking into this and for the patch.


More information about the dm-crypt mailing list