luks1: fix pbkdf iteration estimation with sha1
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
doneBefore 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: 2473429After 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: 2514570Notice 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
@@ -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
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 +0100Fix 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
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
-1if (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
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 +0100Fix 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
-0lib/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
-1if (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 :|
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 +0100Fix 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
-1if (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