prop289: Leave unused random bytes in relay cell payload
This is section 3.3 of proposal 289 which is, in short, to add randomness to some relay cell payload.
Activity
changed milestone to %Tor: 0.4.1.x-final in legacy/trac
added 035-roadmap-subtask in Legacy / Trac 041-proposed-on-roadmap in Legacy / Trac 041-should in Legacy / Trac actualpoints::.3 in Legacy / Trac asn-merge in Legacy / Trac component::core tor/tor in Legacy / Trac milestone::Tor: 0.4.1.x-final in Legacy / Trac owner::nickm in Legacy / Trac parent::26288 in Legacy / Trac postfreeze-ok in Legacy / Trac priority::medium in Legacy / Trac prop289 in Legacy / Trac prop289-assigned-sponsor-v in Legacy / Trac resolution::fixed in Legacy / Trac reviewer::dgoulet in Legacy / Trac security in Legacy / Trac severity::normal in Legacy / Trac sponsor::V in Legacy / Trac status::closed in Legacy / Trac type::enhancement in Legacy / Trac labels
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.
-
My
task26846-demobranch 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 (legacy/trac#26228 (moved)), 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.
-
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 legacy/trac#26288 (moved): "randomize the unused part of relay payloads".
Replying to arma:
I think this logic argues for another subticket on legacy/trac#26288 (moved): "randomize the unused part of relay payloads".
See legacy/trac#26871 (moved).
Integers are cheap, so let's open tickets rather than risk forgetting important tasks.
-
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.
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.
