#933 Feature request: Prefer EC Certificates for HTTPS Inspection

[Steven Smith]

I'd like to request that if it's consistent with the way that Privoxy chooses to generate new certificates, that it use elliptic curves as the default, which provide much greater efficiency per length. I hypothesize that this would have a noticable impact on Provoxy performance, which must generate and encrypt/decrypt with lots of certificates on-the-fly.

A quick bash timing comparison shows that EC certificates are about 20 times faster than RSA for comparably secure bit lengths. There are corresponding speed-ups and bandwidth savings for encryption/decryption because of the shorter bit lengths.

# EC
niter=1000 start=$(gdate +%s.%N) && for k in $(seq 1 ${niter}); do openssl genpkey -out test.key.pem -algorithm EC -pkeyopt ec_paramgen_curve:P-384 -aes256 -pass pass:swordfish; done && end=$(gdate +%s.%N) && bc -l <<< "(${end} - ${start})/${niter}"
.01041699200000000000

# RSA
niter=200 start=$(gdate +%s.%N) && for k in $(seq 1 ${niter}); do openssl genpkey -out test.key.pem -algorithm RSA -pkeyopt rsa_keygen_bits:2048 -aes256 -pass pass:swordfish 1>/dev/null 2>&1; done && end=$(gdate +%s.%N) && bc -l <<< "(${end} - ${start})/${niter}"
.22065649500000000000

[Steven Smith]

20 times faster than RSA for comparably secure bit lengths

Correction: 20X faster than Privoxy's apparent default of RSA 2048. ECC 384 has comparable strength to AES192, but RSA 2048 has only 112 bits of security. The comparable security to ECC 384 is RSA 7680. Reference:

https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-57p1r3.pdf

The P-521 curve is also comparably fast, has 256 bits of security, and is comparable to RSA 15360:

niter=1000 start=$(gdate +%s.%N) && for k in $(seq 1 ${niter}); do openssl genpkey -out test.key.pem -algorithm EC -pkeyopt ec_paramgen_curve:P-521 -aes256 -pass pass:swordfish; done && end=$(gdate +%s.%N) && bc -l <<< "(${end} - ${start})/${niter}"
.01173566000000000000

[Fabian Keil]

Thanks for the suggestion.

Please note that Privoxy by default generates certificates that
are valid for 90 days so the public key generation should
not be a bottleneck in normal operation.

A while ago I started to do some benchmarks with various
TLS implementations and had to explicitly patch Privoxy to
optionally generate a new certificate for each new connection
to be able to measure the effect of the certificate generation:
https://www.fabiankeil.de/gehacktes/privoxy-tls-benchmarks/#20210216-rsa-key-generation

Also note that the performance of the various supported TLS
implementations and their release version varies.

On my ElectroBSD amd64 systems the certificate generation
with MbedTLS seems to be significantly slower than with
OpenSSL, LibreSSL or WolfSSL but in practice I can't tell
the difference when I'm not actually benchmarking or checking
the logs.

There's also the interoperability aspect.

I'm not sure if all commonly used clients support algorithms
other than RSA.

I'm not opposed to a config directive to change the algorithm
(patches welcome!) but don't think we should change the defaults
at this time.

[Steven Smith]

On our LAN we observe that Privoxy with HTTPS Inspection slows browsing down considerably, especially on complex web pages. This affects performance enough to cause users to want to turn off the proxy. I see using a process monitor that privoxy is using a many seconds of multi-core server resources to accomplish HTTPS Inspection for complex web pages.

I implemented EC keys (P-384 curve) for Privoxy to test for possible speedup, and although I haven't done comprehensive benchmarks, anecdotally I observe that performance is roughly twice as fast on a 6-core i7 server. This appears to be consistent with published comparisons of RSA vs. ECC encryption times, with the caveat that there is no detailed timing analysis here that accounts for RSA decryption from the destination server, rule processing and filtering, and so forth.

I've added this as a variant to the MacPorts privoxy port. Please see https://github.com/macports/macports-ports/pull/13054.

I've also attached the two patch files.

[Steven Smith]

Additionally, I see no issue with the ECC certs on any up-to-date browser: FF, Chrome, or Safari. These OpenSSL NIST EC groups have widespread implementation now.

[Fabian Keil]

Thanks a lot for looking into this.

I don't have time to look at your patches right now as I'm trying to get the next release out (the release date has not yet been decided) but I'll try to look at the patches afterwards.

I'm surprised that your impression is that it actually impacts performance, but I have not yet tried it myself and maybe I also can't reproduce the environment or maybe the OS or the OpenSSL version is relevant as well.

Are you familiar with DTrace? My understanding is that DTrace is still available on some Apple systems but I don't have details and could be wrong.

I'd be interested to see flamegraphs or maybe Apple platforms have something similar anyway?

[Steven Smith]

I'm surprised that your impression is that it actually impacts performance

RSA 2048 key length is 5X EC 384 key length, so something's wrong if the PKI parts aren't correspondingly faster. The question is whether the overall speedups are consistent and worth the effort.

The bottom line on my server is that HTTPS Inspection is hammering the CPUs, and some combination of steps must address that.

[Steven Smith]

Here are the flamegraphs for Privoxy using EC P-384 versus RSA 2048, along with the macOS Activity Monitor that illustrates the 2–3X speedup of EC versus RSA PKI.

Thank you for suggesting this analytic—I'm quite confident now that EC is much faster than RSA for HTTPS Inspection.

In the flamegraphs, note that EC P-384 has 79,149 samples, and that RSA 2048 has 292,526 samples for the same page load, a factor of 3.7X, and that most of the time is spent in libcrypto, all consistent with the relative key lengths.

Bottom line: EC is many times faster because it uses shorter key lengths, and at the same time is many times more secure, with 192 bits of security versus RSA 2048's 112 bits (see above).

Commands:

sudo dtrace -x ustackframes=100 -n 'profile-997 /execname == "privoxy"/ { @[ustack()] = count(); } tick-60s { exit(0); }' -o out.stacks
stackcollapse.pl out.stacks > out.folded
flamegraph.pl out.folded > out.svg

[Fabian Keil]

I started looking into this again and am currently waiting for the Privoxy packages to be generated.

It looks like EVP_EC_gen() is only available in OpenSSL 3.0.x and last I checked the RSA key generation was significantly slower on OpenSSL's 3.0.x branch when compared to 1.1.x:
https://www.fabiankeil.de/gehacktes/privoxy-tls-benchmarks/#20210216-rsa-key-generation

I intend benchmark this again with OpenSSL 3.0.1 but would not be surprised if this was still the case.

[Fabian Keil]

I've updated the key regeneration benchmarks:
https://www.fabiankeil.de/gehacktes/privoxy-tls-benchmarks/#2022-01-06

The results seem to confirm that generating EC keys is significantly faster (as expected) but also seem to indicate that RSA key generation etc. with OpenSSL 3.0.1 is a lot slower than with OpenSSL 1.1.1m.

Further investigation needed ...

[Steven Smith]

I strongly recommend the migration to ECC certs. This makes a huge difference in privoxy performance.

I verify that these patch files work for version 3.0.34:

• https://github.com/macports/macports-ports/blob/master/www/privoxy/files/patch-openssl.c.diff
• https://github.com/macports/macports-ports/blob/master/www/privoxy/files/patch-ssl_common.h.diff

[Fabian Keil]

I've committed support for an elliptic-curve-keys directive that is enabled by default.

Thanks again for the reminder.