Opened 21 months ago

Closed 21 months ago

Last modified 19 months ago

#6537 closed defect (fixed)

Possible timing side-channel in router selection

Reported by: nickm Owned by:
Priority: major Milestone: Tor: 0.2.2.x-final
Component: Tor Version:
Keywords: tor-client Cc:
Actual Points: Parent ID:
Points:

Description

Robert Ransom found a possible timing side-channel in how we select routers by bandwidth: we finish faster if we're selecting a router earlier in the list than we do if we select a router later in the list. If this timing information is available on the wire, it could be used to tell which nodes a client is selecting based on how long it takes to pick them.

This is probably not an end-of-the-world attack, since:

  • There is a lot of noise in client timing information, especially in this case, since after picking a circuit we do a bunch of crypto, pk, and network ops too.
  • For exit nodes at least, we pick them at circuit_establish_circuit(), before we send any data to the network.
  • The timing information isn't likely to be finegrained enough to leak particular nodes; rather, if it is available at all, it is likelier to leak which general segment of the node list was selected.

Nevertheless, this isn't something we should even risk exposing, and there might be other factors here too that I'm not analyzing right. Better safe than sorry. Let's fix this one.

Child Tickets

Change History (10)

comment:1 Changed 21 months ago by nickm

Merged rransom's initial patch to 0.2.2, and forward-ported it to 0.2.3 and later.

He has a more advanced version that does bit-twiddling tricks to avoid even branching based on secret info. I'm not applying that one right now, since I think it needs more review than I can give it.

comment:2 Changed 21 months ago by nickm

  • Resolution set to fixed
  • Status changed from new to closed

Added the bittwidding approach as #6538.

comment:3 Changed 21 months ago by cypherpunks

No one of smartlists used by router selection funcs is strongly sorted. Order of it members is depend by limits from launch_descriptor_downloads() and by network timings from connection_dir_client_reached_eof(). Two different clients has differently ordered smartlists in result.

How could attacker using cpu-time of router selection funcs if attacker can't be sure about lists' order?

comment:4 Changed 21 months ago by cypherpunks

routers_sort_by_identity() do not affect the_nodelist->nodes used by router selection funcs.

comment:5 follow-up: Changed 21 months ago by cypherpunks

the_nodelist->nodes will be sorted by calling of nodelist_set_consensus() if consensus was loaded first. it should happen for most usage scenarios.

So we should assume smartlists determinately sorted.

comment:6 in reply to: ↑ 5 Changed 21 months ago by cypherpunks

Replying to cypherpunks:

the_nodelist->nodes will be sorted by calling of nodelist_set_consensus() if consensus was loaded first. it should happen for most usage scenarios.

So we should assume smartlists determinately sorted.

It's true only if client used that firstly loaded consensus. the_nodelist->nodes will never be resorted for next consensuses. Depends client uptime and relays statuses it could be not so obvious what order of the_nodelist->nodes in result.

comment:7 Changed 21 months ago by nickm_mobile

Yeah, it's not an *easy* attack. I'm not even convinced that the attacker can get a nonzero amount of timing bits to even work with anyway, due to the noise in the rest of the system. That said, there are indeed cases where the attacker can know something about the ordering. ISTR that when these functions are used to choose a routerstatus, that's in consensus order often. Also, if a client uses some of my nodes as directories to download routerinfos, I can force those nodes to appear late in the list, possibly in an order of my choosing. Finally, even if I start knowing nothing about a list's order, I could still know that later routerinfos are those that a client chose to update more recently.

I don't have the code in front of me right now, so I probably have some details wrong, and I forget completely what we do with microdescs: probably pick them in routerstatus order. :/

Tl;dr: The attack here is hard; I am not 100%convinced it is possible; but there are some bits leaked. There are. Enough historical traffic analysis attacks that I am not happy trusting that a tiny leak will remain safe.

comment:8 Changed 21 months ago by nickm_mobile

Another reason to patch this: it's going to take more analysis than I am capable of doing to tell for sure if it was exploitable. I would rather have the experts count the horses, as they say, *after* the barn door is closed.

comment:9 Changed 19 months ago by nickm

  • Keywords tor-client added

comment:10 Changed 19 months ago by nickm

  • Component changed from Tor Client to Tor
Note: See TracTickets for help on using tickets.