[dm-crypt] Purpose of mkDigest field in LUKS header

[dm-crypt] Purpose of mkDigest field in LUKS header

[Carlo Contavalli]

Hello,

I was looking into the LUKS implementation for a crypto related project.

The field mkDigest in the LUKS header contains a PKDBF2 hash of the
volume key, which I believe is indirectly used to verify the user
passphrase.
Eg, if mkDigest on disk does not match PBKDF2 of volume key decrypted
with user passphrase, user passphrase is likely wrong.

Correct? Is there any other purpose to it?

Reason I'm asking: assuming that's the case, at passphrase insertion
time there are at least 2 PBKDF2 that need to be computed - one to
derive a key from the passphrase entered by the user, one to verify
that the volume key is correct. Both eat time and CPU.

If I was an attacker, though, I would not bother checking mkDigest at
all. I would probably just try the guessed key to decrypt a disk
block, and check for an ext4 or file system header, which I believe
would be trivial to do (cost of decrypting a block for each attempted
key, and look for common signatures).

So.. is that PBKDF2 necessary? could we replace it by, for example,
storing an encrypted one way hash of the volume key?

Eg, compute volume key, use it to decrypt a small chunk of data,
verify that the encrypted hash matches hash of volume key, without
iterations or time/cpu complexity.

My guess is that this would not significantly reduce the security of
something like LUKS and/or increase the attack surface.

Am I wrong? Did I miss anything I should be aware of?

Thanks,
Carlo

Re: [dm-crypt] Purpose of mkDigest field in LUKS header

[Arno Wagner]

On Tue, Jan 28, 2014 at 18:35:19 CET, Carlo Contavalli wrote:
> Hello,
> 
> I was looking into the LUKS implementation for a crypto related project.
> 
> The field mkDigest in the LUKS header contains a PKDBF2 hash of the
> volume key, which I believe is indirectly used to verify the user
> passphrase.
> Eg, if mkDigest on disk does not match PBKDF2 of volume key decrypted
> with user passphrase, user passphrase is likely wrong.
> 
> Correct? Is there any other purpose to it?
> 
> Reason I'm asking: assuming that's the case, at passphrase insertion
> time there are at least 2 PBKDF2 that need to be computed - one to
> derive a key from the passphrase entered by the user, one to verify
> that the volume key is correct. Both eat time and CPU.
> 
> If I was an attacker, though, I would not bother checking mkDigest at
> all. I would probably just try the guessed key to decrypt a disk
> block, and check for an ext4 or file system header, which I believe
> would be trivial to do (cost of decrypting a block for each attempted
> key, and look for common signatures).
> 
> So.. is that PBKDF2 necessary? could we replace it by, for example,
> storing an encrypted one way hash of the volume key?
> 
> Eg, compute volume key, use it to decrypt a small chunk of data,
> verify that the encrypted hash matches hash of volume key, without
> iterations or time/cpu complexity.
> 
> My guess is that this would not significantly reduce the security of
> something like LUKS and/or increase the attack surface.
> 
> Am I wrong? Did I miss anything I should be aware of?

Yes. There is no reliable way to detect "decrypted" data. It
is fundamentally impossible to do.

Also, the master key protected just by a simple has would
be open to any "reversing" attack on the hash. But if you
look at the actual parameters, you see that the PBKDF2 iteration
count for the master key is much smaller than for keyslots.
That is because it ie ensured to have high entropy. So it
really does not matter much in the volume opening time.

The second thing you missed is that this would break the LUKS 
header format, not a thing to do lightly and just for performance.

Arno
-- 
Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: arno@wagner.name
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
A good decision is based on knowledge and not on numbers. -  Plato

Re: [dm-crypt] Purpose of mkDigest field in LUKS header

[Carlo Contavalli]

On Tue, Jan 28, 2014 at 12:15 PM, Arno Wagner <arno@wagner.name> wrote:
> On Tue, Jan 28, 2014 at 18:35:19 CET, Carlo Contavalli wrote:
>> Hello,
>>
>> I was looking into the LUKS implementation for a crypto related project.
>>
>> The field mkDigest in the LUKS header contains a PKDBF2 hash of the
>> volume key, which I believe is indirectly used to verify the user
>> passphrase.
>> Eg, if mkDigest on disk does not match PBKDF2 of volume key decrypted
>> with user passphrase, user passphrase is likely wrong.
>>
>> Correct? Is there any other purpose to it?
>>
>> Reason I'm asking: assuming that's the case, at passphrase insertion
>> time there are at least 2 PBKDF2 that need to be computed - one to
>> derive a key from the passphrase entered by the user, one to verify
>> that the volume key is correct. Both eat time and CPU.
>>
>> If I was an attacker, though, I would not bother checking mkDigest at
>> all. I would probably just try the guessed key to decrypt a disk
>> block, and check for an ext4 or file system header, which I believe
>> would be trivial to do (cost of decrypting a block for each attempted
>> key, and look for common signatures).
>>
>> So.. is that PBKDF2 necessary? could we replace it by, for example,
>> storing an encrypted one way hash of the volume key?
>>
>> Eg, compute volume key, use it to decrypt a small chunk of data,
>> verify that the encrypted hash matches hash of volume key, without
>> iterations or time/cpu complexity.
>>
>> My guess is that this would not significantly reduce the security of
>> something like LUKS and/or increase the attack surface.
>>
>> Am I wrong? Did I miss anything I should be aware of?
>
> Yes. There is no reliable way to detect "decrypted" data. It
> is fundamentally impossible to do.

Not sure what the Yes refers to :)

But as per email, I was going to settle for decrypting some data, and
verifying result is as expected to make sure key is correct. Eg,
decrypt data, cleartext contains either a salted hash of the original
key, specific expected value, CCM/GCM decryption for that specific
block is passing verifications correctly, ... use some random other
method to report an error with high probability if the key is
incorrect, without actually using a PBKDF2.

> Also, the master key protected just by a simple has would
> be open to any "reversing" attack on the hash.

Agreed, that's also one of the reason I was planning not to expose a
hash of the key, but use one of the methods above.

> The second thing you missed is that this would break the LUKS
> header format, not a thing to do lightly and just for performance.

Sure, agreed!
As per email, I'm not planning to make any change to LUKS, this is
just to understand some of the design decisions for unrelated
projects.

Carlo

Re: [dm-crypt] Purpose of mkDigest field in LUKS header

[Arno Wagner]

On Wed, Jan 29, 2014 at 01:28:27 CET, Carlo Contavalli wrote:
> On Tue, Jan 28, 2014 at 12:15 PM, Arno Wagner <arno@wagner.name> wrote:
> > On Tue, Jan 28, 2014 at 18:35:19 CET, Carlo Contavalli wrote:
> >> Hello,
> >>
> >> I was looking into the LUKS implementation for a crypto related project.
> >>
> >> The field mkDigest in the LUKS header contains a PKDBF2 hash of the
> >> volume key, which I believe is indirectly used to verify the user
> >> passphrase.
> >> Eg, if mkDigest on disk does not match PBKDF2 of volume key decrypted
> >> with user passphrase, user passphrase is likely wrong.
> >>
> >> Correct? Is there any other purpose to it?
> >>
> >> Reason I'm asking: assuming that's the case, at passphrase insertion
> >> time there are at least 2 PBKDF2 that need to be computed - one to
> >> derive a key from the passphrase entered by the user, one to verify
> >> that the volume key is correct. Both eat time and CPU.
> >>
> >> If I was an attacker, though, I would not bother checking mkDigest at
> >> all. I would probably just try the guessed key to decrypt a disk
> >> block, and check for an ext4 or file system header, which I believe
> >> would be trivial to do (cost of decrypting a block for each attempted
> >> key, and look for common signatures).
> >>
> >> So.. is that PBKDF2 necessary? could we replace it by, for example,
> >> storing an encrypted one way hash of the volume key?
> >>
> >> Eg, compute volume key, use it to decrypt a small chunk of data,
> >> verify that the encrypted hash matches hash of volume key, without
> >> iterations or time/cpu complexity.
> >>
> >> My guess is that this would not significantly reduce the security of
> >> something like LUKS and/or increase the attack surface.
> >>
> >> Am I wrong? Did I miss anything I should be aware of?
> >
> > Yes. There is no reliable way to detect "decrypted" data. It
> > is fundamentally impossible to do.
> 
> Not sure what the Yes refers to :)

Yes, you are missing somehint ;-)
 
> But as per email, I was going to settle for decrypting some data, and
> verifying result is as expected to make sure key is correct. Eg,
> decrypt data, cleartext contains either a salted hash of the original
> key, specific expected value, CCM/GCM decryption for that specific
> block is passing verifications correctly, ... use some random other
> method to report an error with high probability if the key is
> incorrect, without actually using a PBKDF2.

That does expose the key to attacks in a way that is not needed 
and decreases secuirty. Otherwise, you could just store
a single hash of the key in plain. That would be about as secure.
I recommend reading clemen's original thesis for the raionale
of these design decidions. It is here:
   
   http://clemens.endorphin.org/cryptography
 
> > Also, the master key protected just by a simple has would
> > be open to any "reversing" attack on the hash.
> 
> Agreed, that's also one of the reason I was planning not to expose a
> hash of the key, but use one of the methods above.

The are really not better. In fact, hashes are generally much 
harder to reverse than breaking cipher keys.

And, as I said, the time for master-key BPKDF2-ing is insignificant
anyways. Originally, it used to just get 1000 iterations, but
now it gets, I think, 0.2 sec, compared to the 1 sec every
key-slot needs anyways. There is really no reason to make any
additional trade-offs here.
 
> > The second thing you missed is that this would break the LUKS
> > header format, not a thing to do lightly and just for performance.
> 
> Sure, agreed!
> As per email, I'm not planning to make any change to LUKS, this is
> just to understand some of the design decisions for unrelated
> projects.

I really recoomend reading the original tesis. It has much
more reasoning then the LUKS spec.

If you have questions after that, feel free to ask, maybe
I can help.

Arno
-- 
Arno Wagner,     Dr. sc. techn., Dipl. Inform.,    Email: arno@wagner.name
GnuPG: ID: CB5D9718  FP: 12D6 C03B 1B30 33BB 13CF  B774 E35C 5FA1 CB5D 9718
----
A good decision is based on knowledge and not on numbers. -  Plato