Route Consistency Testing

A route consistency test takes two different route advertisements to the same destination as input and outputs true if the routes are consistent and outputs false otherwise. Consistency is abstractly defined as follows:

1. If both route announcements are valid then the output is true.
2. If one route announcement is valid and the other one is invalid then the output is false.
3. If both route announcements are invalid then the output is true or false.

=

Figure: Different outcomes for a route consistency test. In all these scenarios, the verifying node is $V$. The verifying node checks whether the two routes it receives to destination $P$ are consistent with each other.

The key output from a route consistency test is false. This output unambiguously signals that at least one of the two route announcements is invalid. In this case, our protocols can raise an alarm and flag both the suspicious routes as potential candidates for invalid routes. If the consistency test outputs true, both the routes could either be valid or invalid. Figure 2 depicts the outcomes of a route consistency test for various examples of network configurations.

We will now describe two whisper consistency tests, namely Weak Split Whisper and Strong Split Whisper (SSW), of increasing complexity offering different security guarantees. We primarily use Weak Split, a simple hash chain based construction, to motivate the construction of SSW. SSW offers path integrity in the presence of misconfigurations or isolated adversaries and all the results in the paper are based on SSW.

Conceptually, both these constructions introduce a signature field in every BGP UPDATE message which is used for performing the route consistency test. There are three basic operations that are allowed on the signature field:

1. Generate-Signature: The origin AS (the originator of a route announcement) of a destination prefix generates a signature and initializes this field in the BGP UPDATE message and forwards it to its neighbor. The origin AS uses different initial signatures for every prefix it owns.
2. Update-Signature: Every intermediary AS that is not the origin of a destination prefix is required to update the signature field using a cryptographic hash function. This operation is only performed by one router in every AS (typically at the entry point of an AS).
3. Verify-Signature: Any intermediary router that receives two different routes (with different AS paths) can compare whether the signatures in the two different routes are consistent with each other.

=

The path integrity property requires the whisper protocol to satisfy two properties: (a) a malicious adversary should not be able to reverse engineer the signature field of an AS path; (b) any modification to the AS path or signature field in an advertisement should be detected as an inconsistency when tested with a valid route to the same destination.