Opened 5 months ago

Last modified 43 hours ago

#28634 needs_review defect

Design a first useful padding machine (hiding client-side intro/rend circuits)

Reported by: asn Owned by:
Priority: Very High Milestone: Tor: unspecified
Component: Core Tor/Tor Version:
Severity: Normal Keywords: wtf-pad, tor-relay, tor-cell, padding, 041-proposed
Cc: nickm Actual Points:
Parent ID: #28632 Points: 8
Reviewer: mikeperry Sponsor: Sponsor2

Description

#28142 will get merged with no active padding machine. This ticket is about designing a useful padding machine that can act as a decent testbed for the WTF-PAD project.

Child Tickets

TicketStatusOwnerSummaryComponent
#28693needs_reviewAdd an option to disable circuit paddingCore Tor/Tor
#28780needs_reviewcircpadding: Add machine flag for not closing circuit if machine is activeCore Tor/Tor
#29085newWTF-PAD: Reduce monotime usage because of performance issuesCore Tor/Tor
#29204closedInspect circuit queue during padding decisionsCore Tor/Tor
#29231newRelays vastly underreport write-total in padding-counts line in extrainfo descriptorCore Tor/Tor
#29494needs_revisionmikeperryOptimize interaction between circuitmux and circuitpaddingCore Tor/Tor
#30092needs_revisionAdd a probability-to-apply field for circuitpadidng machinesCore Tor/Tor
#30172newAlways send PADDING_NEGOTIATE if middle supports itCore Tor/Tor
#30173needs_reviewEnsure circuit padding can be safely disabled from consensusCore Tor/Tor

Change History (18)

comment:1 Changed 5 months ago by nickm

IMO it doesn't need to be a useful padding machine if we can't get a useful one done in time. If the best we can do is "cheap and harmless" instead of "useful", that would still give us a testbed.

comment:2 Changed 5 months ago by asn

Reviewer: mikeperry

Here are some thoughts https://github.com/torproject/tor/pull/461#discussion_r239838732

The above plan depends on getting #28780 and #28633 done in time.

comment:3 Changed 5 months ago by mikeperry

#28633 is done, I believe. #28780 could technically be called nice-to-have gravy. The machines won't be effective against any real adversary without it since lifetimes give away too much info, but we could at least test the machines.

The harmless piece is the tricky bit, though. The Padding TODO file has items for sending an ordered preference list of machine choices in the negotiation, and a way to stop re-trying negotiation if it keeps failing. One (or both) of these must be done to meet the harmless property. I *think* that having an ordered preference will be sufficient for safety, if we specify a "null" machine that is the last preference/fallback in case of error, and if you negotiate a "null" machine, you don't try to negotiate anything more on that circuit.

So if we really want something that can work in 0.4.0, we definitely need to implement this preference ordering idea with explicit "null" fallback. And then we can try to get #28780 done after that.

comment:4 Changed 4 months ago by asn

OK I have some WIP here: https://github.com/torproject/tor/pull/635 based on the #28780 branch.

tl;dr I made a machine that obfuscates client-side IP circuits. I did some initial testing on chutney and it seems to work okay-ish. Needs more work and feedback.

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

comment:5 Changed 4 months ago by mikeperry

Re "XXX This is not good enough since this randomization is global...This should be randomized for each circuit" in +setup_machine_states_for_hiding_ip_circuits().. This is what the circpad_state_t.length_dist is for -- it allows you to specify a probability distribution that governs how many cells the state should last for (and length_includes_nonpadding specifies if that should count nonpadding cells too).

comment:6 Changed 3 months ago by asn

Milestone: Tor: 0.4.0.x-finalTor: unspecified

comment:7 Changed 3 months ago by nickm

Keywords: 041-proposed added

comment:8 Changed 3 months ago by mikeperry

Points: 4

comment:9 Changed 3 months ago by mikeperry

Priority: MediumVery High

comment:10 Changed 3 months ago by nickm

Sponsor: Sponsor2

comment:11 Changed 4 weeks ago by asn

Status: newneeds_review

OK I have an initial PoC here, as well as a spec patch:
https://github.com/torproject/torspec/pull/72

Check out the code here:
https://github.com/torproject/tor/pull/868

I'm setting this to needs_review to receive some comments from Mike.
I'd also like some suggestions on how to do the bandwidth overhead analysis in the spec.

Thanks!

Here is how an intro point circuit looks like with this patch in chutney (had to change the latency to fit chutney):

IP circuit 6 was created at 20:49:49.973
Relay cells:
0: 20:49:49.978 -> EXTEND2
1: 20:49:50.000 <- EXTENDED2
2: 20:49:50.001 -> EXTEND2
3: 20:49:50.023 <- EXTENDED2
4: 20:50:25.520 -> PADDING_NEGOTIATE
5: 20:50:25.520 -> EXTEND
6: 20:50:25.528 -> DROP
7: 20:50:25.532 <- PADDING_NEGOTIATED
8: 20:50:25.532 <- DROP
9: 20:50:25.537 -> DROP
10: 20:50:25.545 -> DROP
11: 20:50:25.552 -> DROP
12: 20:50:25.553 <- DROP
13: 20:50:25.554 <- EXTENDED
14: 20:50:25.555 -> INTRODUCE1
15: 20:50:25.556 <- DROP
16: 20:50:25.556 <- DROP
17: 20:50:25.561 -> DROP
18: 20:50:25.565 -> DROP
19: 20:50:25.569 -> DROP
20: 20:50:25.573 -> DROP
21: 20:50:25.578 <- DROP
22: 20:50:25.578 <- DROP
23: 20:50:25.584 -> DROP
24: 20:50:25.592 -> DROP
25: 20:50:25.597 -> DROP
26: 20:50:25.601 <- DROP
27: 20:50:25.601 <- DROP
28: 20:50:25.602 <- DROP
29: 20:50:25.625 <- DROP
30: 20:50:25.625 <- DROP
31: 20:50:25.626 <- DROP
32: 20:50:25.626 <- INTRODUCE_ACK

and here is a rendezous circuit:

RP circuit 8 was created at 20:49:51.978
Relay cells:
0: 20:49:51.986 -> EXTEND2
1: 20:49:52.116 <- EXTENDED2
2: 20:49:52.117 -> EXTEND2
3: 20:49:52.162 <- EXTENDED2
4: 20:50:25.519 -> PADDING_NEGOTIATE
5: 20:50:25.519 -> ESTABLISH_RENDEZVOUS
6: 20:50:25.525 -> DROP
7: 20:50:25.532 <- PADDING_NEGOTIATED
8: 20:50:25.535 -> DROP
9: 20:50:25.540 -> DROP
10: 20:50:25.545 -> DROP
11: 20:50:25.552 -> DROP
12: 20:50:25.553 <- RENDEZVOUS_ESTABLISHED
13: 20:50:25.554 <- DROP
14: 20:50:25.555 <- DROP
15: 20:50:25.560 -> DROP
16: 20:50:25.564 -> DROP
17: 20:50:25.569 -> DROP
18: 20:50:25.578 <- DROP
19: 20:50:25.578 <- DROP
20: 20:50:25.601 <- DROP
21: 20:50:25.601 <- DROP
22: 20:50:25.601 <- DROP
23: 20:50:25.625 <- DROP
24: 20:50:25.625 <- DROP
25: 20:50:25.625 <- DROP
26: 20:50:25.626 <- DROP
27: 20:50:25.635 <- DROP
28: 20:50:25.677 <- DROP
29: 20:50:25.677 <- DROP
30: 20:50:25.681 <- DROP
31: 20:50:25.704 <- RENDEZVOUS2
32: 20:50:25.705 -> BEGIN
33: 20:50:25.749 <- CONNECTED
34: 20:50:25.837 -> DATA
35: 20:50:26.753 -> DATA

comment:12 Changed 4 weeks ago by asn

Points: 48

(This was marked for 8 points, not 4)

comment:13 Changed 3 weeks ago by teor

Reviewer: mikeperry

Remove Mike as reviewer, because he's overloaded.
We'll work out what to do with these tickets in the weekly meeting.

comment:14 Changed 3 weeks ago by teor

Reviewer: mikeperry

Mike is the only possible reviewer for this draft.

comment:15 Changed 2 weeks ago by mikeperry

Status: needs_reviewneeds_revision

I have some comments on the PR. Some need fixups; some may just need discussion.

Also I found that Rob Jansen and Marc Juarez actually did make a proper classifier out of Kwon's decision tree algorithm, so we might need to be a little more careful with considering how such a classifier will behave (I have some comments about how we might do that in the PR). Also maybe we can get them to re-run their classifier for us on their beefy Shadow simulator box: https://www.robgjansen.com/publications/insidejob-ndss2018.pdf

For these reasons, we might also want #30092 for this. I could do it if we agree.

Last edited 2 weeks ago by mikeperry (previous) (diff)

comment:16 Changed 7 days ago by asn

OK I have a new branch in bug28634: https://github.com/torproject/tor/pull/635
and I also updated the spec PR: https://github.com/torproject/torspec/pull/72

This branch takes the simplistic approach of only trying to make the initial circuit setup cell sequence blend in with general circuits. I find this to be more sophisticated than a look-like-nothing and it also has minimal overhead. I also addressed your comments in the previous PR.

Also, this is a fine start if we want to build this into a more advanced machine. We can just create new states that handle obfuscation after the initial circuit setup sequence.

Last edited 7 days ago by asn (previous) (diff)

comment:17 Changed 7 days ago by asn

Status: needs_revisionneeds_review

comment:18 Changed 43 hours ago by asn

Summary: Design a useful padding machine that we can enableDesign a first useful padding machine (hiding client-side intro/rend circuits)
Note: See TracTickets for help on using tickets.