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

#28142 (moved) 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.

changed milestone to %Tor: 0.4.1.x-final

added 041-proposed 041-should component::core tor/tor dgoulet-merge milestone::Tor: 0.4.1.x-final network-team-roadmap-2019-Q1Q2 nickm-merge owner::mikeperry padding points::8 priority::very high resolution::implemented reviewer::mikeperry severity::normal sponsor::2 status::closed tor-cell tor-relay type::defect wtf-pad labels

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.

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

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

Trac:
Reviewer: N/A to mikeperry

#28633 (moved) is done, I believe. #28780 (moved) 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 (moved) done after that.

OK I have some WIP here: https://github.com/torproject/tor/pull/635 based on the #28780 (moved) 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.

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).

Trac:
Milestone: Tor: 0.4.0.x-final to Tor: unspecified

Trac:
Keywords: N/A deleted, 041-proposed added

Trac:
Points: N/A to 4

Trac:
Priority: Medium to Very High

Trac:
Sponsor: N/A to Sponsor2

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

Trac:
Status: new to needs_review

(This was marked for 8 points, not 4)

Trac:
Points: 4 to 8

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

Trac:
Reviewer: mikeperry to N/A

Mike is the only possible reviewer for this draft.

Trac:
Reviewer: N/A to mikeperry

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 (moved) for this. I could do it if we agree.

Trac:
Status: needs_review to needs_revision

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.

Trac:
Status: needs_revision to needs_review

Trac:
Summary: Design a useful padding machine that we can enable to Design a first useful padding machine (hiding client-side intro/rend circuits)