14998297
Computationally sound compositional logic for key exchange protocols
We develop a compositional method for proving cryptographically sound security properties of key exchange protocols, based on a symbolic logic that is interpreted over conventional runs of a protocol against a probabilistic polynomial-time attacker. Since reasoning about an unbounded number of runs of a protocol involves induction-like arguments about properties preserved by each run, we formulate a specification of secure key exchange that is closed under general composition with steps that use the key We present formal proof rules based on this game-based condition, and prove that the proof rules are sound over a computational semantics. The proof system is used to establish security of a standard protocol in the computational model
64829873
Secure Protocol Composition
This paper continues the program initiated in [5], towards a derivation system for security protocols. The general idea is that complex protocols can be formally derived, starting from basic security components, using a sequence of refinements and transformations, just like logical proofs are derived starting from axioms, using proof rules and transformations. The claim is that in practice, many protocols are already derived in such a way, but informally. Capturing this practice in a suitable formalism turns out to be a considerable task. The present paper proposes rules for composing security protocols from given security components. In general, security protocols are, of course, not compositional: information revealed by one may interfere with the security of the other. However, annotating protocol steps by pre- and post-conditions, allows secure sequential composition. Establishing that protocol components satisfy each other's invariants allows more general forms of composition, ensuring that the individually secure sub-protocols will not interact insecurely in the composite protocol. The applicability of the method is demonstrated on modular derivations of two standard protocols, together with their simple security properties.
2481740
Compositional analysis of contract signing protocols
We develop a general method for reasoning about contract-signing protocols using a specialized protocol logic. The method is applied to prove properties of the Asokan-Shoup-Waidner and the Garay-Jacobson-MacKenzie protocols. Our method offers certain advantages over previous analysis techniques. First, it is compositional: the security guarantees are proved by combining the independent proofs for the three sub-protocols of which each protocol is comprised. Second, the formal proofs are carried out in a "template" form, which gives us a reusable proof that may be instantiated for the ASW and GJM protocols, as well as for other protocols with the same arrangement of messages. Third, the proofs follow the design intuition. In particular, in proving game-theoretic properties like fairness, we demonstrate that the specific strategy that the protocol designer had in mind works, instead of showing that one exists. Finally, our results hold even when an unbounded number of sessions are executed in parallel.
14006300
Abstraction and refinement in protocol derivation
Protocols may be derived from initial components by composition, refinement, and transformation. Adding function variables to a previous protocol logic, we develop an abstraction-instantiation method for reasoning about a class of protocol refinements. The main idea is to view changes in a protocol as a combination of finding a meaningful "protocol template" that contains function variables in messages, and producing the refined protocol as an instance of the template. Using higher-order protocol logic, we can develop a single proof for all instances of a template. A template can also be instantiated to another template, or a single protocol may be an instance of more than one template, allowing separate protocol properties to be proved modularly. These methods are illustrated using some challenge-response and key exchange protocol templates and an exploration of the design space surrounding JFK (just fast keying) and related protocols from the IKE (Internet key exchange) family, which produces some interesting protocols not previously studied in the open literature.
1971532
A derivation system and compositional logic for security protocols
Many authentication and key exchange protocols are built using an accepted set of standard concepts such as Diffie-Hellman key exchange, nonces to avoid replay, certificates from an accepted authority, and encrypted or signed messages. We propose a general framework for deriving security protocols from simple components, using composition, refinements, and transformations. AS a case study, we examine the structure of a family of key exchange protocols that includes Station-TO-Station (STS), ISO-9798-3, Just Fast Keying (JFK), IKE and related protocols, derving all members of the family from two basic protocols, In order to associate formal proofs with protocol derivations, we extend our previous security protocol logic with preconditions, temporal assertions, composition rules, and Several other improvements. Using the logic, which we prove is sound with respect to the standard symbolic model of protocol execution and attack (the "Dolev-Yao model"), the security properties of the standard signature based Challange- Response protocol and the Diffie-Hellman key exchange protocol are estabilished. The ISO-9798-3 protocol is then proved correct by composing the correctness proofs of these two simple protocols Although our current formal logic is not sufficient to modulary prove security for all of our current protocol derivations. the derivation system provides a framework for further improvements.
38254762
Update-Efficient Data Structures for Dynamic IP Router Tables
11950525
Anonymous publish/subscribe in P2P networks
One of the most important issues to deal with in peer-to-peer networks is how to disseminate information. In this paper, we use a completely new approach to solving the information dissemination problem. Our approach uses the publish/subscribe paradigm. The publish/subscribe method is the most inclusive strategy to establish communication between the information providers (publishers) and the information consumers (subscribers). We give a formal definition of publish/subscribe systems. We then use the publish/subscribe communication paradigm to design deterministic protocols (topic and content-based) for peer-to-peer networks. Our protocols are designed on top of an innovative information dissemination scheme, and can cope with the anonymity and mobility of both publishers and subscribers, weak-connectivity, and polarization, which are some of the characteristics of peer-to-peer networks. Moreover, in our solutions, every node could play a role of both publisher and subscriber The algorithms are designed completely independent of the underlying routing substrates. The key advantage of our protocols is that they are scalable without additional re-organization cost. To the best of our knowledge, this is the first time the content-based subscription has been addressed in peer-to-peer networks.
14845392
Internet-Scale Storage Systems under Churn -- A Study of the Steady-State using Markov Models
Content storage in a distributed collaborative environment uses redundancy for better resilience and thus provides good availability and durability. In a peer-to-peer environment, where peers continuously leave and rejoin the network, various lazy strategies can be employed to maintain a minimal redundancy of stored content in the system. Existing static resilience analyses fail to capture in detail the system's behavior over time, particularly the probability mass function of the actual available redundancy, since it ignores the crucial interplay between churn and maintenance operations, and looks only at the average system property. We perform a Markovian time-evolution analysis of the system specified by probability mass function of each possible system state, and establish that given a fixed rate of churn and a specific maintenance strategy, the system operates in a corresponding steady-state (dynamic equilibrium). Understanding the behavior of the system under such a dynamic equilibrium is a fundamental ingredient to precisely evaluate analytically the system's performance and availability as well as to determine the required operational maintenance cost. We also propose a new randomized variant of a lazy-maintenance scheme which has significant performance benefits in comparison to the existing deterministic procrastination based maintenance. We demonstrate the use of our analysis methodology in comparing performance of maintenance schemes using the examples of the new maintenance scheme we propose and the erstwhile best known existing lazy maintenance scheme. The comparative study shows that our randomized lazy maintenance strategy has substantially better resilience at same maintenance cost
1427545
Self-stabilizing mutual exclusion using unfair distributed scheduler
A self-stabilizing algorithm, regardless of the initial system state, converges infinite time to a set of states that satisfy a legitimacy predicate without the need for explicit exception handler of backward recovery. Mutual exclusion is fundamental in the area of distributed computing, by serializing the accesses to a common shared resource. All existing probabilistic self-stabilizing mutual exclusion algorithms designed to work under an unfair distributed scheduler suffer from the following common drawback: Once stabilized, there exists no upper bound of time between two executions of the critical section at a given node. We present the first probabilistic self-stabilizing algorithm that guarantees such a bound (O(n/sup 3/), where n is the network size) while working using an unfair distributed scheduler. As the scheduling adversary gets weaker the bound gets better. Our algorithm works in an anonymous unidirectional ring of any size and has a O(n/sup 3/) expected stabilization time.
9624059
Publish/subscribe scheme for mobile networks
The information dissemination in mobile networks is an important but complex and challenging problem. Designing suitable communication primitives for these systems is critical. One of these primitives is the publish/subscribe paradigm. The publish/subscribe is a strategy to establish communication between the information providers (publishers) and information consumers (subscribers) in a distributed system. Our work focuses on an appropriate distributed infrastructure suitable for a scalable implementation of a publish/subscribe system. We present a formal model which is adapted for the peer-based particular subscription criteria of publish/subscribe systems. Moreover, we propose a general deterministic information diffusion scheme for mobile systems. The three main features of our communication scheme are the following: First, our scheme is well-adapted to scalable systems without compromising any subscription criteria or network reorganization. Second, we maintain the anonymity of the distributed system --- in order to maintain the network structure, we need only local information. Third, our solution is fully decentralized and modular, thus making it appropriate for practical implementations.