tree 136b4da52fe367e0d15f693184d5929f6c0197d2
parent 48b1f45203f64e2c273736ef2deaef7bb0fa7095
author David Benjamin <davidben@google.com> 1741939447 +0900
committer Boringssl LUCI CQ <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com> 1742057530 -0700

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>