Opened 8 months ago

Closed 7 months ago

#29023 closed enhancement (fixed)

prop289: Implement a fast PRNG

Reported by: dgoulet Owned by: nickm
Priority: Medium Milestone: Tor: 0.4.1.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: prop289, tor-relay, 041-proposed-on-roadmap
Cc: nickm Actual Points: 3
Parent ID: #26871 Points: 3
Reviewer: asn Sponsor: SponsorV

Description

In order to add randomness to each relay cell, we require a very fast PRNG. This ticket is for the implementation of such a feature so we can use it for prop289.

The ticket that adds randomness is #26871.

Child Tickets

Change History (12)

comment:1 Changed 8 months ago by dgoulet

prop289 won't make it in 040. Feature freeze is in 7 days.

comment:2 Changed 8 months ago by teor

Keywords: 041-proposed-on-roadmap added

Let's review these tickets at the next meeting using our 041-proposed process.
They're on the roadmap, so the review should focus on ticket size and team capacity (and sponsor expectations).

comment:3 Changed 8 months ago by nickm

Cc: nickm added

comment:4 Changed 8 months ago by nickm

As discussed: the OpenSSL 1.1.1 and NSS PRNGs are probably fast enough, so we might be able to have this prng be only for OpenSSL 1.1.0 and earlier.

comment:5 Changed 7 months ago by nickm

Actual Points: 3
Points: 3
Status: assignedneeds_review

See my branch fast_rng with PR at https://github.com/torproject/tor/pull/685

The code uses a AES256-CTR, with a much more efficient construction than CTR-DBRG. The construction is the same one used in libottery, libottery-lite, and the BSDs' replacements for arc4random() -- except that it uses AES instead of ChaCha. I'm using AES here because performance matters most here on relays, and relays all ought to have cpu support for AES.

Performance here is much better than the alternatives, even with openssl 1.1.1a:

===== rand =====
crypto_rand(4): 999.539250 nsec.
crypto_fast_rng_getbytes(4): 9.474050 nsec.
crypto_strongest_rand(4): 2306.595720 nsec.
weak_rand(4): 2.113900 nsec.
crypto_rand(16): 948.858240 nsec.
crypto_fast_rng_getbytes(16): 13.679440 nsec.
crypto_strongest_rand(16): 2319.716010 nsec.
crypto_rand(128): 1110.183610 nsec.
crypto_fast_rng_getbytes(128): 56.717480 nsec.

I am *not* using this branch by default anywhere yet, but I think we should probably remove our weak_rng uses and use this instead.

No changes file here, since the code isn't actually used yet.

Please remember that one can bikeshed a rng forever. Let's not do that in this case?

comment:6 Changed 7 months ago by dgoulet

Reviewer: asn

comment:7 Changed 7 months ago by asn

Status: needs_reviewneeds_revision

Done an initial review here. Most of the code looks great.

comment:8 Changed 7 months ago by nickm

Your comments all look reasonable! I've made the changes you requested in a set of fixup commits, pushed to the same branch and PR.

comment:9 Changed 7 months ago by nickm

Status: needs_revisionneeds_review

comment:10 Changed 7 months ago by asn

Status: needs_reviewmerge_ready

LGTM after latest fixups. An appveyor build broke because of circuitpadding unittests which I reported here #29500. I think we are good here.

comment:11 Changed 7 months ago by nickm

Thanks! I've made a squashed version as fast_rng_squashed, with new PR at https://github.com/torproject/tor/pull/702

comment:12 Changed 7 months ago by dgoulet

Resolution: fixed
Status: merge_readyclosed

Merged! Thanks.

Note: See TracTickets for help on using tickets.