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

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

[Daniel P. Berrange]

A previous commit attempted to fix the pbkdf iteration
estimation:

  commit 4609fd87d7f3cbccf1ed6db257f01b18a1edcb55
  Author: Milan Broz <gmazyland@gmail.com>
  Date:   Thu Oct 29 11:52:18 2015 +0100

    Fix PBKDF2 iteration benchmark for longer key sizes.

Before this commit, it would estimate using a derived
key size of 1. After this commit, it will estimate using
a derived key size matching the key bytes recorded in
the LUKS header.

Unfortuntely this is still incorrect as there are two
different places where luks estimates pbkdf2 iterations.
For the key slots, the derived key size needs to match
master key bytes, but for the master key digest, it must
match LUKS_DIGESTSIZE.

The relationship between the derived key size and the
pbkdf2 hash size is directly related to the time spent
in computation. For example, with aes, key size 256 and
sha1, we have

  key size = 32
  hash digest = 20

Since the sha1 hash has as a 20 byte digest size, when
doing estimation with a derived key size of 32, each
iteration invokes 2 sha1 operations. If we passed a derived
key size of 20, then each iteration invokes 1 sha1 operation.

Thus, by passing 32, instead of 20, when estimating the
master key digest iterations, we're getting a value of
iterations that is 50% too small. This only affects the
sha1 hash, and only when using key sizes greater than
160 bits, since all other hashes have a large enough
digest size that they'll only ever require 1 operation
per iteration.

A second, minor mistake is made when scaling the value
of iterations per second, to match the requested iteration
time. There are 1000 milliseconds in 1 second, but the
code is scaling by 1024, making the number of iterations
ever so slightly smaller than it should be. This isn't
a significant issue, but for clarity it is good to use
the correct scaling factor for ms -> secs.

As a final cleanup, the callers to estimate iterations
are also switched so that the key/salt parameters also
match the value that will be used in the real pbkdf
call later, instead of a fixed 3 character string.

Comparative data generated with

  $ for h in sha1 sha256 sha512
    do
      echo 123456 | \
        cryptsetup luksFormat --cipher aes \
	  --key-size 256  --hash $h -q /dev/loop1
    done

Before this commit:

    master key iters: 375750
    key slot 1 iters: 3020648

    master key iters: 396250
    key slot 1 iters: 3141103

    master key iters: 312750
    key slot 1 iters: 2473429

After this commit:

    master key iters: 776500
    key slot 1 iters: 3052622

    master key iters: 398250
    key slot 1 iters: 3206654

    master key iters: 314500
    key slot 1 iters: 2514570

Notice only the master key iters changed. Although
it looks wierd that sha1 requires less iterations
than sha256 for key slot 1, this is expected because
each iteration is doing 2 * sha1 ops, but only
1 * sha256 ops causing sha1 to be more expensive
on aggregate.

Signed-off-by: Daniel P. Berrange <berrange@redhat.com>
---
 lib/luks1/keymanage.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)

diff --git a/lib/luks1/keymanage.c b/lib/luks1/keymanage.c
index 4a9cbd6..f1682c1 100644
--- a/lib/luks1/keymanage.c
+++ b/lib/luks1/keymanage.c
@@ -707,8 +707,11 @@ int LUKS_generate_phdr(struct luks_phdr *header,
 		return r;
 	}
 
-	r = crypt_benchmark_kdf(ctx, "pbkdf2", header->hashSpec,
-				"foo", 3, "bar", 3, PBKDF2_per_sec);
+	r = crypt_pbkdf_check("pbkdf2", header->hashSpec,
+			      vk->key, vk->keylength,
+			      header->mkDigestSalt, LUKS_SALTSIZE,
+			      LUKS_DIGESTSIZE,
+			      PBKDF2_per_sec);
 	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);
 
 	r = crypt_pbkdf("pbkdf2", header->hashSpec, vk->key,vk->keylength,
@@ -803,8 +806,11 @@ int LUKS_set_key(unsigned int keyIndex,
 
 	log_dbg("Calculating data for key slot %d", keyIndex);
 
-	r = crypt_benchmark_kdf(ctx, "pbkdf2", hdr->hashSpec,
-				"foo", 3, "bar", 3, PBKDF2_per_sec);
+	r = crypt_pbkdf_check("pbkdf2", hdr->hashSpec,
+			      password, passwordLen,
+			      hdr->keyblock[keyIndex].passwordSalt, LUKS_SALTSIZE,
+			      hdr->keyBytes,
+			      PBKDF2_per_sec);
 	if (r < 0) {
 		log_err(ctx, _("Not compatible PBKDF2 options (using hash algorithm %s).\n"),
 			hdr->hashSpec);
@@ -816,7 +822,7 @@ int LUKS_set_key(unsigned int keyIndex,
 	 * Final iteration count is at least LUKS_SLOT_ITERATIONS_MIN
 	 */
 	PBKDF2_temp = *PBKDF2_per_sec * (uint64_t)iteration_time_ms;
-	PBKDF2_temp /= 1024;
+	PBKDF2_temp /= 1000;
 	if (PBKDF2_temp > UINT32_MAX)
 		PBKDF2_temp = UINT32_MAX;
 	hdr->keyblock[keyIndex].passwordIterations = at_least((uint32_t)PBKDF2_temp,
-- 
2.7.4

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

[Milan Broz]

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@gmail.com>
>   Date:   Thu Oct 29 11:52:18 2015 +0100
> 
>     Fix PBKDF2 iteration benchmark for longer key sizes.
> 
> Before this commit, it would estimate using a derived
> key size of 1. After this commit, it will estimate using
> a derived key size matching the key bytes recorded in
> the LUKS header.
> 
> Unfortuntely this is still incorrect as there are two
> different places where luks estimates pbkdf2 iterations.
> For the key slots, the derived key size needs to match
> master key bytes, but for the master key digest, it must
> match LUKS_DIGESTSIZE.

For the keyslot it already matches key size, for the volume key
fingerprint (see note below).

> The relationship between the derived key size and the
> pbkdf2 hash size is directly related to the time spent
> in computation. For example, with aes, key size 256 and
> sha1, we have

.... yes, that what the original patch is about.

> A second, minor mistake is made when scaling the value
> of iterations per second, to match the requested iteration
> time. There are 1000 milliseconds in 1 second, but the
> code is scaling by 1024, making the number of iterations
> ever so slightly smaller than it should be. This isn't
> a significant issue, but for clarity it is good to use
> the correct scaling factor for ms -> secs.

Not a mistake, but just cosmetic, see below :)

> diff --git a/lib/luks1/keymanage.c b/lib/luks1/keymanage.c
> index 4a9cbd6..f1682c1 100644
> --- a/lib/luks1/keymanage.c
> +++ b/lib/luks1/keymanage.c
> @@ -707,8 +707,11 @@ int LUKS_generate_phdr(struct luks_phdr *header,
>  		return r;
>  	}
>  
> -	r = crypt_benchmark_kdf(ctx, "pbkdf2", header->hashSpec,
> -				"foo", 3, "bar", 3, PBKDF2_per_sec);
> +	r = crypt_pbkdf_check("pbkdf2", header->hashSpec,
> +			      vk->key, vk->keylength,
> +			      header->mkDigestSalt, LUKS_SALTSIZE,
> +			      LUKS_DIGESTSIZE,
> +			      PBKDF2_per_sec);

if you check  crypt_benchmark_kdf() code, it contains this

       // FIXME: this should be in KDF check API parameters later
        if (cd)
                key_length = crypt_get_volume_key_size(cd);

so the key length *is* taken into account. I intentionally want to use
libcryptsetup call here and not crypt_pbkdf_check() (but it is detail).

I just did not want to change API in stable branch, so for now it is done this way.
In next major version crypt_benchmark_kdf() will change and will contain key size.

For the benchmarking - the "foo" + "bar" (salt), yes, it is strange,
but we just benchmark to fixed password, then use baseline for real calculation.
It was this way from the beginning. In the worst case, the final iteration count
will be higher, not smaller (for reasonable long passwords).

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.

(Original LUKS has this fixed to 10 iteration anyway.)

>  	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.

So we add cca ~120ms more for check if keyslot iteration is set to 1s.

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.

Milan

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

[Daniel P. Berrange]

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@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 ?

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.

> > 
> > Before this commit, it would estimate using a derived
> > key size of 1. After this commit, it will estimate using
> > a derived key size matching the key bytes recorded in
> > the LUKS header.
> > 
> > Unfortuntely this is still incorrect as there are two
> > different places where luks estimates pbkdf2 iterations.
> > For the key slots, the derived key size needs to match
> > master key bytes, but for the master key digest, it must
> > match LUKS_DIGESTSIZE.
> 
> For the keyslot it already matches key size, for the volume key
> fingerprint (see note below).
> 
> > The relationship between the derived key size and the
> > pbkdf2 hash size is directly related to the time spent
> > in computation. For example, with aes, key size 256 and
> > sha1, we have
> 
> .... yes, that what the original patch is about.
> 
> > A second, minor mistake is made when scaling the value
> > of iterations per second, to match the requested iteration
> > time. There are 1000 milliseconds in 1 second, but the
> > code is scaling by 1024, making the number of iterations
> > ever so slightly smaller than it should be. This isn't
> > a significant issue, but for clarity it is good to use
> > the correct scaling factor for ms -> secs.
> 
> Not a mistake, but just cosmetic, see below :)
> 
> > diff --git a/lib/luks1/keymanage.c b/lib/luks1/keymanage.c
> > index 4a9cbd6..f1682c1 100644
> > --- a/lib/luks1/keymanage.c
> > +++ b/lib/luks1/keymanage.c
> > @@ -707,8 +707,11 @@ int LUKS_generate_phdr(struct luks_phdr *header,
> >  		return r;
> >  	}
> >  
> > -	r = crypt_benchmark_kdf(ctx, "pbkdf2", header->hashSpec,
> > -				"foo", 3, "bar", 3, PBKDF2_per_sec);
> > +	r = crypt_pbkdf_check("pbkdf2", header->hashSpec,
> > +			      vk->key, vk->keylength,
> > +			      header->mkDigestSalt, LUKS_SALTSIZE,
> > +			      LUKS_DIGESTSIZE,
> > +			      PBKDF2_per_sec);
> 
> if you check  crypt_benchmark_kdf() code, it contains this
> 
>        // FIXME: this should be in KDF check API parameters later
>         if (cd)
>                 key_length = crypt_get_volume_key_size(cd);
> 
> so the key length *is* taken into account. I intentionally want to use
> libcryptsetup call here and not crypt_pbkdf_check() (but it is detail).
> 
> I just did not want to change API in stable branch, so for now it is done this way.

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.

> In next major version crypt_benchmark_kdf() will change and will contain key size.
> 
> For the benchmarking - the "foo" + "bar" (salt), yes, it is strange,
> but we just benchmark to fixed password, then use baseline for real calculation.
> It was this way from the beginning. In the worst case, the final iteration count
> will be higher, not smaller (for reasonable long passwords).

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.

> 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.

> >  	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/

> 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.

> 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.

Regards,
Daniel
-- 
|: http://berrange.com      -o-    http://www.flickr.com/photos/dberrange/ :|
|: http://libvirt.org              -o-             http://virt-manager.org :|
|: http://autobuild.org       -o-         http://search.cpan.org/~danberr/ :|
|: http://entangle-photo.org       -o-       http://live.gnome.org/gtk-vnc :|

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

[Milan Broz]

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@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.

Milan