NRL Resources
Publications
| 2013 | 2012 | 2011 | 2010 | 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002 | 2001 | 2000 |
View Abstract
Tor, the most popular deployed distributed onion routing network, suffers from performance and scalability problems stemming from a lack of incentives for volunteers to contribute. Insufficient capacity limits scalability and harms the anonymity of its users. We introduce LIRA, a lightweight scheme that creates performance incentives for users to contribute bandwidth resources to the Tor network. LIRA uses a novel cryptographic lottery: winners may be guessed with tunable probability by any user or bought in exchange for resource contributions. The traffic of those winning the lottery is prioritized through Tor. The uncertainty of whether a buyer or a guesser is getting priority improves the anonymity of those purchasing winners, while the performance incentives encourage contribution. LIRA is more lightweight than prior reward schemes that pay for service and provides better anonymity than schemes that simply give priority to traffic originating from fast relays. We analyze LIRA's efficiency, anonymity, and incentives, present a prototype implementation, and describe experiments that show it indeed improves performance for those servicing the network.
View Abstract
Current anonymous communication systems exhibit a trade-off between weak anonymity among many nodes, via onion routing, or strong anonymity among a few nodes, via DC-nets. To addresses this trade-off we introduce Dissent, a practical anonymity system that increases by 1-2 orders of magnitude the anonymity set sizes achievable using traffic-analysis-resistant techniques. Dissent's design achieves these gains via a client/server architecture, in which many unreliable clients partially offload communication and computation costs to a smaller and more robust, but decentralized, set of servers. Clients trust only that at least one server in the set is honest, but need not know or choose which server to trust. Unlike the quadratic costs of prior peer-to-peer DC-nets schemes, Dissent's client/server design reduces communication and processing costs to linear in the number of clients, and hence in anonymity set size. Further, Dissent's servers can unilaterally ensure progress, even if clients respond slowly or disconnect at arbitrary times, ensuring robustness against client churn, tail latencies, and DoS attacks. On PlanetLab, Dissent scales to 2,000 online participants and offers latencies as low as 3 seconds for network sizes of 500. An anonymous Web browsing application also shows that Dissent's performance suffices for interactive communication within smaller local-area groups.
View Abstract
We perform a probabilistic analysis of onion routing. The analysis is presented in a black-box model of anonymous communication in the Universally Composable framework that abstracts the essential properties of onion routing in the presence of an active adversary who controls a portion of the network and knows all a priori distributions on user choices of destination. Our results quantify how much the adversary can gain in identifying users by exploiting knowledge of their probabilistic behavior. In particular, we show that, in the limit as the network gets large, a user u's anonymity is worst either when the other users always choose the destination u is least likely to visit or when the other users always choose the destination u chooses. This worst-case anonymity with an adversary that controls a fraction b of the routers is shown to be comparable to the best-case anonymity against an adversary that controls a fraction √b.
View Abstract
Anonymous communication capabilities are useful and desirable, but practical onion routing approaches are vulnerable to traffic analysis and DoS attacks — especially against a powerful adversary, such as a repressive government or compromised ISP. To fill this gap we introduce D3, the first practical anonymous group communication system offering anonymity and disruption resistance against strong traffic analysis and collusion attacks, with scalability to hundreds of group members and quick response to churn. D3 builds on a trust model we call anytrust. Anytrust is a decentralized client/server network model, in which each of many clients — representing group members — trust only that at least one of a smaller but diverse set of “server” or “super-peers” behaves honestly, but clients need not know which server to trust. By combining and adapting verifiable shuffle and DC-nets techniques to anytrust, D3 achieves short shuffle latencies and efficient tree-based DC-nets ciphertext combining, while guaranteeing message anonymity and integrity, transmission proportionality among group members, and adaptability to both network/node failures and active disruption. Experiments with a working prototype demonstrate that D3 is practical at scales infeasible in prior systems offering comparable security.
View Abstract
We introduce a novel model of routing security that incorporates the ordinarily overlooked variations in trust that users have for different parts of the network. We focus on anonymous communication, and in particular onion routing, although we expect the approach to apply more broadly. This paper provides two main contributions. First, we present a novel model to consider the various security concerns for route selection in anonymity networks when users vary their trust over parts of the network. Second, to show the usefulness of our model, we present as an example a new algorithm to select paths in onion routing. We analyze its effectiveness against deanonymization and other information leaks, and particularly how it fares in our model versus existing algorithms, which do not consider trust. In contrast to those, we find that our trust-based routing strategy can protect anonymity against an adversary capable of attacking a significant fraction of the network.
View Abstract
Low-latency anonymous communication protocols in general, and the popular onion-routing protocol in particular, are broken against simple timing attacks. While there have been few proposed solutions to this problem when the adversary is active, several padding schemes have been proposed to defend against a passive adversary that just observes timing patterns. Unfortunately active adversaries can break padding schemes by inserting delays and dropping messages. We present a protocol that provides anonymity against an active adversary by using a black-box padding scheme that is effective against a passive adversary. Our protocol reduces, in some sense, providing anonymous communication against active attacks to providing a padding scheme against passive attacks. Our analytical results show that anonymity can be made arbitrarily good at the cost of some added latency and required bandwidth. We also perform measurements on the Tor network to estimate the real-world performance of our protocol, showing that the added delay is not excessive.
View Abstract
We consider using trust information to improve the security of onion-routing networks. In particular, we introduce a model of trust in network nodes and use it to design path-selection strategies that minimize the probability that the adversary can successfully perform a correlation attack. We first describe the general case in which onion routers can be assigned arbitrary levels of trust. Selecting a strategy can be formulated in a straightforward way as a linear program, but it is exponential in size. We thus analyze a natural simplification of path selection for this case. More importantly, however, when choosing routes in practice, only a very coarse assessment of trust in specific onion routers is likely to be feasible. Therefore, we focus next on the special case in which there are only two trust levels. For this more practical case we identify three optimal route-selection strategies such that at least one is optimal, depending on the trust levels of the two classes, their size, and the reach of the adversary. This can yield practical input into routing decisions . We set out the relevant parameters and choices for making such decisions.
View Abstract
We perform a probabilistic analysis of onion routing. The analysis is presented in a black-box model of anonymous communication that abstracts the essential properties of onion routing in the presence of an active adversary that controls a portion of the network and knows all a priori distributions on user choices of destination. Our results quantify how much the adversary can gain in identifying users by exploiting knowledge of their probabilistic behavior. In particular, we show that a user u's anonymity is worst either when the other users always choose the destination u is least likely to visit or when the other users always choose the destination u chooses. This worst-case anonymity with an adversary that controls a fraction b of the routers is comparable to the bestcase anonymity against an adversary that controls a fraction sqrt(b).
View Abstract
Tor (the Onion Routing) is an open source, distributed, low-latency anonymity network. This article examines how Tor works, the underlying design philosophy, and some of the challenges in building, deploying, and sustaining a network for anonymous communications.
View Abstract
In this paper we demonstrate how to reduce the overhead and delay of circuit establishment in the Tor anonymizing network by using predistributed Diffie-Hellman values. We eliminate the use of RSA encryption and decryption from circuit setup, and we reduce the number of DH exponentiations vs. the current Tor circuit setup protocol while maintaining immediate forward secrecy. We also describe savings that can be obtained by precomputing during idle cycles values that can be determined before the protocol starts. We introduce the distinction of eventual vs. immediate forward secrecy and present protocols that illustrate the distinction. These protocols are even more efficient in communication and computation than the one we primarily propose, but they provide only eventual forward secrecy. We describe how to reduce the overhead and the complexity of hidden server connections by using our DH-values to implement valet nodes and eliminate the need for rendezvous points as they exist today. We also discuss the security of the new elements and an analysis of efficiency improvements.
View Abstract
Onion routing is a scheme for anonymous communication that is designed for practical use. Until now, however, it has had no formal model and therefore no rigorous analysis of its anonymity guarantees. We give an IO-automata model of an onion-routing protocol and, under possibilistic definitions, characterize the situations in which anonymity and unlinkability are guaranteed.
View Abstract
Location hidden services have received increasing attention as a means to resist censorship and protect the identity of service operators. Research and vulnerability analysis to date has mainly focused on how to locate the hidden service. But while the hiding techniques have improved, almost no progress has been made in increasing the resistance against DoS attacks directly or indirectly on hidden services. In this paper we suggest improvements that should be easy to adopt within the existing hidden service design, improvements that will both reduce vulnerability to DoS attacks and add QoS as a service option. In addition we show how to hide not just the location but the existence of the hidden service from everyone but the users knowing its service address. Not even the public directory servers will know how a private hidden service can be contacted, or know it exists.
View Abstract
Hidden services were deployed on the Tor anonymous communication network in 2004. Announced properties include server resistance to distributed DoS. Both the EFF and Reporters Without Borders have issued guides that describe using hidden services via Tor to protect the safety of dissidents as well as to resist censorship.
We present fast and cheap attacks that reveal the location of a hidden server. Using a single hostile Tor node we have located deployed hidden servers in a matter of minutes. Although we examine hidden services over Tor, our results apply to any client using a variety of anonymity networks. In fact, these are the first actual intersection attacks on any deployed public network: thus confirming general expectations from prior theory and simulation.
We recommend changes to route selection design and implementation for Tor. These changes require no operational increase in network overhead and are simple to make; but they prevent the attacks we have demonstrated. They have been implemented.
View Abstract
Digital watermarking is a technology to hide information in digital media. We extend the digital watermarking technique PhasemarkT, originally developed solely for image authentication, to biometrics to assist in forensic analysis. Using a signature extracted from the Fourier phase of the original image, we hide an encoded signature back into the original image forming a watermarked image. The hiding occurs in the Fourier transform frequency domain. The detection process computes the Fourier transform of the watermarked images, extracts the embedded signature and then correlates it with a calculated signature. Various correlation metrics determine the identity degree of biometric authentication. We show how a composite filter can be used in conjunction with PhasemarkT for robust authentication of fingerprints.
View Abstract
There are many unexpected or unexpectedly difficult obstacles to deploying anonymous communications. Drawing on our experiences deploying Tor (the second-generation onion routing network), we describe social challenges and technical issues that must be faced in building, deploying, and sustaining a scalable, distributed, low-latency anonymity network.
View Abstract
A basic radio-frequency identification (RFID) tag is a small and inexpensive microchip that emits a static identifier in response to a query from a nearby reader. Basic tags of the ``smart-label'' variety are likely to serve as a next-generation replacement for barcodes. This would introduce a strong potential for various forms of privacy infringement, such as invasive physical tracking and inventorying of individuals.
Researchers have proposed several types of external devices of moderate-to-high computational ability that interact with RFID devices with the aim of protecting user privacy. In this paper, we propose a new design principle for a personal RFID-privacy device. We refer to such a device as a REP (RFID Enhancer Proxy).
Briefly stated, a REP assumes the identities of tags and simulates them by proxy. By merit of its greater computing power, the REP can enforce more sophisticated privacy policies than those available in tags. (As a side benefit, it can also provide more flexible and reliable communications in RFID systems.) Previous, similar systems have been vulnerable to a serious attack, namely malicious exchange of data between RFID tags. An important contribution of our proposal is a technique that helps prevent this attack, even when tags do not have access-control features.
View Abstract
Properties of the difference of two sums containing products of binomial coefficients and their logarithms which arise in the application of Shannon's information theory to a certain class of covert channels are deduced. Some allied consequences of the latter are also recorded.
View Abstract
The simpler situation of collaborating transmitters is used as a bounding result. We also discuss the surprising results of Gaarder and Wolf that feedback can increase capacity, unlike the situation for standard covert channel analysis. This is of importance when dealing with the network scenario.
View Abstract
We propose a correlation-based digital watermarking technique for pattern recognition applications robust image pattern authentication. We hide a phase-based signature of the image back into its Fourier magnitude spectrum in the embedding stage. The detector computes the Fourier transform of the watermarked image and extracts the embedded signature. Authentication performance is measured by a correlation test of the extracted signature and the signature computed from the watermarked image. The quality of the watermarked image is obtained from the peak signal-to-noise ratio metric. We also furnish simulation results to show the robustness of our approach to typical image processing as found in JPEG compression.
View Abstract
We describe our new method for watermarking digital images. Our work is motivated by the study of phase only filters in Fourier optics. In this paper we concentrate on greyscale images, even though our method works for color also. We take the discrete Fourier transform of an image and determine a signature based upon a binary phase-only filter (BPOF). We replace certain frequency magnitudes with this BPOF. This serves as the basis for our watermark. We may also insert additional side information and our method prevents spoofing of the watermark. Our method survives JPEG compression so that the watermark survives to pass various correlation tests. Our watermarking scheme is used for authentication purposes.
View Abstract
Barwise and Seligman proposed a very general qualitative theory of information flow (in distributed systems) while Shannon proposed a very general quantitative theory for communication flow. The two kinds of flow are not synonymous, with information flow being the more general of the two. We synthesize a new theory from these two theories so that the qualitative and quantitative analysis use the same theory structures. The main advantages are (1) Shannon theory gets a more expressive framework within which to operate, (2) Barwise/Seligman theory gets to take advantage of quantitative mechanisms. The resultant theory has direct applications to steganography and covert channels although the development of these applications will appear in a subsequent paper.
View Abstract
We present Tor, a circuit-based low-latency anonymous communication service. This second-generation Onion Routing system addresses limitations in the original design by adding perfect forward secrecy, congestion control, directory servers, integrity checking, configurable exit policies, and a practical design for location-hidden services via rendezvous points. Tor works on the real-world Internet, requires no special privileges or kernel modifications, requires little synchronization or coordination between nodes, and provides a reasonable tradeoff between anonymity, usability, and efficiency. We briefly describe our experiences with an international network of more than 30 nodes. We close with a list of open problems in anonymous communication.
View Abstract
The variety of possible anonymity network topologies has spurred much debate in recent years. In a synchronous batching design, each batch of messages enters the mix network together, and the messages proceed in lockstep through the network. We show that a synchronous batching strategy can be used in various topologies, including a free-route network, in which senders choose paths freely, and a cascade network, in which senders choose from a set of fixed paths. We show that free-route topologies can provide better anonymity as well as better message reliability in the event of partial network failure.
View Abstract
Properties of the difference of two sums containing products of binomial coefficients and their logarithms which arise in the application of Shannon's information theory to a certain class of covert channels are deduced. Some allied consequences of the latter are also recorded.
View Abstract
Traditional methods for evaluating the amount of anonymity afforded by various Mix configurations have depended on either measuring the size of the set of possible senders of a particular message (the anonymity set size), or by measuring the entropy associated with the probability distribution of the messages possible senders. This report explores further in detail an alternative way of assessing the anonymity of a Mix system by considering the capacity of a covert channel from a sender behind the Mix to an observer of the Mix's output. Initial work considered a simple model, where an observer (Eve) was restricted to counting the number of messages leaving a Mix configured as a firewall guarding an enclave with one malicious sender (Alice) and some other naive senders. Here, we consider the case where Eve can distinguish between multiple destinations, and the senders can select to which destination their message (if any) is sent each clock tick.
View Abstract
Traditional methods for evaluating the amount of anonymity afforded by various Mix configurations have depended on either measuring the size of the set of possible senders of a particular message (the anonymity set size), or by measuring the entropy associated with the probability distribution of the messages possible senders. This paper explores further an alternative way of assessing the anonymity of a Mix system by considering the capacity of a covert channel from a sender behind the Mix to an observer of the Mix's output. Initial work considered a simple model with an observer (Eve) restricted to counting the number of messages leaving a Mix configured as a firewall guarding an enclave with one malicious sender (Alice) and some other naive senders. Here, we consider the case where Eve can distinguish between multiple destinations, and the senders can select to which destination their message (if any) is sent each clock tick.
View Abstract
It is commonplace to note that in surveys people claim to place a high value on privacy while they paradoxically throw away their privacy in exchange for a free hamburger or a two dollar discount on groceries. The usual conclusion is that people do not really value their privacy as they claim to or that they are irrational about the risks they are taking. Similarly it is generally claimed that people will not pay for privacy; the failure of various ventures focused on selling privacy is offered as evidence of this. In this chapter we will debunk these myths. Another myth we will debunk is that identity theft is a privacy problem. In fact it is an authentication problem and a problem of misplaced liability and cost. When these are allocated to those who create them, the problem does not exist. Finally we consider the oft asked question of how much privacy should be given up for security. We find this to be the wrong question. Security of institutions may decrease and infrastructure costs may be increased by a reduction in privacy.
View Abstract
In this paper, we propose to use the randomized response techniques to conduct the data mining computation. Specially, we present a method to build naive Bayesian classifiers from the disguised data. We conduct experiments to compare the accuracy of our classifier with the one built from the original undisguised data. Our results show that although the data are disguised, our method can still achieve fairly high accuracy. We also show how the parameter used in the randomized response techniques affects the accuracy of the results.
View Abstract
In this paper, we study how to conduct sequential pattern mining, which is one of the data mining computations, on private data in the following scenario: Multiple parties, each having a private data set, want to jointly conduct sequential pattern mining. Since no party wants to disclose its private data to other parties, a secure method needs to be provided to make such a computation feasible. We develop a practical solution to the above problem in this paper.
View Abstract
In this paper we show how we can increase the ease of reading and writing security requirements for cryptographic protocols by developing a visual language based on fault trees. We develop such a semantics for a subset of NPATRL, a temporal language used for expressing safety requirements for cryptographic protocols, and show that the subset is sound and complete with respect to the semantics. We also show how the fault trees can be used to improve the presentation of some specifications that we developed in our analysis of the Group Domain of Interpretation (GDOI) protocol.
View Abstract
We present a new approach for protecting sensitive data in a relational table (columns: attributes; rows: records). If sensitive data can be inferred by unauthorized users with non-sensitive data, we have the inference problem. We consider inference as correct classification and approach it with decision tree methods. We present a generalized decision tree method for distributed sensitive data. This method takes in turn each attribute as the class and analyze the corresponding classification error. Attribute values that maximize an integrated error measure are selected for modification. Our analysis shows that modified attribute values can be restored and hence, sensitive data are not securely protected. This result implies that modified values must themselves be subjected to protection. We present methods for this ramified protection problem.
View Abstract
Recently there has been an increasing amount of research in the introduction of cryptographic ideas into discrete methods for cryptographic protocol analysis. This is often done by developing a discrete model and a cryptographic model such that the discrete model can be shown sound with respect to the cryptographic model. In this position paper we talk about some of the other issues in cryptographic protocol analysis that could be addressed with this approach, and propose a hierarchy of models.
View Abstract
Much attention has been paid to the design of languages for the specification of cryptographic protocols. However, the ability to specify their desired behavior correctly is also important; indeed many perceived protocol flaws arise out of a misunderstanding of the protocol's requirements. In this talk we give a brief survey of the history of requirements specification in formal analysis of cryptographic protocols. We outline the main approaches and describe some of the open issues.
View Abstract
A type confusion attack is one in which a principal accepts data of one type as data of another. Although it has been shown by Heather et al. that there are simple formatting conventions that will guarantee that protocols are free from simple type confusions in which fields of one type are substituted for fields of another, it is not clear how well they defend against more complex attacks, or against attacks arising from interaction with protocols that are formatted according to different conventions.
In this paper we show how type confusion attacks can arise in realistic situations even when the types are explicitly defined in at least some of the messages, using examples from our recent analysis of the Group Domain of Interpretation Protocol. We then develop a formal model of types that can capture potential ambiguity of type notation, and outline a procedure for determining whether or not the types of two messages can be confused. This work extends our earlier work on the subject in that it includes an explicit model of attacker and defender and extends the informal model of the type confusion attack in terms of a game between an intruder and a set of honest principals in or earlier work to a more formal model in which actions of intruder and honest principals are described explicitly. This gives us a simpler, more intuitive approach that allows us to calculate probabilities in a more systematic manner, and to compare different intruder strategies and different assumptions about the way in which the protocol is implemented in terms of their effects on type confusio
View Abstract
The history of the application of formal methods to cryptographic protocol analysis spans over twenty years, and recently has been showing signs of new maturity and consolidation. Not only have a number of specialized tools been developed, and general-purpose ones been adapted, but people have begun applying these tools to realistic protocols, in many cases supplying feedback to designers that can be used to improve the protocol's security. In this paper we will describe some of the ongoing work in this area, as well as describe some of the new challenges and the ways in which they are being met.
View Abstract
Although research has been going on in the formal analysis of cryptographic protocols for a number of years, they are only slowly being integrated into the protocol design process. In this paper we describe how we furthered the integration of analysis and design by working closely with the Multicast Security Working Group in the Internet Engineering Task Force on the analysis of a proposed Internet Standard, the Group Domain Of Interpretation (GDOI) Protocol. We describe the challenges that had to be met before the analysis could be successfully completed, and some of the challenges that still remain. Perhaps not surprisingly, some of the most challenging work was in understanding the security requirements for group protocols in general. We give a detailed specification of the requirements for GDOI, describe our formal analysis of the protocol with respect to these requirements, and show how our analysis impacted the development of GDOI.
View Abstract
Although both anonymity and covert channels are part of the larger topic of information hiding, there also exists an intrinsic linkage between anonymity and covert channels. This linkage was illustrated in [1]; however, [1] just scratched the surface of the interplay between covert channels and anonymity, without a formal analysis of the related issues. This paper begins the process of formalizing the linkage between anonymity and covert channels via the study of quasi-anonymous channels. We also discuss and contrast some of the existing formal mathematical models of anonymity.
View Abstract
There have long been threads of investigation into covert channels, and threads of investigation into anonymity, but these two closely related areas of information hiding have not been directly associated. This paper represents an initial inquiry into the relationship between covert channel capacity and anonymity, and poses more questions than it answers. Even this preliminary work has proven difficult, but in this investigation lies the hope of a deeper understanding of the nature of both areas. MIXes have been used for anonymity, where the concern is shielding the identity of the sender or the receiver of a message, or both. Traffic analysis prevention (TAP) methods are used to conceal larger traffic patterns. Here, we are concerned with how much information a sender to a MIX can leak to an eavesdropping outsider, despite the concealment efforts of MIXes acting as firewalls.
View Abstract
This paper considers systems for Traffic Analysis Prevention (TAP) in a theoretical model. It considers TAP based on padding and rerouting of messages and describes the effects each has on the difference between the actual and the observed traffic matrix (TM). The paper introduces an entropy-based approach to the amount of uncertainty a global passive adversary has in determining the actual TM, or alternatively, the probability that the actual TM has a property of interest. Unlike previous work, the focus is on determining the overall amount of anonymity a TAP system can provide, or the amount it can provide for a given cost in padding and rerouting, rather than on the amount of protection afforded particular communications.
View Abstract
This paper proposes a novel scheme that uses robust principal component classifier in intrusion detection problems where the training data may be unsupervised. Assuming that anomalies can be treated as outliers, an intrusion predictive model is constructed from the major and minor principal components of the normal instances. A measure of the difference of an anomaly from the normal instance is the distance in the principal component space. The distance based on the major components that account for 50% of the total variation and the minor components whose eigenvalues less than 0.20 is shown to work well. The experiments with KDD Cup 1999 data demonstrate that the proposed method achieves 98.94% in recall and 97.89% in precision with the false alarm rate 0.92% and outperforms the nearest neighbor method, density-based local outliers (LOF) approach, and the outlier detection algorithm based on Canberra metric.
View Abstract
We consider some common assumptions about the value placed on privacy in society. We observe that: *Contrary to popular accounts, individuals are not obviously irrational in how they value privacy. *Current governmental and economic structures do not properly place the cost of privacy, thus skewing incentives and behavior. *Security of institutions may decrease and infrastructure costs may be increased by a reduction in privacy.
View Abstract
We propose an inference prevention agent as a tool that enables each of the databases in a distributed system to keep track of probabilistic dependencies with other databases and then use that information to help preserve the confidentiality of sensitive data. This is accomplished with minimal sacrifice of the performance and survivability gains that are associated with distributed database systems.
View Abstract
In this paper, we study how to conduct association rule mining, one of the core data mining techniques, on private data in the following scenario: Multiple parties, each having a private data set, want to jointly conduct association rule mining without disclosing their private data to other parties. Because of the interactive nature among parties, developing a secure framework to achieve such a computation is both challenging and desirable. We present a secure framework for multiple parties to conduct privacy-preserving association rule mining.
View Abstract
There have long been threads of investigation into covert channels, and threads of investigation into anonymity, but these two closely related areas of information hiding have not been directly associated. This paper represents an initial inquiry into the relationship between covert channel capacity and anonymity, and poses more questions than it answers. Even this preliminary work has prove difficult, but in this investigation lies the hope of a deeper understanding of the nature of both areas. MIXes have been used for anonymity, where the concern is shielding the identity of the sender or the receiver of a message, or both. In contrast to traffic analysis prevention methods which conceal larger traffic patterns, we are concerned with how much information a sender to a MIX can leak to an eavesdropping outsider, despite the concealment efforts of MIXes acting as firewalls.
View Abstract
Most work on requirements in the area of authentication protocols has concentrated on identifying requirements for the protocol without much consideration of context. Little work has concentrated on assumptions about the environment, for example, the applications that make use of authenticated keys. We will show in this paper how the interaction between a protocol and its environment can have a major effect on a protocol. Specifically we will demonstrate a number of attacks on published and/or widely used protocols that are not feasible against the protocol running in isolation (even with multiple runs) but become feasible in some application environments. We will also discuss the tradeoff between putting constraints on a protocol and putting constraints on the environment in which it operates.
View Abstract
We propose an inference prevention agent as a tool that enables each of the databases in a distributed system to keep track of probabilistic dependencies with other databases and then use that information to help preserve the confidentiality of sensitive data. This is accomplished with minimal sacrifice of the performance and survivability gains that are associated with distributed database systems.
View Abstract
The database inference problem is a challenging and important issue in data privacy. Database inference for distributed systems is an emerging research area. In this paper, we describe our proposed framework and approach to the inference problem for distributed databases.
View Abstract
In this paper, we give a brief review of prevailing transform embedding techniques for information hiding, and we discuss the robustness and detectability of two specific methods. Spatial embedding inserts messages into image pixels. Transform embedding embeds a message by modifying selected frequency coefficients of the cover image. Ideally, the message embedded with transform techniques is more robust to different image processing attacks and more transparent to human visual systems than that of spatial domain techniques. Transform embedding techniques that we are particularly interested in are the Discrete Fourier Transform (DFT), the Discrete Cosine Transform (DCT) and the Discrete Wavelet Transform (DWT). Detection of the hidden message and robust embedding are two of the principle objectives of our information hiding research. We show that a watermarked image that is perceptually invisible in the spatial domain may fail our detectability test. Our approach to detectability is based on DFT domain analysis. Embedding a message under the least significant bits of pixels (LSB embedding) is commonly used. We investigate ways to improve the robustness of LSB embedding and propose a method for protecting embedded data against two specific forms of filtering.
View Abstract
We present a novel approach to the challenging issue of database confidential data protection. We adopt the decision tree framework as our baseline and extend it to cope with databases where the class_label attribute is not specified. We are interested in confidential data that are randomly distributed over different attributes (referred to as multi-dimensional inference). For confidential data protection, our method (referred to as adaptive modification) mitigates inference by evaluating and modifying some, not all, relevant data records. We localize data modification in a decision tree and, instead of exhaustively evaluating all modification possibilities, we select informative data to modify. Our proposed method is effective in protection of confidential data and scalable for handling large databases.
View Abstract
We describe a MIX cascade protocol and a reputation system that together increase the reliability of a network of MIX cascades. In our protocol, MIX nodes periodically generate a communally random seed that, along with their reputations, determines cascade configuration. Nodes send test messages to monitor their cascades. Senders can also demonstrate message decryptions to convince honest cascade members that a cascade is misbehaving. By allowing any node to declare the failure of its own cascade, we eliminate the need for global trusted witnesses.
View Abstract
Reputation is the linchpin of a dynamic and pseudonymous future. In a networked world where individuals interact via anonymous remailers, and where the online services they use are themselves provided by an ever-changing pool of semi-anonymous users, the distinction between pseudonym and identity blurs. In this world, reputation is one of the few tools that can still provide trust -- trust among the users of distributed services, and even the trust necessary to maintain reliability and accountability of these services.
View Abstract
Equational unification can be an effective tool for the analysis of cryptographic protocols. This, for example, is the technique used by the NRL Protocol Analyzer, which uses narrowing to reason about cryptographic operations which can be described in terms of rewrite rules. However, the effectiveness of equational unification in cryptographic protocol analysis has been hampered by the lack of unification algorithms that can be used to reason about some of the more equationally rich algorithms used by many cryptographic systems, such as Diffie-Hellman, group Diffie-Hellman, and blinded signatures. In this paper we attempt to close this gap by providing an algorithm that can be used to reason about protocols that use the Diffie-Hellman and group Diffie-Hellman algorithm.
View Abstract
In this paper we give a brief summary of our experience in using a declarative language, Prolog, to develop an experimental formal analysis tool, the NRL Protocol Analyzer, which was updated and modified over the years to incorporate new theories and techniques. We discuss the benefits of using such an approach, and also some of the downsides.
View Abstract
A type confusion attack is one in which a principal accepts data of one type as data of another. Although it has been shown by Heather et al. that there are simple formatting conventions that will guarantee that protocols are free from simple type confusions in which fields of one type are substituted for fields of another, it is not clear how well they defend against more complex attacks, or against attacks arising from interaction with protocols that are formatted according to different conventions. In this paper we show how type confusion attacks can arise in realistic situations even when the types are explicitly defined in at least some of the messages, using examples from our recent analysis of the Group Domain of Interpretation Protocol. We then develop a formal model of types that can capture potential ambiguity of type notation, and outline a procedure for determining whether or not the types of two messages can be confused. We also discuss some open issues.
View Abstract
In this report we analyze in detail a method of image steganography developed by NRL. Our conclusion is that this method of steganography is undetectable by current pragmatic statistical stego detection techniques, primarily because it alters a very small number of pixels. The small size of the embedded message is the key to the lack of detection, provided that a non-anomalous cover image is used.
View Abstract
At present, "capacity" is the prevailing paradigm for covert channels. With respect to steganography, however, capacity is at best insufficient, In this paper, we propose a new paradigm called "capability" which gauges the effectiveness of a steganographic method. It includes payload carrying ability, detectability, and robustness We also discuss the use of zero-error capacity for channel analysis and demonstrate that a JPEG compressed image always has the potential to carry hidden information.
View Abstract
Steganography and steganalysis of digital images is a cat-and-mouse game. In recent work, Fridrich, Goljan and Du introduced a method that is surprisingly accurate at determining if bitmap images that originated as JPEG files have been altered (and even specifying where and how they were altered), even if only a single bit has been changed. However, steganographic embeddings that encode embedded data in the JPEG coefficients are not detectable by their JPEG compatibility steganalysis. This paper describes a steganographic method that encodes the embedded data in the spatial domain, yet cannot be detected by their steganalysis mechanism. Furthermore, we claim that our method can also be used as a steganographic method on files stored in JPEG format. The method described herein uses a novel, topological approach to embedding. The paper also outlines some extensions to the proposed embedding method.
View Abstract
The literature contains a variety of different mixes, some of which have been used in deployed anonymity systems. We explore their anonymity and message delay properties, and show how to mount active attacks against them by altering the traffic between the mixes. We show that if certain mixes are used, such attacks cannot destroy the anonymity of a particular message completely. We work out the cost of these attacks in terms of the number of messages the attacker must insert into the network and the time he must spend. We discuss advantages and disadvantages of these mixes and the settings in which their use is appropriate. Finally, we look at dummy traffic and SG mixes as other promising ways of protecting against the attacks, point out potential weaknesses in existing designs, and suggest improvements.
View Abstract
One of the central objectives of studying database privacy protection is to protect sensitive information held in a database from being inferred by the general unauthorized database user. In this paper, we present a framework to assist in the formal analysis of the database inference problem. The framework is based on an association network which is composed of a similarity measure and a Bayesian network model.
View Abstract
"Database inference" occurs when unauthorized users infer sensitive information from publicly released data. To protect against such "inference attacks," information that is probabilistically related to sensitive information must be examined and perhaps modified. We introduce a formal schema for database inference analysis, based upon a Bayesian network structure, which identifies critical parameters involved in the inference problem and represents them in a coherent framework.
View Abstract
Although there is a substantial amount of work on formal requirements for two and three-party key distribution protocols, very little has been done on requirements for group protocols. However, since the latter have security requirements that can differ in important but subtle ways, we believe that a rigorous expression of these requirements can be useful in determining whether a given protocol can satisfy an application's needs. In this paper we make a first step in providing a formal understanding of security requirements for group key distribution by using the NPATRL language, a temporal requirement specification language for use with the NRL Protocol Analyzer. We specify the requirements for GDOI, a protocol being proposed as an IETF standard, which we are formally specifying and verifying in cooperation with the MSec working group.
View Abstract
Agent based intrusion detection systems (IDS) have advantages such as scalability, reconfigurability, and survivability. In this paper, we introduce a mobile-agent based IDS, called ABIDE (Agent Based Intrusion Detection Environment). ABIDE is comprised of various types of agents, all of which are mobile, lightweight, and specialized. The most common form of agent is the DMA (Data Mining Agent), which randomly moves around the network and collects information. The DMA then relays the information it has gathered to a DFA (Data Fusion Agent) which assesses the likelihood of intrusion. As we show in this paper, there is a quantifiable relationship between the number of DMA and the probability of detecting an intrusion. We study this relationship and its implications.
View Abstract
The rationale of authentication has been a topic of study for about a decade and a half. First attempts at formal analysis of authentication protocols were not using logics per se, but were certainly logical. Millen's Interrogator was a Prolog based tool specifically designed for authentication protocol analysis that functioned essentially as a special purpose model checker. Kemmerer used the general purpose formal specification language Ina Jo and an accompanying symbolic execution tool Inatest to specify and analyze protocols.
We will focus on logics of authentication, beginning with BAN. However, we will not only be discussing logics per se. We will also be looking at the `rhyme and reason' of authentication, the attempts to formalize and define notions of authentication and to apply these. Thus, we will also be considering the logic of authentication in a broader sense.
We will not discuss (except incidentally) other formal methods that have been applied to authentication. In particular, we will not be describing process algebras, automata, automated tools such as theorem provers or model checkers.
View Abstract
Denial of service is becoming a growing concern. As computer systems communicate more and more with others that they know less and less, they become increasingly vulnerable to hostile intruders who may take advantage of the very protocols intended for the establishment and authentication of communication to tie up resources and disable servers. This paper shows how some principles that have already been used to make cryptographic protocols more resistant to denial of service by trading off the cost to defender against the cost to the attacker can be formalized based on a modification of the Gong-Syverson fail-stop model of cryptographic protocols, and indicates the ways in which existing cryptographic protocol analysis tools could be modified to operate within this formal framework. We also indicate how this framework could be extended to protocols that do not make use of strong authentication.
View Abstract
In this paper we show how we have been using the NRL Protocol Analyzer to analyze the Cliques protocol, a group key distribution protocol based on Group Diffie-Hellman.
View Abstract
The growing interest in the application of formal methods of cryptographic protocol analysis has led to the development of a number of different techniques for generating and describing invariants that are defined in terms of what messages an intruder can and cannot learn. These invariants, which can be used to prove authentication as well as secrecy results, appear to be central to many different tools and techniques. However, since they are usually developed independently for different systems, it is often not easy to see what they have in common with each other, or to tell whether or not they can be used in systems other than the ones for which they were developed. In this paper we attempt to remedy this situation by giving an overview of several of these techniques, discussing their relationships to each other, and developing a simple taxonomy. We also discuss some of the implications for future research.
View Abstract
The history of the application of formal methods to cryptographic protocol analysis spans nearly twenty years, and recently has been showing signs of new maturity and consolidation. A number of specialized tools have been developed, and others have effectively demonstrated that existing general-purpose tools can also be applied to these problems with good results. However, with this better understanding of the field comes new problems that strain against the limits of the existing tools. In this paper we will outline some of these new problem areas, and describe what new research needs to be done to to meet the challenges posed.
View Abstract
We discuss how steganography, in contrast to similar disciplines, requires a new paradigm based upon discontinuities and the absence of noise as a detection deterrent.
View Abstract
It is sometimes necessary for the owner of proprietary data to publicize some of it while keeping the rest as private. For example, when releasing census data or corporate financial information, the release must be conducted in a manner consistent with individual privacy. The process of publicly releasing formerly private data is called downgrading. However, it may be possible to infer unreleased private information from the downgraded public information—the so called inference problem. Here, we discuss some of the design decisions that we have made, and continue to make, concerning our prototype for a high assurance system that evaluates downgrading decisions based upon the amount of private information that may be deduced through inference. Our software system, the Rational Downgrader, is composed of a knowledge-based decision maker to determine the rules that may be inferred, a GUARD to measure the amount of leaked information, and a parsimonious downgrader to modify the initial downgrading decisions. At present, we have restricted the Rational Downgrader to relational databases. Of course, the underlying theories apply to all forms of data. In this paper, we concentrate on design decisions made with the aim of achieving high assurance with respect to an optimality condition
View Abstract
Collecting accurate profile information and protecting an individual's privacy are ordinarily viewed as being at odds. This paper presents mechanisms that protect individual privacy while presenting accurate---indeed authenticated---profile information to servers and merchants. In particular, we give a pseudonym registration scheme and system that enforces unique user registration while separating trust required of registrars, issuers, and validators. This scheme enables the issuance of global unique pseudonyms (GUPs) and attributes enabling practical applications such as authentication of accurate attributes and enforcement of ``one-to-a-customer'' properties. We also present a scheme resilient to even pseudonymous profiling yet preserving the ability of merchants to authenticate the accuracy of information. It is the first mechanism of which the authors are aware to guarantee recent validity for group signatures, and more generally multi-group signatures, thus effectively enabling revocation of all or some of the multi-group certificates held by a principal.
View Abstract
We show that all attacks that can be mounted by a traditional Dolev-Yao intruder against common cryptographic protocols can be enacted by an apparently weaker `Machiavellian' adversary in which compromised principals will not share long-term secrets and will not send arbitrary messages. We also show that a Dolev-Yao adversary composed of multiple compromised principals is equivalent to an adversary consisting of a single dishonest principal who is only willing to produce messages in valid protocol form.
View Abstract
This paper presents a security analysis of Onion Routing, an application independent infrastructure for traffic-analysis-resistant and anonymous Internet connections. It also includes an overview of the current system design, definitions of security goals and new adversary models.
View Abstract
Onion Routing is an infrastructure for private communication over a public network. It provides anonymous connections that are strongly resistant to both eavesdropping and traffic analysis. Thus it hides not only the data being sent, but who is talking to whom. Onion Routing's anonymous connections are bidirectional and near real-time, and can be used anywhere a socket connection can be used. Proxy aware applications, such as web browsing and e-mail, require no modification to use Onion Routing, and do so through a series of proxies. Other applications, such as remote login, can also use the system without modification. Access to an onion routing network can be configured in a variety of ways depending on the needs, policies, and facilities of those connecting. This paper describes some of these access configurations and also provides a basic overview of Onion Routing and comparisons with related work.