Google Git
Sign in
boringssl / boringssl / 89eb6ddbf52887631ca45ad2242862515cd698ab
commit89eb6ddbf52887631ca45ad2242862515cd698ab[log] [tgz]
authorDavid Benjamin <davidben@google.com>Fri Mar 14 17:04:07 2025 +0900
committerBoringssl LUCI CQ <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com>Sat Mar 15 09:52:10 2025 -0700
tree136b4da52fe367e0d15f693184d5929f6c0197d2
parent48b1f45203f64e2c273736ef2deaef7bb0fa7095 [diff]
Remove Karatsuba multiplication in BIGNUM

BN_mul, for sufficiently large inputs, uses Karatsuba multiplication
from OpenSSL, but one that we later modified to compute the absolute
value in constant time.

The value of this complexity has always been odd. BN_mul is not a
performance-sensitive operation... except when it is. Almost all of our
multiplications are Montgomery modular multiplication. On x86 and Arm,
32-bit and 64-bit, we have a bn_mul_mont assembly function which
implements the two operations combined. But, when bn_mul_mont is not
available, we use BN_mul followed by a Montgomery reduction.

At one point I remember benchmarking this and concluding that, in builds
where it matters (i.e. no-asm), the Karatsuba multiplication was an
impactful optimization.

It would be nice to remove this code. The shape of our BIGNUM
abstractions means we need to account for operands being differently
sized, even though our cryptography code actually knows the sizes of
things (a sign that we should rethink those abstractions a bit). It also
makes reasoning about the scratch spaces of these functions difficult,
which in turn makes it difficult to remove BN_CTX.

That it's only useful in no-asm (and niche CPU arches) is probably
enough to justify removing it. But I've benchmarked it again and I'm not
sure why I thought it was beneficial on even no-asm builds. Running the
benchmarks again, it's either harmful or a hash.

So, let's remove it. This CL is just a straightforward deletion of
unreachable code. We can probably clean this up a bit from here.

Apple M1 Pro, OPENSSL_NO_ASM
Before:
Did 1000 RSA 2048 signing operations in 1007150us (992.9 ops/sec)
Did 45000 RSA 2048 verify (same key) operations in 1004117us (44815.5 ops/sec)
Did 41000 RSA 2048 verify (fresh key) operations in 1012323us (40500.9 ops/sec)
Did 10444 RSA 2048 private key parse operations in 1021921us (10220.0 ops/sec)
Did 416 RSA 3072 signing operations in 1053261us (395.0 ops/sec)
Did 24000 RSA 3072 verify (same key) operations in 1041675us (23039.8 ops/sec)
Did 22000 RSA 3072 verify (fresh key) operations in 1038466us (21185.1 ops/sec)
Did 5604 RSA 3072 private key parse operations in 1056724us (5303.2 ops/sec)
Did 168 RSA 4096 signing operations in 1018456us (165.0 ops/sec)
Did 13000 RSA 4096 verify (same key) operations in 1072555us (12120.6 ops/sec)
Did 12000 RSA 4096 verify (fresh key) operations in 1068795us (11227.6 ops/sec)
Did 3751 RSA 4096 private key parse operations in 1055083us (3555.2 ops/sec)

After:
Did 1152 RSA 2048 signing operations in 1019638us (1129.8 ops/sec) [+13.8%]
Did 52000 RSA 2048 verify (same key) operations in 1008049us (51584.8 ops/sec) [+15.1%]
Did 47000 RSA 2048 verify (fresh key) operations in 1017770us (46179.4 ops/sec) [+14.0%]
Did 10829 RSA 2048 private key parse operations in 1048927us (10323.9 ops/sec) [+1.0%]
Did 442 RSA 3072 signing operations in 1064619us (415.2 ops/sec) [+5.1%]
Did 24000 RSA 3072 verify (same key) operations in 1026170us (23387.9 ops/sec) [+1.5%]
Did 22000 RSA 3072 verify (fresh key) operations in 1024522us (21473.4 ops/sec) [+1.4%]
Did 5472 RSA 3072 private key parse operations in 1032525us (5299.6 ops/sec) [-0.1%]
Did 192 RSA 4096 signing operations in 1014930us (189.2 ops/sec) [+14.7%]
Did 14000 RSA 4096 verify (same key) operations in 1070762us (13074.8 ops/sec) [+7.9%]
Did 13000 RSA 4096 verify (fresh key) operations in 1076995us (12070.6 ops/sec) [+7.5%]
Did 3806 RSA 4096 private key parse operations in 1069780us (3557.7 ops/sec) [+0.1%]

Intel(R) Xeon(R) Gold 6154 CPU @ 3.00GHz, OPENSSL_NO_ASM
Before:
Did 760 RSA 2048 signing operations in 1007864us (754.1 ops/sec)
Did 36000 RSA 2048 verify (same key) operations in 1015915us (35436.0 ops/sec)
Did 32000 RSA 2048 verify (fresh key) operations in 1002094us (31933.1 ops/sec)
Did 9812 RSA 2048 private key parse operations in 1030069us (9525.6 ops/sec)
Did 264 RSA 3072 signing operations in 1011794us (260.9 ops/sec)
Did 18000 RSA 3072 verify (same key) operations in 1054096us (17076.2 ops/sec)
Did 16000 RSA 3072 verify (fresh key) operations in 1042326us (15350.3 ops/sec)
Did 5181 RSA 3072 private key parse operations in 1052445us (4922.8 ops/sec)
Did 132 RSA 4096 signing operations in 1048017us (126.0 ops/sec)
Did 11000 RSA 4096 verify (same key) operations in 1072348us (10257.9 ops/sec)
Did 10080 RSA 4096 verify (fresh key) operations in 1087489us (9269.1 ops/sec)
Did 3157 RSA 4096 private key parse operations in 1080304us (2922.3 ops/sec)

After:
Did 741 RSA 2048 signing operations in 1001629us (739.8 ops/sec) [-1.9%]
Did 36000 RSA 2048 verify (same key) operations in 1000102us (35996.3 ops/sec) [+1.6%]
Did 33000 RSA 2048 verify (fresh key) operations in 1031105us (32004.5 ops/sec) [+0.2%]
Did 9724 RSA 2048 private key parse operations in 1019805us (9535.2 ops/sec) [+0.1%]
Did 276 RSA 3072 signing operations in 1005262us (274.6 ops/sec) [+5.2%]
Did 17000 RSA 3072 verify (same key) operations in 1007153us (16879.3 ops/sec) [-1.2%]
Did 16000 RSA 3072 verify (fresh key) operations in 1012666us (15799.9 ops/sec) [+2.9%]
Did 5280 RSA 3072 private key parse operations in 1077362us (4900.9 ops/sec) [-0.4%]
Did 132 RSA 4096 signing operations in 1039495us (127.0 ops/sec) [+0.8%]
Did 11000 RSA 4096 verify (same key) operations in 1086299us (10126.1 ops/sec) [-1.3%]
Did 9559 RSA 4096 verify (fresh key) operations in 1031203us (9269.8 ops/sec) [+0.0%]
Did 3201 RSA 4096 private key parse operations in 1094303us (2925.1 ops/sec) [+0.1%]

Bug: 42290433
Change-Id: I774c8c3af57d0d3aed95272b86b1c6f9c64ccce7
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/77567
Auto-Submit: David Benjamin <davidben@google.com>
Reviewed-by: Bob Beck <bbe@google.com>
Commit-Queue: David Benjamin <davidben@google.com>
1 file changed
tree: 136b4da52fe367e0d15f693184d5929f6c0197d2
  1. .bcr/
  2. .github/
  3. cmake/
  4. crypto/
  5. decrepit/
  6. docs/
  7. fuzz/
  8. gen/
  9. include/
  10. infra/
  11. pki/
  12. rust/
  13. ssl/
  14. third_party/
  15. tool/
  16. util/
  17. .bazelignore
  18. .bazelrc
  19. .bazelversion
  20. .clang-format
  21. .gitignore
  22. API-CONVENTIONS.md
  23. AUTHORS
  24. BREAKING-CHANGES.md
  25. BUILD.bazel
  26. build.json
  27. BUILDING.md
  28. CMakeLists.txt
  29. codereview.settings
  30. CONTRIBUTING.md
  31. FUZZING.md
  32. go.mod
  33. go.sum
  34. INCORPORATING.md
  35. LICENSE
  36. MODULE.bazel
  37. MODULE.bazel.lock
  38. PORTING.md
  39. PrivacyInfo.xcprivacy
  40. README.md
  41. SANDBOXING.md
  42. 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: