Opened 9 months ago

Closed 7 months ago

#28837 closed enhancement (fixed)

Use openssl's SHA3 implementations when they are faster.

Reported by: nickm Owned by: nickm
Priority: Medium Milestone: Tor: 0.4.1.x-final
Component: Core Tor/Tor Version: Tor: 0.3.4.9
Severity: Normal Keywords: android startup performance controller 041-proposed dgoulet-merge
Cc: Actual Points:
Parent ID: #28481 Points: .3
Reviewer: catalyst Sponsor:

Description

OpenSSL now has sha3 support. At least some versions have assembly implementations of the keccak core function. That's our signal to update crypto_digest.c to use openssl for sha3.

This matters for startup, since keccakf() is about 10% of our startup time when we have a cached directory.

Child Tickets

Change History (17)

comment:1 Changed 9 months ago by nickm

On my desktop, openssl 1.1.1's SHA3-256 implementations is 26% faster than Tor's on short inputs, and 37% faster on medium inputs. The version in openssl git master is 30% faster on short inputs, and 38% faster on medium inputs.

comment:2 Changed 9 months ago by nickm

Owner: set to nickm
Status: newaccepted

work in progress in branch sha3_openssl.

comment:3 Changed 9 months ago by nickm

I opened https://github.com/openssl/openssl/issues/7894 for a missing piece in the openssl XOF api.

comment:4 Changed 9 months ago by nickm

Status: acceptedneeds_review

The branch is now ticket28837, with PR at https://github.com/torproject/tor/pull/586.

Here are some benchmarks.

Before (OpenSSL 1.1.1):

sha3-256(1): 687.92 ns per call
sha3-256(16): 683.90 ns per call
sha3-256(32): 677.67 ns per call
sha3-256(64): 658.13 ns per call
sha3-256(128): 641.06 ns per call
sha3-256(512): 2359.19 ns per call
sha3-256(1024): 4568.29 ns per call
sha3-256(2048): 9001.67 ns per call
sha3-512(1): 646.63 ns per call
sha3-512(16): 643.29 ns per call
sha3-512(32): 638.93 ns per call
sha3-512(64): 629.00 ns per call
sha3-512(128): 1175.99 ns per call
sha3-512(512): 4537.59 ns per call
sha3-512(1024): 8357.33 ns per call
sha3-512(2048): 15993.35 ns per call

After (OpenSSL 1.1.1):

sha3-256(1): 514.90 ns per call
sha3-256(16): 516.48 ns per call
sha3-256(32): 514.68 ns per call
sha3-256(64): 515.61 ns per call
sha3-256(128): 521.45 ns per call
sha3-256(512): 1573.38 ns per call
sha3-256(1024): 3015.68 ns per call
sha3-256(2048): 5751.61 ns per call
sha3-512(1): 513.23 ns per call
sha3-512(16): 517.77 ns per call
sha3-512(32): 519.98 ns per call
sha3-512(64): 512.96 ns per call
sha3-512(128): 865.99 ns per call
sha3-512(512): 2979.52 ns per call
sha3-512(1024): 5375.05 ns per call
sha3-512(2048): 10133.94 ns per call

After (OpenSSL git master):

sha3-256(1): 473.84 ns per call
sha3-256(16): 480.56 ns per call
sha3-256(32): 474.24 ns per call
sha3-256(64): 475.56 ns per call
sha3-256(128): 477.37 ns per call
sha3-256(512): 1490.75 ns per call
sha3-256(1024): 2906.49 ns per call
sha3-256(2048): 5578.25 ns per call
sha3-512(1): 475.24 ns per call
sha3-512(16): 473.44 ns per call
sha3-512(32): 473.78 ns per call
sha3-512(64): 473.85 ns per call
sha3-512(128): 813.76 ns per call
sha3-512(512): 2869.84 ns per call
sha3-512(1024): 5197.20 ns per call
sha3-512(2048): 9873.17 ns per call

comment:5 Changed 9 months ago by sha3

What's the reason of using SHA3? Is it faster than SHA2? In NSS?

comment:6 Changed 9 months ago by dgoulet

Reviewer: teor

comment:7 Changed 8 months ago by gaba

Sponsor: Sponsor8-can

comment:8 Changed 8 months ago by gaba

Reviewer: teorcatalyst

comment:9 Changed 8 months ago by catalyst

Status: needs_reviewneeds_revision

Mostly looks good. I left some comments on the pull request about some refactoring opportunities, and some minor things.

I tried building this with openssl-1.1.1a that I built from source and make check passes, for what that's worth.

It would be good to have a rebased branch build in Travis to confirm that the TEST_STEM failure is due to the likely known cause.

comment:10 Changed 8 months ago by nickm

Keywords: 041-proposed added
Milestone: Tor: 0.4.0.x-finalTor: 0.4.1.x-final

comment:11 Changed 8 months ago by nickm

Status: needs_revisionneeds_review

I've made the requested small changes in the branch, and make a rebased-and-squashed version as ticket28837_rebased with a PR as https://github.com/torproject/tor/pull/655 , to test the Stem issue.

For the reorganization of crypto_digest.c, I'd like to do that in a separate ticket, since I think it will take at least one round of review after this is done. Is that okay?

comment:12 in reply to:  11 ; Changed 8 months ago by catalyst

Replying to nickm:

I've made the requested small changes in the branch, and make a rebased-and-squashed version as ticket28837_rebased with a PR as https://github.com/torproject/tor/pull/655 , to test the Stem issue.

Thanks!

For the reorganization of crypto_digest.c, I'd like to do that in a separate ticket, since I think it will take at least one round of review after this is done. Is that okay?

Yes. I would like that ticket opened before we close this one, if possible.

comment:13 in reply to:  12 ; Changed 8 months ago by nickm

Replying to catalyst:

Yes. I would like that ticket opened before we close this one, if possible.

Okay! Here it is: #29108 .

comment:14 in reply to:  13 Changed 8 months ago by catalyst

Replying to nickm:

Replying to catalyst:

Yes. I would like that ticket opened before we close this one, if possible.

Okay! Here it is: #29108 .

Thanks!

comment:15 in reply to:  11 Changed 8 months ago by catalyst

Status: needs_reviewmerge_ready

Replying to nickm:

I've made the requested small changes in the branch, and make a rebased-and-squashed version as ticket28837_rebased with a PR as https://github.com/torproject/tor/pull/655 , to test the Stem issue.

Thanks! The new changes look good to me. After a detour through the land of stochastic spurious failures, it looks like CI passes on both the old and the rebased pull requests.

comment:16 Changed 7 months ago by nickm

Keywords: dgoulet-merge added

comment:17 Changed 7 months ago by dgoulet

Resolution: fixed
Status: merge_readyclosed

Merged into 041!

Note: See TracTickets for help on using tickets.