Publication Abstracts

Home • Research • Teaching • Publications • Vita • Personal

Origin Authentication in Interdomain Routing

Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence of {\it origin authentication}; there is no way to validate claims of address ownership or location. The lack of such services not only enables attacks by malicious entities, but also indirectly allows seemingly inconsequential misconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize original, broad classes of origin authentication proof systems. We estimate the {\it address delegation graph} representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80\% of the delegation on the Internet. We conclude by evaluating the proposed services via trace-based simulation, which demonstrates that the enhanced proof systems can significantly reduce resource costs associated with origin authentication.

Paper: comnet05.pdf ( 2005)

Security Policy Enforcement in the Antigone System

Works in communication security policy have recently focused on general-purpose policy languages and evaluation algorithms. However, because the supporting frameworks often defer enforcement, the correctness of a realization of these policies in software is limited by the quality of domain-specific implementations. This paper introduces the Antigone communication security policy enforcement framework. The Antigone framework fills the gap between representations and enforcement by implementing and integrating the diverse security services needed by policy. Policy is enforced by the run-time composition, configuration, and regulation of security services. We present the Antigone architecture, and demonstrate non-trivial applications and policies. A profile of policy enforcement performance is developed, and key architectural enhancements identified. We conclude by considering the advantages and disadvantages of a broad range of software architectures appropriate for policy enforcement.

Paper: jcs05.pdf ( 2005)

Analysis of Security Vulnerabilities in the Movie Production and Distribution Process

Unauthorized copying of movies is a major concern for the motion picture industry. While unauthorized copies of movies have been distributed via portable physical media for some time, low-cost, high-bandwidth Internet connections and peer-to-peer file sharing networks provide highly efficient distribution media. Many movies are showing up on file sharing networks shortly after, and in some cases prior to, theatrical release. It has been argued that the availability of unauthorized copies directly affects theater attendance and DVD sales, and hence represents a major financial threat to the movie industry. Our research attempts to determine the source of unauthorized copies by studying the availability and characteristics of recent popular movies in file sharing networks. We developed a data set of 312 popular movies and located one or more samples of 183 of these movies on file sharing networks, for a total of 285 movie samples. 77% of these samples appear to have been leaked by industry insiders. Most of our samples appeared on file sharing networks prior to their official consumer DVD release date. Indeed, of the movies that had been released on DVD as of the time of our study, only 5% first appeared after their DVD release date on a web site that indexes file sharing networks, indicating that consumer DVD copying currently represents a relatively minor factor compared with insider leaks. We perform a brief analysis of the movie production and distribution process and identify potential security vulnerabilities that may lead to unauthorized copies becoming available to those who may wish to redistribute them. Finally, we offer recommendations for reducing security vulnerabilities in the movie production and distribution process.

Paper: tcpolicy04.pdf (August 2004)

Enterprise Security: A Community of Interest Based Approach

Enterprise networks today carry a range of mission critical communications. A successful worm attack within an enterprise network can be substantially more devastating to most companies than attacks on the larger Internet. In this paper we explore a brownfield approach to hardening an enterprise network against active malware such as worms. The premise of our approach is that if future communication patterns are constrained to historical ÓnormalÓ communication patterns, then the ability of malware to exploit vulnerabilities in the enterprise can be severely curtailed. We present techniques for automatically deriving individual host profiles that capture historical communication patterns (i.e., community of interest (COI)) of end hosts within an enterprise network. Using traces from a large enterprise network, we investigate how a range of different security policies based on these profiles impact usability (as valid communications may get restricted) and security (how well the policies contain malware). Our evaluations indicate that a simple security policy comprising our Extended COI-based profile and relaxed Throttling Discipline can effectively contains worm behavior within an enterprise without significantly impairing normal network operation.

Paper: ndss06.pdf (February 2006)

Understanding Mutable Internet Pathogens, or How I Learned to Stop Worrying and Love Parasitic Behavior

Worms are becoming increasingly hostile. The exponential growth of infection rates allows small outbreaks to have worldwide consequences within minutes. Moreover, the collateral damage caused by infections can cripple the entire Internet. While harmful, such behaviors have historically been short-lived. We assert the future holds much more caustic malware. Attacks based on mutation and covert propagation are likely to be ultimately more damaging and long lasting. This assertion is supported by observations of natural systems, where similarly behaving parasites represent by far the most successful class of living creatures. This talk considers a parasite for the Internet, providing biological metaphors for its behavior and demonstrating the structure of pathogens. Through simulation, we show that even with low infection rates, a mutating pathogen will eventually infect an entire community. We posit the inevitability of such parasites, and consider ways that they can be mitigated.

Paper: iciss05.pdf (December 2005)

TARP: Ticket-Based Address Resolution Protocol

IP networks fundamentally rely on the Address Resolution Protocol (ARP) for proper operation. Unfortunately, vulnerabilities in the ARP protocol enable a raft of IP-based impersonation, man-in-the-middle, or DoS attacks. Proposed countermeasures to these vulnerabilities have yet to simultaneously address backward compatibility and cost requirements. This paper introduces the Ticket-based Address Resolution Protocol (TARP). TARP implements security by distributing centrally issued secure MAC/IP address mapping attestations through existing ARP messages. We detail the TARP protocol and its implementation within the Linux operating system. Our experimental analysis shows that TARP improves the costs of implementing ARP security by as much as two orders of magnitude over existing protocols. We conclude by exploring a range of operational issues associated with deploying and administering ARP security.

Paper: acsac05b.pdf (December 2005)

Exploiting Open Functionality in SMS-Capable Cellular Networks

Cellular networks are a critical component of the economic and social infrastructures in which we live. In addition to voice services, these networks deliver alphanumeric text messages to the vast majority of wireless subscribers. To encourage the expansion of this new service, telecommunications companies offer connections between their networks and the Internet. The ramifications of such connections, however, have not been fully recognized. In this paper, we evaluate the security impact of the SMS interface on the availability of the cellular phone network. Specifically, we demonstrate the ability to deny voice service to cities the size of Washington D.C. and Manhattan with little more than a cable modem. Moreover, attacks targeting the entire United States are feasible with resources available to medium-sized zombie networks. This analysis begins with an exploration of the structure of cellular networks. We then characterize network behavior and explore a number of reconnaissance techniques aimed at effectively targeting attacks on these systems. We conclude by discussing countermeasures that mitigate or eliminate the threats introduced by these attacks.

Paper: ccs05.pdf (November 2005)

The Sleep Deprivation Attack in Sensor Networks: Analysis and Methods of Defense

The ability of sensor nodes to enter a low power sleep mode is very useful for extending network longevity. We show how adversary nodes can exploit clustering algorithms to ensure their selection as cluster heads for the purpose of launching attacks that prevent victim nodes from sleeping. We present two such attacks: the barrage attack and the sleep deprivation attack. The barrage attack bombards victim nodes with legitimate requests, whereas the sleep deprivation attack makes requests of victim nodes only as often as is necessary to keep the victims awake. We show that while the barrage attack causes its victims to spend slightly more energy, it is more easily detected and requires more effort on behalf of the attacker. Thus we have focused our research on the sleep deprivation attack. Our analysis indicates that this attack can nullify any energy savings obtained by allowing sensor nodes to enter sleep mode. We also analyze three separate methods for mitigating this attack: the random vote scheme, the round robin scheme, and the hash-based scheme. We have evaluated these schemes based upon their ability to reduce the adversaryÕs attack, the amount of time required to select a cluster head, and the amount of energy required to perform each scheme. We have found that of the three clustering methods analyzed, the hash-based scheme is the best at mitigating the sleep deprivation attack.

Paper: ICA_DSN_05b.pdf (October 2005)

Privacy Preserving Clustering

The freedom and transparency of information flow on the Internet has heightened concerns of privacy. Given a set of data items, clustering algorithms group similar items together. Clustering has many applications, such as customer-behavior analysis, targeted marketing, forensics, and bioinformatics. In this paper, we present the design and analysis of a privacy-preserving k-means clustering algorithm, where only the cluster means at the various steps of the algorithm are revealed to the participating parties. The crucial step in our privacy-preserving k-means is privacy-preserving computation of cluster means. We present two protocols (one based on oblivious polynomial evaluation and the second based on homomorphic encryption) for privacy-preserving computation of cluster means. We have a JAVA implementation of our algorithm. Using our implementation, we have performed a thorough evaluation of our privacy-preserving clustering algorithm on three data sets. Our evaluation demonstrates that privacy-preserving clustering is feasible, i.e., our homomorphic-encryption based algorithm finished clustering a large data set in approximately 66 seconds.

Paper: esorics05.pdf (September 2005)

Secure Reporting of Traffic Forwarding Activity in Mobile Ad Hoc Networks

Nodes forward data on behalf of each other in mobile ad hoc networks. In a civilian application, nodes are assumed to be selfish and rational, i.e., they pursue their own self-interest. Hence, the ability to accurately measure traffic forwarding is critical to ensure proper network operation. These measurements are often used to credit nodes based on their level of participation, or to detect loss. Past solutions employ neighbor monitoring and reporting on node forwarding traffic. These methods are not applicable in civilian networks where neighbor nodes lack the desire or ability to perform the monitoring function. Such environments occur frequently in which neighbor hosts are resource constrained, or in networks where directional antennas are used and reliable monitoring is difficult or impossible.

In this paper, we propose a protocol that uses nodes on the data path to securely produce packet forwarding reports. Reporting nodes are chosen randomly and secretly so that malicious nodes cannot modify their behavior based upon the monitoring point. The integrity and authenticity of reports are preserved through the use of secure link layer acknowledgments and monitoring reports. The robustness of the reporting mechanism is strengthened by forwarding the report to multiple destinations (source and destination). We explore the security, cost, and accuracy of our protocol.

Paper: mobiq05.pdf (July 2005)

Origin Authentication in Interdomain Routing

Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence origin authentication: there is no way to validate claims of address ownership or location. The lack of such services enables not only attacks by malicious entities, but indirectly allow seemingly inconsequential miconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize broad classes of origin authentication proof systems. We estimate the address delegation graph representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80% of the delegation on the Internet. We conclude by evaluating the proposed services via traced based simulation. This simulation shows the enhanced proof systems can reduce resource consumption by an order of magnitude over currently proposed solutions.

Paper: ccs03a.pdf (October 2003)

On the Performance, Feasibility, and Use of Forward Secure Signatures

Forward-secure signatures (FSSs) have recently received much attention from the cryptographic theory community as a potentially realistic way to mitigate many of the difficulties digital signatures face with key exposure. However, no previous works have explored the practical performance of these proposed constructions in real-world applications, nor have they compared FSS to traditional, non-forward-secure, signatures in a non-asymptotic way.

We present an empirical evaluation of several FSS schemes that looks at the relative performance among different types of FSS as well as between FSS and traditional signatures. Our study provides the following contributions: first, a new methodology for comparing the performance of signature schemes, and second, a thorough examination of the practical performance of FSS. We show that for many cases the best FSS scheme has essentially identical performance to traditional schemes, and even in the worst case is only 2-4 times slower. On the other hand, we also show that if the wrong FSS configuration is used, the performance can be orders of magnitude slower. Our methodology provides a way to prevent such misconfigurations, and we examine common applications of digital signatures using it. In addition to the evaluation methodology and empirical study, a third contribution of this paper is the open-source FSS library developed for the study.

We conclude that not only are forward-secure signatures a useful theoretical construct as previous works have shown, but they are also, when used correctly, a very practical solution to some of the problems associated with key exposure in real-world applications. Through our metrics and our reference implementation we provide the tools necessary for developers to efficiently use forward-secure signatures.

Paper: ccs03b.pdf (October 2003)

On Context in Authorization Policy

Authorization policy infrastructures are evolving with the complex environments that they support. One key, but not yet well understood, aspect of policy is the need and support of context. Often implemented as condition functions or predefined attributes, context is used to more precisely control when and how policy is enforced. This paper considers context requirements and services in authorization policy. The properties and security requirements of context evaluation are classified. A key observation gleaned from this classification is the degree to which context functions share common properties. The Antigone Condition Framework (ACF) exploits these commonalities to provide a general purpose service and associated API used to defined and implemented context. The prototype ACF design is presented and illustrated, and directions for future work considered.

Paper: sacmat03.pdf (June 2003)

Working Around BGP: An Incremental Approach to Improving Security and Accuracy of Interdomain Routing

BGP is essential to the operation of the Internet, but is vulnerable to both accidental failures and malicious attacks. We propose a new protocol that works in concert with BGP, which Autonomous Systems will use to help detect and mitigate accidentally or maliciously introduced faulty routing information. The protocol differs from previous efforts at securing BGP in that it is receiver-driven, meaning that there is a mechanism for recipients of BGP UPDATE messages to corroborate the information they receive and to provide feedback. We argue that our new protocol can be adopted incrementally, and we show that there is incentive for network operators to do so. We also describe our prototype implementation.

Paper: ndss03.pdf (February 2003)

Methods and Limitations of Security Policy Reconciliation

A security policy is the means by which participant session requirements are specified. However, existing frameworks provide limited facilities for the automated reconciliation of participant security policies. This paper considers the limits and methods of reconciliation in a general-purpose policy model. We identify an algorithm for efficient two-policy reconciliation, and show that, in the worst-case, reconciliation of three or more policies is intractable. When reconciliation is intractable, we suggest efficient heuristics for detecting intractability and reconciliation of such policies. Based upon the policy model, we describe the design and implementation of the Ismene policy language. The expressiveness of Ismene, and indirectly of our model, is demonstrated through the representation and exposition of policies supported by existing policy languages. We conclude with brief notes on the integration and enforcement of Ismene policy within the Antigone group communication system.

Paper: oak2002.pdf (MAY 2002)

Flexibly Constructing Secure Groups in Antigone 2.0

Group communication is increasingly used as a low cost building block for the development of highly available and survivable services in dynamic environments. However, contemporary frameworks often provide limited facilities for the definition and enforcement of precise security policies. This paper presents the Antigone 2.0 framework that allows the flexible specification and enforcement of group security policies. Enforcement is achieved through the policy directed composition and configuration of sets of basic security services implementing the group. We summarize the design of the Antigone 2.0 architecture, its use, and the Application Programming Interface (API). The use of the API is illustrated through two applications built on Antigone; a reliable multicast system and host level multicast security service. We conclude with a description of current status and plans for future work.

Paper: discex01.pdf (June 2001)

Principles of Policy in Secure Groups

Security policy is increasingly being used as a vehicle for specifying complex entity relationships. When used to define group security, policy must be extended to state the entirety of the security context. For this reason, the policy requirements of secure groups are more complex than found in traditional peer communication; group policies convey information about associations greater and more abstract than their pair-wise counterparts. This paper identifies and illustrates universal requirements of secure group policy and reasons about the adherence of the Group Security Association Key Management Protocol (GSAKMP) to these principles.

Paper: ndss01.pdf (February 2001)

Windowed Certificate Revocation

The advent of electronic commerce and personal communications on the Internet heightens concerns over the lack of privacy and security. Network services providing a wide range of security related guarantees are increasingly based on public key certificates. A fundamental problem inhibiting the wide acceptance of existing certificate distribution services is the lack of a scalable certificate revocation mechanism. We argue in this paper that the resource requirements of extant revocation mechanisms place significant burden on certificate servers and network resources. We propose a novel mechanism called windowed revocation that satisfies the security policies and requirements of existing mechanisms and, at the same time, reduces the burden on certificate servers and network resources. We include a proof of correctness of windowed revocation and analyze worst case performance scenarios.

Paper: info00.pdf (March 2000)

A Response to `Can We Eliminate Certificate Revocation Lists?'

The massive growth of electronic commerce on the Internet heightens concerns over the lack of meaningful certificate management. One issue limiting the availability of such services is the absence of scalable certificate revocation. The use of certificate revocation lists (CRLs) to convey revocation state in public key infrastructures has long been the subject of debate. Centrally, opponents of the technology attribute a range of semantic and technical limitations to CRLs. In this paper, we consider arguments advising against the use of CRLs made principally by Rivest in his paper ``Can we eliminate certificate revocation lists?''. Specifically, the assumptions and environments on which these arguments are based are separated from those features inherent to CRLs. We analyze the requirements and potential solutions for three distinct PKI environments. The fundamental tradeoffs between revocation technologies are identified. From the case study analysis we show how, in some environments, CRLs are the most efficient vehicle for distributing revocation state. The lessons learned from our case studies are applied to a realistic PKI environment. The result, revocation on demand, is a CRL based mechanism providing timely revocation information.

Paper: finc00.pdf (February 2000)

Secure Distributed Virtual Conferencing

We describe a secure distributed virtual conferencing application (SDVC) that provides high quality streaming video and audio using IP multicast for efficient distribution, uses strong authentication via cryptographic means, and (optionally) provides fully encrypted communication without sacrificing the quality of the medium or the user experience. We summarize our experiences with SDVC in a recent live demonstration and conclude with a discussion of future plans.

Paper: cms99.pdf (September 1999)

Antigone: A Flexible Framework for Secure Group Communication

Many emerging applications on the Internet requiring group communication have varying security requirements. Significant strides have been made in achieving strong semantics and security guarantees within group environments. However, in existing solutions, the scope of available security policies is often limited. This paper presents the Antigone framework. Antigone provides a suite of mechanisms from which flexible application security policies may be implemented. Using this approach, developers may chose a policy that best addresses their security and performance requirements. We describe the Antigone's mechanisms, consisting of a set of micro-protocols, and show how different security policies can be implemented using those mechanisms. We also present a performance study illustrating the security/performance tradeoffs that can be made using Antigone.

Paper: usec99.pdf (August 1999)

Analysis of Communities Of Interest in Data Networks

Communities of interest (COI) have been applied in a variety of environments ranging from characterizing the online buying behavior of individuals to detecting fraud in telephone networks. The common thread among these applications is that the historical COI of an individual can be used to predict future behavior as well as the behavior of other members of the COI. It would clearly be beneficial if COIs can be used in the same manner to characterize and predict the behavior of hosts within a data network. In this paper, we introduce a methodology for evaluating various aspects of COIs of hosts within an IP network. In the context of this study, we broadly define a COI as a collection of interacting hosts. We apply our methodology using data collected from a large enterprise network over a eleven week period. First, we study the distributions and stability of the size of COIs. Second, we evaluate multiple heuristics to determine a stable core set of COIs and determine the stability of these sets over time. Third, we evaluate how much of the communication is not captured by these core COI sets.

Paper: pam05.pdf (March 2005)

Searching for Privacy: Design and Implementation of a P3P-Enabled Search Engine

Although the number of online privacy policies is increasing, it remains difficult for Internet users to understand them, let alone to compare policies across sites or identify sites with the best privacy practices. The World Wide Web Consortium (W3C) developed the Platform for Privacy Preferences (P3P 1.0) specification to provide a standard computer-readable format for privacy policies. This standard enables web browsers and other user agents to interpret privacy policies on behalf of their users. This paper introduces our prototype P3P-enabled Privacy Bird Search engine. Users of this search service are given visual indicators of the privacy policies at sites included in query results. Our system acts as a front end to a general search engine by evaluating the P3P policies associated with search results against a user's privacy preference settings. To improve system performance we cache unexpired P3P policy information (including information about the absence of P3P policies) for thousands of the most popular sites as well as for sites that have been returned in previous search results. We discuss the system architecture and its implementation, and consider the work necessary to evolve our prototype into a fully functional and efficient service.

Paper: pets04.pdf (May 2004)

Security Policy Reconciliation in Distributed Computing Environments

A major hurdle in sharing resources between organizations is heterogeneity. Therefore, in order for two organizations to collaborate their policies have to be resolved. The process of resolving different policies is known as policy reconciliation, which in general is an intractable problem. This paper addresses policy reconciliation in the context of security. We present a formal framework and hierarchical representation for security policies. Our hierarchical representation exposes the structure of the policies and leads to an efficient reconciliation algorithm. We also demonstrate that agent preferences for security mechanisms can be readily incorporated into our framework. We have implemented our reconciliation algorithm in a library called the Policy Reconciliation Engine or PRE. In order to test the implementation and measure the overhead of our reconciliation algorithm, we have integrated PRE into a distributed high-throughput system called Condor.

Paper: policy04.pdf (June 2004)

Analysis of Security Vulnerabilities in the Movie Production and Distribution Process

Unauthorized copying of movies is a major concern for the motion picture industry. While unauthorized copies of movies have been distributed via portable physical media for some time, low-cost, high-bandwidth Internet connections and peer-to-peer file sharing networks provide highly efficient distribution media. Many movies are showing up on file sharing networks shortly after, and in some cases prior to, theatrical release. It has been argued that the availability of unauthorized copies directly affects theater attendance and DVD sales, and hence represents a major financial threat to the movie industry. Our research attempts to determine the source of unauthorized copies by studying the availability and characteristics of recent popular movies in file sharing networks. We developed a data set of 312 popular movies and located one or more samples of 183 of these movies on file sharing networks, for a total of 285 movie samples. 77\% of these samples appear to have been leaked by industry insiders. Most of our samples appeared on file sharing networks prior to their official consumer DVD release date. Indeed, of the movies that had been released on DVD as of the time of our study, only 5\% first appeared after their DVD release date on a web site that indexes file sharing networks, indicating that consumer DVD copying currently represents a relatively minor factor compared with insider leaks. We perform a brief analysis of the movie production and distribution process and identify potential security vulnerabilities that may lead to unauthorized copies becoming available to those who may wish to redistribute them. Finally, we offer recommendations for reducing security vulnerabilities in the movie production and distribution process.

Paper: drm03.pdf (October 2003)

GSAKMP (Draft)

This document specifies the Group Secure Association Key Management Protocol (GSAKMP). The GSAKMP provides a security framework for creating and managing cryptographic groups on a network. It provides mechanisms to disseminate group policy and authenticate users, rules to perform access control decisions during group establishment and recovery, capabilities to recover from the compromise of group members, delegation of group security functions, and capabilities to destroy the group. It also generates group keys.

Paper: draft-ietf-msec-gsakmp-sec-03.txt (August 2003)

A Flexible Architecture for Security Policy Enforcement

Significant progress has been made on the design of security policy representations for complex communication systems. A significant problem however remains -- how to design software architectures that enforce ever-changing security policy requirements efficiently. This research summary describes the security policy enforcement architecture of the Antigone 2.0 the group communication system. The architecture is designed to be flexible: new security mechanism modules are added as needed to support emerging policy requirements. Such mechanisms regulate the processing of system and network events as directed by the policy and enforce fine-grained control over sensitive data. A software bus is used coordinate the delivery of these events to mechanisms within each process. We summarize an analysis of the performance of the architecture and show that the overheads are modest for typical environments.

Paper: discex03.pdf (April 2003)

Multicast Security Policy Requirements and Building Blocks (Draft)

Policy has long been accepted as means of bridging the gap between changing user requirements and static implementations. Policy management infrastructures provide abstractions of underlying services. In this way, applications can freely adapt to the needs and capabilities of changing environments. The policy approach has been especially successful in the deployment of security services.

This document identifies the requirements of the policy management infrastructure of the SMuG secure multicast architecture. The requirements of the processes by which policies are created and enforced are presented. Major design decisions are presented and alternate solutions are identified. Relevant works defining architectures and protocols for the distribution, evaluation, and enforcement of policy are reviewed. We identify potential building blocks and identify a sample policy data structure appropriate for secure multicast.

Paper: draft-irtf-smug-polreq-00.txt (November 2000)

Group Security Policy Token (Draft)

This document provides a definition for Group Security Policy, describes the set of elements that make-up an instance of group policy for a given group, and provides an explanation of the intended functions of each element of a group security policy as expressed in the form of the Policy Token or Policy Certificate.

Paper: draft-ietf-msec-gspt-01.txt (November 2001)

Multicast Security Policy (Draft)

Security is increasingly becoming a concern in applications built on multi-party communication. Centrally, protection of the application content from non-authorized or malicious parties is the fundamental goal of any security policy specification. This draft seeks to illuminate the design space of secure multicast communication policy. The security requirements of existing application policies are intended to be addressable by these policy dimensions. It is from an understanding of policy design space that the mechanisms for policy specification and enforcement can be derived.

Paper: draft-irtf-smug-mcast-policy-01.txt (June 2000)

Declassification with Cryptographic Functions in a Security-Typed Language

Security-typed languages are powerful tools for provably enforcing noninterference. Real computing systems, however, often intentionally violate noninterference by deliberately releasing (or declassifying) sensitive information. These systems frequently trust cryptographic functions to achieve declassification while still maintaining confidentiality. We introduce the notion of trusted functions that implicitly act as declassifiers within a security-typed language. Proofs of the new language's soundness and its enforcement of a weakened form of noninterference are given. Additionally, we implement trusted functions used for declassification in the Jif language. This represents a step forward in making security-typed languages more practical for use in real systems.

Path Authentication in Interdomain Routing

Interdomain routing is implemented on the Internet through the Border Gateway Protocol (BGP). Many approaches have been proposed to mitigate or solve the many problems of BGP security; yet, none of the proposed solutions have been widely deployed. The lack of adoption is largely caused by a failure to find an acceptable balance between deployability, cost, and security. In this paper, we study one aspect of the BGP security puzzle: path validation. We develop formal semantics for path and route attestations, which provide the basis for a suite of cryptographic proof systems for path validation. We analyze the security relevant stability of paths in the Internet and profile resource consumption of the proposed constructions via trace-based simulations. Our constructions are shown through these experiments to reduce signature validation costs by as much as 97.3\% over existing proposals while requiring nominal storage resources. We conclude by considering how our solution can be deployed in the Internet.

Paper: nas-tr-0002-2004.pdf (November 2004)

Origin Disturbances in BGP

This paper develops an empirical profile of BGP prefix announcements that originate from multiple ASes, so-called MOAS announcements. Analysis of Oregon RouteViews data over one year shows that a small fraction of prefixes are responsible for a very large fraction of all origin AS transitions observed at RouteViews. Moreover, these heavy-hitter prefixes oscillated between two origin ASes. The prevalence of this behavior indicates that a clear profile of its characteristics will inform a larger understanding of MOASes and ultimately BGP.

The central contribution of this paper is a detailed analysis of these MOAS multihoming oscillations at different time scales. We empirically derive a model of AS disturbance periods during which the origin AS observed oscillates with heavy tailed holding times. We demonstrate that these disturbances arrive according to a Poisson process. We also show that the update stream within these disturbances exhibits long range dependence. Using simulations, and physical-based modeling of events at origin to drive these simulations, we demonstrate that heavy-tailed oscillation at the origin is a possible explanation for our observations (while the complex interplay of the BGP protocol and network topology is not such an explanation). Comparison with BGP beacon data verifies our simulations that discrete and singular events at the origin do not generate heavy-tailed oscillations at the viewpoint. In sum, we find that AS oscillations driven by heavy-tailed oscillations between different multihomed providers are a widespread and important BGP phenomenon with complex but recognizable signatures such as heavy-tailed holding times and long-range dependence.

Paper: td-62tjf8.pdf (July 2004)

A Survey of BGP Security Issues and Solutions

BGP is {\em the} protocol that enables interdomain routing in the Internet. Although BGP has proven to be generally stable, there are mounting concerns about its ability to meet the needs of the rapidly evolving Internet. A central limitation of BGP is its failure to address security. The design and ubiquity of BGP have complicated past efforts at securing interdomain routing. This paper surveys works relating to BGP security. We explore the limitations and advantages of proposed solutions, an consider the systemic and operational implications of their design. We centrally note that no current solution has yet found a perfect balance between comprehensive security and deployment cost. Recent BGP-related outages and security analyses clearly indicate that the current Internet routing infrastructure is highly vulnerable. Our investigation calls not only for application of ideas and approaches described within this paper, but also for further introspection on the problems and solutions for BGP security.

Paper: td-5ugj33.pdf (February 2004)

Securing Distributed Applications Using a Policy-based Approach

Distributed applications are increasingly being used for communication, sharing data, and distributing data by users. However, incorporating security in them remains a significant challenge for both developers and users for several reasons. First, the security features required in an instance of an application may depend on the environment in which the application is operating, the type of data exchanged, and the capability of the end-points of communication. Second, the security mechanisms deployed could apply to both communication and application layers in the system, making it difficult to understand and manage overall system security. This paper presents a policy-based approach to meeting these needs. A security policy language framework, Ismene, is extended to allow security policy specification to be used by both the communication and the application layers. To illustrate the use of the framework, we specify security policy for a prototype distributed file mirroring application that operates in environments with different security requirements. We report on our experiences in using a policy-driven approach for securing such applications.

Paper: td-5udkvd.pdf (December 2003)

Origin Authentication in Interdomain Routing

Attacks against Internet routing are increasing in number and severity. Contributing greatly to these attacks is the absence origin authentication: there is no way to validate claims of address ownership or location. The lack of such services enables not only attacks by malicious entities, but indirectly allow seemingly inconsequential miconfigurations to disrupt large portions of the Internet. This paper considers the semantics, design, and costs of origin authentication in interdomain routing. We formalize the semantics of address delegation and use on the Internet, and develop and characterize broad classes of origin authentication proof systems. We estimate the address delegation graph representing the current use of IPv4 address space using available routing data. This effort reveals that current address delegation is dense and relatively static: as few as 16 entities perform 80% of the delegation on the Internet. We conclude by evaluating the proposed services via traced based simulation. This simulation shows the enhanced proof systems can reduce resource consumption by an order of magnitude over currently proposed solutions.

Paper: td-5qhg2g.pdf (August 2003)

On the Performance, Feasibility, and Use of Forward Secure Signatures

Forward-secure signatures (FSSs) have recently received much attention from the cryptographic theory community as a potentially realistic way to mitigate many of the difficulties digital signatures face with key exposure. However, no previous works have explored the practical performance of these proposed constructions in real-world applications, nor have they compared FSS to traditional, non-forward-secure, signatures in a non-asymptotic way.

We present an empirical evaluation of several FSS schemes that looks at the relative performance among different types of FSS as well as between FSS and traditional signatures. Our study provides the following contributions: first, a new methodology for comparing the performance of signature schemes, and second, a thorough examination of the practical performance of FSS. We show that for many cases the best FSS scheme has essentially identical performance to traditional schemes, and even in the worst case is only 2-4 times slower. On the other hand, we also show that if the wrong FSS configuration is used, the performance can be orders of magnitude slower. Our methodology provides a way to prevent such misconfigurations, and we examine common applications of digital signatures using it. In addition to the evaluation methodology and empirical study, a third contribution of this paper is the open-source FSS library developed for the study.

We conclude that not only are forward-secure signatures a useful theoretical construct as previous works have shown, but they are also, when used correctly, a very practical solution to some of the problems associated with key exposure in real-world applications. Through our metrics and our reference implementation we provide the tools necessary for developers to efficiently use forward-secure signatures.

Paper: td-5qhgbk.pdf (August 2003)

Analysis of Security Vulnerabilities in the Movie Production and Distribution Process

Unauthorized copying of movies is a major concern for the motion picture industry. While unauthorized copies of movies have been distributed via portable physical media for some time, low-cost, high-bandwidth Internet connections and peer-to-peer file sharing networks provide highly efficient distribution media. Many movies are showing up on file sharing networks shortly after, and in some cases prior to, theatrical release. It has been argued that the availability of unauthorized copies directly affects theater attendance and DVD sales, and hence represents a major financial threat to the movie industry. Our research attempts to determine the source of unauthorized copies by studying the availability and characteristics of recent popular movies in file sharing networks. We developed a data set of 312 popular movies and located one or more samples of 183 of these movies on file sharing networks, for a total of 285 movie samples. 77\% of these samples appear to have been leaked by industry insiders. Most of our samples appeared on file sharing networks prior to their official consumer DVD release date. Indeed, of the movies that had been released on DVD as of the time of our study, only 5\% first appeared after their DVD release date on a web site that indexes file sharing networks, indicating that consumer DVD copying currently represents a relatively minor factor compared with insider leaks. We perform a brief analysis of the movie production and distribution process and identify potential security vulnerabilities that may lead to unauthorized copies becoming available to those who may wish to redistribute them. Finally, we offer recommendations for reducing security vulnerabilities in the movie production and distribution process.

Paper: td-5n6sj4.pdf (August 2003)

On Context in Authorization Policy

Authorization policy infrastructures are evolving with the complex environments that they support. One key, but not yet well understood, aspect of policy is the need and support of context. Often implemented as condition functions or predefined attributes, context is used to more precisely control when and how policy is enforced. This paper considers context requirements and services in authorization policy. We classify the use, properties, and security requirements of context evaluation. A key observation gleaned from this classification is the degree to which context functions share common properties. The Antigone Condition Framework (ACF) exploits these commonalities to provide a general purpose service and associated API used to defined and implemented context. We present and illustrate the prototype ACF design, and conclude by considering directions for future work.

Paper: td-5jcjck.pdf (January 2003)

An Architecture for Security Policy Enforcement

Recent advances in policy specification and evaluation have increased the usage of general-purpose policy frameworks. However, because these frameworks typically defer enforcement, the quality with which policy is realized is subject to the correctness of each domain-specific implementation. This paper considers the requirements and machinery of an architecture supporting general-purpose policy enforcement. The tangible result of this investigation, the Antigone 2.0 enforcement framework adopts a broad definition of policy. Antigone policies encompass context sensitive session provisioning and access control. Antigone enforces policies meeting this definition through the run-time composition, configuration, and regulation of security services. We present the Antigone 2.0 architecture, and demonstrate enforcement through several non-trivial policies. A profile of policy enforcement performance is developed, and key architectural enhancements identified.

Paper: td-5c6jfv.pdf (July 2002)

Methods and Limitations of Security Policy Reconciliation

A security policy is the means by which participant session requirements are specified. However, existing frameworks provide limited facilities for the automated reconciliation of participant security policies. This paper considers the limits and methods of reconciliation in a general-purpose policy model. We identify an algorithm for efficient two-policy reconciliation, and show that, in the worst-case, reconciliation of three or more policies is intractable. When reconciliation is intractable, we suggest efficient heuristics for detecting intractability and reconciliation of such policies. Based upon the policy model, we describe the design and implementation of the Ismene policy language. The expressiveness of Ismene, and indirectly of our model, is demonstrated through the representation and exposition of policies supported by existing policy languages. We conclude with brief notes on the integration and enforcement of Ismene policy within the Antigone group communication system.

Paper: td57-paw.pdf (February 2002)

Ismene: Provisioning and Policy Reconciliation in Secure Group Communication

Group communication systems increasingly provide security services. However, in practice, the use of such systems is complicated by the divergent requirements and abilities of group members. In this paper, we define a policy language called Ismene that directs the provisioning of security-related resources at member sites. The communication service is defined through a reconciliation of a group policy and member's local policies into a security configuration. Group authorization and access control appropriate for the operating conditions and session configuration are also defined within the policy. The use of Ismene policies to define security is illustrated through an extended example of a group application built on the prototype Ismene framework.

Paper: CSE-TR-438-00.pdf (December 2000)

Lightweight Failure Detection in Secure Group Communication

The secure and efficient detection of process failures is an essential requirement of many distributed systems. In this paper, we present the design and analysis of a mechanism used for the detection of member failures in secure groups. Based on one-time passwords, our solution does not obviate the need for periodic statements from group members, but significantly reduces the cost of their generation and validation. A study comparing the costs of traditional mechanisms with our proposed approach is presented. Results of the study indicate the average case performance of the proposed scheme is 1/10th of traditional failure detection in trusted groups, and negligible in the untrusted groups. A discussion of security and performance tradeoffs made through mechanism policy is provided.

Paper: CSE-TR-428-00.pdf (June 2000)

Antigone: Implementing Policy in Secure Group Communication

Significant strides have been made in achieving strong semantics and security guarantees within group communication and multicast systems. However, the scope of available security policies in these systems is often limited. In contrast, the applications that require the services provided by these systems can differ significantly in their security policy needs. Often application designers have to either make significant compromises in using a given group communication system or build their own customized solutions, an error-prone task. This paper presents Antigone, a framework that provides a suite of mechanisms from which flexible application security policies may be implemented. With Antigone, developers may choose a policy that best addresses their security and performance requirements of an application requiring group communication. We describe the Antigone's mechanisms, consisting of a set of micro-protocols, and show how different security policies can be implemented using those mechanisms. We also present a performance study illustrating the security/performance tradeoffs that can be made using Antigone. Through an example conferencing application, we demonstrate the use of the Antigone applications programming interface and consider the use of policy in several distinct session environments.

Paper: CSE-TR-426-00.pdf (May 2000)

Windowed Certificate Revocation

The advent of electronic commerce and personal communications on the Internet heightens concerns over the lack of privacy and security. Network services providing a wide range of security related guarantees are increasingly based on public key certificates. A fundamental problem inhibiting the wide acceptance of existing certificate distribution services is the lack of a scalable certificate revocation mechanism. We argue in this paper that the resource requirements of extant revocation mechanisms place significant burden on certificate servers and network resources. We propose a novel mechanism called Windowed Revocation that satisfies the security policies and requirements of existing mechanisms and, at the same time, reduces the burden on certificate servers and network resources. We include a proof of correctness of windowed revocation and a trace-based performance study illustrating the scalability and general applicability of windowed revocation.

Paper: CSE-TR-413-99.pdf (November 1999)

Antigone: A Flexible Framework for Secure Group Communication

Many emerging applications on the Internet requiring group communication have varying security requirements. Significant strides have been made in achieving strong semantics and security guarantees within group environments. However, in existing solutions, the scope of available security policies is often limited. This paper presents the Antigone framework. Antigone provides a suite of mechanisms from which flexible application security policies may be implemented. Using this approach, developers may chose a policy that best addresses their security and performance requirements. We describe the Antigone's mechanisms, consisting of a set of micro-protocols, and show how different security policies can be implemented using those mechanisms. We also present a performance study illustrating the security/performance tradeoffs that can be made using Antigone.

Paper: citi-tr-99-2.pdf (September 1999)

A Response to ``Can We Eliminate Certificate Revocation Lists?''

The use of certificate revocation lists (CRLs) to convey revocation state in public key infrastructures has long been the subject of debate. Centrally, opponents of the technology attribute a range of semantic and technical limitations to CRLs. In this paper, we consider arguments advising against the use of CRLs made principally by Rivest in his paper ``Can we eliminate certificate revocation lists?''. Specifically, the assumptions and environments on which these arguments are based are separated from those features inherent to CRLs. We analyze the requirements and potential solutions for three distinct PKI environments. The fundamental tradeoffs between revocation technologies are identified. From the case study analysis we show how, in some environments, CRLs are the most efficient vehicle for distributing revocation state. The lessons learned from our case studies are applied to a realistic PKI environment. The result, revocation on demand, is a CRL based mechanism providing timely revocation information.

Paper: att9981.pdf (August 1999)

Secure Distributed Virtual Conferencing: Multicast or Bust

We describe a secure distributed virtual conferencing application (SDVC) that provides high quality streaming video and audio using IP multicast for efficient distribution, using strong authentication via cryptographic means, and optionally providing fully encrypted communication without sacrificing quality of the medium or the user experience. We summarize our experiences with SDVC in a recent live demonstration and conclude with a discussion of future plans.

Paper: citi-tr-99-1.pdf (January 1999)

Windowed Key Revocation in Public Key Infrastructures

A fundamental problem inhibiting the wide acceptance of a Public Key Infrastructure (PKI) in the Internet is the lack of a mechanism that provides scalable certificate revocation. In this paper, we propose a novel mechanism called Windowed Revocation. In windowed revocation, certificate revocation is announced for short periods in periodic Certificate Revocation Lists (CRLs). Due to the assurances provided by the protocol over which certificates are retrieved, we bound the amount of time that any certificate is cached by users. Thus, we can limit the announcement of revocation only to the time in which the certificate may be cached; not until its expiration. Because the time in which certificate are announced is short, CRLs are similarly small. By limiting the size of CRLs, we are able to integrate other mechanisms that increase the scalability of the PKI. One such mechanism is the use of ``pushed'' CRLs using multicast. We include a proof of the correctness of our approach.

Paper: CSE-TR-376-98.pdf ( 1998)

A Scalable Key Distribution Hierarchy

As the use of the Internet for electronic commerce, audio and video conferencing, and other applications with sensitive content grows, the need for secure services becomes critical. Central to the success of these services is the support for secure public key distribution. Although there are several existing services available for this purpose, they are not very scalable, either because they depend on a centralized server or rely on ad hoc trust relationships.

In this paper, we present and examine a flexible approach to certificate distribution scalable to arbitrarily large networks. We propose a two level hierarchy where certificates can be independently authenticated by one or more peer authorities, called keyservers. Certificates for end-user and host entities are managed within local domains, called enterprises. By administrating certificates close to the source, we reduce the load on the key servers and the effects of network topology changes. We describe the design of our system and present a preliminary performance analysis based on traces of present-day DNS requests.

Paper: CSE-TR-366-98.pdf ( 1998)

Lightweight Secure Group Communication

An advantage of today's high speed networks is the ability to support group communication. Applications that support group communication allow the free exchange of ideas and data in real time, regardless of the physical distance between the participants. Unfortunately, support for additional protocol features such as reliability, secrecy, and total ordering in the multicast context requires more bandwidth and greater complexity than in traditional point-to-point communication. In this paper we describe a middleware software layer and associated API that attempts to minimize these requirements by providing multiple secure channels based on IP multicast within the same logical group. Named LSGC (lightweight secure group communication), the software provides the important features needed by a group application: reliable delivery, best-effort delivery, and security. In providing both reliable and unreliable channels, an application need pay only for the delivery assurances it needs. We conclude with a description of our implementation and supporting performance data.

Paper: citi-tr-98-2.pdf (April 1998)

Evaluating Design Metrics on Large-Scale Software

The purpose of the Design Metrics project is to develop a metrics approach for analyzing software designs which helps designers engineer quality into the design product. These metrics will gauge project quality as well as design complexity at all times during the design phase. Having quantifiable measurements could help managers and software developers determine the better design when alternative choices exist, as well as identify stress points which may lead to difficulty during coding and maintenance.

We have developed, for a structured design G, a design quality metric D(G) of the form D(G)=k1De+k2Di. In this equation, k1 and k2 are constants and De and Di are, respectively, an external and internal design quality component. In De we consider a module's external relationships to other modules in the software system, whereas in Di we consider factors related to the internal structure. To form De and Di, we searched for a combination of primitive design metrics which are useful, predictive, objective and automatable. This report will present our D(G), with its current De and Di composite metrics, and empirical results as to how D(G) can identify stress points in a large-scale software design and how it is related to the quality of the resulting software.

Paper: tr106p91.html (September 1991)

patrickmcdaniel.org