LinuxLists.cc - xts fuzz testing and lack of ciphertext stealing support

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Wed, 17 Jul 2019 at 19:28, Eric Biggers <[email protected]> wrote:
>
> On Wed, Jul 17, 2019 at 05:09:31PM +0000, Horia Geanta wrote:
> > On 7/17/2019 1:16 AM, Eric Biggers wrote:
> > > Hi Horia,
> > >
> > > On Tue, Jul 16, 2019 at 05:46:29PM +0000, Horia Geanta wrote:
> > >> Hi,
> > >>
> > >> With fuzz testing enabled, I am seeing xts(aes) failures on caam drivers.
> > >>
> > >> Below are several failures, extracted from different runs:
> > >>
> > >> [ 3.921654] alg: skcipher: xts-aes-caam encryption unexpectedly succeeded on test vector "random: len=40 klen=64"; expected_error=-22, cfg="random: inplace use_finup nosimd src_divs=[57.93%@+11, 37.18%@+164, <reimport>0.68%@+4, 0.50%@+305, 3.71%@alignmask+3975]"
> > >>
> > >> [ 3.726698] alg: skcipher: xts-aes-caam encryption unexpectedly succeeded on test vector "random: len=369 klen=64"; expected_error=-22, cfg="random: inplace may_sleep use_digest src_divs=[100.0%@alignmask+584]"
> > >>
> > >> [ 3.741082] alg: skcipher: xts-aes-caam encryption unexpectedly succeeded on test vector "random: len=2801 klen=64"; expected_error=-22, cfg="random: inplace may_sleep use_digest src_divs=[100.0%@+6] iv_offset=18"
> > >>
> > >> It looks like the problem is not in CAAM driver.
> > >> More exactly, fuzz testing is generating random test vectors and running
> > >> them through both SW generic (crypto/xts.c) and CAAM implementation:
> > >> -SW generic implementation of xts(aes) does not support ciphertext stealing
> > >> and throws -EINVAL when input is not a multiple of AES block size (16B)
> > >> -caam has support for ciphertext stealing, and allows for any input size
> > >> which results in "unexpectedly succeeded" error messages.
> > >>
> > >> Any suggestion how this should be fixed?
> > >>
> > >> Thanks,
> > >> Horia
> > >
> > > I don't think drivers should allow inputs the generic implementation doesn't,
> > > since those inputs aren't tested by the crypto self-tests (so how do you know
> > How about implementation adding static test vectors and using them to validate
> > the standard feature set that's not supported by the generic implementation?
> >
> > > it's even correct?), and people could accidentally rely on the driver-specific
> > > behavior and then be unable to migrate to another platform or implementation.
> > >
> > People could also *intentionally* rely on a driver offering an implementation
> > that is closer to the spec / standard.
> >
> > > So for now I recommend just updating the caam driver to return -EINVAL on XTS
> > > inputs not evenly divisible by the block size.
> > >
> > I was hoping for something more constructive...
> >
> > > Of course, if there are actual use cases for XTS with ciphertext stealing in the
> > > kernel, we could add it to all the other implementations too. But I'm not aware
> > > of any currently. Don't all XTS users in the kernel pass whole blocks?
> > >
> > That's my guess too.
> >
> > What about user space relying on offloading and xts working
> > according to the spec?
> >
>
> Sure, AF_ALG users could expect ciphertext stealing to work. I don't know of
> any actual examples of people saying they want it, but it's possible.
>
> My point is simply that we add this, we need to find a way to support it in all
> implementations. It's not helpful to add it to only one specific driver, as
> then it's inconsistent and is untestable with the common tests.
>

IIRC there are different ways to implement CTS, and the cts template
we have in the kernel (which is used for CBC in some cases) implements
the flavor where the last two blocks are reordered if the input size
is an exact multiple of the block size. If your CTS implementation
does not implement this reordering (which seems to be the case since
it is compatible with plain XTS), it implements CTS in an incompatible
way.

Since the kernel does not support CTS for XTS any way, and since no
AF_ALG users can portably rely on this, I agree with Eric that the
only sensible way to address this is to disable this functionality in
the driver.

2019-07-18 06:54:48

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Wed, Jul 17, 2019 at 08:08:27PM +0200, Ard Biesheuvel wrote:
>
> Since the kernel does not support CTS for XTS any way, and since no
> AF_ALG users can portably rely on this, I agree with Eric that the
> only sensible way to address this is to disable this functionality in
> the driver.

But the whole point of XTS is that it supports sizes that are
not multiples of the block size. So implementing it without
supporting ciphertext stealing is just wrong.

So let's fix the generic implementation rather than breaking
the caam driver.

Thanks,
--
Email: Herbert Xu <[email protected]>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

2019-07-18 07:16:41

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, 18 Jul 2019 at 08:52, Herbert Xu <[email protected]> wrote:
>
> On Wed, Jul 17, 2019 at 08:08:27PM +0200, Ard Biesheuvel wrote:
> >
> > Since the kernel does not support CTS for XTS any way, and since no
> > AF_ALG users can portably rely on this, I agree with Eric that the
> > only sensible way to address this is to disable this functionality in
> > the driver.
>
> But the whole point of XTS is that it supports sizes that are
> not multiples of the block size. So implementing it without
> supporting ciphertext stealing is just wrong.
>
> So let's fix the generic implementation rather than breaking
> the caam driver.
>

Not just the generic implementation: there are numerous synchronous
and asynchronous implementations of xts(aes) in the kernel that would
have to be fixed, while there are no in-kernel users that actually
rely on CTS. Also, in the cbc case, we support CTS by wrapping it into
another template, i.e., cts(cbc(aes)).

So retroactively redefining what xts(...) means seems like a bad idea
to me. If we want to support XTS ciphertext stealing for the benefit
of userland, let's do so via the existing cts template, and add
support for wrapping XTS to it.

2019-07-18 07:24:29

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, Jul 18, 2019 at 09:15:39AM +0200, Ard Biesheuvel wrote:
>
> Not just the generic implementation: there are numerous synchronous
> and asynchronous implementations of xts(aes) in the kernel that would
> have to be fixed, while there are no in-kernel users that actually
> rely on CTS. Also, in the cbc case, we support CTS by wrapping it into
> another template, i.e., cts(cbc(aes)).
>
> So retroactively redefining what xts(...) means seems like a bad idea
> to me. If we want to support XTS ciphertext stealing for the benefit
> of userland, let's do so via the existing cts template, and add
> support for wrapping XTS to it.

XTS without stealing should be renamed as XEX. Sure you can then
wrap it inside cts to form xts but the end result needs to be called
xts.

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

2019-07-18 07:28:36

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, 18 Jul 2019 at 09:22, Herbert Xu <[email protected]> wrote:
>
> On Thu, Jul 18, 2019 at 09:15:39AM +0200, Ard Biesheuvel wrote:
> >
> > Not just the generic implementation: there are numerous synchronous
> > and asynchronous implementations of xts(aes) in the kernel that would
> > have to be fixed, while there are no in-kernel users that actually
> > rely on CTS. Also, in the cbc case, we support CTS by wrapping it into
> > another template, i.e., cts(cbc(aes)).
> >
> > So retroactively redefining what xts(...) means seems like a bad idea
> > to me. If we want to support XTS ciphertext stealing for the benefit
> > of userland, let's do so via the existing cts template, and add
> > support for wrapping XTS to it.
>
> XTS without stealing should be renamed as XEX. Sure you can then
> wrap it inside cts to form xts but the end result needs to be called
> xts.
>

If we were adding XTS to the kernel today, then I would agree with
you. But xts() has an established meaning now, and I don't think it
makes sense to update all implementations for a theoretical use case,
given that no portable userland code can rely on the correct semantics
today, since CAAM is the only one that implements them correctly.

In any case, I won't have time to fix the ARM or arm64 implementations
(or review the changes if someone else steps up) until the end of
September.

2019-07-18 07:40:38

by Milan Broz

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On 18/07/2019 09:21, Herbert Xu wrote:
> On Thu, Jul 18, 2019 at 09:15:39AM +0200, Ard Biesheuvel wrote:
>>
>> Not just the generic implementation: there are numerous synchronous
>> and asynchronous implementations of xts(aes) in the kernel that would
>> have to be fixed, while there are no in-kernel users that actually
>> rely on CTS. Also, in the cbc case, we support CTS by wrapping it into
>> another template, i.e., cts(cbc(aes)).
>>
>> So retroactively redefining what xts(...) means seems like a bad idea
>> to me. If we want to support XTS ciphertext stealing for the benefit
>> of userland, let's do so via the existing cts template, and add
>> support for wrapping XTS to it.
>
> XTS without stealing should be renamed as XEX. Sure you can then
> wrap it inside cts to form xts but the end result needs to be called
> xts.

While I fully agree here from the technical point of view,
academically XEX, XEX* is a different mode.
It would create even more confusion.

Couldn't resist, but this is a nice example of what happens when academic,
standardization, and reality meets in one place :)

XTS is already implemented in gcrypt and OpenSSL.
IMO all the implementation should be exactly the same.

I agree with Herbert that the proper way is to implement ciphertext stealing.
Otherwise, it is just incomplete implementation, not a redefining XTS mode!

See the reference in generic code - the 3rd line - link to the IEEE standard.
We do not implement it properly - for more than 12 years!

Reality check - nobody in block layer needs ciphertext stealing, we are always
aligned to block. AF_ALG is a different story, though.

Milan

2019-07-18 07:51:43

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, Jul 18, 2019 at 09:28:03AM +0200, Ard Biesheuvel wrote:
>
> If we were adding XTS to the kernel today, then I would agree with
> you. But xts() has an established meaning now, and I don't think it
> makes sense to update all implementations for a theoretical use case,
> given that no portable userland code can rely on the correct semantics
> today, since CAAM is the only one that implements them correctly.
>
> In any case, I won't have time to fix the ARM or arm64 implementations
> (or review the changes if someone else steps up) until the end of
> September.

I'm not asking you or anyone to fix this right away. I'm just
saying that this is the direction we should be moving in.

After all, there is no immediate crisis as all that is broken
today is a fuzz test.

It should be possible to do this without causing performance
regressions for ARM. We could rename the existing xts to a
new name (xek perhaps) and add xts into the cts template as
a wrapper around xek.

That way you don't have to touch the ARM code at all and it
should just work.

PS should we mark xek or whatever it's called as internal so
it isn't visible to user-space?

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

2019-07-18 10:41:52

[permalink] [raw]

Subject: RE: xts fuzz testing and lack of ciphertext stealing support

> -----Original Message-----
> From: [email protected] <[email protected]> On Behalf Of Milan Broz
> Sent: Thursday, July 18, 2019 9:40 AM
> To: Herbert Xu <[email protected]>; Ard Biesheuvel <[email protected]>
> Cc: Horia Geanta <[email protected]>; [email protected]; [email protected]
> Subject: Re: xts fuzz testing and lack of ciphertext stealing support
>
> On 18/07/2019 09:21, Herbert Xu wrote:
> > On Thu, Jul 18, 2019 at 09:15:39AM +0200, Ard Biesheuvel wrote:
> >>
> >> Not just the generic implementation: there are numerous synchronous
> >> and asynchronous implementations of xts(aes) in the kernel that would
> >> have to be fixed, while there are no in-kernel users that actually
> >> rely on CTS. Also, in the cbc case, we support CTS by wrapping it into
> >> another template, i.e., cts(cbc(aes)).
> >>
> >> So retroactively redefining what xts(...) means seems like a bad idea
> >> to me. If we want to support XTS ciphertext stealing for the benefit
> >> of userland, let's do so via the existing cts template, and add
> >> support for wrapping XTS to it.
> >
> > XTS without stealing should be renamed as XEX. Sure you can then
> > wrap it inside cts to form xts but the end result needs to be called
> > xts.
>
> While I fully agree here from the technical point of view,
> academically XEX, XEX* is a different mode.
> It would create even more confusion.
>
> Couldn't resist, but this is a nice example of what happens when academic,
> standardization, and reality meets in one place :)
>
> XTS is already implemented in gcrypt and OpenSSL.
> IMO all the implementation should be exactly the same.
>
> I agree with Herbert that the proper way is to implement ciphertext stealing.
> Otherwise, it is just incomplete implementation, not a redefining XTS mode!
>
> See the reference in generic code - the 3rd line - link to the IEEE standard.
> We do not implement it properly - for more than 12 years!
>

Full XTS is XEX-TCB-CTS so the proper terminology for "XTS without CTS" would be XEX-TCB.
But the problem there is that TCB and CTS are generic terms that do not imply a specific
implementation for generating the tweak -or- performing the ciphertext stealing.
Only the *full* XTS operation is standardized (as IEEE Std P1619).

In fact, using the current cts template around the current xts template actually does NOT
implement standards compliant XTS at all, as the CTS *implementation* for XTS is
different from the one for CBC as implemented by the current CTS template.
The actual implementation of the ciphertext stealing has (or may have) a security impact,
so the *combined* operation must be cryptanalyzed and adding some random CTS scheme
to some random block cipher mode would be a case of "roll your own crypto" (i.e. bad).

From that perspective - to prevent people from doing cryptographically stupid things -
IMHO it would be better to just pull the CTS into the XTS implementation i.e. make
xts natively support blocks that are not a multiple of (but >=) the cipher blocksize ...

> Reality check - nobody in block layer needs ciphertext stealing, we are always
> aligned to block. AF_ALG is a different story, though.

So you don't support odd sector sizes like 520 , 528, 4112, 4160 or 4224 bytes?
>
> Milan

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-18 11:21:01

by Milan Broz

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On 18/07/2019 12:40, Pascal Van Leeuwen wrote:
...
>> See the reference in generic code - the 3rd line - link to the IEEE standard.
>> We do not implement it properly - for more than 12 years!
>>
>
> Full XTS is XEX-TCB-CTS so the proper terminology for "XTS without CTS" would be XEX-TCB.
> But the problem there is that TCB and CTS are generic terms that do not imply a specific
> implementation for generating the tweak -or- performing the ciphertext stealing.
> Only the *full* XTS operation is standardized (as IEEE Std P1619).

Yes. Also XTS is allowed in FIPS now. Because the current code cannot submit
anything else than aligned blocks, we are ok.
(I hope. Speaking for disk encryption, dm-crypt, only).

> In fact, using the current cts template around the current xts template actually does NOT
> implement standards compliant XTS at all, as the CTS *implementation* for XTS is
> different from the one for CBC as implemented by the current CTS template.
> The actual implementation of the ciphertext stealing has (or may have) a security impact,
> so the *combined* operation must be cryptanalyzed and adding some random CTS scheme
> to some random block cipher mode would be a case of "roll your own crypto" (i.e. bad).

> From that perspective - to prevent people from doing cryptographically stupid things -
> IMHO it would be better to just pull the CTS into the XTS implementation i.e. make
> xts natively support blocks that are not a multiple of (but >=) the cipher blocksize ...

I would definitely prefer adding CTS directly to XTS (as it is in gcrypt or OpenSSL now)
instead of some new compositions.

Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)

(That said, I will try to find some volunteer to help with CTS in XTS implementation, if needed.)

>> Reality check - nobody in block layer needs ciphertext stealing, we are always
>> aligned to block. AF_ALG is a different story, though.
>
> So you don't support odd sector sizes like 520 , 528, 4112, 4160 or 4224 bytes?

No. Dm-crypt supports only power of two blocks, up to 4k (IOW: 512, 1024, 2048, 4096 bytes).
(Not more, because of compatible page size - this could be fixed in future though.)

The 520 hw sector is usually 512 + 8 bytes for DIF (data integrity field).
We can emulate something similar with dm-integrity, but the data section (input to encryption)
must be always as specified above (rest is in integrity bio section).

Milan

2019-07-18 15:29:12

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
>
> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
>
> (That said, I will try to find some volunteer to help with CTS in XTS implementation, if needed.)

Well the main advantage of doing it on top of the existing xts is
that you can retain the existing ARM implementations without any
changes. This would also apply to any existing xts drivers that
also don't implement CTS (I'm not aware of the status on these so
someone will need to check them one by one).

But if you were going to volunteer to change them all in one swoop
then it wouldn't matter.

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

2019-07-18 15:29:32

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, Jul 18, 2019 at 10:40:54AM +0000, Pascal Van Leeuwen wrote:
>
> In fact, using the current cts template around the current xts template actually does NOT
> implement standards compliant XTS at all, as the CTS *implementation* for XTS is
> different from the one for CBC as implemented by the current CTS template.

The template is just a name. The implementation can do whatever it
wants for each instance. So obviously we would employ a different
implementation for xts compared to cbc.

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

2019-07-18 15:43:59

[permalink] [raw]

Subject: RE: xts fuzz testing and lack of ciphertext stealing support

> > In fact, using the current cts template around the current xts template actually does NOT
> > implement standards compliant XTS at all, as the CTS *implementation* for XTS is
> > different from the one for CBC as implemented by the current CTS template.
>
> The template is just a name. The implementation can do whatever it
> wants for each instance. So obviously we would employ a different
> implementation for xts compared to cbc.
>
Hmmm ... so the generic CTS template would have to figure out whether it is wrapped
around ECB, CBC, XTS or whatever and then adjust to that?

For ECB and CBC I suppose that's techically possible. But then what do I get when I
try to wrap CTS around some block cipher mode it doesn't recognise? Tricky ...

For XTS, you have this additional curve ball being thrown in called the "tweak".
For encryption, the underlying "xts" would need to be able to chain the tweak,
from what I've seen of the source the implementation cannot do that.

For decryption, you actually first need to decrypt the last block with the last
tweak before you can decrypt the 2nd last block with the 2nd last tweak.

Not sure how you intend to handle that with some generic wrapper around "xts".

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

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-18 15:52:06

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, Jul 18, 2019 at 03:43:28PM +0000, Pascal Van Leeuwen wrote:
>
> Hmmm ... so the generic CTS template would have to figure out whether it is wrapped
> around ECB, CBC, XTS or whatever and then adjust to that?

That's not hard to do. Right now cts only supports cbc. IOW
if you pass it anything else it will refuse to instantiate.

> For XTS, you have this additional curve ball being thrown in called the "tweak".
> For encryption, the underlying "xts" would need to be able to chain the tweak,
> from what I've seen of the source the implementation cannot do that.

You simply use the underlying xts for the first n - 2 blocks and
do the last two by hand.

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

2019-07-18 16:19:59

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, 18 Jul 2019 at 17:51, Herbert Xu <[email protected]> wrote:
>
> On Thu, Jul 18, 2019 at 03:43:28PM +0000, Pascal Van Leeuwen wrote:
> >
> > Hmmm ... so the generic CTS template would have to figure out whether it is wrapped
> > around ECB, CBC, XTS or whatever and then adjust to that?
>
> That's not hard to do. Right now cts only supports cbc. IOW
> if you pass it anything else it will refuse to instantiate.
>
> > For XTS, you have this additional curve ball being thrown in called the "tweak".
> > For encryption, the underlying "xts" would need to be able to chain the tweak,
> > from what I've seen of the source the implementation cannot do that.
>
> You simply use the underlying xts for the first n - 2 blocks and
> do the last two by hand.
>

OK, so it appears the XTS ciphertext stealing algorithm does not
include the peculiar reordering of the 2 final blocks, which means
that the kernel's implementation of XTS already conforms to the spec
for inputs that are a multiple of the block size.

The reason I am not a fan of making any changes here is that there are
no in-kernel users that require ciphertext stealing for XTS, nor is
anyone aware of any reason why we should be adding it to the userland
interface. So we are basically adding dead code so that we are
theoretically compliant in a way that we will never exercise in
practice.

Note that for software algorithms such as the bit sliced NEON
implementation of AES, which can only operate on 8 AES blocks at a
time, doing the final 2 blocks sequentially is going to seriously
impact performance. This means whatever wrapper we invent around xex()
(or whatever we call it) should go out of its way to ensure that the
common, non-CTS case does not regress in performance, and the special
handling is only invoked when necessary (which will be never).

2019-07-18 16:23:44

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, Jul 18, 2019 at 06:19:24PM +0200, Ard Biesheuvel wrote:
>
> Note that for software algorithms such as the bit sliced NEON
> implementation of AES, which can only operate on 8 AES blocks at a
> time, doing the final 2 blocks sequentially is going to seriously
> impact performance. This means whatever wrapper we invent around xex()
> (or whatever we call it) should go out of its way to ensure that the
> common, non-CTS case does not regress in performance, and the special
> handling is only invoked when necessary (which will be never).

Agreed.

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

2019-07-18 16:38:18

[permalink] [raw]

Subject: RE: xts fuzz testing and lack of ciphertext stealing support

> >
> > Hmmm ... so the generic CTS template would have to figure out whether it is wrapped
> > around ECB, CBC, XTS or whatever and then adjust to that?
>
> That's not hard to do. Right now cts only supports cbc. IOW
> if you pass it anything else it will refuse to instantiate.
>

Ah, I see it now:

if (strncmp(alg->base.cra_name, "cbc(", 4))
goto err_drop_spawn;

So you cannot even do cts(xts) at the moment.

> > For XTS, you have this additional curve ball being thrown in called the "tweak".
> > For encryption, the underlying "xts" would need to be able to chain the tweak,
> > from what I've seen of the source the implementation cannot do that.
>
> You simply use the underlying xts for the first n - 2 blocks and
> do the last two by hand.
>

Possible, but then you're basically pulling a generic XTS implementation into cts.c,
since XTS is nothing more than the repeated application of just that.
Same thing would apply to any other mode you eventually need cts for.

But I suppose it would save you the trouble of having to add cts to all individual
optimized software implementations of xts-which-is-not-really-xts, so I can see
WHY you would want to do it that way ...

Tthen there's still the issue of advancing that last tweak. From what I've seen,
the xts implementation does not output the last tweak so you would have to
recompute it locally in cts.c as block_cipher_enc(iv) * alpha^j. Which is wasteful.
Of course this could be solved by redefining xts to output the last tweak
like CBC/CTR output their last IV ... Which would probably give us HW guys
trouble again because our HW cannot do *that* ... (While the HW very likely
*does* implement the cipher text stealing properly, just to be able to boast
about IEEE P1619 compliance ...)

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

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-18 17:03:55

[permalink] [raw]

Subject: RE: xts fuzz testing and lack of ciphertext stealing support

> > > For XTS, you have this additional curve ball being thrown in called the "tweak".
> > > For encryption, the underlying "xts" would need to be able to chain the tweak,
> > > from what I've seen of the source the implementation cannot do that.
> >
> > You simply use the underlying xts for the first n - 2 blocks and
> > do the last two by hand.
> >
>
> OK, so it appears the XTS ciphertext stealing algorithm does not
> include the peculiar reordering of the 2 final blocks, which means
> that the kernel's implementation of XTS already conforms to the spec
> for inputs that are a multiple of the block size.
>
Yes, for XTS you effectively don't do CTS if it's a 16 byte multiple ...

> The reason I am not a fan of making any changes here is that there are
> no in-kernel users that require ciphertext stealing for XTS, nor is
> anyone aware of any reason why we should be adding it to the userland
> interface. So we are basically adding dead code so that we are
> theoretically compliant in a way that we will never exercise in
> practice.
>
You know, having worked on all kinds of workarounds for silly irrelevant
(IMHO) corner cases in the inside-secure hardware driver over the past
months just to keep testmgr happy, this is kind of ironic ...

Cipher text stealing happens to be a *major* part of the XTS specification
(it's not actually XTS without the CTS part!), yet you are suggesting not
to implement it because *you* don't have or know a use case for it.
That seems like a pretty bad argument to me. It's not some minor corner
case that's not supported.The implementation is just *incomplete*
without it.

> Note that for software algorithms such as the bit sliced NEON
> implementation of AES, which can only operate on 8 AES blocks at a
> time, doing the final 2 blocks sequentially is going to seriously
> impact performance. This means whatever wrapper we invent around xex()
> (or whatever we call it) should go out of its way to ensure that the
> common, non-CTS case does not regress in performance, and the special
> handling is only invoked when necessary (which will be never).
>
I pretty much made the same argument about all these driver workarounds
slowing down my driver fast path but that was considered a non-issue.

In this particular case, it should not need to be more than:

if (unlikely(size & 15)) {
xts_with_partial_last_block();
} else {
xts_with_only_full_blocks();
}

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-19 01:49:31

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, Jul 18, 2019 at 04:35:26PM +0000, Pascal Van Leeuwen wrote:
>
> Tthen there's still the issue of advancing that last tweak. From what I've seen,
> the xts implementation does not output the last tweak so you would have to
> recompute it locally in cts.c as block_cipher_enc(iv) * alpha^j. Which is wasteful.
> Of course this could be solved by redefining xts to output the last tweak
> like CBC/CTR output their last IV ... Which would probably give us HW guys
> trouble again because our HW cannot do *that* ... (While the HW very likely
> *does* implement the cipher text stealing properly, just to be able to boast
> about IEEE P1619 compliance ...)

If your hardware supports XTS properly then you wouldn't even need
to use this new template. You would directly export the xts
interface.

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

2019-07-19 05:35:15

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Thu, 18 Jul 2019 at 19:03, Pascal Van Leeuwen
<[email protected]> wrote:
>
> > > > For XTS, you have this additional curve ball being thrown in called the "tweak".
> > > > For encryption, the underlying "xts" would need to be able to chain the tweak,
> > > > from what I've seen of the source the implementation cannot do that.
> > >
> > > You simply use the underlying xts for the first n - 2 blocks and
> > > do the last two by hand.
> > >
> >
> > OK, so it appears the XTS ciphertext stealing algorithm does not
> > include the peculiar reordering of the 2 final blocks, which means
> > that the kernel's implementation of XTS already conforms to the spec
> > for inputs that are a multiple of the block size.
> >
> Yes, for XTS you effectively don't do CTS if it's a 16 byte multiple ...
>
> > The reason I am not a fan of making any changes here is that there are
> > no in-kernel users that require ciphertext stealing for XTS, nor is
> > anyone aware of any reason why we should be adding it to the userland
> > interface. So we are basically adding dead code so that we are
> > theoretically compliant in a way that we will never exercise in
> > practice.
> >
> You know, having worked on all kinds of workarounds for silly irrelevant
> (IMHO) corner cases in the inside-secure hardware driver over the past
> months just to keep testmgr happy, this is kind of ironic ...
>
> Cipher text stealing happens to be a *major* part of the XTS specification
> (it's not actually XTS without the CTS part!), yet you are suggesting not
> to implement it because *you* don't have or know a use case for it.
> That seems like a pretty bad argument to me. It's not some minor corner
> case that's not supported.The implementation is just *incomplete*
> without it.
>

I would argue that these cases are diametrically opposite: you
proposed to remove support for zero length input vectors from the
entire crypto API to prevent your driver from having to deal with
inputs that the hardware cannot handle.

I am proposing not to add support for cases that we have no need for.
XTS without CTS is indistinguishable from XTS with CTS if the inputs
are always a multiple of the block size, and in 12 years, nobody has
ever raised the issue that our support is limited to that. So what
problem are we fixing by changing this? dm-crypt does not care,
fscrypt does not care, userland does not care (given that it does not
work today and we are only finding out now due to some fuzz test
failing on CAAM)

> > Note that for software algorithms such as the bit sliced NEON
> > implementation of AES, which can only operate on 8 AES blocks at a
> > time, doing the final 2 blocks sequentially is going to seriously
> > impact performance. This means whatever wrapper we invent around xex()
> > (or whatever we call it) should go out of its way to ensure that the
> > common, non-CTS case does not regress in performance, and the special
> > handling is only invoked when necessary (which will be never).
> >
> I pretty much made the same argument about all these driver workarounds
> slowing down my driver fast path but that was considered a non-issue.
>
> In this particular case, it should not need to be more than:
>
> if (unlikely(size & 15)) {
> xts_with_partial_last_block();
> } else {
> xts_with_only_full_blocks();
> }
>

Of course. But why add this at all if it is known to be dead code?

2019-07-19 07:30:23

[permalink] [raw]

Subject: RE: xts fuzz testing and lack of ciphertext stealing support

> -----Original Message-----
> From: Ard Biesheuvel <[email protected]>
> Sent: Friday, July 19, 2019 7:35 AM
> To: Pascal Van Leeuwen <[email protected]>
> Cc: Herbert Xu <[email protected]>; Milan Broz <[email protected]>; Horia Geanta <[email protected]>; linux-
> [email protected]; [email protected]
> Subject: Re: xts fuzz testing and lack of ciphertext stealing support
>
> I would argue that these cases are diametrically opposite: you
> proposed to remove support for zero length input vectors from the
> entire crypto API to prevent your driver from having to deal with
> inputs that the hardware cannot handle.
>
I did not propose any such thing - I just proposed to make zero length hash support *optional*
(i.e. don't fail and disable the driver on it) as it's totally irrelevant for 99.99999% of use cases.
(including *all* use cases I consider relevant for HW acceleration)

> I am proposing not to add support for cases that we have no need for.
>
While you are proposing to stick with an implementation that can only deal with 6.25% (1/16th) of
*legal* input data for XTS and fails on the remaining 93.75%. That's hardly a corner case anymore.

> XTS without CTS is indistinguishable from XTS with CTS if the inputs
> are always a multiple of the block size, and in 12 years, nobody has
> ever raised the issue that our support is limited to that. So what
> problem are we fixing by changing this? dm-crypt does not care,
> fscrypt does not care, userland does not care (given that it does not
> work today and we are only finding out now due to some fuzz test
> failing on CAAM)
>
If it's not supported, then it cannot be used. Most people would not start complaining about that,
they would just roll their own locally or they'd give up and/or use something else.
So the fact that it's currently not being used does not mean a whole lot. Also, it does not mean
that there will not be a relevant use case tomorrow. (and I can assure you there *are* definitely
real-life use cases, so I have to assume these are currently handled outside of the base kernel)

In any case, if you try to use XTS you would *expect* it to work for any input >= 16 bytes as that's
how the algorithm is *specified*. Without the CTS part it's simply not XTS.

> > I pretty much made the same argument about all these driver workarounds
> > slowing down my driver fast path but that was considered a non-issue.
> >
> > In this particular case, it should not need to be more than:
> >
> > if (unlikely(size & 15)) {
> > xts_with_partial_last_block();
> > } else {
> > xts_with_only_full_blocks();
> > }
> >
>
> Of course. But why add this at all if it is known to be dead code?
>
But that's just an assumption and assumptions are the root of all evil ;-)

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-19 17:35:46

[permalink] [raw]

Subject: Re: xts fuzz testing and lack of ciphertext stealing support

On Fri, 19 Jul 2019 at 09:29, Pascal Van Leeuwen
<[email protected]> wrote:
>
> > -----Original Message-----
> > From: Ard Biesheuvel <[email protected]>
> > Sent: Friday, July 19, 2019 7:35 AM
> > To: Pascal Van Leeuwen <[email protected]>
> > Cc: Herbert Xu <[email protected]>; Milan Broz <[email protected]>; Horia Geanta <[email protected]>; linux-
> > [email protected]; [email protected]
> > Subject: Re: xts fuzz testing and lack of ciphertext stealing support
> >
> > I would argue that these cases are diametrically opposite: you
> > proposed to remove support for zero length input vectors from the
> > entire crypto API to prevent your driver from having to deal with
> > inputs that the hardware cannot handle.
> >
> I did not propose any such thing - I just proposed to make zero length hash support *optional*
> (i.e. don't fail and disable the driver on it) as it's totally irrelevant for 99.99999% of use cases.
> (including *all* use cases I consider relevant for HW acceleration)
>

Fair enough. But it did involve making modifications to the generic
layer, since there are known users of the AF_ALG interface that may
pass zero length inputs (e.g., sha1sum).

> > I am proposing not to add support for cases that we have no need for.
> >
> While you are proposing to stick with an implementation that can only deal with 6.25% (1/16th) of
> *legal* input data for XTS and fails on the remaining 93.75%. That's hardly a corner case anymore.
>

I never said it was a corner case, nor does it make a lot of sense to
reason about fractional compliance, given that 100% of the inputs we
ever encounter are covered by your 6.25% of legal input data.

What i did say was that the moving parts we will add to the code will
never be put into motion, while they do increase the validation space,
and so the value of the contribution will be negative.

Perhaps I should emphasize that my concern is mainly about in-kernel
usage of the sync software ciphers, since they typically have no use
for userland, given that they can simply issue the same instructions
directly. For AF_ALG, I agree that exposing a non-compliant XTS
implementation is a bad idea.

> > XTS without CTS is indistinguishable from XTS with CTS if the inputs
> > are always a multiple of the block size, and in 12 years, nobody has
> > ever raised the issue that our support is limited to that. So what
> > problem are we fixing by changing this? dm-crypt does not care,
> > fscrypt does not care, userland does not care (given that it does not
> > work today and we are only finding out now due to some fuzz test
> > failing on CAAM)
> >
> If it's not supported, then it cannot be used. Most people would not start complaining about that,
> they would just roll their own locally or they'd give up and/or use something else.
> So the fact that it's currently not being used does not mean a whole lot. Also, it does not mean
> that there will not be a relevant use case tomorrow. (and I can assure you there *are* definitely
> real-life use cases, so I have to assume these are currently handled outside of the base kernel)
>
> In any case, if you try to use XTS you would *expect* it to work for any input >= 16 bytes as that's
> how the algorithm is *specified*. Without the CTS part it's simply not XTS.
>

I really don't care what we call it. My point is that we don't need
functionality that we will not use, regardless of how it is called.

> > > I pretty much made the same argument about all these driver workarounds
> > > slowing down my driver fast path but that was considered a non-issue.
> > >
> > > In this particular case, it should not need to be more than:
> > >
> > > if (unlikely(size & 15)) {
> > > xts_with_partial_last_block();
> > > } else {
> > > xts_with_only_full_blocks();
> > > }
> > >
> >
> > Of course. But why add this at all if it is known to be dead code?
> >
> But that's just an assumption and assumptions are the root of all evil ;-)
>

I think it was premature optimization that is the root of all evil, no?

2019-07-20 00:31:54

[permalink] [raw]

Subject: RE: xts fuzz testing and lack of ciphertext stealing support

Hi Ard,

> -----Original Message-----
> From: Ard Biesheuvel <[email protected]>
> Sent: Friday, July 19, 2019 7:15 PM
> To: Pascal Van Leeuwen <[email protected]>
> Cc: Herbert Xu <[email protected]>; Milan Broz <[email protected]>; Horia Geanta <[email protected]>; linux-
> [email protected]; [email protected]
> Subject: Re: xts fuzz testing and lack of ciphertext stealing support
>
> On Fri, 19 Jul 2019 at 09:29, Pascal Van Leeuwen
> <[email protected]> wrote:
> >
> > > -----Original Message-----
> > > From: Ard Biesheuvel <[email protected]>
> > > Sent: Friday, July 19, 2019 7:35 AM
> > > To: Pascal Van Leeuwen <[email protected]>
> > > Cc: Herbert Xu <[email protected]>; Milan Broz <[email protected]>; Horia Geanta <[email protected]>; linux-
> > > [email protected]; [email protected]
> > > Subject: Re: xts fuzz testing and lack of ciphertext stealing support
> > >
> > > I would argue that these cases are diametrically opposite: you
> > > proposed to remove support for zero length input vectors from the
> > > entire crypto API to prevent your driver from having to deal with
> > > inputs that the hardware cannot handle.
> > >
> > I did not propose any such thing - I just proposed to make zero length hash support *optional*
> > (i.e. don't fail and disable the driver on it) as it's totally irrelevant for 99.99999% of use cases.
> > (including *all* use cases I consider relevant for HW acceleration)
> >
>
> Fair enough. But it did involve making modifications to the generic
> layer, since there are known users of the AF_ALG interface that may
> pass zero length inputs (e.g., sha1sum).
>
Which is why I gave up and grudgingly implemented those workarounds ;-)

But they complicate the driver by orders of a magnitude and for that the
same validation argument you give below applies: there's now a lot more
- and worse: a lot more complicated! - code to validate in this driver.

While I seriously question the value of that contribution as well: I don't
expect this driver to ever be used for these corner cases, as you would
simply never *select* it for the applications that might hit them (or, if
you try it an run into trouble, just select another implementation). So
its really just there to keep testmgr happy and nothing else (IMHO).

Also: hardware may have a lot more "problematic" limitations that are not
currently hit by testmgr. The limitations that are hit are kind of arbitrary.
(and I'm not going to shoot myself in the foot by going into detail there ;-)

> > > I am proposing not to add support for cases that we have no need for.
> > >
> > While you are proposing to stick with an implementation that can only deal with 6.25% (1/16th) of
> > *legal* input data for XTS and fails on the remaining 93.75%. That's hardly a corner case anymore.
> >
>
> I never said it was a corner case, nor does it make a lot of sense to
> reason about fractional compliance, given that 100% of the inputs we
> ever encounter are covered by your 6.25% of legal input data.
>
> What i did say was that the moving parts we will add to the code will
> never be put into motion, while they do increase the validation space,
> and so the value of the contribution will be negative.
>
How can you be so sure that it will never be used?

> Perhaps I should emphasize that my concern is mainly about in-kernel
> usage of the sync software ciphers, since they typically have no use
> for userland, given that they can simply issue the same instructions
> directly. For AF_ALG, I agree that exposing a non-compliant XTS
> implementation is a bad idea.
>
And my concern is that I want to accelerate xts but I will now have to
cripple my driver to return -EINVAL on non-multiple-of-16 inputs while
my hardware can actually handle that just fine, just because the actual
"reference" implementation is not compliant. And if I don't match its
(incorrect!) behavior *I* will be the one being failed by testmgr.
Which seems rather unfair :-(

Note that I'm not just interested in providing support to existing
implementations, I may want to support additional features to provide
to my customers that they can use from their own drivers/applications
they build on top of it (which do not exist yet at this moment)

> > > XTS without CTS is indistinguishable from XTS with CTS if the inputs
> > > are always a multiple of the block size, and in 12 years, nobody has
> > > ever raised the issue that our support is limited to that. So what
> > > problem are we fixing by changing this? dm-crypt does not care,
> > > fscrypt does not care, userland does not care (given that it does not
> > > work today and we are only finding out now due to some fuzz test
> > > failing on CAAM)
> > >
> > If it's not supported, then it cannot be used. Most people would not start complaining about that,
> > they would just roll their own locally or they'd give up and/or use something else.
> > So the fact that it's currently not being used does not mean a whole lot. Also, it does not mean
> > that there will not be a relevant use case tomorrow. (and I can assure you there *are* definitely
> > real-life use cases, so I have to assume these are currently handled outside of the base kernel)
> >
> > In any case, if you try to use XTS you would *expect* it to work for any input >= 16 bytes as that's
> > how the algorithm is *specified*. Without the CTS part it's simply not XTS.
> >
>
> I really don't care what we call it. My point is that we don't need
> functionality that we will not use, regardless of how it is called.
>
If you make an implementation that is considered (e.g. by testmgr for fuzz testing)
to be the golden reference, then it'd better be fully compliant with the relevant
specification(s). I guess that's the real point I'm trying to make.
Now a fully compliant implementation would get penalized for being fully compliant.

> > > > I pretty much made the same argument about all these driver workarounds
> > > > slowing down my driver fast path but that was considered a non-issue.
> > > >
> > > > In this particular case, it should not need to be more than:
> > > >
> > > > if (unlikely(size & 15)) {
> > > > xts_with_partial_last_block();
> > > > } else {
> > > > xts_with_only_full_blocks();
> > > > }
> > > >
> > >
> > > Of course. But why add this at all if it is known to be dead code?
> > >
> > But that's just an assumption and assumptions are the root of all evil ;-)
> >
>
> I think it was premature optimization that is the root of all evil, no?

You are talking to a guy who used to prefer to use hand-optimized assembly
for *everything* :-D There's no such thing as time wasted on optimization!
(if it wasn't useful, at least it was fun to do! :-P)

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-20 15:25:42

by Eric Biggers

[permalink] [raw]

Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
>
> > From that perspective - to prevent people from doing cryptographically stupid things -
> > IMHO it would be better to just pull the CTS into the XTS implementation i.e. make
> > xts natively support blocks that are not a multiple of (but >=) the cipher blocksize ...
>
> I would definitely prefer adding CTS directly to XTS (as it is in gcrypt or OpenSSL now)
> instead of some new compositions.
>
> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
>

Can't the "missing modules in initramfs" issue be solved by using a
MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?

(There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
but that was simply a bug, which was fixed.)

Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
this a non-issue.

Anyway, I agree that the partial block support, if added, should just be made
available under the name "xts", as people would expect. It doesn't need a new
name.

- Eric

2019-07-20 15:44:49

by Milan Broz

[permalink] [raw]

Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

On 20/07/2019 08:58, Eric Biggers wrote:
> On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
>> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
>> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
>> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
>> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
>>
>
> Can't the "missing modules in initramfs" issue be solved by using a
> MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?
>
> (There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
> but that was simply a bug, which was fixed.)

Sure, and it is solved now. (Some systems with a hardcoded list of modules
have to be manually updated etc., but that is just bad design).
It can be done properly from the beginning.

I just want to say that that switching to XEX looks like wasting time to me
for no additional benefit.

Fully implementing XTS does make much more sense for me, even though it is long-term
the effort and the only user, for now, would be testmgr.

So, there are no users because it does not work. It makes no sense
to implement it, because there are no users... (sorry, sounds like catch 22 :)

(Maybe someone can use it for keyslot encryption for keys not aligned to
block size, dunno. Actually, some filesystem encryption could have use for it.)

> Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
> this a non-issue.

If it is not available for users, I really see no reason to introduce XEX when
it is just XTS with full blocks.

If it is visible to users, it needs some work in userspace - XEX (as XTS) need two keys,
people are already confused enough that 256bit key in AES-XTS means AES-128...
So the examples, hints, man pages need to be updated, at least.

Milan

2019-07-21 09:57:30

[permalink] [raw]

Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

On Sat, 20 Jul 2019 at 10:35, Milan Broz <[email protected]> wrote:
>
> On 20/07/2019 08:58, Eric Biggers wrote:
> > On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
> >> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> >> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> >> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> >> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
> >>
> >
> > Can't the "missing modules in initramfs" issue be solved by using a
> > MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?
> >
> > (There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
> > but that was simply a bug, which was fixed.)
>
> Sure, and it is solved now. (Some systems with a hardcoded list of modules
> have to be manually updated etc., but that is just bad design).
> It can be done properly from the beginning.
>
> I just want to say that that switching to XEX looks like wasting time to me
> for no additional benefit.
>
> Fully implementing XTS does make much more sense for me, even though it is long-term
> the effort and the only user, for now, would be testmgr.
>
> So, there are no users because it does not work. It makes no sense
> to implement it, because there are no users... (sorry, sounds like catch 22 :)
>
> (Maybe someone can use it for keyslot encryption for keys not aligned to
> block size, dunno. Actually, some filesystem encryption could have use for it.)
>
> > Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
> > this a non-issue.
>
> If it is not available for users, I really see no reason to introduce XEX when
> it is just XTS with full blocks.
>
> If it is visible to users, it needs some work in userspace - XEX (as XTS) need two keys,
> people are already confused enough that 256bit key in AES-XTS means AES-128...
> So the examples, hints, man pages need to be updated, at least.
>

OK, consider me persuaded. We are already exposing xts(...) to
userland, and since we already implement a proper subset of true XTS,
it will be simply a matter of making sure that the existing XTS
implementations don't regress in performance on the non-CTS code
paths.

It would be useful, though, to have some generic helper functions,
e.g., like the one we have for CBC, or the one I recently proposed for
CTS, so that existing implementations (such as the bit sliced AES) can
easily be augmented with a CTS code path (but performance may not be
optimal in those cases). For the ARM implementations based on AES
instructions, it should be reasonably straight forward to implement it
close to optimally by reusing some of the code I added for CBC-CTS
(but I won't get around to doing that for a while). If there are any
volunteers for looking into the generic or x86/AES-NI implementations,
please come forward :-) Also, if any of the publications that were
quoted in this thread have suitable test vectors, that would be good
to know.

2019-07-22 09:51:46

[permalink] [raw]

Subject: RE: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

> -----Original Message-----
> From: Ard Biesheuvel <[email protected]>
> Sent: Sunday, July 21, 2019 11:50 AM
> To: Milan Broz <[email protected]>
> Cc: Pascal Van Leeuwen <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> [email protected]; Horia Geanta <[email protected]>
> Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
>
> On Sat, 20 Jul 2019 at 10:35, Milan Broz <[email protected]> wrote:
> >
> > On 20/07/2019 08:58, Eric Biggers wrote:
> > > On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
> > >> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> > >> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> > >> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> > >> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
> > >>
> > >
> > > Can't the "missing modules in initramfs" issue be solved by using a
> > > MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?
> > >
> > > (There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
> > > but that was simply a bug, which was fixed.)
> >
> > Sure, and it is solved now. (Some systems with a hardcoded list of modules
> > have to be manually updated etc., but that is just bad design).
> > It can be done properly from the beginning.
> >
> > I just want to say that that switching to XEX looks like wasting time to me
> > for no additional benefit.
> >
> > Fully implementing XTS does make much more sense for me, even though it is long-term
> > the effort and the only user, for now, would be testmgr.
> >
> > So, there are no users because it does not work. It makes no sense
> > to implement it, because there are no users... (sorry, sounds like catch 22 :)
> >
> > (Maybe someone can use it for keyslot encryption for keys not aligned to
> > block size, dunno. Actually, some filesystem encryption could have use for it.)
> >
> > > Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
> > > this a non-issue.
> >
> > If it is not available for users, I really see no reason to introduce XEX when
> > it is just XTS with full blocks.
> >
> > If it is visible to users, it needs some work in userspace - XEX (as XTS) need two keys,
> > people are already confused enough that 256bit key in AES-XTS means AES-128...
> > So the examples, hints, man pages need to be updated, at least.
> >
>
> OK, consider me persuaded. We are already exposing xts(...) to
> userland, and since we already implement a proper subset of true XTS,
> it will be simply a matter of making sure that the existing XTS
> implementations don't regress in performance on the non-CTS code
> paths.
>
> It would be useful, though, to have some generic helper functions,
> e.g., like the one we have for CBC, or the one I recently proposed for
> CTS, so that existing implementations (such as the bit sliced AES) can
> easily be augmented with a CTS code path (but performance may not be
> optimal in those cases). For the ARM implementations based on AES
> instructions, it should be reasonably straight forward to implement it
> close to optimally by reusing some of the code I added for CBC-CTS
> (but I won't get around to doing that for a while). If there are any
> volunteers for looking into the generic or x86/AES-NI implementations,
> please come forward :-) Also, if any of the publications that were
> quoted in this thread have suitable test vectors, that would be good
> to know.

Unfortunately, these algorithm & protocol specifications tend to be very frugal when it
comes to providing test vectors, barely scratching the surface of any corner cases, but
at least there is one non-multiple-of-16 vector in the original IEEE P1619 / D16
specification in Annex B Test Vectors (last vector, "XTS-AES-128 applied for a data unit
that is not a multiple of 16 bytes")

Besides that, I'd be happy to generate some testvectors from our defacto-standard
implementation ;-)

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-22 17:43:20

[permalink] [raw]

Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

On Mon, 22 Jul 2019 at 12:44, Pascal Van Leeuwen
<[email protected]> wrote:
>
> > -----Original Message-----
> > From: Ard Biesheuvel <[email protected]>
> > Sent: Sunday, July 21, 2019 11:50 AM
> > To: Milan Broz <[email protected]>
> > Cc: Pascal Van Leeuwen <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> > [email protected]; Horia Geanta <[email protected]>
> > Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
> >
> > On Sat, 20 Jul 2019 at 10:35, Milan Broz <[email protected]> wrote:
> > >
> > > On 20/07/2019 08:58, Eric Biggers wrote:
> > > > On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
> > > >> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> > > >> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> > > >> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> > > >> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
> > > >>
> > > >
> > > > Can't the "missing modules in initramfs" issue be solved by using a
> > > > MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?
> > > >
> > > > (There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
> > > > but that was simply a bug, which was fixed.)
> > >
> > > Sure, and it is solved now. (Some systems with a hardcoded list of modules
> > > have to be manually updated etc., but that is just bad design).
> > > It can be done properly from the beginning.
> > >
> > > I just want to say that that switching to XEX looks like wasting time to me
> > > for no additional benefit.
> > >
> > > Fully implementing XTS does make much more sense for me, even though it is long-term
> > > the effort and the only user, for now, would be testmgr.
> > >
> > > So, there are no users because it does not work. It makes no sense
> > > to implement it, because there are no users... (sorry, sounds like catch 22 :)
> > >
> > > (Maybe someone can use it for keyslot encryption for keys not aligned to
> > > block size, dunno. Actually, some filesystem encryption could have use for it.)
> > >
> > > > Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
> > > > this a non-issue.
> > >
> > > If it is not available for users, I really see no reason to introduce XEX when
> > > it is just XTS with full blocks.
> > >
> > > If it is visible to users, it needs some work in userspace - XEX (as XTS) need two keys,
> > > people are already confused enough that 256bit key in AES-XTS means AES-128...
> > > So the examples, hints, man pages need to be updated, at least.
> > >
> >
> > OK, consider me persuaded. We are already exposing xts(...) to
> > userland, and since we already implement a proper subset of true XTS,
> > it will be simply a matter of making sure that the existing XTS
> > implementations don't regress in performance on the non-CTS code
> > paths.
> >
> > It would be useful, though, to have some generic helper functions,
> > e.g., like the one we have for CBC, or the one I recently proposed for
> > CTS, so that existing implementations (such as the bit sliced AES) can
> > easily be augmented with a CTS code path (but performance may not be
> > optimal in those cases). For the ARM implementations based on AES
> > instructions, it should be reasonably straight forward to implement it
> > close to optimally by reusing some of the code I added for CBC-CTS
> > (but I won't get around to doing that for a while). If there are any
> > volunteers for looking into the generic or x86/AES-NI implementations,
> > please come forward :-) Also, if any of the publications that were
> > quoted in this thread have suitable test vectors, that would be good
> > to know.
>
> Unfortunately, these algorithm & protocol specifications tend to be very frugal when it
> comes to providing test vectors, barely scratching the surface of any corner cases, but
> at least there is one non-multiple-of-16 vector in the original IEEE P1619 / D16
> specification in Annex B Test Vectors (last vector, "XTS-AES-128 applied for a data unit
> that is not a multiple of 16 bytes")
>

Actually, that spec has a couple of test vectors. Unfortunately, they
are all rather short (except the last one in the 'no multiple of 16
bytes' paragraph, but unfortunately, that one is in fact a multiple of
16 bytes)

I added them here [0] along with an arm64 implementation for the AES
instruction based driver. Could you please double check that these
work against your driver? That would establish a ground truth against
which we can implement the generic version as well.

[0] https://git.kernel.org/pub/scm/linux/kernel/git/ardb/linux.git/log/?h=xts-cts

> Besides that, I'd be happy to generate some testvectors from our defacto-standard
> implementation ;-)
>

One or two larger ones would be useful, yes.

2019-07-23 08:02:36

[permalink] [raw]

Subject: RE: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

> -----Original Message-----
> From: Ard Biesheuvel <[email protected]>
> Sent: Monday, July 22, 2019 6:43 PM
> To: Pascal Van Leeuwen <[email protected]>
> Cc: Milan Broz <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> [email protected]; Horia Geanta <[email protected]>
> Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
>
> On Mon, 22 Jul 2019 at 12:44, Pascal Van Leeuwen
> <[email protected]> wrote:
> >
> > > -----Original Message-----
> > > From: Ard Biesheuvel <[email protected]>
> > > Sent: Sunday, July 21, 2019 11:50 AM
> > > To: Milan Broz <[email protected]>
> > > Cc: Pascal Van Leeuwen <[email protected]>; Herbert Xu <[email protected]>; [email protected];
> linux-
> > > [email protected]; Horia Geanta <[email protected]>
> > > Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
> > >
> > > On Sat, 20 Jul 2019 at 10:35, Milan Broz <[email protected]> wrote:
> > > >
> > > > On 20/07/2019 08:58, Eric Biggers wrote:
> > > > > On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
> > > > >> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> > > > >> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> > > > >> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> > > > >> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
> > > > >>
> > > > >
> > > > > Can't the "missing modules in initramfs" issue be solved by using a
> > > > > MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?
> > > > >
> > > > > (There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
> > > > > but that was simply a bug, which was fixed.)
> > > >
> > > > Sure, and it is solved now. (Some systems with a hardcoded list of modules
> > > > have to be manually updated etc., but that is just bad design).
> > > > It can be done properly from the beginning.
> > > >
> > > > I just want to say that that switching to XEX looks like wasting time to me
> > > > for no additional benefit.
> > > >
> > > > Fully implementing XTS does make much more sense for me, even though it is long-term
> > > > the effort and the only user, for now, would be testmgr.
> > > >
> > > > So, there are no users because it does not work. It makes no sense
> > > > to implement it, because there are no users... (sorry, sounds like catch 22 :)
> > > >
> > > > (Maybe someone can use it for keyslot encryption for keys not aligned to
> > > > block size, dunno. Actually, some filesystem encryption could have use for it.)
> > > >
> > > > > Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
> > > > > this a non-issue.
> > > >
> > > > If it is not available for users, I really see no reason to introduce XEX when
> > > > it is just XTS with full blocks.
> > > >
> > > > If it is visible to users, it needs some work in userspace - XEX (as XTS) need two keys,
> > > > people are already confused enough that 256bit key in AES-XTS means AES-128...
> > > > So the examples, hints, man pages need to be updated, at least.
> > > >
> > >
> > > OK, consider me persuaded. We are already exposing xts(...) to
> > > userland, and since we already implement a proper subset of true XTS,
> > > it will be simply a matter of making sure that the existing XTS
> > > implementations don't regress in performance on the non-CTS code
> > > paths.
> > >
> > > It would be useful, though, to have some generic helper functions,
> > > e.g., like the one we have for CBC, or the one I recently proposed for
> > > CTS, so that existing implementations (such as the bit sliced AES) can
> > > easily be augmented with a CTS code path (but performance may not be
> > > optimal in those cases). For the ARM implementations based on AES
> > > instructions, it should be reasonably straight forward to implement it
> > > close to optimally by reusing some of the code I added for CBC-CTS
> > > (but I won't get around to doing that for a while). If there are any
> > > volunteers for looking into the generic or x86/AES-NI implementations,
> > > please come forward :-) Also, if any of the publications that were
> > > quoted in this thread have suitable test vectors, that would be good
> > > to know.
> >
> > Unfortunately, these algorithm & protocol specifications tend to be very frugal when it
> > comes to providing test vectors, barely scratching the surface of any corner cases, but
> > at least there is one non-multiple-of-16 vector in the original IEEE P1619 / D16
> > specification in Annex B Test Vectors (last vector, "XTS-AES-128 applied for a data unit
> > that is not a multiple of 16 bytes")
> >
>
> Actually, that spec has a couple of test vectors. Unfortunately, they
> are all rather short (except the last one in the 'no multiple of 16
> bytes' paragraph, but unfortunately, that one is in fact a multiple of
> 16 bytes)
>
Yes, as usual it's very limited and does not cover all the interesting cases.
It's still better than nothing, though.
The fact that the last one actually *is* a multiple of 16 is quite hilarious, I
had not spotted that myself yet ...

> I added them here [0] along with an arm64 implementation for the AES
> instruction based driver. Could you please double check that these
> work against your driver? That would establish a ground truth against
> which we can implement the generic version as well.
>
> [0] https://git.kernel.org/pub/scm/linux/kernel/git/ardb/linux.git/log/?h=xts-cts
>
I'd be happy to do that except that adding XTS support to the driver is still
on my todo list. I was actually waiting for some of my earlier patches to be
acked as the situation is becoming rather unmanageable for me ...

But I suppose I can give it a shot anyway - adding XTS should be relatively
simple compare to, say, adding AES-GCM. But I'm sure I'll somehow regret
saying that.

> > Besides that, I'd be happy to generate some testvectors from our defacto-standard
> > implementation ;-)
> >
>
> One or two larger ones would be useful, yes.
>
It was more or less a joke as how would you know them to be correct?
(not that I don't trust my hardware, of course ...)
If it's just for playing around, I can provide some larger vectors, no problem.

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-24 13:27:25

[permalink] [raw]

Subject: RE: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

Ard,

> -----Original Message-----
> From: Ard Biesheuvel <[email protected]>
> Sent: Monday, July 22, 2019 6:43 PM
> To: Pascal Van Leeuwen <[email protected]>
> Cc: Milan Broz <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> [email protected]; Horia Geanta <[email protected]>
> Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
>
> On Mon, 22 Jul 2019 at 12:44, Pascal Van Leeuwen
> <[email protected]> wrote:
> >
> > > -----Original Message-----
> > > From: Ard Biesheuvel <[email protected]>
> > > Sent: Sunday, July 21, 2019 11:50 AM
> > > To: Milan Broz <[email protected]>
> > > Cc: Pascal Van Leeuwen <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> > > [email protected]; Horia Geanta <[email protected]>
> > > Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
> > >
> > > On Sat, 20 Jul 2019 at 10:35, Milan Broz <[email protected]> wrote:
> > > >
> > > > On 20/07/2019 08:58, Eric Biggers wrote:
> > > > > On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
> > > > >> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> > > > >> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> > > > >> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> > > > >> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
> > > > >>
> > > > >
> > > > > Can't the "missing modules in initramfs" issue be solved by using a
> > > > > MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?
> > > > >
> > > > > (There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
> > > > > but that was simply a bug, which was fixed.)
> > > >
> > > > Sure, and it is solved now. (Some systems with a hardcoded list of modules
> > > > have to be manually updated etc., but that is just bad design).
> > > > It can be done properly from the beginning.
> > > >
> > > > I just want to say that that switching to XEX looks like wasting time to me
> > > > for no additional benefit.
> > > >
> > > > Fully implementing XTS does make much more sense for me, even though it is long-term
> > > > the effort and the only user, for now, would be testmgr.
> > > >
> > > > So, there are no users because it does not work. It makes no sense
> > > > to implement it, because there are no users... (sorry, sounds like catch 22 :)
> > > >
> > > > (Maybe someone can use it for keyslot encryption for keys not aligned to
> > > > block size, dunno. Actually, some filesystem encryption could have use for it.)
> > > >
> > > > > Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
> > > > > this a non-issue.
> > > >
> > > > If it is not available for users, I really see no reason to introduce XEX when
> > > > it is just XTS with full blocks.
> > > >
> > > > If it is visible to users, it needs some work in userspace - XEX (as XTS) need two keys,
> > > > people are already confused enough that 256bit key in AES-XTS means AES-128...
> > > > So the examples, hints, man pages need to be updated, at least.
> > > >
> > >
> > > OK, consider me persuaded. We are already exposing xts(...) to
> > > userland, and since we already implement a proper subset of true XTS,
> > > it will be simply a matter of making sure that the existing XTS
> > > implementations don't regress in performance on the non-CTS code
> > > paths.
> > >
> > > It would be useful, though, to have some generic helper functions,
> > > e.g., like the one we have for CBC, or the one I recently proposed for
> > > CTS, so that existing implementations (such as the bit sliced AES) can
> > > easily be augmented with a CTS code path (but performance may not be
> > > optimal in those cases). For the ARM implementations based on AES
> > > instructions, it should be reasonably straight forward to implement it
> > > close to optimally by reusing some of the code I added for CBC-CTS
> > > (but I won't get around to doing that for a while). If there are any
> > > volunteers for looking into the generic or x86/AES-NI implementations,
> > > please come forward :-) Also, if any of the publications that were
> > > quoted in this thread have suitable test vectors, that would be good
> > > to know.
> >
> > Unfortunately, these algorithm & protocol specifications tend to be very frugal when it
> > comes to providing test vectors, barely scratching the surface of any corner cases, but
> > at least there is one non-multiple-of-16 vector in the original IEEE P1619 / D16
> > specification in Annex B Test Vectors (last vector, "XTS-AES-128 applied for a data unit
> > that is not a multiple of 16 bytes")
> >
>
> Actually, that spec has a couple of test vectors. Unfortunately, they
> are all rather short (except the last one in the 'no multiple of 16
> bytes' paragraph, but unfortunately, that one is in fact a multiple of
> 16 bytes)
>
> I added them here [0] along with an arm64 implementation for the AES
> instruction based driver. Could you please double check that these
> work against your driver? That would establish a ground truth against
> which we can implement the generic version as well.
>
> [0] https://git.kernel.org/pub/scm/linux/kernel/git/ardb/linux.git/log/?h=xts-cts
>
I'm working on my XTS implementation now and I noticed something funny with the test
vectors. The new CTS ones you added here, I can perfectly trace back to the IEEE spec,
they match byte-for-byte.

However, the ones that already existed puzzle me. The input data matches vectors from
the IEEE spec, however the expected output cipher text does NOT ????

Case in point, the very first vector, which has a key of all zeroes, a sector number (IV)
or all zeroes and an all zeroes plaintext of 32 bytes, which matches the 1st spec vector:
testmgr.h expects:
"\x4b\xc9\x44\x4a\x11\xa3\xef\xac"
"\x30\x74\xe4\x44\x52\x77\x97\x43"
"\xa7\x60\xb2\x45\x2e\xf9\x00\x90"
"\x9f\xaa\xfd\x89\x6e\x9d\x4a\xe0"

But the specification expects:
917cf69ebd68b2ec9b9fe9a3eadda692cd43d2f59598ed858c02c2652fbf922e

Which also happens to be what our hardware does ...

Did you notice the same thing with your implementation? Am I missing something??

> > Besides that, I'd be happy to generate some testvectors from our defacto-standard
> > implementation ;-)
> >
>
> One or two larger ones would be useful, yes.

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-24 13:40:45

[permalink] [raw]

Subject: RE: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

Ah, ugh, my bad. Ignore my previous mail below. Turns out the tf_xts_tv_template I was looking
at is for xts(twofish) not xts(aes) ... which was not immediately obvious from the name, for me.

Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

> -----Original Message-----
> From: [email protected] <[email protected]> On Behalf Of Pascal Van Leeuwen
> Sent: Wednesday, July 24, 2019 2:23 PM
> To: Ard Biesheuvel <[email protected]>
> Cc: Milan Broz <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> [email protected]; Horia Geanta <[email protected]>
> Subject: RE: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
>
> Ard,
>
> > -----Original Message-----
> > From: Ard Biesheuvel <[email protected]>
> > Sent: Monday, July 22, 2019 6:43 PM
> > To: Pascal Van Leeuwen <[email protected]>
> > Cc: Milan Broz <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> > [email protected]; Horia Geanta <[email protected]>
> > Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
> >
> > On Mon, 22 Jul 2019 at 12:44, Pascal Van Leeuwen
> > <[email protected]> wrote:
> > >
> > > > -----Original Message-----
> > > > From: Ard Biesheuvel <[email protected]>
> > > > Sent: Sunday, July 21, 2019 11:50 AM
> > > > To: Milan Broz <[email protected]>
> > > > Cc: Pascal Van Leeuwen <[email protected]>; Herbert Xu <[email protected]>; [email protected];
> linux-
> > > > [email protected]; Horia Geanta <[email protected]>
> > > > Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
> > > >
> > > > On Sat, 20 Jul 2019 at 10:35, Milan Broz <[email protected]> wrote:
> > > > >
> > > > > On 20/07/2019 08:58, Eric Biggers wrote:
> > > > > > On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
> > > > > >> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> > > > > >> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> > > > > >> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> > > > > >> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
> > > > > >>
> > > > > >
> > > > > > Can't the "missing modules in initramfs" issue be solved by using a
> > > > > > MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?
> > > > > >
> > > > > > (There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
> > > > > > but that was simply a bug, which was fixed.)
> > > > >
> > > > > Sure, and it is solved now. (Some systems with a hardcoded list of modules
> > > > > have to be manually updated etc., but that is just bad design).
> > > > > It can be done properly from the beginning.
> > > > >
> > > > > I just want to say that that switching to XEX looks like wasting time to me
> > > > > for no additional benefit.
> > > > >
> > > > > Fully implementing XTS does make much more sense for me, even though it is long-term
> > > > > the effort and the only user, for now, would be testmgr.
> > > > >
> > > > > So, there are no users because it does not work. It makes no sense
> > > > > to implement it, because there are no users... (sorry, sounds like catch 22 :)
> > > > >
> > > > > (Maybe someone can use it for keyslot encryption for keys not aligned to
> > > > > block size, dunno. Actually, some filesystem encryption could have use for it.)
> > > > >
> > > > > > Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
> > > > > > this a non-issue.
> > > > >
> > > > > If it is not available for users, I really see no reason to introduce XEX when
> > > > > it is just XTS with full blocks.
> > > > >
> > > > > If it is visible to users, it needs some work in userspace - XEX (as XTS) need two keys,
> > > > > people are already confused enough that 256bit key in AES-XTS means AES-128...
> > > > > So the examples, hints, man pages need to be updated, at least.
> > > > >
> > > >
> > > > OK, consider me persuaded. We are already exposing xts(...) to
> > > > userland, and since we already implement a proper subset of true XTS,
> > > > it will be simply a matter of making sure that the existing XTS
> > > > implementations don't regress in performance on the non-CTS code
> > > > paths.
> > > >
> > > > It would be useful, though, to have some generic helper functions,
> > > > e.g., like the one we have for CBC, or the one I recently proposed for
> > > > CTS, so that existing implementations (such as the bit sliced AES) can
> > > > easily be augmented with a CTS code path (but performance may not be
> > > > optimal in those cases). For the ARM implementations based on AES
> > > > instructions, it should be reasonably straight forward to implement it
> > > > close to optimally by reusing some of the code I added for CBC-CTS
> > > > (but I won't get around to doing that for a while). If there are any
> > > > volunteers for looking into the generic or x86/AES-NI implementations,
> > > > please come forward :-) Also, if any of the publications that were
> > > > quoted in this thread have suitable test vectors, that would be good
> > > > to know.
> > >
> > > Unfortunately, these algorithm & protocol specifications tend to be very frugal when it
> > > comes to providing test vectors, barely scratching the surface of any corner cases, but
> > > at least there is one non-multiple-of-16 vector in the original IEEE P1619 / D16
> > > specification in Annex B Test Vectors (last vector, "XTS-AES-128 applied for a data unit
> > > that is not a multiple of 16 bytes")
> > >
> >
> > Actually, that spec has a couple of test vectors. Unfortunately, they
> > are all rather short (except the last one in the 'no multiple of 16
> > bytes' paragraph, but unfortunately, that one is in fact a multiple of
> > 16 bytes)
> >
> > I added them here [0] along with an arm64 implementation for the AES
> > instruction based driver. Could you please double check that these
> > work against your driver? That would establish a ground truth against
> > which we can implement the generic version as well.
> >
> > [0] https://git.kernel.org/pub/scm/linux/kernel/git/ardb/linux.git/log/?h=xts-cts
> >
> I'm working on my XTS implementation now and I noticed something funny with the test
> vectors. The new CTS ones you added here, I can perfectly trace back to the IEEE spec,
> they match byte-for-byte.
>
> However, the ones that already existed puzzle me. The input data matches vectors from
> the IEEE spec, however the expected output cipher text does NOT ????
>
> Case in point, the very first vector, which has a key of all zeroes, a sector number (IV)
> or all zeroes and an all zeroes plaintext of 32 bytes, which matches the 1st spec vector:
> testmgr.h expects:
> "\x4b\xc9\x44\x4a\x11\xa3\xef\xac"
> "\x30\x74\xe4\x44\x52\x77\x97\x43"
> "\xa7\x60\xb2\x45\x2e\xf9\x00\x90"
> "\x9f\xaa\xfd\x89\x6e\x9d\x4a\xe0"
>
> But the specification expects:
> 917cf69ebd68b2ec9b9fe9a3eadda692cd43d2f59598ed858c02c2652fbf922e
>
> Which also happens to be what our hardware does ...
>
> Did you notice the same thing with your implementation? Am I missing something??
>
> > > Besides that, I'd be happy to generate some testvectors from our defacto-standard
> > > implementation ;-)
> > >
> >
> > One or two larger ones would be useful, yes.
>
> Regards,
> Pascal van Leeuwen
> Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
> http://www.insidesecure.com
>
>

2019-07-24 17:01:02

[permalink] [raw]

Subject: RE: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

Ard,

> -----Original Message-----
> From: Ard Biesheuvel <[email protected]>
> Sent: Monday, July 22, 2019 6:43 PM
> To: Pascal Van Leeuwen <[email protected]>
> Cc: Milan Broz <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> [email protected]; Horia Geanta <[email protected]>
> Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
>
> On Mon, 22 Jul 2019 at 12:44, Pascal Van Leeuwen
> <[email protected]> wrote:
> >
> > > -----Original Message-----
> > > From: Ard Biesheuvel <[email protected]>
> > > Sent: Sunday, July 21, 2019 11:50 AM
> > > To: Milan Broz <[email protected]>
> > > Cc: Pascal Van Leeuwen <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> > > [email protected]; Horia Geanta <[email protected]>
> > > Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
> > >
> > > On Sat, 20 Jul 2019 at 10:35, Milan Broz <[email protected]> wrote:
> > > >
> > > > On 20/07/2019 08:58, Eric Biggers wrote:
> > > > > On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
> > > > >> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> > > > >> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> > > > >> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> > > > >> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
> > > > >>
> > > > >
> > > > > Can't the "missing modules in initramfs" issue be solved by using a
> > > > > MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?
> > > > >
> > > > > (There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
> > > > > but that was simply a bug, which was fixed.)
> > > >
> > > > Sure, and it is solved now. (Some systems with a hardcoded list of modules
> > > > have to be manually updated etc., but that is just bad design).
> > > > It can be done properly from the beginning.
> > > >
> > > > I just want to say that that switching to XEX looks like wasting time to me
> > > > for no additional benefit.
> > > >
> > > > Fully implementing XTS does make much more sense for me, even though it is long-term
> > > > the effort and the only user, for now, would be testmgr.
> > > >
> > > > So, there are no users because it does not work. It makes no sense
> > > > to implement it, because there are no users... (sorry, sounds like catch 22 :)
> > > >
> > > > (Maybe someone can use it for keyslot encryption for keys not aligned to
> > > > block size, dunno. Actually, some filesystem encryption could have use for it.)
> > > >
> > > > > Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
> > > > > this a non-issue.
> > > >
> > > > If it is not available for users, I really see no reason to introduce XEX when
> > > > it is just XTS with full blocks.
> > > >
> > > > If it is visible to users, it needs some work in userspace - XEX (as XTS) need two keys,
> > > > people are already confused enough that 256bit key in AES-XTS means AES-128...
> > > > So the examples, hints, man pages need to be updated, at least.
> > > >
> > >
> > > OK, consider me persuaded. We are already exposing xts(...) to
> > > userland, and since we already implement a proper subset of true XTS,
> > > it will be simply a matter of making sure that the existing XTS
> > > implementations don't regress in performance on the non-CTS code
> > > paths.
> > >
> > > It would be useful, though, to have some generic helper functions,
> > > e.g., like the one we have for CBC, or the one I recently proposed for
> > > CTS, so that existing implementations (such as the bit sliced AES) can
> > > easily be augmented with a CTS code path (but performance may not be
> > > optimal in those cases). For the ARM implementations based on AES
> > > instructions, it should be reasonably straight forward to implement it
> > > close to optimally by reusing some of the code I added for CBC-CTS
> > > (but I won't get around to doing that for a while). If there are any
> > > volunteers for looking into the generic or x86/AES-NI implementations,
> > > please come forward :-) Also, if any of the publications that were
> > > quoted in this thread have suitable test vectors, that would be good
> > > to know.
> >
> > Unfortunately, these algorithm & protocol specifications tend to be very frugal when it
> > comes to providing test vectors, barely scratching the surface of any corner cases, but
> > at least there is one non-multiple-of-16 vector in the original IEEE P1619 / D16
> > specification in Annex B Test Vectors (last vector, "XTS-AES-128 applied for a data unit
> > that is not a multiple of 16 bytes")
> >
>
> Actually, that spec has a couple of test vectors. Unfortunately, they
> are all rather short (except the last one in the 'no multiple of 16
> bytes' paragraph, but unfortunately, that one is in fact a multiple of
> 16 bytes)
>
> I added them here [0] along with an arm64 implementation for the AES
> instruction based driver. Could you please double check that these
> work against your driver?
>
I got XTS working with the inside-secure driver and these (and all other) vectors pass :-)

> That would establish a ground truth against
> which we can implement the generic version as well.
>
> [0] https://git.kernel.org/pub/scm/linux/kernel/git/ardb/linux.git/log/?h=xts-cts
>
> > Besides that, I'd be happy to generate some testvectors from our defacto-standard
> > implementation ;-)
> >
>
> One or two larger ones would be useful, yes.
>
I'll see if I can extract some suitable vectors from our verification suite ...

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-25 06:34:30

[permalink] [raw]

Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

On Wed, 24 Jul 2019 at 19:10, Pascal Van Leeuwen
<[email protected]> wrote:
>
> Ard,
>
> > -----Original Message-----
> > From: Ard Biesheuvel <[email protected]>
> > Sent: Monday, July 22, 2019 6:43 PM
> > To: Pascal Van Leeuwen <[email protected]>
> > Cc: Milan Broz <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> > [email protected]; Horia Geanta <[email protected]>
> > Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
> >
> > On Mon, 22 Jul 2019 at 12:44, Pascal Van Leeuwen
> > <[email protected]> wrote:
> > >
> > > > -----Original Message-----
> > > > From: Ard Biesheuvel <[email protected]>
> > > > Sent: Sunday, July 21, 2019 11:50 AM
> > > > To: Milan Broz <[email protected]>
> > > > Cc: Pascal Van Leeuwen <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> > > > [email protected]; Horia Geanta <[email protected]>
> > > > Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
> > > >
> > > > On Sat, 20 Jul 2019 at 10:35, Milan Broz <[email protected]> wrote:
> > > > >
> > > > > On 20/07/2019 08:58, Eric Biggers wrote:
> > > > > > On Thu, Jul 18, 2019 at 01:19:41PM +0200, Milan Broz wrote:
> > > > > >> Also, I would like to avoid another "just because it is nicer" module dependence (XTS->XEX->ECB).
> > > > > >> Last time (when XTS was reimplemented using ECB) we have many reports with initramfs
> > > > > >> missing ECB module preventing boot from AES-XTS encrypted root after kernel upgrade...
> > > > > >> Just saying. (Despite the last time it was keyring what broke encrypted boot ;-)
> > > > > >>
> > > > > >
> > > > > > Can't the "missing modules in initramfs" issue be solved by using a
> > > > > > MODULE_SOFTDEP()? Actually, why isn't that being used for xts -> ecb already?
> > > > > >
> > > > > > (There was also a bug where CONFIG_CRYPTO_XTS didn't select CONFIG_CRYPTO_ECB,
> > > > > > but that was simply a bug, which was fixed.)
> > > > >
> > > > > Sure, and it is solved now. (Some systems with a hardcoded list of modules
> > > > > have to be manually updated etc., but that is just bad design).
> > > > > It can be done properly from the beginning.
> > > > >
> > > > > I just want to say that that switching to XEX looks like wasting time to me
> > > > > for no additional benefit.
> > > > >
> > > > > Fully implementing XTS does make much more sense for me, even though it is long-term
> > > > > the effort and the only user, for now, would be testmgr.
> > > > >
> > > > > So, there are no users because it does not work. It makes no sense
> > > > > to implement it, because there are no users... (sorry, sounds like catch 22 :)
> > > > >
> > > > > (Maybe someone can use it for keyslot encryption for keys not aligned to
> > > > > block size, dunno. Actually, some filesystem encryption could have use for it.)
> > > > >
> > > > > > Or "xts" and "xex" could go in the same kernel module xts.ko, which would make
> > > > > > this a non-issue.
> > > > >
> > > > > If it is not available for users, I really see no reason to introduce XEX when
> > > > > it is just XTS with full blocks.
> > > > >
> > > > > If it is visible to users, it needs some work in userspace - XEX (as XTS) need two keys,
> > > > > people are already confused enough that 256bit key in AES-XTS means AES-128...
> > > > > So the examples, hints, man pages need to be updated, at least.
> > > > >
> > > >
> > > > OK, consider me persuaded. We are already exposing xts(...) to
> > > > userland, and since we already implement a proper subset of true XTS,
> > > > it will be simply a matter of making sure that the existing XTS
> > > > implementations don't regress in performance on the non-CTS code
> > > > paths.
> > > >
> > > > It would be useful, though, to have some generic helper functions,
> > > > e.g., like the one we have for CBC, or the one I recently proposed for
> > > > CTS, so that existing implementations (such as the bit sliced AES) can
> > > > easily be augmented with a CTS code path (but performance may not be
> > > > optimal in those cases). For the ARM implementations based on AES
> > > > instructions, it should be reasonably straight forward to implement it
> > > > close to optimally by reusing some of the code I added for CBC-CTS
> > > > (but I won't get around to doing that for a while). If there are any
> > > > volunteers for looking into the generic or x86/AES-NI implementations,
> > > > please come forward :-) Also, if any of the publications that were
> > > > quoted in this thread have suitable test vectors, that would be good
> > > > to know.
> > >
> > > Unfortunately, these algorithm & protocol specifications tend to be very frugal when it
> > > comes to providing test vectors, barely scratching the surface of any corner cases, but
> > > at least there is one non-multiple-of-16 vector in the original IEEE P1619 / D16
> > > specification in Annex B Test Vectors (last vector, "XTS-AES-128 applied for a data unit
> > > that is not a multiple of 16 bytes")
> > >
> >
> > Actually, that spec has a couple of test vectors. Unfortunately, they
> > are all rather short (except the last one in the 'no multiple of 16
> > bytes' paragraph, but unfortunately, that one is in fact a multiple of
> > 16 bytes)
> >
> > I added them here [0] along with an arm64 implementation for the AES
> > instruction based driver. Could you please double check that these
> > work against your driver?
> >
> I got XTS working with the inside-secure driver and these (and all other) vectors pass :-)
>

Excellent, thanks for the report. May I add your Tested-by when I post
the patch? (just the one that adds the test vectors)

> > That would establish a ground truth against
> > which we can implement the generic version as well.
> >
> > [0] https://git.kernel.org/pub/scm/linux/kernel/git/ardb/linux.git/log/?h=xts-cts
> >
> > > Besides that, I'd be happy to generate some testvectors from our defacto-standard
> > > implementation ;-)
> > >
> >
> > One or two larger ones would be useful, yes.
> >
> I'll see if I can extract some suitable vectors from our verification suite ...
>

Great. Once available, I'll run them against my implementations and report back.

2019-07-25 12:37:46

[permalink] [raw]

Subject: RE: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

> -----Original Message-----
> From: Ard Biesheuvel <[email protected]>
> Sent: Thursday, July 25, 2019 8:22 AM
> To: Pascal Van Leeuwen <[email protected]>
> Cc: Milan Broz <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> [email protected]; Horia Geanta <[email protected]>
> Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
>
> > >
> > > Actually, that spec has a couple of test vectors. Unfortunately, they
> > > are all rather short (except the last one in the 'no multiple of 16
> > > bytes' paragraph, but unfortunately, that one is in fact a multiple of
> > > 16 bytes)
> > >
> > > I added them here [0] along with an arm64 implementation for the AES
> > > instruction based driver. Could you please double check that these
> > > work against your driver?
> > >
> > I got XTS working with the inside-secure driver and these (and all other) vectors pass :-)
> >
>
> Excellent, thanks for the report. May I add your Tested-by when I post
> the patch? (just the one that adds the test vectors)
>
Sure, feel free

> > > That would establish a ground truth against
> > > which we can implement the generic version as well.
> > >
> > > [0] https://git.kernel.org/pub/scm/linux/kernel/git/ardb/linux.git/log/?h=xts-cts
> > >
> > > > Besides that, I'd be happy to generate some testvectors from our defacto-standard
> > > > implementation ;-)
> > > >
> > >
> > > One or two larger ones would be useful, yes.
> > >
> > I'll see if I can extract some suitable vectors from our verification suite ...
> >
>
> Great. Once available, I'll run them against my implementations and report back.
>
Just wondering ... do you have any particular requirements on the sizes?
From my implementation's perspective, it doesn't make a whole lot of sense to test vectors
of more than 3 times the cipher block size, but then I realized that you probably need
larger vectors due to the loop unrolling you do for the vector implementations?
You also don't want them to be too big as they take up space in the kernel image ...

Regards,
Pascal van Leeuwen
Silicon IP Architect, Multi-Protocol Engines @ Verimatrix
http://www.insidesecure.com

2019-07-25 12:41:57

[permalink] [raw]

Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support

On Thu, 25 Jul 2019 at 10:49, Pascal Van Leeuwen
<[email protected]> wrote:
>
>
> > -----Original Message-----
> > From: Ard Biesheuvel <[email protected]>
> > Sent: Thursday, July 25, 2019 8:22 AM
> > To: Pascal Van Leeuwen <[email protected]>
> > Cc: Milan Broz <[email protected]>; Herbert Xu <[email protected]>; [email protected]; linux-
> > [email protected]; Horia Geanta <[email protected]>
> > Subject: Re: [dm-devel] xts fuzz testing and lack of ciphertext stealing support
> >
> > > >
> > > > Actually, that spec has a couple of test vectors. Unfortunately, they
> > > > are all rather short (except the last one in the 'no multiple of 16
> > > > bytes' paragraph, but unfortunately, that one is in fact a multiple of
> > > > 16 bytes)
> > > >
> > > > I added them here [0] along with an arm64 implementation for the AES
> > > > instruction based driver. Could you please double check that these
> > > > work against your driver?
> > > >
> > > I got XTS working with the inside-secure driver and these (and all other) vectors pass :-)
> > >
> >
> > Excellent, thanks for the report. May I add your Tested-by when I post
> > the patch? (just the one that adds the test vectors)
> >
> Sure, feel free
>

Thanks

> > > > That would establish a ground truth against
> > > > which we can implement the generic version as well.
> > > >
> > > > [0] https://git.kernel.org/pub/scm/linux/kernel/git/ardb/linux.git/log/?h=xts-cts
> > > >
> > > > > Besides that, I'd be happy to generate some testvectors from our defacto-standard
> > > > > implementation ;-)
> > > > >
> > > >
> > > > One or two larger ones would be useful, yes.
> > > >
> > > I'll see if I can extract some suitable vectors from our verification suite ...
> > >
> >
> > Great. Once available, I'll run them against my implementations and report back.
> >
> Just wondering ... do you have any particular requirements on the sizes?
> From my implementation's perspective, it doesn't make a whole lot of sense to test vectors
> of more than 3 times the cipher block size, but then I realized that you probably need
> larger vectors due to the loop unrolling you do for the vector implementations?
> You also don't want them to be too big as they take up space in the kernel image ...
>

We have code that operates on 1 block, 3 blocks (ARM), 4-5 blocks
(arm64) or 8 blocks (ARM,arm64) at a time. However, the most important
thing is to test the handover between the block based loop and the
epilogue that operates on the final 17-31 bytes when ciphertext
stealing is being done.

So ideally, we'd have 1 full block + 1 full/1 partial, 3 full blocks +
1 full/1 partial, and so on for 4, 5 and 8 blocks, to cover all the
code flows, but since the unrolled routines all support arbitrary
block counts (and so the handover between the multiblock and the
single block handling is already covered), just having the first two
would be sufficient IMO.

2019-07-26 10:33:13