Opened 9 months ago

Closed 3 months ago

#26846 closed enhancement (implemented)

prop289: Leave unused random bytes in relay cell payload

Reported by: dgoulet Owned by: dgoulet
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
Cc: Actual Points:
Parent ID: #26288 Points:
Reviewer: 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 (11)

comment:1 Changed 9 months ago by dgoulet

Keywords: 035-roadmap-subtask added

comment:2 Changed 9 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 9 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 9 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 9 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 9 months ago by teor

Keywords: prop289-assigned-sponsor-v added

I think all prop#289 tickets are Sponsor V.

comment:7 Changed 8 months ago by dgoulet

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

Deferring prop289 work to 036

comment:8 Changed 6 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 4 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 3 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 3 months ago by nickm

Resolution: implemented
Status: assignedclosed

Done as part of parent.

Note: See TracTickets for help on using tickets.