Opened 13 months ago

Closed 6 months ago

#26871 closed enhancement (fixed)

prop289: randomize the unused part of relay payloads

Reported by: teor Owned by: dgoulet
Priority: Medium Milestone: Tor: 0.4.1.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: prop289, 035-roadmap-master, 035-triaged-in-20180711, prop289-assigned-sponsor-v, 041-proposed-on-roadmap
Cc: dmr Actual Points:
Parent ID: #26288 Points:
Reviewer: Sponsor: SponsorV

Description

arma says:
I think this logic argues for another subticket on #26288: "randomize the unused part of relay payloads".

https://trac.torproject.org/projects/tor/ticket/26846#comment:4

Child Tickets

TicketTypeStatusOwnerSummary
#29023enhancementclosednickmprop289: Implement a fast PRNG

Change History (18)

comment:1 Changed 13 months ago by arma

Owner: set to dgoulet
Status: newassigned
Type: defectenhancement

comment:2 Changed 13 months ago by arma

My task26871 branch shows where we would make this change. If we like it, it still needs unit tests, changes entry, etc.

I thought about breaking out the memcpy and the crypto_rand into their own function, called something like relay_payload_pack(), but all the extra lines didn't seem worth it.

comment:3 Changed 13 months ago by teor

I hope our PRNG is cheap.

Here's an attack on exits with expensive PRNGs:

  • make a client you control connect to a site you control
  • feed the exit one byte at a time

The exit then creates ~500 bytes of random padding per byte sent by the remote site.
(This would be a devastating attack if we used /dev/random directly, on an OS that thinks entropy is subtractive, like Linux.)

comment:4 in reply to:  3 ; Changed 13 months ago by arma

Replying to teor:

Here's an attack on exits with expensive PRNGs:

(a) don't just worry about exits; clients also will fill relay payloads.

(b) if this is actually a practical issue, I could get behind a design where we randomize only the first byte of the unused part of the relay payload. That would serve my purposes. But I bet we'd be forever explaining to people why we cut that corner.

(c) For added efficiency, let's only *sometimes* randomize that first byte. We can flip a coin to figure out whether we will, thus saving the prng that extra call to -- oh. :)

comment:5 in reply to:  4 Changed 13 months ago by nickm

Replying to arma:

Replying to teor:

Here's an attack on exits with expensive PRNGs:

FWIW, OpenSSL's old PRNG is exceptionally slow, but the newer one isn't too bad. LibreSSL is reasonably fast, and so is NSS IIRC.

If we need to get a faster PRNG, we have a couple of designs ready to go, with code.

comment:6 in reply to:  4 Changed 13 months ago by teor

Replying to arma:

(c) For added efficiency, let's only *sometimes* randomize that first byte. We can flip a coin to figure out whether we will, thus saving the prng that extra call to -- oh. :)

At this point, you might as well use a cheap sponge construction.

comment:7 Changed 13 months ago by teor

I patched tor-spec to randomise relay cell padding, see:

https://trac.torproject.org/projects/tor/ticket/26228#comment:15

comment:8 in reply to:  7 Changed 13 months ago by dmr

Replying to teor:

I patched tor-spec to randomise relay cell padding, see:

https://trac.torproject.org/projects/tor/ticket/26228#comment:15

Now tracking all of #26228, #26870, #26871 in this pull request:
https://github.com/torproject/torspec/pull/28

EDIT: only the tor-spec part of #26871 is tracked here.

Last edited 13 months ago by dmr (previous) (diff)

comment:9 in reply to:  2 ; Changed 13 months ago by teor

Status: assignedneeds_revision

Replying to arma:

My task26871 branch shows where we would make this change. If we like it, it still needs unit tests, changes entry, etc.

I thought about breaking out the memcpy and the crypto_rand into their own function, called something like relay_payload_pack(), but all the extra lines didn't seem worth it.

comment:10 Changed 13 months ago by teor

Keywords: prop289-assigned-sponsor-v added
Sponsor: SponsorV

I think all prop#289 tickets are Sponsor V.

comment:11 Changed 13 months ago by nickm

I've squashed and merged the spec branch.

comment:12 Changed 12 months ago by dgoulet

Milestone: Tor: 0.3.5.x-finalTor: 0.3.6.x-final

Deferring prop289 work to 036

comment:13 Changed 12 months ago by dgoulet

What is the needed revision here? Randomize some bytes? Use faster RNG? ...

comment:14 in reply to:  9 Changed 12 months ago by teor

Here are the revisions that are needed:

Replying to teor:

Replying to arma:

My task26871 branch shows where we would make this change. If we like it, it still needs unit tests, changes entry, etc.

Here are the revisions we probably don't need:

I thought about breaking out the memcpy and the crypto_rand into their own function, called something like relay_payload_pack(), but all the extra lines didn't seem worth it.

comment:15 Changed 10 months ago by nickm

Milestone: Tor: 0.3.6.x-finalTor: 0.4.0.x-final

Tor 0.3.6.x has been renamed to 0.4.0.x.

comment:16 Changed 8 months ago by dgoulet

Milestone: Tor: 0.4.0.x-finalTor: 0.4.1.x-final

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

comment:17 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:18 Changed 6 months ago by dgoulet

Resolution: fixed
Status: needs_revisionclosed

With the fast prng, this is done in the parent ticket.

Note: See TracTickets for help on using tickets.