14.4. Threats and Countermeasures in Link-State Routing

14.4.1. Link-State Routing Model and Threat Model

In this section, our discussion focuses on the origination, verification, and transmission of routing data. We start with a brief description of link-state routing and security threats specific to it. We discuss the security mechanisms that are known, as of now, to prevent some of these threat actions from taking place. Furthermore, we discuss the vulnerabilities of existing network routing security mechanisms and the improvements that can be done by using stronger authentication and a new method to manage routing data through encryption.

Link-State Routing Model

The link-state routing model is composed of physical entities (routers and communication links) and logical entities (the link-state routing protocol running in the routers). Within a link-state routing domain, each router generates the link-state information for the link that has the direct connection with the router (the link-state information is directional) and floods^[1] this information to its neighbors. A receiving router will forward the routing information (unmodified) via flooding again. Therefore, each router will have the same view of a network. When a router joins the network, it needs to synchronize the link-state database with its neighbors. The routing information carried by a link-state routing protocol is typically the link-state of a router’s interface. This information is called the link-state advertisement (LSA). During flooding, multiple LSAs can be encapsulated in a single link-state update (LSU) routing packet.

^[1] Flooding provides robust data transmission, in which a router forwards the link-state routing information packet to every interface except the one that receives the link-state routing information packet.

The security issues related to the link-state routing model can be broadly classified as security for the network device, operational security, and communication security. Security for the network devices concerns the physical access to the routers and communication links. Operational security includes the access control of the operating system of a router, privilege mode of a router, and so on. Communication security is related to the transmission, reception, and processing of routing data (LSAs and LSUs). Note that all data security-related issues discussed here are based on routing data but not on user data, and we focus on the communication security aspect of the link-state routing protocol.

Threats to Link-State Routing

In order to categorize the security threats to the routing protocol, we first need to identify the possible threat sources and their actions. We will follow definitions (such as threats, insider/outsider, etc.) provided in RFC 2828 [11] for this purpose and use them in the context of network routing and routing protocols.

Threat sources

The threat sources for link-state routing can be through communication links and routers. In the context of a deliberate attack, a threat source is defined as a motivated, capable adversary. Attacks can come from outside as well as from inside. As such, it is equally important to provide adequate safeguards for both internal and external threat sources. Here, internal threat sources are called insiders and external threat sources are called outsiders. In other words, the legitimate participants in network routing are called insiders. On the contrary, the illegitimate participants in the network routing are called outsiders. The outsiders can reside anywhere in a network and have the ability to observe routed traffic on a link or send attack packets to routers. Note that an outsider can masquerade to generate routing information as an insider. However, an outsider has no valid identifier and is not authorized to perform routing functions. An insider can also masquerade as another authorized router and generate forged routing information. It has a valid identifier, but it is not authorized to impersonate other routers or forge other routers’ routing information (by “authorized” we mean the permission for overall routing operational functionalities). In this sense, we can say an outsider is unauthorized and an insider is authorized.

Threat actions

Threat actions are also called attacks. Here, all our discussions focus on the origination, verification, and transmission of routing data. The attacks can be active or passive. Defined in RFC 2828: “An active attack attempts to alter system resources or affects their operation; a passive attack attempts to learn or makes use of information from the system but does not affect system resources.” Attacks can also be classified based on threat sources—insiders and outsiders. This classification helps to categorize corresponding preventive cryptographic countermeasures, which will be discussed in Section 14.4.2. Note that we focus on the attack model that an attacker uses to compromise other routers’ resources. Thus, we exclude the discussion of insider attackers that over-claim/underclaim/misclaim network resources that are under its control. For example, a subverted router claims that the bandwidth attached to one of its interfaces is w, but in fact, the actual bandwidth is r, where w ≠ r.

Outsider attacks

There are several types of outsider attacks:

a.	Sniffing (passive): Monitoring and recording routing data transmitted on the communication links among routers (Figure 14.2a).
b.	Falsification and masquerading (active): This attack can be of three kinds: Substitution: Altering or replacing valid routing information with false routing information (i in Figure 14.2b). Insertion: Introducing false routing data that serve to deceive an authorized router (ii in Figure 14.2b), Masquerading: Impersonating an authorized link/router (iii in Figure 14.2b). Masquerading is usually executed concurrently with substitution and/or insertion.
c.	Obstruction (active): This attack can be of two types: Interference: An attacker can block the transmission link, by cutting off the transmission link or by introducing noise into the transmission link to prevent the victims from receiving the routing information correctly (i in Figure 14.2c). Overload: An attacker can place excess dummy routing traffic that can saturate the victim’s input buffer or exhaust victim’s computer processing unit (CPU) capacity (ii in Figure 14.2c).
d.1.	Replay (active): A valid routing data transmission is maliciously or fraudulently repeated by an outsider (i in Figure 14.2d).

Insider attacks

There are several types of insider attacks:

d.2.	Replay (active): A valid routing data transmission is maliciously or fraudulently repeated by insiders (ii in Figure 14.2d).
e.	Falsification and masquerading (active): This is the same as specified in outsiders’ threat actions (see Figure 14.2e). Thus, there are three sub-cases: (e.1) substitution, (e.2) insertion, and (e.3) masquerading. Compared to an outsider’s falsification and masquerading, the insider attack can be more effective. Since the insider is a legitimate participant, he or she might know the shared key or serve as an intermediate forwarder, which makes the attack easier but more difficult to detect.
f.	Obstruction (active): Stop forwarding: The subverted router does not forward received routing packets (i in Figure 14.2f). Overload: Excessive routing information processing burden is placed on the router in order to saturate the victim’s input buffer or exhaust the victim’s CPU capacity (ii in Figure 14.2f). This is the same as the outsider’s overload attack.
g.	Repudiation (active): False denial of origin: A subverted router denies the operations that it has made on the transmitted routing information (i in Figure 14.2g). False denial of receipt: A subverted router denies receiving the routing data (ii in Figure 14.2g). Although an outsider can repudiate what he or she has done, it is more critical for insider attacks. A subverted router can cause a more serious problem when it is authorized to perform routing functions. Quickly identifying the subverted routers/links will help to reduce the recovery time imposed by the attacks.
h.	Exposure (active): Nondeliberate exposure: A router unintentionally releases sensitive routing data to attackers, both insiders and outsiders (i in Figure 14.2h). Deliberate exposure: A subverted router intentionally releases sensitive routing data to attackers, both insiders and outsiders (ii in Figure 14.2h).

We note that in our classification all attacks originating from outsiders occur on the routing transmission links (e.g., Figures 14.2a–d). Among these, attacks interference (c.1) and replay (active) (d.2) need to get access to the transmission link first and then attackers can launch attacks. Attacks originating from insiders are generated by the subverted routers (e.g., Figures 14.2d–h). When an outsider successfully takes over an authorized router, it becomes an insider (or subverted router). In other words, the outsider usurps the rights of a legitimate router.

14.4.2. Preventive Cryptographic Countermeasures against Attacks

The challenges posed due to the enormity and diversity of threats has led to various research activities in recent years that address techniques to safeguard a network. On the other hand, the current standards for network routing protocols have not incorporated all of the techniques required to make them as foolproof as possible. A set of unplugged security holes remain that an adversary can use to paralyze a network. In this section, we first analyze the possible preventive cryptographic countermeasures, and then describe how they can completely or partially prevent attacks from taking place.

Preventive Cryptographic Countermeasures

Computer security rests on confidentiality, integrity, and availability. Table 14.1 enlists two preventive cryptographic countermeasures that are described in the literature, including those that have found a place in protocol standards. The two main preventive cryptographic countermeasures that have been suggested for routing protocols are confidentiality and integrity. Confidentiality ensures that no unauthorized entities can decipher the routing information on its way to its destination. Integrity refers to the trustworthiness of data or resources, and it is usually phrased in terms of preventing improper or unauthorized change.

Table 14.1. Security mechanisms.

Methods		Label	Description	Protection
Authentication	Packet level	PLAP2P[†]	Packet level, point-to-point authentication	Data and origin integrity
(A)		PLAE2E[¶]	Packet level, end-to-end authentication
	Information level	ILAP2P[$]	Information level, point-to-point authentication
		ILAE2E[‡]	Information level, end-to-end authentication
Confidentiality		PLC[†]	Confidentiality for the whole packet	Information availability
(C)		ILC[¶]	Confidentiality for the information within the packet

^[†] OSPFv2 RFC 2328 and OSPFv3.

^[¶] Not in current literature.

^[$] Proposed in Huang et al. [12].

^[‡] OSPF extension RFC 2154.

Integrity includes data integrity (the content of the information) and origin integrity (the source of the data, often called authentication). The interpretations of integrity and authentication vary, as do the contexts in which they arise. In a link-state routing context/setting, authentication is generally considered as both data integrity and origin integrity [12]. For example, a keyed-hashing message authentication (HMAC) code can be used as the cryptographic authentication for OSPF (see RFC 2328 [13]). It provides data integrity and only an authorized user (possesses a shared key) can generate and verify the HMAC. Similarly, digital signatures for OSPF (see RFC 2154 [14]) also provide both data integrity and origin integrity. In the following, we consider authentication as providing both data integrity and origin integrity.

Availability refers to the ability to use the information or resource desired. The aspect of availability that is relevant to security is that someone may deliberately arrange to deny access to data or to a service by making them unavailable, such as a DoS attack. Preventive cryptographic countermeasures, by themselves, can do little to prevent DoS attacks. Most of the current solutions to DoS attacks are reactive solutions (i.e., solutions that depend on IDSs), which are beyond the scope of this research. We will show later on how to create multiple trusted routing domains to mitigate the consequence of a DoS attack.

Here, we focus on the following two preventive cryptographic countermeasures: confidentiality and authentication. These two countermeasures can provide protection at either the packet level (PL) or at the information level (IL). If we assume a routing packet to be a bus filled with a group of passengers, PL and IL represent the cryptographic countermeasures being provided for the bus and each individual passenger, respectively. Besides authentication and confidentiality, there are two other important concepts we need to introduce: point-to-point (P2P) and end-to-end (E2E) authentication. In terms of authentication, P2P means that the generation and verification of an authentication code are performed by every forwarding router. E2E means that the generation of an authentication code is performed only at the source; all the forwarding routers and termination routers are part of the end system, and they only perform verification. In Table 14.1, we provide a summary of the two main preventive cryptographic countermeasures for link-state routing protocols.

In the link-state routing protocol, pieces of routing information, link-state advertisements (LSAs), are encapsulated in a link-state update (LSU) packet. Most of the current implementations fall into the category of PLA_P2P. If PLA_P2P is provided for the entire LSU packet, then PLA_P2P can guard against the “man-in-the-middle” attack [11]. But, in link-state routing, flooding is used for distributing LSAs within a link-state routing domain. PLA_P2P cannot prevent any intermediate subverted router from modifying forwarded LSAs or a router from originating forged LSAs. E2E is more desirable to provide stronger protection for LSAs. But another difficulty of link-state routing is that multiple LSAs are encapsulated within a single LSU packet and the content of each LSU that originated from different routers may be different. This prevents PLA_E2E from being implemented efficiently. Hence, ILA_E2E and ILA_P2P are required to provide information-level protection. OSPF with digital signatures [14] is an example of ILA_E2E, while the double authentication scheme [12] is an example of ILA_P2P.

For confidentiality, too, we differentiate between packet level and information level, which are shown in Table 14.1. OSPF running over IPSec [15] is an example of providing PLC, which provides confidentiality for the internet provider (IP) payload. Providing confidentiality for each LSA individually is represented by ILC.

Using Preventive Cryptographic Countermeasures to Guard against Attacks

Next, we analyze how to use cryptographic countermeasures presented in Table 14.1 to guard against threat actions illustrated in Figure 14.2. Table 14.2 presents the mapping of threats and corresponding countermeasures. Threat actions that are marked with ✓ are solvable via well-known solutions and are outsider attacks. Attacks presented in (b) can be easily guarded against by using PLA_P2P. The dummy routing traffic due to attack (c.2) can be filtered out using PLA_P2P. Although, a cryptographic-based operation can aggravate the computer processing unit (CPU) computation burden, the overload attack is usually limited within a small range of where it happens. This is because the excess routing traffic cannot get through a router. This may be useful in preventing distributed denial of service (DDoS).

Table 14.2. Threats and corresponding cryptographic preventive countermeasures.

Threats		Attack Types			Preventive Countermeasures	Remarks
Threat Actions (Attacks)		Label	I/O	P/A
Wiretapping	Sniffing	(a)	O	Passive	PLC or ILC	**
Outsider	Substitution	(b.1)	O	Active	PLAP2P	✓
falsification and	Insertion	(b.2)	O	Active	PLAP2P	✓
masquerade	Masquerading	(b.3)	O	Active	PLAP2P	✓
Outsider obstruction	Interference	(c.1)	O	Active	PLC or ILC	***
	Overload	(c.2)	O	Active	PLAP2P	✓
Replay	Outsider replay	(d.1)	O	Active	New keys	**
	Insider replay	(d.2)	I	Active	New keys and ILC or	***
					ILAE2E
Insider	Substitution	(e.1)	I	Active	ILAE2E	*
falsification and	Insertion	(e.2)	I	Active	n/a	✠
masquerade	Masquerading	(e.3)	I	Active	ILAE2E	*
Insider obstruction	Stop forwarding	(f.1)	I	Active	n/a	✠
	Overload	(f.2)	I	Active	ILC	***
Repudiation	False denial of	(g.1)	I	Active	ILAE2E or ILAP2P	*
	origin
	False denial of	(g.2)	I	Active	PLAP2P	**
	receipt
Exposure	Nondeliberate exposure	(h.1)	I	Active	PLC† or ILC‡	**
	Deliberate exposure	(h.2)	I	Active	ILC	***
I/O: Insider/Outsider (attacks). P/A: Passive/Active (attacks). †: Guard against outsider attacks. ‡: Guard against insider attacks. *: Solvable via well known solutions but less deployed. ✓: Solvable via well known solutions and widely deployed. ***: Partially solvable via our proposed solution. **: Solvable via solutions proposed here. ✠: Unsolvable via authentication and confidentiality.

It may be noted that preventive countermeasures, such as authentication and confidentiality, cannot prevent attacks that are marked with ✠ (see (e.2) and (f.1)). These attacks need other security mechanisms such as admission/access control, intrusion detection, and so on.

Our discussion here will focus only on the countermeasures marked by *, **, or ***. The countermeasures marked by * are specified in the current literature, such as OSPF with digital signatures [14]. We note that end-to-end authentication is considered as a strong preventive cryptographic countermeasure. A widely accepted proposal uses the public key scheme to sign each LSA. The reason we separate it from PLA, marked by ✓, is because of the deployment difficulty of digital signatures, which comes with a high computation overhead compared with the traditional authentication schemes (e.g., the keyed hash function (HMAC) [16]). Countermeasures marked by ** are barely addressed in the current literature, while countermeasures marked by *** have not been addressed so far.

Guarding against Attacks on Communication Links

As shown in Table 14.2, attacks from (a) to (d.1) are injected on the communication link. Here, we investigate the possible use of preventive cryptographic countermeasures when attacks (a), (c.1), and (d.1) occur (marked with ** and ***).

Outsider wiretapping attack (a)

PLC or ILC can be used to prevent outsiders from sniffing packets containing routing information. This is a straightforward method to prevent passive attacks. When PLC is provided for the entire IP payload, the outsider would not know general information, such as link-state type, advertising router, and sequence number, that is contained within the routing packet header. This information can help an attacker to derive network topology and traffic patterns. ILC cannot prevent an attacker from knowing the information within the routing packet header, but it can prevent subverted routers from decrypting the routing information when they use different encryption/decryption keys. The combination of PLC and ILC provides strong security features to guard against ineligible entities.

Outsider interference attack (c.1)

We assume that there is an admission control mechanism to prevent outsiders from using network tools to derive the network topology. This can also be done by simply disabling those network services. Then an attacker might arbitrarily wiretap any possible communication links to intercept the routing information. Plaintext routing information can help attackers to derive network topology and traffic patterns. Due to flooding of the routing information used by the link-state routing protocol, tapping one link can help attackers to intercept all flooded LSAs within its routing domain. The intercepted routing information can be valuable for attackers to decide the location of an attack target, such as the weakest communication links or the partition routers. We note that providing confidentiality cannot prevent an attacker from doing active attacks. However, without the network topology and traffic pattern information, it is hard for attackers to deploy attacks successfully. Note that most of the active attacks presented here require the network topology or traffic pattern information.

Outsider replay attack (d.1)

Although link-state routing protocols typically use a nondecreasing sequence number to prevent replay attack, the replay attack can still take place when the sequence number is rolled over or a router reboots.

Guarding against Attacks on Routers

We next discuss possible use of preventive cryptographic countermeasures when attacks take place on a router. Insider attacks (d.2), (e.1), (f.2), (g), and (h) are some examples of attacks on routers (marked by *, **, and ***).

Insider replay attack (d.2)

The analysis of attack (d.2) is similar to the outsider replay attack (d.1). The difference is that information-level confidentiality is required. We illustrate the reason through a simple example; the LSA contains the bandwidth information of a particular link l, which is c_l. When all routers share a common key to sign/encrypt LSAs, any subverted insider can replay an LSA. Preventing this form of attack in the current framework is difficult. Therefore, a new framework should be such that one can allocate a different set of keys to routers and sign/encrypt only a subportion of bandwidth of link l, say c′_l. The insider attacker can only replay the old routing information c′_l, which only affects parts of a network’s resources. This would mean that not all routers within the link-state routing domain share the same network resource information. If we consider a link-state routing domain as a trust domain (TD), through ILC we can differentiate it as multiple subtrust domains. Hence, if one of the subrouting systems is compromised, it does not affect others or can only cause minimal damage to other subtrust domains. Since routers within a TD share the crypto key, the replay attack can still occur, and updating the crypto key will not be helpful to prevent the subverted routers from replaying the old routing packets. Thus, building multiple trust domains through ILC can only limit the effect of attack (d.2).

Insider substitution attack (e.1) and insider masquerading attack (e.3)

In the case of attacks (e.1) and (e.3), ILA_E2E can prevent subverted routers from substituting the routing information and masquerading as other routers when data origin authentication is provided for each LSA and is guaranteed E2E.

Insider overload attack (f.2)

This scenario occurs when there is an excessive routing information burden on routers, overloading the routers’ input buffer or CPU. It is different from outsider overload attack (c.2), which only aims to overload the neighboring routers’ input buffers or CPU. Insider overload can cause more damage, because the attacked routers will forward the excessive routing information to the next hop due to flooding. Although some link-state routing protocols set a minimal arrival interval to limit LSA updating, a subverted router can circumvent this protection via constantly inventing new LSA instances. Thus, the attacking traffic can be spread throughout a network due to flooding.

In order to limit the routing data traffic overload attack, we again need to divide the link-state routing domain into multiple smaller link-state routing (sub)domains. We assume here that the network has the link bandwidth management capability. An illustrative example is shown in Figure 14.3, which represents a network segment composed of three routers and two links. The capacity of a communication link 1–2 is c_1–2. TD₁ and TD₂ are configured to run through link 1–2. The bandwidth allocated for these two TDs are μ¹_1–2 and μ²_1–2 (the superscript is the identifier of a TD and the subscript is the identifier of a link). The available bandwidth of link 1–2 is given by α_1–2. Then, we have c_1–2 = μ¹_1–2 + μ²_1–2 + α_1–2. Similarly, the capacity allocation of link 2–3 is c_2–3 =μ²_2–3 + α_2–3. Note that the reserved bandwidth is guaranteed through both bandwidth management and confidentiality provided for each TD. A particular encryption/decryption session key is used to provide confidentiality for a TD. In our example, both routers R1 and R2 can decrypt LSAs for TD₁ and TD₂, and R3 can only see the available bandwidth allocated for TD₂. R3 does not possess the session key used by TD₂, and it cannot forge routing information to announce allocated bandwidth on link 2–3 for TD₁. If the subverted router R3 overloads R2, then R2 would not forward the excessive routing traffic that exceeds μ²_1–2. The traffic control is done through bandwidth management and the TD identification is done through providing confidentiality (ILC) to hide the network resources.

Insider false denial of origin attack (g.1)

In the case of attack (g.1), ILA_E2E can prevent insiders from denying the original sources that sent the false routing information. The authentication code should provide evidence that the sender cannot deny (e.g., a digital signature).

Insider false denial of receipt attack (g.2)

The acknowledgment mechanism of a link-state routing protocol is neighbor-to-neighbor based. Multiple LSAs can be acknowledged by a single link-state acknowledgment packet. The acknowledgment packet can use a shared key between the communication peers to authenticate the received packet. However, by using a shared-key based neighbor-to-neighbor authentication mechanism, there is no way to explicitly determine who generates the packets. Use of ILA_E2E and ILA_P2P for acknowledgment of every LSA is impractical and unnecessary. Moreover, the receiver can stop sending back acknowledgments. Thus, using PLA_P2P for acknowledgment is optional and can only benefit in preventing the “man-in-the-middle” attack.

Insider nondeliberate exposure attack (h.1)

An insider may unintentionally expose routing information to outsiders or other insiders that are not necessarily receiving the routing information (e.g., if the communication is via a wireless link). The analysis of this scenario is the same as scenario (a). PLC ensures no outsider can reveal the content. Within the multiple TD’s framework, ILC ensures only eligible TD members can reveal the content within their TD.

Insider deliberate exposure attack (h.2)

An insider can deliberately expose the routing information to anyone. But, with the routing information protected by ILC, a subverted/compromised router cannot expose the routing information of other TDs to which it does not belong.