Intrusion Detection for Routers and Domain Name Systems

An Efficient Message Authentication Scheme for Link State Routing

Routers exchange routing update packets to disseminate their current states. Based on these update packets, routers can construct their routing tables to cooperatively forward packets from source to destination. If routing infrastructure components, such as routers or inter-router links, are faulty, misconfigured, or compromised, the network may suffer from degradation of service or even unavailability. In secure link state routing, routers may need to verify the authenticity of many routing updates, and some routers such as border routers may need to sign many routing updates. Previous work such as public-key based schemes either is very expensive computationally (e.g., Murphy and Badger's SNDSS '96 paper) or has certain limitations (e.g., Hauser et al.'s SNDSS '97 paper). Preliminary results show that our message authentication scheme is up to two orders of magnitude faster than an MD5/RSA digital signature scheme. Our scheme is scalable to handle large networks, applicable to routing protocols that use multiple-valued cost metrics, and applicable even when link states change frequently.

Our message authentication scheme is based on a detection-diagnosis-recovery approach, which is intrusion detection augmented with system diagnosis and reconfiguration. Our main goal is to minimize the cost of performing link state update authentication when the network components function normally, which occurs most of the time. In our scheme, a router $r$ uses a key $k$ and a symmetric-key based data authentication scheme (e.g., a keyed-hash scheme) to sign a link state update. The link state update and the signature are disseminated to all other routers. A receiving router optimistically accepts the routing update as if it were authenticated. Later, router $r$ will release the key $k$. When the key $k$ arrives, the receiving router verifies the authenticity of the key using a secure and efficient method. Then the verified key will be used to verify the authenticity of the link state update using the symmetric-key based data authentication scheme. Note that signature generation and verification can be done very efficiently using a symmetric-key based data authentication scheme. If bogus routing updates are detected, a distributed diagnosis protocol will be invoked to locate the mischievous routers. Then network reconfiguration will be performed to logically disconnect those routers to restore the operational status of the network.

Protecting Routing Infrastructures from Denial of Service Attacks

To protect a network from routers that incorrectly drop packets and misroute packets, which can cause denial of service. Based on our detection-diagnosis-recovery approach, we propose protocols that detect and respond to those misbehaving routers. One of our techniques is called flow analysis, which monitors the transit traffic flowing in and out of a router to ensure they are of the same amount. Periodically, the neighbors of a router exchange their counts. A failed router that incorrectly drops transit packets can thus be detected by its neighbors. Subsequently, those neighbors will cease the neighbor relationship with the failed router. We prove that our protocols have the following properties: (1) A good router never incorrectly claims another router as a failed router; (2) If a network has failed routers, one or more of them can be located; (3) Failed routers will eventually be removed.

Protecting Domain Name Systems

A domain name system (DNS) is a network service used to implement a large mapping. For instance, DNS maps IP addresses to host names and vice versa. The mapping is partitioned into zones, which are managed by DNS servers. Many distributed applications---such as file transfer, remote login, electronic mail, and WWW---rely on DNS. Entity authentication may fail if host names are used for authentication and the mapping is compromised. DNS attacks such as cache poisoning and query ID guessing have been used by attackers to compromise end systems. To cope with those attacks, Vixie, Bellovin, and others have proposed fixes. However, it is not clear if those fixes are sufficient because of the complexity of existing DNS implementations.

We propose a formal intrusion detection approach to protect DNS. Our approach uses formal modeling, formal specifications, and proofs with respect to these specifications---all of which facilitate reasoning to increase assurance of the intrusion detection solution. By specifications, we refer to the expected behaviors of DNS that are security-related. We have designed a DNS wrapper to monitor the DNS traffic going in and going out of a DNS server. DNS traffic is checked against our specifications and deviations from these specifications are noted as anomalous. For each deviation, the DNS wrapper verifies with a DNS server responsible for the corresponding part of the database. If the monitored traffic disagrees with the authoritative answer, this event is flagged as a possible attack. Our ongoing work is to implement the DNS wrapper, to evaluate its effectiveness and its performance overhead, and to formally prove safety properties.

Additional information

Steven Cheung 7/30/98