tree caee9dac311bff954fe1df8a3f7eb17089af427d
parent 98f969491ce613f146087d6c694808b7d0e81d88
author David Benjamin <davidben@google.com> 1573188178 -0500
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1573518422 +0000

Add a constant-time fallback GHASH implementation.

We have several variable-time table-based GHASH implementations, called
"4bit" in the code. We have a fallback one in C and assembly
implementations for x86, x86_64, and armv4. This are used if assembly is
off or if the hardware lacks NEON or SSSE3.

Note these benchmarks are all on hardware several generations beyond
what would actually run this code, so it's a bit artificial.

Implement a constant-time implementation of GHASH based on the notes in
https://bearssl.org/constanttime.html#ghash-for-gcm, as well as the
reduction algorithm described in
https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf.

This new implementation is actually faster than the fallback C code for
both 32-bit and 64-bit. It is slower than the assembly implementations,
particularly for 32-bit. I've left 32-bit x86 alone but replaced the
x86_64 and armv4 ones.  The perf hit on x86_64 is smaller and affects a
small percentage of 64-bit Chrome on Windows users. ARM chips without
NEON is rare (Chrome for Android requires it), so replace that too.

The answer for 32-bit x86 is unclear. More 32-bit Chrome on Windows
users lack SSSE3, and the perf hit is dramatic. gcm_gmult_4bit_mmx uses
SSE2, so perhaps we can close the gap with an SSE2 version of this
strategy, or perhaps we can decide this perf hit is worth fixing the
timing leaks.

32-bit x86 with OPENSSL_NO_ASM
Before: (4bit C)
Did 1136000 AES-128-GCM (16 bytes) seal operations in 1000762us (1135135.0 ops/sec): 18.2 MB/s
Did 190000 AES-128-GCM (256 bytes) seal operations in 1003533us (189331.1 ops/sec): 48.5 MB/s
Did 40000 AES-128-GCM (1350 bytes) seal operations in 1022114us (39134.6 ops/sec): 52.8 MB/s
Did 7282 AES-128-GCM (8192 bytes) seal operations in 1117575us (6515.9 ops/sec): 53.4 MB/s
Did 3663 AES-128-GCM (16384 bytes) seal operations in 1098538us (3334.4 ops/sec): 54.6 MB/s
After:
Did 1503000 AES-128-GCM (16 bytes) seal operations in 1000054us (1502918.8 ops/sec): 24.0 MB/s
Did 252000 AES-128-GCM (256 bytes) seal operations in 1001173us (251704.8 ops/sec): 64.4 MB/s
Did 53000 AES-128-GCM (1350 bytes) seal operations in 1016983us (52114.9 ops/sec): 70.4 MB/s
Did 9317 AES-128-GCM (8192 bytes) seal operations in 1056367us (8819.9 ops/sec): 72.3 MB/s
Did 4356 AES-128-GCM (16384 bytes) seal operations in 1000445us (4354.1 ops/sec): 71.3 MB/s

64-bit x86 with OPENSSL_NO_ASM
Before: (4bit C)
Did 2976000 AES-128-GCM (16 bytes) seal operations in 1000258us (2975232.4 ops/sec): 47.6 MB/s
Did 510000 AES-128-GCM (256 bytes) seal operations in 1000295us (509849.6 ops/sec): 130.5 MB/s
Did 106000 AES-128-GCM (1350 bytes) seal operations in 1001573us (105833.5 ops/sec): 142.9 MB/s
Did 18000 AES-128-GCM (8192 bytes) seal operations in 1003895us (17930.2 ops/sec): 146.9 MB/s
Did 9000 AES-128-GCM (16384 bytes) seal operations in 1003352us (8969.9 ops/sec): 147.0 MB/s
After:
Did 2972000 AES-128-GCM (16 bytes) seal operations in 1000178us (2971471.1 ops/sec): 47.5 MB/s
Did 515000 AES-128-GCM (256 bytes) seal operations in 1001850us (514049.0 ops/sec): 131.6 MB/s
Did 108000 AES-128-GCM (1350 bytes) seal operations in 1004941us (107469.0 ops/sec): 145.1 MB/s
Did 19000 AES-128-GCM (8192 bytes) seal operations in 1034966us (18358.1 ops/sec): 150.4 MB/s
Did 9250 AES-128-GCM (16384 bytes) seal operations in 1005269us (9201.5 ops/sec): 150.8 MB/s

32-bit ARM without NEON
Before: (4bit armv4 asm)
Did 952000 AES-128-GCM (16 bytes) seal operations in 1001009us (951040.4 ops/sec): 15.2 MB/s
Did 152000 AES-128-GCM (256 bytes) seal operations in 1005576us (151157.1 ops/sec): 38.7 MB/s
Did 32000 AES-128-GCM (1350 bytes) seal operations in 1024522us (31234.1 ops/sec): 42.2 MB/s
Did 5290 AES-128-GCM (8192 bytes) seal operations in 1005335us (5261.9 ops/sec): 43.1 MB/s
Did 2650 AES-128-GCM (16384 bytes) seal operations in 1004396us (2638.4 ops/sec): 43.2 MB/s
After:
Did 540000 AES-128-GCM (16 bytes) seal operations in 1000009us (539995.1 ops/sec): 8.6 MB/s
Did 90000 AES-128-GCM (256 bytes) seal operations in 1000028us (89997.5 ops/sec): 23.0 MB/s
Did 19000 AES-128-GCM (1350 bytes) seal operations in 1022041us (18590.3 ops/sec): 25.1 MB/s
Did 3150 AES-128-GCM (8192 bytes) seal operations in 1003199us (3140.0 ops/sec): 25.7 MB/s
Did 1694 AES-128-GCM (16384 bytes) seal operations in 1076156us (1574.1 ops/sec): 25.8 MB/s
(Note fallback AES is dampening the perf hit.)

64-bit x86 with OPENSSL_ia32cap=0
Before: (4bit x86_64 asm)
Did 2615000 AES-128-GCM (16 bytes) seal operations in 1000220us (2614424.8 ops/sec): 41.8 MB/s
Did 431000 AES-128-GCM (256 bytes) seal operations in 1001250us (430461.9 ops/sec): 110.2 MB/s
Did 89000 AES-128-GCM (1350 bytes) seal operations in 1002209us (88803.8 ops/sec): 119.9 MB/s
Did 16000 AES-128-GCM (8192 bytes) seal operations in 1064535us (15030.0 ops/sec): 123.1 MB/s
Did 8261 AES-128-GCM (16384 bytes) seal operations in 1096787us (7532.0 ops/sec): 123.4 MB/s
After:
Did 2355000 AES-128-GCM (16 bytes) seal operations in 1000096us (2354773.9 ops/sec): 37.7 MB/s
Did 373000 AES-128-GCM (256 bytes) seal operations in 1000981us (372634.4 ops/sec): 95.4 MB/s
Did 77000 AES-128-GCM (1350 bytes) seal operations in 1003557us (76727.1 ops/sec): 103.6 MB/s
Did 13000 AES-128-GCM (8192 bytes) seal operations in 1003058us (12960.4 ops/sec): 106.2 MB/s
Did 7139 AES-128-GCM (16384 bytes) seal operations in 1099576us (6492.5 ops/sec): 106.4 MB/s
(Note fallback AES is dampening the perf hit. Pairing with AESNI to roughly
isolate GHASH shows a 40% hit.)

For comparison, this is what removing gcm_gmult_4bit_mmx would do.
32-bit x86 with OPENSSL_ia32cap=0
Before:
Did 2014000 AES-128-GCM (16 bytes) seal operations in 1000026us (2013947.6 ops/sec): 32.2 MB/s
Did 367000 AES-128-GCM (256 bytes) seal operations in 1000097us (366964.4 ops/sec): 93.9 MB/s
Did 77000 AES-128-GCM (1350 bytes) seal operations in 1002135us (76836.0 ops/sec): 103.7 MB/s
Did 13000 AES-128-GCM (8192 bytes) seal operations in 1011394us (12853.5 ops/sec): 105.3 MB/s
Did 7227 AES-128-GCM (16384 bytes) seal operations in 1099409us (6573.5 ops/sec): 107.7 MB/s
If gcm_gmult_4bit_mmx were replaced:
Did 1350000 AES-128-GCM (16 bytes) seal operations in 1000128us (1349827.2 ops/sec): 21.6 MB/s
Did 219000 AES-128-GCM (256 bytes) seal operations in 1000090us (218980.3 ops/sec): 56.1 MB/s
Did 46000 AES-128-GCM (1350 bytes) seal operations in 1017365us (45214.8 ops/sec): 61.0 MB/s
Did 8393 AES-128-GCM (8192 bytes) seal operations in 1115579us (7523.4 ops/sec): 61.6 MB/s
Did 3840 AES-128-GCM (16384 bytes) seal operations in 1001928us (3832.6 ops/sec): 62.8 MB/s
(Note fallback AES is dampening the perf hit. Pairing with AESNI to roughly
isolate GHASH shows a 73% hit. gcm_gmult_4bit_mmx is almost 4x as faster.)

Change-Id: Ib28c981e92e200b17fb9ddc89aef695ac6733a43
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/38724
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>