Whisper: Security Properties against Isolated Adversaries

Figure: Effects of penalty based route selection

In this section, we quantify the maximum damage an isolated adversary can inflict on the Internet given that Strong Split Whisper is deployed. Since SSW offers path integrity, an isolated adversary cannot propagate invalid routes without raising alarms unless there exists no alternate route from the origin to the verifier (i.e. adversary is present in all paths from the origin to the Internet).

Given an adversary that is willing to raise alarms, we analyzed how many AS's can one such adversary affect. In this analysis, we exclude cases where the adversary is already present in the only routing path to a destination AS. We use penalty based route selection as the main defense to contain the effects of such invalid routes. We assume that in the worst-case, an adversary compromising a single router in an AS is equivalent to compromising the entire AS especially if all routers within the AS choose the invalid route propagated by the compromised router.

Let $M$ represent an isolated adversary propagating an invalid route claiming direct connectivity to an origin AS $O$. AS $V$ is said to be affected by the invalid route if $V$ chooses the route through $M$ rather than a genuine route to $O$ either due to BGP policies or shorter hop length. Based on common practices, we associate all AS's with a simple policy where customer routes have the highest preference followed by peers and providers [18]. Given all these relationships, we define the vulnerability of an origin AS, $O$, as $V(O,M)$ to be the maximum fraction of AS's, $M$ can affect. Given an isolated adversary $M$, we can quantify the worst-case effect that $M$ can have on the Internet using the cumulative distribution of $V(O,M)$ across all origin AS's in the Internet.

With AS's deploying penalty based route selection as a defense, we expect the vulnerability $V(O,M)$ to reduce. We study how the cumulative distribution of $V(O,M)$ for a single adversary $M$ varies as a function of how many AS's deploy penalty based route selection. We consider the scenario where the top $n$ ISPs deploy penalty based route selection (based on AS degree). Figure 7 shows this cumulative distribution for for different values of $n=100,300,500$ and $1000$. These distributions are averaged across all possible choices for $M$.

We make the following observations. First, a median value of $1\%$ for $n=1000$ indicates that a randomly located adversary can affect at most $1\%$ of destination AS's by propagating bogus advertisements assuming that the top $1000$ ISPs use penalties. This is orders of magnitude better that what the current Internet can offer where a randomly located adversary can on an average affect nearly $30\%$ of the routes (repeat the same analysis without SSW) to a randomly chosen destination AS.

Second, in the worst case, a single AS can at most affect $8\%$ of the destination AS's for $n=1000$. $8\%$ is a limit imposed by the structure of the Internet topology since it represents the size of the largest connected without the top $1000$ ISPs. One malicious AS in this component can potentially affect other AS's within the same component.

Third, if all provider AS's use penalties for route selection, the worst case behavior can be brought to a much smaller value than $8\%$. Additionally, there is very little benefit in deploying penalty based route selection in the end-host networks since they are not transit networks and typically are sources and sinks of route advertisements. Hence, any filtering at these end-hosts only protects themselves but not other AS's.

To summarize, the Whisper protocol in conjunction with penalty based route selection can guarantee that a randomly placed isolated adversary propagating invalid routes can affect at most $1\%$ of the AS's in the Internet topology.