[dm-crypt] Question on LUKS master key digest and its effect on security

[dm-crypt] Question on LUKS master key digest and its effect on security

[Tero Pesonen]

Hi!

I've been using LUKS with dm-crypt for a while now and have recently 
been trying to learn more about how it works. There's still one aspect 
in LUKS I have not found a simple answer to. That is, is the security 
of my data dependent on the public (visible in the headers) master key 
digest? I've understood that it is derived by PBKDF2 where in LUKS's 
case SHA-1 is the hash used. LuksDump accordingly shows the 160-bit 
digest which, if I again understand correctly, is used to check if the 
supplied key and the master key match. 

Now, the impression I've gathered is that in this case if I were able to 
derive from this digest the original input, I could recover the master 
key and hence decrypt the encrypted data. In other words, the master 
key is secured by the strength of the PBKDF2 procedure, which in this 
case relies on SHA-1. I've been told that SHA-1 is now considered 
broken for all uses except generating pseudo random data, i.e. hashing 
password strings to key bits in cases where the digest is not made 
availabe, i.e. the GnuPG S2K scheme and many similar. I've also gathered 
that even if SHA-1 were not broken, it would provide at max. 80 bits of 
security (due to the birthday paradox) against recovering the input 
from the digest output. Now if it is true that the LUKS master key 
digest is truly the SHA-1 derived digest of the master key, then to me 
it seems the LUKS-dm-crypt security relies on this weak point, not on 
the AES-128, for example. I guess I must be wrong here?

I tried, nevertheless, to create a new LUKS partition with a different 
hash spec, but despite what I provided for the --hash=HASH (e.g. 
SHA256) it always created a partition with hash spec SHA1 (and hence a 
20 HEX chars long digest.)

So my question is, why is having the digest generated by SHA-1 not a 
security concern, i.e. this will not make recovering the key easier 
than brute forcing a high-entropy, user-specified password string or  
AES-128 directly (in case that was used)? If there are actual security 
implications, is it possible to change the hash spec by the user?

Thank you for any comments on this,
and kind regards,
Tero Pesonen

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Milan Broz]

Tero Pesonen wrote:
> from the digest output. Now if it is true that the LUKS master key 
> digest is truly the SHA-1 derived digest of the master key, then to me 
> it seems the LUKS-dm-crypt security relies on this weak point, not on 
> the AES-128, for example. I guess I must be wrong here?

Note that hash verification is not applied directly to master key, but to 
result of PBKDF2 (with DigestKey iterations) where master key is only on its input.
See LUKS_verify_master_key() in code to verify that.

Please read archive of this list, explaining that sha-1 is not problem is
here http://article.gmane.org/gmane.linux.kernel.device-mapper.dm-crypt/3300

> I tried, nevertheless, to create a new LUKS partition with a different 
> hash spec, but despite what I provided for the --hash=HASH (e.g. 
> SHA256) it always created a partition with hash spec SHA1 (and hence a 
> 20 HEX chars long digest.)

Yes it was hardcoded to use sha1. But it is no longer true anyway.
Using another hash (all algorithms provided by libgcrypt) is already
implemented in devel code.

There is only one 20 bytes in LUKS header for digest verification,
so final verification of digest uses only first 160bits, but it is
not a security problem.

(And I'll release testing version soon with this code.)

Milan

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Tero Pesonen]

On Friday 18 September 2009, you wrote:
> Note that hash verification is not applied directly to master key,
> but to result of PBKDF2 (with DigestKey iterations) where master key
> is only on its input. See LUKS_verify_master_key() in code to verify
> that.
>
> Please read archive of this list, explaining that sha-1 is not
> problem is here
> http://article.gmane.org/gmane.linux.kernel.device-mapper.dm-crypt/33
>00

OK. I see the current attacks do not apply, and that in future versions 
the user may be able to change this.

But does this still mean that current LUKS volumes provide only 
mk-digest-iteration-count x 80 bits of effective security against brute 
force attacks?

If we presume that SHA-1 provides 80-bits of security against 
bruteforcing the input by knowing only the output, and that PBKDF2 
hashes the initial password string with salt iteration_count times, 
then it should be possible to reverse the procedure with 
iteration_count many brute force breaks of SHA-1, starting from the 
final digest and going backwards, towards the initial password string + 
salt value? The salt here only helps against dictionary attacks on the 
password string, doesn't it? If the iteration count is not very high, 
and if there is only a limited number of inputs that can generate the 
same SHA-1 output (collisions?), then if one is able to mount a 80-bit 
attack (surely one day in less-than-unforeseeable future), then simply 
forcing this then-feasible attack level to be carried out few more 
times (iter count 10 now?) should not provide long-term security, as if 
that level (80 bits) is achieved, then doing it ten times should become 
after that equally feasible quite quickly, especially if the default 
LUKS setup is for a 256 bit AES key, which would suggest an entirely 
different level of attempted security. For example, 10x2^80 < 2^84. 
This, of course, presuming that SHA-1 maintains its current, maximum, 
security level, which many seem to believe it will not retain for very 
long. This could be countered by SHA-1 actually having very many 
collisions for those outputs, i.e. the iteration output when broken 
provides many possible inputs, but even for that the iter count seems 
low in a 80-bit-is-feasible scenario.

I have no issue with, say, 80+something bits of security for my USB 
memory sticks, for example, but seeing that some people make root 
partitions with 256 bit keys, it seems they expect their password 
string entropy to determine their "weakest link", or the lowest 
determiner for the level of security achieved, not the 80 bits plus 
something level actually provided. It even begs the question why >128 
bit keys are offered in the first place.

Is this even remotely there? Or am I still missing something big here? 
Sorry if I make stupid claims, but it is good to get the information 
out there for other novices also to find when Googling.

Thanks,
Tero Pesonen

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Heinz Diehl]

On 18.09.2009, Milan Broz wrote: 

> Yes it was hardcoded to use sha1. But it is no longer true anyway.
> Using another hash (all algorithms provided by libgcrypt) is already
> implemented in devel code.

As reported some weeks ago, the buffer i/o errors are still present with
the latest svn code (from today):

[....]
Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 32
Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 4
Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 5
Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 6
Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 7
Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 8
Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 9
Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 10
Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 11
Sep 19 18:35:57 liesel kernel: __ratelimit: 37 callbacks suppressed
Sep 19 18:35:57 liesel kernel: Buffer I/O error on device dm-4, logical block 64
Sep 19 18:35:57 liesel kernel: Buffer I/O error on device dm-4, logical block 65
Sep 19 18:35:57 liesel kernel: Buffer I/O error on device dm-4, logical block 64
Sep 19 18:35:57 liesel kernel: Buffer I/O error on device dm-4, logical block 65
Sep 19 18:35:57 liesel kernel: Buffer I/O error on device dm-4, logical block 120
Sep 19 18:35:57 liesel kernel: Buffer I/O error on device dm-4, logical block 121
Sep 19 18:35:57 liesel kernel: Buffer I/O error on device dm-4, logical block 120
Sep 19 18:35:57 liesel kernel: Buffer I/O error on device dm-4, logical block 121
Sep 19 18:35:57 liesel kernel: Buffer I/O error on device dm-4, logical block 8
[....]

cryptsetup-1.0.7 works fine.

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Milan Broz]

Heinz Diehl wrote:
> On 18.09.2009, Milan Broz wrote: 
> 
> As reported some weeks ago, the buffer i/o errors are still present with
> the latest svn code (from today):
> 
> [....]
> Sep 19 18:33:05 liesel kernel: Buffer I/O error on device dm-4, logical block 32

This is not cryptsetup bug but interference with badly written
udev rules or programs reacting to uevents (like DeviceKit etc) which tries
to open/scan temporary/keyslot cryptstetup devices (I see this messages too
with dracut in Fedora).
(In 1.0.7 was 1 sec timeout which was removed, that caused these messages to appear
more often. But this timeout slowed down keyslot scan unnecessarily.)

You can easily verify that - run command which produces this messages
like cryptsetup luksOpen with --debug, and if you see
WARNING: other process locked internal device ... it is this problem.

These messages are ugly, but there is actually no problem - if cryptsetup
detects that someone locks internal keyslot device by opening it (usually it is blkid),
it remaps it to error target, so that program receives io errors on read
and quickly closes it. (unfortunately kernel log this read error to syslog.)

(I hope that udev problems will be solved soon by switching device-mapper
to use udev directly and maintain its own, correctly written, rules.)

Milan

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Heinz Diehl]

On 19.09.2009, Milan Broz wrote: 

> (I hope that udev problems will be solved soon by switching device-mapper
> to use udev directly and maintain its own, correctly written, rules.)

Today I upgraded to the latest device-mapper, and the buffer i/o errors
are completely gone.

Btw: how stable is current svn, actually? ;-)

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Heinz Diehl]

On 20.09.2009, Heinz Diehl wrote: 

> Today I upgraded to the latest device-mapper, and the buffer i/o errors
> are completely gone.

Have to correct myself, after some hours there are some buffer i/o errors
in the logs again. It's a lot less errors as it has been before, but they
are not gone...

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Milan Broz]

Heinz Diehl wrote:
> On 20.09.2009, Heinz Diehl wrote: 
> 
>> Today I upgraded to the latest device-mapper, and the buffer i/o errors
>> are completely gone.
> 
> Have to correct myself, after some hours there are some buffer i/o errors
> in the logs again. It's a lot less errors as it has been before, but they
> are not gone...

Sure, because libdevmapper is still not completely udev aware:-)

Anyway, because I do not want to spent too much time with this bug
(I am sure you are not only one who see this) I moved that
error workaround after first 1 sec waiting, this should be similar to
behaviour in 1.07 but do not adds sleep when not needed)

Please can you retest with current svn code?

And btw code should be in stable state, I just need to find some time
to implement some new features before releasing stable candidate.

Milan

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Heinz Diehl]

On 20.09.2009, Milan Broz wrote: 

> Please can you retest with current svn code?

Runs fine so far, I'll let the machine stay powered on over night
and tomorrow morning, should something strange show up during this time,
I'll report it back to you.

> And btw code should be in stable state, I just need to find some time
> to implement some new features before releasing stable candidate.

Good to hear :-)

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Tero Pesonen]

On Friday 18 September 2009, Tero Pesonen wrote:
> On Friday 18 September 2009, you wrote:
> > Note that hash verification is not applied directly to master key,
> > but to result of PBKDF2 (with DigestKey iterations) where master
> > key is only on its input. See LUKS_verify_master_key() in code to
> > verify that.
> >
> > Please read archive of this list, explaining that sha-1 is not
> > problem is here
> > http://article.gmane.org/gmane.linux.kernel.device-mapper.dm-crypt/
> >33 00
>
> OK. I see the current attacks do not apply, and that in future
> versions the user may be able to change this.
>
> But does this still mean that current LUKS volumes provide only
> mk-digest-iteration-count x 80 bits of effective security against
> brute force attacks?
>
> If we presume that SHA-1 provides 80-bits of security against
> bruteforcing the input by knowing only the output, and that PBKDF2
> hashes the initial password string with salt iteration_count times,
> then it should be possible to reverse the procedure with
> iteration_count many brute force breaks of SHA-1, starting from the
> final digest and going backwards, towards the initial password string
> + salt value? The salt here only helps against dictionary attacks on
> the password string, doesn't it? If the iteration count is not very
> high, and if there is only a limited number of inputs that can
> generate the same SHA-1 output (collisions?), then if one is able to
> mount a 80-bit attack (surely one day in less-than-unforeseeable
> future), then simply forcing this then-feasible attack level to be
> carried out few more times (iter count 10 now?) should not provide
> long-term security, as if that level (80 bits) is achieved, then
> doing it ten times should become after that equally feasible quite
> quickly, especially if the default LUKS setup is for a 256 bit AES
> key, which would suggest an entirely different level of attempted
> security. For example, 10x2^80 < 2^84. This, of course, presuming
> that SHA-1 maintains its current, maximum, security level, which many
> seem to believe it will not retain for very long. This could be
> countered by SHA-1 actually having very many collisions for those
> outputs, i.e. the iteration output when broken provides many possible
> inputs, but even for that the iter count seems low in a
> 80-bit-is-feasible scenario.
>
> I have no issue with, say, 80+something bits of security for my USB
> memory sticks, for example, but seeing that some people make root
> partitions with 256 bit keys, it seems they expect their password
> string entropy to determine their "weakest link", or the lowest
> determiner for the level of security achieved, not the 80 bits plus
> something level actually provided. It even begs the question why >128
> bit keys are offered in the first place.
>
> Is this even remotely there? Or am I still missing something big
> here? Sorry if I make stupid claims, but it is good to get the
> information out there for other novices also to find when Googling.

Since there have been no comments on this, I was wondering if I should 
rather send questions of this sort on scri.crypt or some such place 
where these kind of topics are discussed? If so, is the iteration count 
10 for the PBKDF2 correct? (So that I am able to formulate my question 
right and not pass on wrong information.)

Thanks,
Tero Pesonen

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Milan Broz]

Tero Pesonen wrote:
> Since there have been no comments on this, I was wondering if I should 
> rather send questions of this sort on scri.crypt or some such place 
> where these kind of topics are discussed? If so, is the iteration count 
> 10 for the PBKDF2 correct? (So that I am able to formulate my question 
> right and not pass on wrong information.)

Yes, 10 is currently hardcoded:

// Numbers of iterations for the master key digest
#define LUKS_MKD_ITER 10

If you need Clemens' formal LUKS specification it is here
http://cryptsetup.googlecode.com/svn-history/r42/wiki/LUKS-standard/on-disk-format.pdf

Please cc me if you receive analysis in reply, thanks.

(And btw independent code review to find possible implementation mistakes is
always welcomed too, mainly now after reimplementation PBKDF2 and AF to use
gcrypt and allowing other hash algorithms:-)

Milan
--
mbroz@redhat.com

Re: [dm-crypt] Question on LUKS master key digest and its effect on?security

[Heinz Diehl]

On 22.09.2009, Tero Pesonen wrote: 

> Since there have been no comments on this, I was wondering if I should 
> rather send questions of this sort on scri.crypt or some such place 
> where these kind of topics are discussed? If so, is the iteration count 
> 10 for the PBKDF2 correct? (So that I am able to formulate my question 
> right and not pass on wrong information.)

First, I'm by no means a professional programmer, and I'm not a
LUKS/dmcrypt developer either.

As far as I understand the source, MK iterations is the iterations used to
derive the master key via PBKDF2 (mkDigestIterations), and what you can specify by using
"--iter-time" is the iterations used to transform a passphrase into a key
for one of the keyslots (passwordIterations), used to unlock the master key.

Feel free to correct me if I'm wrong.

Re: [dm-crypt] Question on LUKS master key digest and its effect on?security

[Milan Broz]

Heinz Diehl wrote:
> On 22.09.2009, Tero Pesonen wrote: 
> As far as I understand the source, MK iterations is the iterations used to
> derive the master key via PBKDF2 (mkDigestIterations), and what you can specify by using
> "--iter-time" is the iterations used to transform a passphrase into a key
> for one of the keyslots (passwordIterations), used to unlock the master key.

--iter-time applies to PBKDF2 in keyslot calculation, NOT to MK digest verification,
here is iteration count fixed.

See PBKDF2 use in LUKS_verify_master_key() vs LUKS_set_key().

Milan

Re: [dm-crypt] Question on LUKS master key digest and its effect on security

[Tero Pesonen]

On Tuesday 22 September 2009, Milan Broz wrote:
> Tero Pesonen wrote:
> > Since there have been no comments on this, I was wondering if I
> > should rather send questions of this sort on scri.crypt or some
> > such place where these kind of topics are discussed? If so, is the
> > iteration count 10 for the PBKDF2 correct? (So that I am able to
> > formulate my question right and not pass on wrong information.)
>
> Yes, 10 is currently hardcoded:
>
> // Numbers of iterations for the master key digest
> #define LUKS_MKD_ITER 10
>
> If you need Clemens' formal LUKS specification it is here
> http://cryptsetup.googlecode.com/svn-history/r42/wiki/LUKS-standard/o
>n-disk-format.pdf
>
> Please cc me if you receive analysis in reply, thanks.

I will send something on Wednesday. Thanks.

Tero Pesonen