Re: AES leaks, cgd ciphers, and vector units in the kernel

[Taylor R Campbell <riastradh%NetBSD.org@localhost>]

> Date: Thu, 18 Jun 2020 13:18:13 +0000
> From: <Paul.Koning%dell.com@localhost>
> 
> > On Jun 17, 2020, at 7:36 PM, Taylor R Campbell <riastradh%NetBSD.org@localhost> wrote:
> >   Performance impact:  The cost is that constant-time AES software is
> >     much slower -- cgd AES-CBC encryption throughput is reduced to
> >     about 1/3, and decryption to about 1/2 (very roughly).  This is
> >     bad, obviously, but it is mostly addressed by the next two parts.
> 
> That's a pretty steep price.  It is worth it for some, not clear if
> it's worth it for others.  If I understand right, these are local
> attacks, not network attacks.  Users may judge that the risk from
> local attacks is not sufficient to pay this price.

There is a steep price to pay for the bad design of AES because it
presents a conflict between security and performance in software -- I
generally discourage anyone from putting AES into designs because of
this.

It is dangerous to have the leaky AES code around at all because it
will tend to get used, and when it is used it is costly to audit a
system to reliably guarantee it doesn't affect you.  Most users are
not in a position to make a competently informed decision about
whether every use of it really affects them or not.  This is not just
a matter of local attacks -- obvious low-hanging fruit for a `network'
adversary include:

- JavaScript in a web browser can trigger disk I/O and measure
  high-resolution timing

- network packets, especially within a data center or, better, on a
  shared virtual host can be precisely timed

I would rather take the easy effort to rule out this entire class of
attacks and provide cheap alternatives than impose the burden of
studying and mitigating the very subtle risks on users.  And I expect
that for many if not most users the outcome will be a performance
_improvement_.

> > 2. Add support for CPU AES instructions on Intel, AMD, VIA, and
> >   aarch64 CPUs to implement the kernel's synchronous AES API,
> >   including machinery to allow the kernel to use the CPU's vector
> >   unit.
> 
> Are those constant-time instructions?  They would need to be, I
> assume, otherwise we're moving the problem to a different place.

If they're not then it would be some pretty astonishingly bad hardware
design, because AES was designed for fast hardware implementations
with easy side channel resistance.  You'd kind of have to go out of
your way to screw it up.

The only circumstances in which I would expect this to be the case is
in software emulation of the AES instructions in, e.g., qemu.

> > 3. Add an alternative cgd cipher Adiantum[3], which is built out of
> >   AES (used only once per disk sector), Poly1305, NH, and XChaCha12,
> >   and has been deployed by Google for disk encryption on lower-end
> >   ARM systems.
> 
> Has this new system received enough scrutiny to justify its use in
> production?  I know AES but not the other bits, and in any case an
> insecure composite can be built out of secure building blocks.

Poly1305[1] and NH[2] are very simple universal hash families that
have guaranteed security theorems with easily understood unconditional
proofs.  There is no question that they achieve what they advertise.

The security of XChaCha12 has a simple proof[3] (stated in terms of
Salsa20 but it trivially carries over to ChaCha[4]) guaranteeing that
its can't be substantially worse than the security of ChaCha12.  The
best attacks on the ChaCha family are on the reduced-round ChaCha7
variant, giving XChaCha12 a wider security margin than even AES had
two decades ago in 2001 when it was selected.

So the only components whose security is conjectured, rather than
proven, are ChaCha12 and AES.  ChaCha20/Poly1305 may well be the most
widely used symmetric cipher in the world today, with AES-GCM as the
only likely contender, since it is in TLS 1.3 and preferred on smaller
devices without AES hardware support.  That makes it an extremely
attractive target for cryptanalysis.

What remains is whether the specific Adiantum construction is secure.
Adiantum was designed by Google's cryptographers for use in production
in disk encryption on all new low-end Google devices, so it too is a
reasonably attractive target for scrutiny.

Essentially all that is reasonably in question is whether the proof of
the security reduction theorem presented in the paper in the
peer-reviewed IACR Transactions on Symmetric Cryptology journal
(formerly known as the proceedings of Fast Software Encryption) holds.

Adiantum makes a fairly simple application of the components following
block cipher design principles that have been well-understood for
decades.  I gave the paper a cursory review, and although I didn't
review the proof with a fine-toothed comb, the bounds they assert look
plausible to me given how the design is put together.


[1] Daniel J. Bernstein, `The Poly1305-AES message-authentication
    code', in Henri Gilbert and Helena Handschuh (eds.), in Fast
    Software Encryption: 12th international workshop -- FSE 2005,
    Springer LNCS 3557, pp. 32--49.
    https://cr.yp.to/papers.html#poly1305

[2] John Black, Shai Halevi, Hugo Krawczyk, Ted Krovetz, and Phillip
    Rogaway, `UMAC: Fast and secure message authentication', in
    Michael Wiener (ed.), Advances in Cryptology -- CRYPTO '99,
    Springer LNCS 1666, pp. 215--233.
    https://www.cs.ucdavis.edu/~rogaway/papers/umac.html

[3] Daniel J. Bernstein, `Extending the Salsa20 nonce', Workshop
    Record of Symmetric Key Encryption Workshop 2011.
    https://cr.yp.to/papers.html#xsalsa

[4] Scott Arciszewski, `XChaCha: eXtended-nonce ChaCha and
    AEAD_XChaCha20_Poly1305', IETF Internet-Draft
    draft-irtf-cfrg-xchacha-03, January 10, 2020.
    https://tools.ietf.org/html/draft-irtf-cfrg-xchacha-03

[5] Paul Crowley and Eric Biggers, `Adiantum: length-preserving
    encryption for entry-level processors', IACR Transactions on
    Symmetric Cryptology 2018(4), pp. 39--61.
    https://doi.org/10.13154/tosc.v2018.i4.39-61