![]() |
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:. .
is chosen as
where
and
are two large primes of the form
and
where
and
are also prime. It then computes a generator
in the
prime group
and
. Finally, it chooses a random number
and computes
mod
. The signature generated is a tuple
mod
. While the origin AS publicly announces
, only it knows the prime factors of
. Similar to RSA, we rely
on the fact that an adversary cannot factor
to determine its prime
factors.
update-signature: Every AS is associated with a unique AS
number which is specified in the path. Let AS that receive an
advertisement from a neighboring AS with a signature
where
is of the form
mod
for some value of
. AS
updates
this signature to
mod
. In other words, the AS
exponentiates using its AS number. In Figure 4, the
route announcement contains an AS path
, the corresponding
signature of the route is
mod
.
verify-signature: We will describe verify-signature using
the example in Figure 4. The verifier,, receives
two signatures
and
where
mod
and
mod
. Given these values and the
corresponding AS paths, the verifier outputs the routes to be consistent if:
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 and given
mod
, an adversary cannot compute
mod
(where
is the Euler function on natural numbers; given
,
) 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., ; (b) the factoring property i.e.,
implies an AS path
can be replaced by
;
(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 appears in position
in the AS path, the following function
To avoid the factoring problem, we use prime numbers. Given a number
, one can determine the
as the
lowest prime number.
Prime numbers are not factorable and these numbers can be
precomputed. Hence, given an AS
appearing at position
, we use
the exponent to be
to avoid both commutativity and
factoring problems. We refer to
as the psuedo-AS number of
AS
when it appears in position
. 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
forwards a route to AS
, let
be a uniquely computable
identifier which is a function of the AS numbers
and
. An AS
that received an advertisement
should propagate the
advertisement with the signature:
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 bit signatures, ECC only requires
bits to
provide the same level of security.