RE: [RFC PATCH v2] md/dm-crypt - reuse eboiv skcipher for IV generation

[Pascal Van Leeuwen <pvanleeuwen@verimatrix.com>]

> -----Original Message-----
> From: Ard Biesheuvel <ard.biesheuvel@linaro.org>
> Sent: Wednesday, August 7, 2019 5:40 PM
> To: Pascal Van Leeuwen <pvanleeuwen@verimatrix.com>
> Cc: linux-crypto@vger.kernel.org; herbert@gondor.apana.org.au; ebiggers@kernel.org;
> agk@redhat.com; snitzer@redhat.com; dm-devel@redhat.com; gmazyland@gmail.com
> Subject: Re: [RFC PATCH v2] md/dm-crypt - reuse eboiv skcipher for IV generation
> 
> On Wed, 7 Aug 2019 at 16:52, Pascal Van Leeuwen
> <pvanleeuwen@verimatrix.com> wrote:
> >
> > Ard,
> >
> > > -----Original Message-----
> > > From: Ard Biesheuvel <ard.biesheuvel@linaro.org>
> > > Sent: Wednesday, August 7, 2019 3:17 PM
> > > To: Pascal Van Leeuwen <pvanleeuwen@verimatrix.com>
> > > Cc: linux-crypto@vger.kernel.org; herbert@gondor.apana.org.au; ebiggers@kernel.org;
> > > agk@redhat.com; snitzer@redhat.com; dm-devel@redhat.com; gmazyland@gmail.com
> > > Subject: Re: [RFC PATCH v2] md/dm-crypt - reuse eboiv skcipher for IV generation
> > >
> > > On Wed, 7 Aug 2019 at 10:28, Pascal Van Leeuwen
> > > <pvanleeuwen@verimatrix.com> wrote:
> > > >
> > > > Ard,
> > > >
> > > > I've actually been following this discussion with some interest, as it has
> > > > some relevance for some of the things I am doing at the moment as well.
> > > >
> > > > For example, for my CTS implementation I need to crypt one or two
> > > > seperate blocks and for the inside-secure driver I sometimes need to do
> > > > some single crypto block precomputes. (the XTS driver additionally
> > > > also already did such a single block encrypt for the tweak, also using
> > > > a seperate (non-sk)cipher instance - very similar to your IV case)
> > > >
> > > > Long story short, the current approach is to allocate a seperate
> > > > cipher instance so you can conveniently do crypto_cipher_en/decrypt_one.
> > > > (it would be nice to have a matching crypto_skcipher_en/decrypt_one
> > > > function available from the crypto API for these purposes?)
> > > > But if I understand you correctly, you may end up with an insecure
> > > > table-based implementation if you do that. Not what I want :-(
> > > >
> > >
> > > Table based AES is known to be vulnerable to plaintext attacks on the
> > > key, since each byte of the input xor'ed with the key is used as an
> > > index for doing Sbox lookups, and so with enough samples, there is an
> > > exploitable statistical correlation between the response time and the
> > > key.
> > >
> > > So in the context of EBOIV, where the user might specify a SIMD based
> > > time invariant skcipher, it would be really bad if the known plaintext
> > > encryptions of the byte offsets that occur with the *same* key would
> > > happen with a different cipher that is allocated implicitly and ends
> > > up being fulfilled by, e.g., aes-generic, since in that case, each
> > > block en/decryption is preceded by a single, time-variant AES
> > > invocation with an easily guessable input.
> > >
> > No need to tell me, doing crypto has been my dayjob for nearly 18.5 years
> > now :-)
> >
> 
> I didn't mean to imply that you don't know your stuff :-) I am just
> reiterating the EBOIV issue so we can compare it to the issue you are
> bringing up
> 
Fair enough :-)

> > > In your case, we are not dealing with known plaintext attacks,
> > >
> > Since this is XTS, which is used for disk encryption, I would argue
> > we do! For the tweak encryption, the sector number is known plaintext,
> > same as for EBOIV. Also, you may be able to control data being written
> > to the disk encrypted, either directly or indirectly.
> > OK, part of the data into the CTS encryption will be previous ciphertext,
> > but that may be just 1 byte with the rest being the known plaintext.
> >
> 
> The tweak encryption uses a dedicated key, so leaking it does not have
> the same impact as it does in the EBOIV case. 
>
Well ... yes and no. The spec defines them as seperately controllable -
deviating from the original XEX definition - but in most practicle use cases 
I've seen, the same key is used for both, as having 2 keys just increases 
key  storage requirements and does not actually improve effective security 
(of the algorithm itself, implementation peculiarities like this one aside 
:-), as  XEX has been proven secure using a single key. And the security 
proof for XTS actually builds on that while using 2 keys deviates from it.

> And a plaintext attack
> on the data encryption part of XTS involves knowing the value of the
> tweak as well, so you'd have to successfully attack the tweak before
> you can attack the data. So while your point is valid, it's definitely
> less broken than EBOIV.
> 
For the data encryption, you have a very valid point (which I admit I
completely overlooked). For the tweak encryption itself, however ...

But even if you would use 2 independent keys, if you first break the
tweak key, the tweak becomes known plaintext and you can then continue
breaking the data encryption key :-) It's a bit harder, but far from
impossible.

> > > and the
> > > higher latency of h/w accelerated crypto makes me less worried that
> > > the final, user observable latency would strongly correlate the way
> > > aes-generic in isolation does.
> > >
> > If that latency is constant - which it usually is - then it doesn't
> > really matter for correlation, it just filters out.
> >
> 
> Due to the asynchronous nature of the driver, we'll usually be calling
> into the OS scheduler after queuing one or perhaps several blocks for
> processing by the hardware. Even if the processing time is fixed, the
> time it takes for the OS to respond to the completion IRQ and process
> the output is unlikely to correlate the way a table based software
> implementation does, especially if several blocks can be in flight at
> the same time.
> 
Ok, I didn't know the details of that ... still, don't underestimate
the power of statistical analysis. You'd think a SoC would generate 
enough power or EMI noise to hide your puny little crypto accelerator's
contribution to that - well, think again. You'd be surprised by what
the guys in our attack lab manage to achieve.

> But note that we are basically in agreement here: falling back to
> table based AES is undesirable, but for EBOIV it is just much worse
> than for other modes.
> 
Much worse than *certain* other modes. It's definitely something that
always needs to be in the back of your mind as long as there is some
possibility you end up with a not-so-secure implementation.

> > > > However, in many cases there would actually be a very good reason
> > > > NOT to want to use the main skcipher for this. As that is some
> > > > hardware accelerator with terrible latency that you wouldn't want
> > > > to use to process just one cipher block. For that, you want to have
> > > > some SW implementation that is efficient on a single block instead.
> > > >
> > >
> > > Indeed. Note that for EBOIV, such performance concerns are deemed
> > > irrelevant, but it is an issue in the general case.
> > >
> > Yes, my interest was purely in the generic case.
> >
> > > > In my humble opinion, such insecure table based implementations just
> > > > shouldn't exist at all - you can always do better, possibly at the
> > > > expense of some performance degradation. Or you should at least have
> > > > some flag  available to specify you have some security requirements
> > > > and such an implementation is not an acceptable response.
> > > >
> > >
> > > We did some work to reduce the time variance of AES: there is the
> > > aes-ti driver, and there is now also the AES library, which is known
> > > to be slower than aes-generic, but does include some mitigations for
> > > cache timing attacks.
> > >
> > > Other than that, I have little to offer, given that the performance vs
> > > security tradeoffs were decided long before security became a thing
> > > like it is today, and so removing aes-generic is not an option,
> > > especially since the scalar alternatives we have are not truly time
> > > invariant either.
> > >
> > Replacing aes-generic with a truly time-invariant implementation could
> > be an option.
> 
> If you can find a truly time-invariant C implementation of AES that
> isn't orders of magnitude slower than aes-generic, I'm sure we can
> merge it.
> 
I guess the "orders of a magnitude slower" thing is the catch here :-)

But from my perspective, crypto performance is irrelevant if it is not 
secure at all. (after all, it's crypto, so the *intent* is security)
Of course there's gradation in security levels, but timing-attack
resistance really is the lowest of the lowest IMHO.

> > Or selecting aes-generic only if some (new) "allow_insecure"
> > flag is set on the cipher request. (Obviously, you want to default to
> > secure, not insecure. Speaking as someone who earns his living doing
> > security :-)
> >
> 
> We all do. But we all have different use cases to worry about, and
> different experiences and backgrounds :-)
> 
> The main problem is that banning aes-generic is a bit too rigorous
> imo. It highly depends on whether there is known plaintext and whether
> there are observable latencies in the first place.
> 
Agree on the banning part, but it would be good if you could be *certain*
somehow that you don't end up with it. For certain use cases, a (much)
slower, but more, secure implementation may be the better choice. As you
already discovered by yourself.

> > (Disclaimer: I do not know anything about the aes-generic implementation,
> > I'm just taking your word for it that it is not secure (enough) ...)
> >

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