#6252 didn't go far enough

In legacy/trac#6252 (moved) we noted that a client can send sendme cells preemptively to the exit relay, thus cheating on her circuit window (and getting more than her fair share of throughput). We fixed it at the exit relay (now it checks if the window is higher than it's allowed to be), but we didn't fix it at other relays in the circuit -- so she can still send a sendme after the cells have been packaged by the exit relay, but before they've made it all the way to the client, and do a more subtle version of cheating. This one's trickier to execute, but still worth fixing because it opens up all the issues that we thought we'd closed in legacy/trac#6252 (moved).

Reported by Rob Jansen and Florian Tschorsch.

changed milestone to %Tor: 0.2.3.x-final in legacy/trac

added 023-backport in Legacy / Trac component::core tor/tor in Legacy / Trac milestone::Tor: 0.2.3.x-final in Legacy / Trac owner::arma in Legacy / Trac priority::medium in Legacy / Trac resolution::fixed in Legacy / Trac status::closed in Legacy / Trac tor-relay in Legacy / Trac type::defect in Legacy / Trac labels

Trac:
Cc: N/A to robgjansen, Flo

Simple answer is for intermediate nodes, especially the entry guard, to check if they ever see a set of cells that's bigger than the circuit window should allow. If so, kill the circuit.

(We might want to check a slightly higher number, like 1100, to leave some allowance for future design changes, and to leave some tolerance in case there are bugs -- we see (infrequent) warnings in relay logs about the legacy/trac#6252 (moved) fix, perhaps by non-conformant relays but who knows.)

Damon suggested an "authenticated sendme" design -- the sendme payload has to prove receipt of all the cells in the window, else it's not accepted. That would be a good way to avoid the third version of this bug, whatever it will turn out to be.

But it also requires some more design work, since you'd need to put randomness into the flow somewhere so the client can't just preemptively come up with the answer. Or some other smart idea.

See fixes for this in branches in my repo:

• circuit_queue_cap-0.2.5 branched from master
• circuit_queue_cap-0.2.4-2 branched from maint-0.2.4
• circuit_queue_cap-0.2.3-2 branched from maint-0.2.3

Trac:
Status: new to needs_review

In 0.2.4:

src/or/relay.c:2491: warning: format ‘%lu’ expects type ‘long unsigned int’, but argument 8 has type ‘uint64_t’

The 0.2.3 one probably has a similar issue. Use the U64_FORMAT and U64_PRINTF_ARG macros to log 64-bit uints.

Replying to nickm:

In 0.2.4: {{{ src/or/relay.c:2491: warning: format ‘%lu’ expects type ‘long unsigned int’, but argument 8 has type ‘uint64_t’ }}}

The 0.2.3 one probably has a similar issue. Use the U64_FORMAT and U64_PRINTF_ARG macros to log 64-bit uints.

D'oh!

The 0.2.3 one doesn't have a similar issue because 0.2.3 doesn't have channel IDs to log. The 0.2.5 one will, though.

Okay, format arg thing fixed. Any further objections, or shall I go ahead and prepare squashed versions for merging?

The squashed branches are ready to go:

• circuit_queue_cap-0.2.5-squashed branched from master
• circuit_queue_cap-0.2.4-squashed branched from maint-0.2.4
• circuit_queue_cap-0.2.3-squashed branched from maint-0.2.3

Replying to arma:

(We might want to check a slightly higher number, like 1100, to leave some allowance for future design changes, and to leave some tolerance in case there are bugs -- we see (infrequent) warnings in relay logs about the legacy/trac#6252 (moved) fix, perhaps by non-conformant relays but who knows.)

Oops -- we forgot about the leaky pipe topology. We should probably raise this number to 2000, to let us do things like 'adding padding cells from intermediate hops'. And we'll want a spec change, since we're disallowing behaviors that our spec used to allow.

Patched and merged into 0.2.3 and later.

leaving open and assigning to arma, since somebody needs to write the spec patch. :)

Trac:
Status: needs_review to assigned
Owner: N/A to arma

Trac:
Milestone: Tor: 0.2.3.x-final to Tor: 0.2.5.x-final

Fix reverted due to possible anonymity break; see legacy/trac#9072 (moved)

Trac:
Status: assigned to new

(There's a bunch of discussion on that ticket about what the right fix could be)

Branch "bug9063_redux_023" in my public repository has a sketch implementation of "algorithm 1" from legacy/trac#9072 (moved). It's not ideal, but it could work. Please review?

(I'm not suggesting this as a permanent fix, but as a "good enough for now" fix for 0.2.3 and 0.2.4.)

Trac:
Milestone: Tor: 0.2.5.x-final to Tor: 0.2.4.x-final
Status: new to needs_review
Keywords: N/A deleted, tor-relay 023-backport added

I've added more to that branch, to make it more production ready. It's still "good enough for now", and at least as good as we thought the previous legacy/trac#9063 (moved) patch was, I think.

(FWIW, the merge into 0.2.4 isn't completely clean, but resolving the conflict appears to be trivial.)

The bug9063_redux_023 branch looks okay; recommend testing it by running it as a relay for a while with an unnaturally low MaxMemInCellQueues setting to force some OOMs to occur.

The branch is now bug9063_redux_023_squashed. No changes from the above, except to add a changes file.

Merging into 0.2.3 and later. I'll hold this open till we can open a new ticket for "solve all the remaining issues in our legacy/trac#9063 (moved) / legacy/trac#9072 (moved) fixes"

Trac:
Status: needs_review to closed
Resolution: N/A to fixed
Milestone: Tor: 0.2.4.x-final to Tor: 0.2.3.x-final

I opened legacy/trac#9093 (moved) as a place to figure out the remaining issues.

Am I reading this right, that Tor 0.2.5.1-alpha is going to include commit 459aada4, and that the commit will cause intermediate relays to kill any circuit that has more than 1100 cells queued?

Have a look at relay.c : that code is, AFAICT, disabled with some "#if 0" directives.

Ok.

closed

mentioned in issue legacy/trac#9072 (moved)

mentioned in issue legacy/trac#9093 (moved)

mentioned in issue legacy/trac#25226 (moved)

moved from legacy/trac#9063 (moved)

mentioned in issue #9072 (closed)

added Bug label and removed 1 deleted label

added Relay label and removed 1 deleted label