Opened 14 months ago

Closed 4 months ago

#26846 closed enhancement (fixed)

prop289: Leave unused random bytes in relay cell payload

Reported by: dgoulet Owned by: nickm
Priority: Medium Milestone: Tor: 0.4.1.x-final
Component: Core Tor/Tor Version:
Severity: Normal Keywords: prop289, 035-roadmap-subtask, prop289-assigned-sponsor-v, 041-proposed-on-roadmap, security, 041-should, postfreeze-ok, asn-merge
Cc: Actual Points: .3
Parent ID: #26288 Points:
Reviewer: dgoulet Sponsor: SponsorV

Description

This is section 3.3 of proposal 289 which is, in short, to add randomness to some relay cell payload.

Child Tickets

Change History (37)

comment:1 Changed 14 months ago by dgoulet

Keywords: 035-roadmap-subtask added

comment:2 Changed 14 months ago by arma

The first step here is confirming that indeed the rolling circuit cell digest covers all of the bytes in the cell, not just the "in use" (rh->length) ones. I think we're good there: see the two calls to crypto_digest_add_bytes() in relay_crypto.c that have CELL_PAYLOAD_SIZE as their size argument.

comment:3 Changed 14 months ago by arma

My task26846-demo branch has two commits that are an example of what we could do here.

If we like this direction, they'll still need unit tests and a changes file (at least).

We might also want to make a consensus parameter for the "how often to leave a byte empty" choice, but also maybe that's just overengineering things.

And maybe flipping coins every time we consider packaging is expensive -- we could probably get away with some cheaper randomness if we wanted. But I think we should only do that if we are pushed into it, since cheaper randomness is so easy to regret.

I also thought about keeping a "how many cells have we packaged on this circuit" counter and then just doing some sort of mod operation to decide which ones to decrement. But I decided that doing it probabilistically is better, because right now we pad short payloads with 0 bytes (#26228), and somebody should check my logic but I think a rare but unpredictably short payload with a zero is enough to accomplish our goal here -- that is, we don't actually need a random byte, we just need to have it be unpredictable when the 0 will appear.

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

Replying to arma:

and somebody should check my logic but I think a rare but unpredictably short payload with a zero is enough to accomplish our goal here -- that is, we don't actually need a random byte, we just need to have it be unpredictable when the 0 will appear.

Ok, I have two counterexamples that make me resume thinking we need the unused portion of the payload to be random. The first counterexample is sort of ugly and it's unclear how practical it is as an attack, but the second counterexample is elegant and simple.

The first one is: what if the source of bytes at the destination side sends bytes out 400 at a time? Then we would always package them up 400 at a time, and we would never trigger the "decrement the length" function, because we would always only have partially full payloads anyway. Now, this isn't *so* bad for two reasons. One is that if you wanted to be sure to separate your 400 byte chunks so they go in different cells, you're really slowed down on the rate you can generate new cells. And the other related reason is that maybe the exit will package them in a different way than you expect, like 200 at a time every so often, or it will clump together two of your 400's sometimes, or etc. But still, I think this attack could work 'sometimes', and that is worrisome. It would be fixed by making the unused portion of the relay data cell payload random.

And the second attack is: what if the destination is sending a stream of 0 bytes? Then our payloads consist of NUL bytes, and every so often we make a short payload and put a NUL at the end. And our security relies on the attacker not being able to guess which bytes will be padding ("0") and which ones will be in-use-payload (also "0"). Oops. This attack would also be fixed by making the unused portion of the relay data cell payload random.

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

comment:5 in reply to:  4 Changed 14 months ago by teor

Replying to arma:

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

See #26871.

Integers are cheap, so let's open tickets rather than risk forgetting important tasks.

comment:6 Changed 14 months ago by teor

Keywords: prop289-assigned-sponsor-v added

I think all prop#289 tickets are Sponsor V.

comment:7 Changed 13 months ago by dgoulet

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

Deferring prop289 work to 036

comment:8 Changed 11 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:9 Changed 9 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:10 Changed 9 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:11 Changed 8 months ago by nickm

Resolution: implemented
Status: assignedclosed

Done as part of parent.

comment:12 Changed 4 months ago by dgoulet

Resolution: implemented
Status: closedreopened

comment:13 Changed 4 months ago by nickm

Keywords: 0411-alpha added

(why is this reopened?)

comment:14 Changed 4 months ago by nickm

Keywords: security added

comment:15 Changed 4 months ago by arma

We reopened this ticket because it was never done.

The current code in master will fill unused bytes with randomness, but it will never introduce any extra unused bytes in cells. So if cells are always full, there will be no randomness, which will make the entire flow predictable to somebody who already knows what bytes they'll be receiving from the other side.

We need some feature, like the one in my branch from comment:3, that sometimes leaves a bit of space in cells.

comment:16 Changed 4 months ago by nickm

Possibly foolish question: won't the sendme cells themselves have enough empty space?

comment:17 in reply to:  16 ; Changed 4 months ago by nickm

Replying to nickm:

Possibly foolish question: won't the sendme cells themselves have enough empty space?

Ah, never mind. The sendme cells that are guaranteed to get sent in this case aren't going in the right direction.

comment:18 Changed 4 months ago by nickm

Status: reopenednew

dgoulet, I'm happy to do this if you'd like.

comment:19 Changed 4 months ago by nickm

Keywords: 041-should added

comment:20 in reply to:  17 Changed 4 months ago by arma

Replying to nickm:

Replying to nickm:

Possibly foolish question: won't the sendme cells themselves have enough empty space?

Ah, never mind. The sendme cells that are guaranteed to get sent in this case aren't going in the right direction.

Not only that, but sendmes don't count in the circuit digest -- they are control cells, not relay data cells.

comment:21 in reply to:  18 Changed 4 months ago by arma

Replying to nickm:

dgoulet, I'm happy to do this if you'd like.

If you base it on my branch above, which I think is still plausible since it's so simple, be sure to note that dgoulet stuck a "don't mess with the first 4 unused bytes" rule in there, so we'd need to open up at least 5.

Another option, which is less hacky (less probabilistic) but would require more code and more state, would be to have a counter (on each circuit) of how many full cells we've sent, and if we ever send a non-full cell then reset it, and if it ever reaches 1000, make some space in that cell.

And as a final note, it's not actually required (from a technical coordination perspective) that we get this feature in to this release, since we could in theory add this "make some space" logic in a future Tor, and that would be the Tor that finishes doing prop289 properly. But "why not now, it's not that big" is a solid reason for doing it now too.

comment:22 Changed 4 months ago by nickm

Keywords: postfreeze-ok added

comment:23 Changed 4 months ago by nickm

Owner: changed from dgoulet to nickm
Status: newaccepted

comment:24 Changed 4 months ago by nickm

Actual Points: .1

I've done a draft here in a branch called ticket26846. What do you think of this approach, Roger? If you like the general idea, I'll clean it up a little more and add some tests.

comment:25 Changed 4 months ago by arma

Looks reasonable! Sad to use so much more code and per-circuit state but, everything seems to involve adding more and more code and state these days. :)

Cleaning up with attention to detail seems smart, e.g. in the commit message it says 28646, which is a different ticket.

One little nit: connection_edge_get_inbuf_bytes_to_package() in this branch returns 0 if !package_partial and n_available < RELAY_PAYLOAD_SIZE, even if we were planning to send a shorter payload and n_available is enough to send it. Not the end of the world I guess, but kind of weird, and avoided in my earlier branch. Could be fixed with a bit of gymnastics (like "reduce length at the top of the function but don't actually commit to changing state until later in the function").

I also spent a while trying to convince myself that there aren't situations where connection_edge_get_inbuf_bytes_to_package() can return 0 in this branch yet we changed the state. Would probably be smart to clearly delineate, in that function, the point at which we've committed to send a cell. (I think it is right after the final opportunity to "return 0;".)

comment:26 Changed 4 months ago by nickm

Status: acceptedneeds_revision

comment:27 Changed 4 months ago by nickm

Keywords: 0411-alpha removed

comment:28 Changed 4 months ago by nickm

Actual Points: .1.3
Status: needs_revisionneeds_review

Okay, I've force-pushed a new ticket26846, with a PR at https://github.com/torproject/tor/pull/1043

Last edited 4 months ago by nickm (previous) (diff)

comment:29 Changed 4 months ago by dgoulet

Status: needs_reviewneeds_revision

Couple questions on the PR.

comment:30 Changed 4 months ago by dgoulet

Reviewer: dgoulet
Status: needs_revisionneeds_information

comment:31 Changed 4 months ago by nickm

Status: needs_informationneeds_review

I've tried to answer those; please let me know what you think.

comment:32 Changed 4 months ago by dgoulet

Status: needs_reviewneeds_revision

Left a response about CIRCWINDOW_INCREMENT which I think it is a good idea.

Rest if lgtm;

comment:33 Changed 4 months ago by nickm

Okay, I'm fine with CIRCWINDOW_INCREMENT. I'll make that change.

comment:34 Changed 4 months ago by nickm

Status: needs_revisionneeds_review

Done; back to needs_review.

comment:35 Changed 4 months ago by dgoulet

Keywords: asn-merge added

ACK.

comment:36 Changed 4 months ago by dgoulet

Status: needs_reviewmerge_ready

comment:37 Changed 4 months ago by asn

Resolution: fixed
Status: merge_readyclosed

Merged.

Note: See TracTickets for help on using tickets.