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
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
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
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.
- Steven Cheung, "An Efficient Message Authentication Scheme for Link State
Routing". Proceedings of the 13th Annual Computer Security Applications
- Steven Cheung and Karl Levitt, "Protecting Routing Infrastructures from
Denial of Service Using Cooperative Intrusion Detection". Proc. New Security
Paradigms Workshop, 1997. [pdf]
- Kirk A. Bradley, Steven Cheung, Nick Puketza, Biswanath Mukherjee, and
Ronald A. Olsson, "Detecting Disruptive Routers: A Distributed Network Monitoring
Approach". Proceedings of the 1998 IEEE Symposium on Security and Privacy.
Steven Cheung 7/30/98