dm-crypt IV generation (summary)

dm-crypt IV generation (summary)

[Ondrej Mosnacek]

Hi all,

I was tasked to post a summary the whole dm-crypt IV generation
problem and all the suggested solutions along with their drawbacks, so
here it goes...

PROBLEM STATEMENT:
Currently, dm-crypt uses a fixed 512-byte sector size and handles
en-/decrypting of a bio by submitting a separate request to the crypto
API for each sector. This causes a performance problem with some
crypto drivers that have a high processing overhead for small
requests, i.e. most crypto accelerators [1][2] and also e.g. the
AES-NI driver [3].

POSSIBLE SOLUTIONS:
1. Move IV generator algorithms to crypto API and allow them to
process the whole bio at once. ([5] or something equivalent)
    ISSUES:
        a) The 'keycount' parameter.
            In order to support multi-key modes from Loop-AES,
dm-crypt accepts a keycount parameter which, if it != 1, causes
consecutive sectors to be encrypted with a different key. This
parameter can be specified with any of the cipher modes, which makes
porting the whole scale of modes supported by dm-crypt to crypto API
rather messy, since a lot of dm-crypt specific stuff needs to be moved
into the crypto drivers.
        b) New AEAD functionality; random IV generator.
            The soon-to-be-added AEAD functionality in dm-crypt
introduces a new IV generator that generates IVs randomly and stores
them as sector metadata. This means IV generation cannot be handled
solely in the driver. Also, additional AEAD implementation of IV
generators would be eventually needed.

2. Restrict the keycount parameter to allow only reasonable
combinations and then move IV generators to crypto API.
    In Loop-AES, the multi-key mode always uses exactly 64 keys and
there is no reasonable scenario where someone would like to use
keycount != 1 with other IV mode than LMK. Thus it might be acceptable
to only work with multiple keys in LMK (and only allow keycount == 64
for it) and work with just one key in all other modes (and only allow
keycount == 1 for them). I.e., the cipher format would remain the
same, just with more restricted values.

    Note that this would be basically a breaking change (the keycount
parameter is documented [4], so there may be users somewhere that use
it in some unusual combination...). Still, such combinations would
have to be used explicitly, as they are never used with common
LUKS/Loop-AES/TrueCrypt partitions (something like cryptsetup --type
plain ... or dmsetup would have to be used directly).

    Applying this change would allow implementing the IV generators as
simple crypto algorithms that honor the usual interface (without
setkey hacks and passing of special structures via IV).

    ISSUES:
        a) Backward incompatibility (see above).
        b) Again need to somehow handle the new 'random' IV generator.

3. Extend crypto API to allow passing multiple requests at once (each
with a separate IV) to crypto drivers.
    (see [3])
    ISSUES:
        a) HW accelerators would have to specifically support this
scheme (unless they are somehow programmable).
            I.e. accelerators that already have the plain64 IV
generator hard-coded could not fully benefit from this (I don't know
how many are already out there). However, future ones could implement
this 'universal' IV mode and enjoy basically the same benefit.

4. Implement support of 4KB sectors (or other sizes, too) in dm-crypt.
    This would partially help, since on devices with 4K sectors the
size of each crypto request would then be 8x bigger and overhead would
be reduced without the need to mess with the dm-crypt IV generators.

    ISSUES:
        a) Only 4KB would be processed at once, not the whole bio (but
it may suffice).
        b) Partitions encrypted as 4KB sectors could not be safely
moved to a 512B-sector device (writes would not be atomic).

QUESTIONS:
@Mike/dm-devel: Do you think it would be feasible to apply solution 2
(thus introducing the small incompatibility)?

REFERENCES:
[1] https://nelenkov.blogspot.com/2015/05/hardware-accelerated-disk-encryption-in.html
[2] https://lkml.org/lkml/2017/3/2/274
[3] https://www.mail-archive.com/linux-crypto@vger.kernel.org/msg23007.html
[4] https://gitlab.com/cryptsetup/cryptsetup/wikis/DMCrypt
[5] https://lkml.org/lkml/2017/2/7/182

Cheers,
Ondrej

Re: dm-crypt IV generation (summary)

[Mike Snitzer]

On Fri, Mar 10 2017 at  8:44am -0500,
Ondrej Mosnacek <omosnace@redhat.com> wrote:

> Hi all,
> 
> I was tasked to post a summary the whole dm-crypt IV generation
> problem and all the suggested solutions along with their drawbacks, so
> here it goes...

Thanks for the summary.
...
 
> 2. Restrict the keycount parameter to allow only reasonable
> combinations and then move IV generators to crypto API.
>     In Loop-AES, the multi-key mode always uses exactly 64 keys and
> there is no reasonable scenario where someone would like to use
> keycount != 1 with other IV mode than LMK. Thus it might be acceptable
> to only work with multiple keys in LMK (and only allow keycount == 64
> for it) and work with just one key in all other modes (and only allow
> keycount == 1 for them). I.e., the cipher format would remain the
> same, just with more restricted values.
> 
>     Note that this would be basically a breaking change (the keycount
> parameter is documented [4], so there may be users somewhere that use
> it in some unusual combination...). Still, such combinations would
> have to be used explicitly, as they are never used with common
> LUKS/Loop-AES/TrueCrypt partitions (something like cryptsetup --type
> plain ... or dmsetup would have to be used directly).
> 
>     Applying this change would allow implementing the IV generators as
> simple crypto algorithms that honor the usual interface (without
> setkey hacks and passing of special structures via IV).
> 
>     ISSUES:
>         a) Backward incompatibility (see above).
>         b) Again need to somehow handle the new 'random' IV generator.

...
> 
> QUESTIONS:
> @Mike/dm-devel: Do you think it would be feasible to apply solution 2
> (thus introducing the small incompatibility)?

Of all the proposals I think 2 is the best.  But I'm not in a position
to _know_ how problematic such an incompatible change would be.  As such
I unfortunately would need to defer to Milan, Herbert and others to say
how risky such a change would be.  If the real-world risk is very
limited then I think it would enable the most effective solution (moving
the IV generators to crypto without carrying excess dm-crypt baggage).

The other part mentioned ("need to somehow handle the new 'random' IV
generator"): Milan or others, do you have ideas for this?  Presummably
that is a prereq to moving forward with restricting keycount.

Mike

Re: dm-crypt IV generation (summary)

[Herbert Xu]

On Fri, Mar 10, 2017 at 02:44:26PM +0100, Ondrej Mosnacek wrote:
> Hi all,
> 
> I was tasked to post a summary the whole dm-crypt IV generation
> problem and all the suggested solutions along with their drawbacks, so
> here it goes...

Thanks for the summary.  It looks good to me.

Something else to keep mind is the potential to reuse IV generators.

Recently a patch has been proposed for fscrypt that also makes
use of essiv (search for "fscrypt: Add support for AES-128-CBC").
It would be great if we could reuse the same code for both dm-crypt
and fscrypt.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: dm-crypt IV generation (summary)

[Mike Snitzer]

On Thu, Apr 06 2017 at  5:29am -0400,
Herbert Xu <herbert@gondor.apana.org.au> wrote:

> On Fri, Mar 10, 2017 at 02:44:26PM +0100, Ondrej Mosnacek wrote:
> > Hi all,
> > 
> > I was tasked to post a summary the whole dm-crypt IV generation
> > problem and all the suggested solutions along with their drawbacks, so
> > here it goes...
> 
> Thanks for the summary.  It looks good to me.

There were 4 different solutions presented.  In reading each, option 2
looked the most promising.  BUT it requires a tradeoff/decision to be
made, please see my earlier reply where I asked for your (and/or
Milan's) thoughts:
https://www.spinics.net/lists/linux-crypto/msg24586.html

Thanks,
Mike

Re: dm-crypt IV generation (summary)

[Herbert Xu]

On Fri, Mar 10, 2017 at 02:44:26PM +0100, Ondrej Mosnacek wrote:
>
>     ISSUES:
>         a) The 'keycount' parameter.
>             In order to support multi-key modes from Loop-AES,
> dm-crypt accepts a keycount parameter which, if it != 1, causes
> consecutive sectors to be encrypted with a different key. This
> parameter can be specified with any of the cipher modes, which makes
> porting the whole scale of modes supported by dm-crypt to crypto API
> rather messy, since a lot of dm-crypt specific stuff needs to be moved
> into the crypto drivers.

Actually I think this one can probably easily handled in the crypto
layer.  All we need is to add a multikey template that sits on top
of an underlying IV generator.  The multikey instance can then accept
a key length that is a multiple of the underlying key length.

>         b) New AEAD functionality; random IV generator.
>             The soon-to-be-added AEAD functionality in dm-crypt
> introduces a new IV generator that generates IVs randomly and stores
> them as sector metadata. This means IV generation cannot be handled
> solely in the driver. Also, additional AEAD implementation of IV
> generators would be eventually needed.

Again I don't see the problem here.  IV generators are supposed
to return the IV to the caller so that it can be transmitted.

For example, the IV generated in IPsec is explicitly transmitted.
Here we just need to store the IV.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: dm-crypt IV generation (summary)

[Ondrej Mosnacek]

2017-04-07 8:12 GMT+02:00 Herbert Xu <herbert@gondor.apana.org.au>:
> On Fri, Mar 10, 2017 at 02:44:26PM +0100, Ondrej Mosnacek wrote:
>>
>>     ISSUES:
>>         a) The 'keycount' parameter.
>>             In order to support multi-key modes from Loop-AES,
>> dm-crypt accepts a keycount parameter which, if it != 1, causes
>> consecutive sectors to be encrypted with a different key. This
>> parameter can be specified with any of the cipher modes, which makes
>> porting the whole scale of modes supported by dm-crypt to crypto API
>> rather messy, since a lot of dm-crypt specific stuff needs to be moved
>> into the crypto drivers.
>
> Actually I think this one can probably easily handled in the crypto
> layer.  All we need is to add a multikey template that sits on top
> of an underlying IV generator.  The multikey instance can then accept
> a key length that is a multiple of the underlying key length.

I thought of that, too, but unfortunately with TCW the key structure is:

| KEY 1 | KEY 2 | ... | KEY n | IV SEED (size = IV size) | WHITENING
(size = 16 bytes) |

So part of the key needs to be processed before it is split into multiple keys.

Also with the LMK mode, there is a similar optional key appendix,
which is of the same size as the other subkeys.

>>         b) New AEAD functionality; random IV generator.
>>             The soon-to-be-added AEAD functionality in dm-crypt
>> introduces a new IV generator that generates IVs randomly and stores
>> them as sector metadata. This means IV generation cannot be handled
>> solely in the driver. Also, additional AEAD implementation of IV
>> generators would be eventually needed.
>
> Again I don't see the problem here.  IV generators are supposed
> to return the IV to the caller so that it can be transmitted.
>
> For example, the IV generated in IPsec is explicitly transmitted.
> Here we just need to store the IV.

My point is that it doesn't make much sense to have a crypto API alg
that calls get_random_bytes() as part of its implementation. IMHO,
that might tempt HW drivers to replace it with some crappy
alternatives, which wouldn't be good... Also, how would we test such
alg with testmgr?

I would say the best solution in this case would be to treat the
'random' IV mode as a special case in dm-crypt: the IVs would be
generated in dm-crypt and passed to a special template (which would
have a similar interface as the other IV generation templates) that
would just pass the generated IVs to underlying skciphers instead of
generating them from the sequence number. This template would need to
provide some way to pass the IVs, e.g. by prepending them to the
plaintext/ciphertext.

Cheers,
Ondrej

Re: dm-crypt IV generation (summary)

[Herbert Xu]

On Thu, May 18, 2017 at 01:40:38PM +0200, Ondrej Mosnacek wrote:
>
> > Actually I think this one can probably easily handled in the crypto
> > layer.  All we need is to add a multikey template that sits on top
> > of an underlying IV generator.  The multikey instance can then accept
> > a key length that is a multiple of the underlying key length.
> 
> I thought of that, too, but unfortunately with TCW the key structure is:
> 
> | KEY 1 | KEY 2 | ... | KEY n | IV SEED (size = IV size) | WHITENING
> (size = 16 bytes) |
> 
> So part of the key needs to be processed before it is split into multiple keys.
> 
> Also with the LMK mode, there is a similar optional key appendix,
> which is of the same size as the other subkeys.

The format of the key isn't an issue.  Because we're writing this
from scratch.  We can change the format in any way we want, e.g.,
we could include the value n if we wanted in the key stream.

Yes dm-crypt would need to massage the key before passing it over
to the crypto layer, but that should be pretty easy.

> My point is that it doesn't make much sense to have a crypto API alg
> that calls get_random_bytes() as part of its implementation. IMHO,
> that might tempt HW drivers to replace it with some crappy
> alternatives, which wouldn't be good... Also, how would we test such
> alg with testmgr?

You are right.  There is no way we can judge the quality of a
hardware IV generator, just as there is no way to judge the quality
of hardware RNG without looking at its internal structure.

But that doesn't mean that we shouldn't support them if they exist.

In any case, this scenario already exists today with IPsec where
we have multiple hardware implementations that generate the IV.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt