Speed up copy_from_prebuf by accumulating in registers

copy_from_prebuf is the constant-time table lookup in
BN_mod_exp_mont_consttime. It ORs each masked table entry into the
output with b->d[j] |= table[j] & mask. Because b->d may alias table,
the compiler cannot keep the output in registers across table entries,
so each of the 2^window passes reloads and stores every output limb
and depends on the previous pass through a store-to-load round trip.

Instead, compute the 2^window masks up front, still behind
value_barrier_w, and build the output four limbs at a time in local
accumulators, walking all table entries before storing each limb once.
As before, the memory access pattern does not depend on idx: every
limb of every table entry is read, and selection is done only with
masks. The window size macros move above the function so that
BN_MAX_MOD_EXP_CTIME_WINDOW can size the mask array.

On x86_64, RSA uses the mont5 assembly and does not reach this code.
On aarch64 it is on the RSA private key path for 2048- to 4096-bit
keys. In an Envoy TLS-terminating proxy on AWS Graviton4, it was 18%
of CPU time under an RSA-2048 handshake load. (AWS-LC replaced this
function with an s2n-bignum assembly lookup on aarch64; this change
stays in portable C.)

bssl_bench BM_SpeedRSASign, single thread, signs/s:

CPU                          RSA-2048                RSA-3072  RSA-4096
Neoverse V2 (Graviton4) [1]  1061 -> 1268  (+19.5%)  +15%      +12%
Neoverse N1 (Graviton2)       282 ->  304  (+7.8%)   +5.5%     +5.0%
Apple M4 Max                 2645 -> 3045  (+15.1%)  +12.9%    +9.7%
Xeon 8375C, NO_ASM [2]        740 ->  794  (+7.2%)   +3.9%     +7.0%

[1] Measured on BoringSSL 0.20260413.0 with this change applied. In
    Envoy with one TLS 1.3 handshake per request on an RSA-2048
    certificate, throughput went from 806 to 895 requests per
    CPU-second (+11%) and p99 latency from 4.6 to 3.5 ms.
[2] OPENSSL_NO_ASM to exercise the C path on x86_64; median of 8 runs
    on a shared machine, so noisy. With assembly enabled, x86_64 RSA
    does not use this function and is unchanged within noise (Zen 5,
    ~2510 RSA-2048 signs/s either way).

With CONSTANT_TIME_VALIDATION, the BN and RSA tests in crypto_test
report no new valgrind errors on aarch64 (Neoverse N1) or on x86_64
with OPENSSL_NO_ASM. (On aarch64, valgrind flags the same two reads of
an empty std::optional in the ErrorEquals test helper with and without
this change; nothing in the library.)

Change-Id: Idabb8c6d515e9e577a58118da8ec2f964ee5d334
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/103567
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>
Reviewed-by: David Benjamin <davidben@google.com>
1 file changed
tree: d5c5c117b021645042ef8873ee40ab6dbfe72a6a
  1. .agents/
  2. .bcr/
  3. .github/
  4. agents/
  5. bench/
  6. cmake/
  7. crypto/
  8. decrepit/
  9. docs/
  10. fuzz/
  11. gen/
  12. include/
  13. infra/
  14. pki/
  15. rust/
  16. ssl/
  17. third_party/
  18. tool/
  19. util/
  20. .bazelignore
  21. .bazelrc
  22. .bazelversion
  23. .clang-format
  24. .clang-format-ignore
  25. .clangd
  26. .gitattributes
  27. .gitignore
  28. API-CONVENTIONS.md
  29. AUTHORS
  30. BREAKING-CHANGES.md
  31. BUILD.bazel
  32. build.json
  33. BUILDING.md
  34. CMakeLists.txt
  35. codereview.settings
  36. CONTRIBUTING.md
  37. FUZZING.md
  38. go.mod
  39. go.sum
  40. INCORPORATING.md
  41. LICENSE
  42. MODULE.bazel
  43. MODULE.bazel.lock
  44. PORTING.md
  45. PRESUBMIT.py
  46. PrivacyInfo.xcprivacy
  47. README.md
  48. SANDBOXING.md
  49. SECURITY.md
  50. STYLE.md
README.md

BoringSSL

BoringSSL is a fork of OpenSSL that is designed to meet Google's needs.

Although BoringSSL is an open source project, it is not intended for general use, as OpenSSL is. We don't recommend that third parties depend upon it. Doing so is likely to be frustrating because there are no guarantees of API or ABI stability.

Programs ship their own copies of BoringSSL when they use it and we update everything as needed when deciding to make API changes. This allows us to mostly avoid compromises in the name of compatibility. It works for us, but it may not work for you.

BoringSSL arose because Google used OpenSSL for many years in various ways and, over time, built up a large number of patches that were maintained while tracking upstream OpenSSL. As Google's product portfolio became more complex, more copies of OpenSSL sprung up and the effort involved in maintaining all these patches in multiple places was growing steadily.

Currently BoringSSL is the SSL library in Chrome/Chromium, Android (but it's not part of the NDK) and a number of other apps/programs.

Project links:

To file a security issue, use the Chromium process and mention in the report this is for BoringSSL. You can ignore the parts of the process that are specific to Chromium/Chrome.

There are other files in this directory which might be helpful: