The Devil's in The Details: Placing Decoy Routers in the Internet

Decoy Routing, the use of routers (rather than end hosts) as proxies, is a new direction in anti-censorship research. Decoy Routers (DRs), placed in Autonomous Systems, proxy traffic from users; so the adversary, e.g. a censorious government, attempts to avoid them. It is quite difficult to place DRs so the adversary cannot route around them - for example, we need the cooperation of 850 ASes to contain China alone [1]. In this paper, we consider a different approach. We begin by noting that DRs need not intercept all the network paths from a country, just those leading to Overt Destinations, i.e. unfiltered websites hosted outside the country (usually popular ones, so that client traffic to the OD does not make the censor suspicious). Our first question is - How many ASes are required for installing DRs to intercept a large fraction of paths from e.g. China to the top-n websites (as per Alexa)? How does this number grow with n ? To our surprise, the same few ($\approx$ 30) ASes intercept over 90% of paths to the top n sites worldwide, for n = 10, 20...200 and also to other destinations. Investigating further, we find that this result fits perfectly with the hierarchical model of the Internet [2]; our first contribution is to demonstrate with real paths that the number of ASes required for a world-wide DR framework is small ($\approx$ 30). Further, censor nations' attempts to filter traffic along the paths transiting these 30 ASes will not only block their own citizens, but others residing in foreign ASes. Our second contribution in this paper is to consider the details of DR placement: not just in which ASes DRs should be placed to intercept traffic, but exactly where in each AS. We find that even with our small number of ASes, we still need a total of about 11, 700 DRs. We conclude that, even though a DR system involves far fewer ASes than previously thought, it is still a major undertaking. For example, the current routers cost over 10.3 billion USD, so if Decoy Routing at line speed requires all-new hardware, the cost alone would make such a project unfeasible for most actors (but not for major nation states).