Strong Split Whisper

Figure: Basic Strong-Split construction using exponentiation under modulo N where $N=p \times q$, a product of two large primes.

The strong split whisper protocol uses a more sophisticated cryptographic check and can provide path integrity in the presence of independent adversaries i.e., If an adversary removes or changes any entry in the AS path, the strong split whisper will always detect an inconsistency.

Figure 4 shows a construction of the basic SSW using the RSA mechanism. We use a minor modification of the illustrated example. We will elaborate the three basic operations for this protocol:

generate-signature: The origin AS computes three basic parameters:. $N, g,z$. $N$ is chosen as $p \times q$ where $p$ and $q$ are two large primes of the form $2p'+1$ and $2q'+1$ where $p'$ and $q'$ are also prime. It then computes a generator $g$ in the prime group $Z_p$ and $Z_q$. Finally, it chooses a random number $z$ and computes $g^{z}$   mod$N$. The signature generated is a tuple $(N, g^{z}$   mod$N)$. While the origin AS publicly announces $N$, only it knows the prime factors of $N$. Similar to RSA, we rely on the fact that an adversary cannot factor $N$ to determine its prime factors.

update-signature: Every AS is associated with a unique AS number which is specified in the path. Let AS $A$ that receive an advertisement from a neighboring AS with a signature $(N, y)$ where $y$ is of the form $g^{D}$   mod$N$ for some value of $D$. AS $A$ updates this signature to $(N, y^{A}$   mod$N)$. In other words, the AS exponentiates using its AS number. In Figure 4, the route announcement contains an AS path $P, A, B,C$, the corresponding signature of the route is $(N, g^{z.P.A.B.C}$   mod$N)$.

verify-signature: We will describe verify-signature using the example in Figure 4. The verifier,$V$, receives two signatures $(N,s_1)$ and $(N,s_2)$ where $s_1 =g^{z.P.A.B.C}$   mod$N$ and $s_2 = g^{z.P.X.Y}$   mod$N$. Given these values and the corresponding AS paths, the verifier outputs the routes to be consistent if:

$$s_1 ^{X.Y} = s_2 ^{A.B.C}$$

SSW is similar to the MuHASH construction proposed by Bellare et al. [12] for incrementally hashing signatures. A formal proof of the security guarantees offered by MuHASH is also applicable in our context to show that SSW offers path integrity. The key observation with our construction is: given $N$ and given $g^{x}$   mod$N$, an adversary cannot compute $x^{-1}$   mod$\phi(N)$ (where $\phi()$ is the Euler function on natural numbers; given $N=p \times q$, $\phi(N)= (p-1) \times (q-1)$) and hence cannot remove the signature of previous nodes in the AS path.

This construction has three problems: (a) an adversary can permute entries in a path due to commutative property of multiplication i.e., $A.B = B.A$; (b) the factoring property i.e., $8=4 \times 2$ implies an AS path $(2,4)$ can be replaced by $(8)$; (c) More importantly, an adversary can add AS's to the AS path without being detected.

Preventing commutativity and factoring: To prevent commutativity and factoring problems, we define a pseudo-AS number for every AS which depends on the position of the AS in a given AS path. If an AS $X$ appears in position $p$ in the AS path, the following function

$$f(X,p) =2^{16} \times p + X$$

will produce unique values for all AS's in different positions in an AS path (since $16$ bits are sufficient to express AS numbers). To avoid the problem of commutativity, an AS updates a signature using $f(X,p)$ instead of using its AS number $X$.

To avoid the factoring problem, we use prime numbers. Given a number $y$, one can determine the $q(y)$ as the $y^{th}$ lowest prime number. Prime numbers are not factorable and these numbers can be precomputed. Hence, given an AS $X$ appearing at position $p$, we use the exponent to be $X'= q(f(X,p))$ to avoid both commutativity and factoring problems. We refer to $X'$ as the psuedo-AS number of AS $X$ when it appears in position $p$. The pseudo-AS numbers for a given AS are computable by other routers as well. Hence, we only use pseudo AS numbers for computing the signature but do not change AS numbers in the AS path.

Preventing Addition of new AS numbers: The key to preventing an adversary from adding AS numbers is to associate a link identifier to represent an AS link between two AS's. If AS $A$ forwards a route to AS $B$, let $link(A,B)$ be a uniquely computable identifier which is a function of the AS numbers $A$ and $B$. An AS $A$ that received an advertisement $(N, y)$ should propagate the advertisement with the signature:

$$(N,y^{A' \times link(A,B)})$$

where $A'$ is the pseudo-AS numbers of $A$. Since the identifier $link(A,B)$ is added to the signature by $A$, $B$ cannot remove this portion from the signature. This implies $B$ cannot convert an AS path $(B,A)$ to $(B,C,A)$. However, if $B$ adds an AS at the end of a path (e.g., $(C,B,A)$), then the neighbor receiving the advertisement will notice that the neighbor it received the announcement from (i.e., B) does not match the first AS in the path (i.e., C). Hence it will not accept the announcement. One simple way to define a link identifier is:

$$link(A,B) =2^{32} \times A' +B'$$

where $A'$ and $B'$ are the pseudo-AS numbers of $A$ and $B$. $link(A,B)$ will be unique for all AS pairs $A,B$. Note that pseudo-AS numbers are always less than $2^{32}$ since $f(X,p) < 2^{21}$ for all AS paths less than 32 hops in length.

Generalized SSW construction: In this section, we only described the SSW construction using the basic RSA group structure. Alternatively, one can build SSW using elliptic curve cryptography [13]. The main distinction between RSA and ECC is the number of bits necessary for the signature field. While RSA requires $1024$ bit signatures, ECC only requires $256$ bits to provide the same level of security.