tree dae189630ad5bae7961494590158ea2f4175be46
parent cbae965ca03825d517efe98cf7b8812584cab4a0
author David Benjamin <davidben@google.com> 1571583197 -0400
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1578069719 +0000

Replace aes_nohw with a bitsliced implementation.

aes_nohw is currently one of several variable-time table-based
implementations in C or assembly (armv4, x86, and x86_64). Replace all
of these with a C bitsliced implementation, with 32-bit, 64-bit, and
128-bit (SSE2) variants. This is based on the algorithms described in:

https://bearssl.org/constanttime.html#aes
https://eprint.iacr.org/2009/129.pdf
https://eprint.iacr.org/2009/191.pdf

This makes our AES implementation constant-time in all build
configurations!

There were far too many benchmarks to put in the commit message.
Instead, please refer to this fancy spreadsheet:
https://docs.google.com/spreadsheets/d/1wDCzfkPl7brfjWJKq55awQjwCPhOYI8O7zSQZuEc2Xg/edit?usp=sharing

Parallel modes on x86 and x86_64 do fine due to the SSE2 code. AES-GCM
actually gets faster. The 64-bit (4x) bitsliced implementation is less
effective at speeding parallel modes but still helps. The 32-bit (2x)
bitsliced implementation even less.

Non-parallel modes, sadly, take a *dramatic* performance hit. I tried a
constant-time table lookup for comparison, but bitslicing was still
better. This implementation performs comparably to the table in
BearSSL's documentation, which suggests I didn't do anything obviously
wrong. (Note BearSSL's table for 'ct' corresponds to a 32-bit bitsliced
implementation compiled for 64-bit. Compiling this implementation for
64-bit matches, but compiling it for 32-bit seems to be considerably
slower.)

Assumptions that may make this palatable:

- AES-GCM is by far the most important AES mode, and we perform okay
  with it. Modern things aren't built out of CBC.

- A nontrivial chunk of Chrome users on Windows don't have SSSE3 and
  would be affected by this change. They would get the SSE2 version
  which performs well for AES-GCM *and* is constant-time.

- ARM devices are primarily mobile which cycles hardware much faster.
  Chrome for Android has required NEON for several years now, so it
  would not run this code. (Aside from https://crbug.com/341598.)

- aarch64 mandates NEON, so it would not run this code.

- QUIC packet number encryption does use a one-off block operation, but
  only once per packet.

- Arguably this is undoing a performance gain that we never earned. That
  said, it was a dramatic performance gain in places.

As an alternative, we could just check in the SSE2 version and drop the
x86 and x86_64 table-based assembly, but this still leaves the generic
code with cache-timing side channels.

Change-Id: I0f4b4467a49790509503c529d7c0940318096a00
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/39206
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>