Skip to contentSkip to conversation

luks1: fix pbkdf iteration estimation with sha1

PATCH In review Daniel P. Berrange 2 participants 4 messages Sep 7, 2016

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 luks1: fix pbkdf iteration estimation with sha1

A previous commit attempted to fix the pbkdf iteration estimation:

commit 4609fd87d7f3cbccf1ed6db257f01b18a1edcb55
Author: Milan Broz <[email protected]>
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.

---
 lib/luks1/keymanage.c | 18 ++++++++++++------
 1 file changed, 12 insertions(+), 6 deletions(-)
lib/luks1/keymanage.c +12 -6
index 4a9cbd6..f1682c1 100644
@@ -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,
Signature · 1 line
2.7.4
#1 lore raw

Hi Daniel,

Quoted 14 lines · Daniel P. Berrange

A previous commit attempted to fix the pbkdf iteration estimation:

commit 4609fd87d7f3cbccf1ed6db257f01b18a1edcb55
Author: Milan Broz <[email protected]>
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.

Quoted 5 lines

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

Quoted 4 lines

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.

Quoted 7 lines

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

Quoted 5 lines
lib/luks1/keymanage.c +0 -0
index 4a9cbd6..f1682c1 100644

lib/luks1/keymanage.c int LUKS_generate_phdr(struct luks_phdr *header, · line 714

Quoted 10 lines
lib/luks1/keymanage.c +5 -2
@@ -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.)

lib/luks1/keymanage.c int LUKS_generate_phdr(struct luks_phdr *header, · line 724

Quoted 10 lines
lib/luks1/keymanage.c +1 -1
 	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

#2 lore raw
Quoted 11 lines · Milan Broz

Hi Daniel,

Quoted 8 lines · Daniel P. Berrange

A previous commit attempted to fix the pbkdf iteration estimation:

commit 4609fd87d7f3cbccf1ed6db257f01b18a1edcb55
Author: Milan Broz <[email protected]>
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.

Quoted 50 lines
Quoted 11 lines

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

Quoted 4 lines

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.

Quoted 7 lines

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

Quoted 5 lines
lib/luks1/keymanage.c +0 -0
index 4a9cbd6..f1682c1 100644

lib/luks1/keymanage.c int LUKS_generate_phdr(struct luks_phdr *header, · line 714

Quoted 10 lines
lib/luks1/keymanage.c +5 -2
@@ -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

Quoted 8 lines
       // 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.

Quoted 6 lines

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.

Quoted 4 lines

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.

Quoted 16 lines

lib/luks1/keymanage.c int LUKS_generate_phdr(struct luks_phdr *header, · line 724

Quoted 10 lines
lib/luks1/keymanage.c +1 -1
 	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.

Quoted 2 lines

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/

Quoted 1 line

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.

Quoted 9 lines

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

Signature · 4 lines
|: 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 :|
#3 lore raw
Quoted 19 lines · Daniel P. Berrange
Quoted 11 lines · Milan Broz

Hi Daniel,

Quoted 8 lines · Daniel P. Berrange

A previous commit attempted to fix the pbkdf iteration estimation:

commit 4609fd87d7f3cbccf1ed6db257f01b18a1edcb55
Author: Milan Broz <[email protected]>
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

(quoted diff) +1 -1
-       PBKDF2_temp = (*PBKDF2_per_sec / 2) * (uint64_t)iteration_time_ms;
+       PBKDF2_temp = *PBKDF2_per_sec * (uint64_t)iteration_time_ms;
Quoted 1 line

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.

Quoted 4 lines

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.

Quoted 4 lines

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?

Quoted 4 lines

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.

Quoted 8 lines
Quoted 4 lines

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

Quoted 16 lines
Quoted 16 lines

lib/luks1/keymanage.c int LUKS_generate_phdr(struct luks_phdr *header, · line 724

Quoted 10 lines
lib/luks1/keymanage.c +1 -1
 	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.

Quoted 4 lines
Quoted 2 lines

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.

Quoted 5 lines
Quoted 2 lines

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.

Quoted 7 lines
Quoted 7 lines

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?

Quoted 8 lines
Quoted 2 lines

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