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

Daniel P. Berrange berrange at redhat.com
Wed Sep 7 18:52:40 CEST 2016


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 ?

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


More information about the dm-crypt mailing list