PKI schemes provide a critical foundation for applied cryptographic protocols. However, there are no rigorous security specifications for realistic PKI schemes, and therefore, no PKI schemes were proven secure. Cryptographic systems that use PKI are analyzed by adopting overly simplified models of PKI, often simply assuming securely-distributed public keys. This is problematic given the extensive reliance on PKI, the multiple failures of PKI systems, and the complexity of both proposed and deployed systems, which involve complex requirements and models.

Popular instant messaging applications such as WhatsApp and Signal provide end-to-end encryption for billions of users. These applications often rely on a centralized, application-specific server to distribute public keys and relay encrypted messages between the users. As a result, they prevent passive attacks but are vulnerable to some active attacks. A malicious or hacked server can distribute fake keys to users to perform man-in-the-middle or impersonation attacks. While typical secure messaging applications provide a manual method for users to detect these attacks, this burdens users, and studies show it is ineffective in practice. This paper presents KTACA, a completely automated approach for key verification that is oblivious to users and easy to deploy. We motivate KTACA by designing two approaches to automatic key verification. One approach uses client auditing (KTCA) and the second uses anonymous key monitoring (AKM). Both have relatively inferior security properties, leading to KTACA, which combines these approaches to provide the best of both worlds. We provide a security analysis of each defense, identifying which attacks they can automatically detect. We implement the active attacks to demonstrate they are possible, and we also create a prototype implementation of all the defenses to measure their performance and confirm their feasibility. Finally, we discuss the strengths and weaknesses of each defense, the load they impose on clients and service providers, and their deployment considerations.

We investigate an understudied threat: networks of stealthy routers (S-Routers) , relaying messages to a hidden destination . The S-Routers relay communication along a path of multiple short-range, low-energy hops, to avoid remote localization by triangulation. Mobile devices called Interceptors can detect communication by an S-Router, but only when the Interceptor is next to the transmitting S-Router. We examine algorithms for a set of mobile Interceptors to find the destination of the communication relayed by the S-Routers. The algorithms are compared according to the number of communicating rounds before the destination is found, i.e., rounds in which data is transmitted from the source to the destination . We evaluate the algorithms analytically and using simulations, including against a parametric, optimized strategy for the S-Routers. Our main result is an Interceptors algorithm that bounds the expected number of communicating rounds by a term quasilinear in the number of S-Routers. For the case where S-Routers transmit at every round (“continuously”), we present an algorithm that improves this bound.

Cyber physical systems (CPS) typically contain multiple control loops, where the controllers use actuators to trigger a physical process, based on sensor readings. Attackers typically coordinate attack with multiple corrupted devices; defenses often focus on detecting this abnormal communication.

Performing Route Origin Validation (ROV) to filter BGP announcements, which contradict Route Origin Authorizations (ROAs) is critical for protection against BGP prefix hijacks. Recent works quantified ROV enforcing Autonomous Systems (ASes) using control-plane experiments. In this work we show that control-plane experiments do not provide accurate information about ROV-enforcing ASes. We devise data-plane approaches for evaluating ROV in the Internet and perform both control and data-plane experiments using different data acquisition sources. We analyze and correlate the results of our study to identify the number of ASes enforcing ROV, and hence protected with RPKI. We perform simulations with the ROV-enforcing ASes that we identified, and find that their impact on the Internet security against prefix hijacks is negligible. As a countermeasure we provide recommendations how to cope with the main factor hindering wide adoption of ROV.

S.57-63

Extensive standardization and R&D efforts are dedicated to establishing secure interdomain routing. These efforts focus on two mechanisms: origin authentication with RPKI, and path validation with BGPsec. However, while RPKI is finally gaining traction, the adoption of BGPsec seems not even on the horizon due to inherent, possibly insurmountable, obstacles, including the need to replace today's routing infrastructure, the overhead of online cryptography, and meagre benefits in partial deployment. Consequently, secure interdomain routing remains a distant dream. We propose an easily deployable, modest extension to RPKI, called ``path-end validation'', which does not entail replacing/upgrading today's BGP routers nor online cryptographic operations. We show, through rigorous security analyses and extensive simulations on empirically-derived datasets, that path-end validation yields significant security benefits even in very limited partial adoption. We present an open-source, readily deployable prototype implementation of path-end validation.

We present the malicious CAPTCHA attack, allowing a rogue website to trick users into unknowingly disclosing their private information. The rogue site displays the private information to the user in obfuscated manner, as if it is a CAPTCHA challenge; the user is unaware that solving the CAPTCHA, results in disclosing private information. This circumvents the Same Origin Policy (SOP), whose goal is to prevent access by rogue sites to private information, by exploiting the fact that many websites allow display of private information (to the user), upon requests from any (even rogue) website. Information so disclosed includes name, phone number, email and physical addresses, search history, preferences, partial credit card numbers, and more. The vulnerability is common and the attack works for many popular sites, including nine out of the ten most popular websites. We evaluated the attack using IRB-approved, ethical user experiments.

We identify the threat of cross-site framing attacks, which involves planting false evidence that incriminates computer users, without requiring access to their computer. We further show that a variety of framing-evidence can be planted using only modest framing-attacker capabilities. The attacker can plant evidence in both the logs of popular reputable sites and in the computer of the victim, without requiring client-side malware and without leaving traces.

Cross-site search (XS-search) attacks circumvent the same-origin policy and extract sensitive information, by using the time it takes for the browser to receive responses to search queries. This side-channel is usually considered impractical, due to the limited attack duration and high variability of delays. This may be true for naive XS-search attacks; however, we show that the use of better tools facilitates effective XS-search attacks, exposing information efficiently and precisely.

Extensive standardization and R&D efforts are dedicated to establishing secure interdomain routing. These efforts focus on two complementary mechanisms: origin authentication with RPKI, and path validation with BGPsec. However, while RPKI is finally gaining traction, the adoption of BGPsec seems not even on the horizon. This is due to inherent, possibly insurmountable, obstacles, including the need to replace today's routing infrastructure, meagre benefits in partial deployment and online cryptography.

We present the first defence against DNS-amplification DoS attacks, which is compatible with the common DNS servers configurations and with the (important standard) DNSSEC. We show that the proposed DNS-authentication system is efficient, and effectively prevents DNS-based amplification DoS attacks abusing DNS name servers. We present a game-theoretic model and analysis, predicting a wide-spread adoption of our design, sufficient to reduce the threat of DNS amplification DoS attacks. To further reduce costs and provide additional defences for DNS servers, we show how to deploy our design as a cloud based service.

We propose a transport layer cipher-suite negotiation mechanism for DNSSEC standard, allowing name-servers to send responses containing only the keys and signatures that correspond to the cipher-suite option negotiated with the resolver, rather than sending all the signatures and keys (as is done currently).

We present practical off-path TCP injection attacks for connections between current, nonbuggy browsers and Web servers. The attacks allow Web-cache poisoning with malicious objects such as spoofed Web pages and scripts; these objects can be cached for a long period of time, exposing any user of that cache to cross-site scripting , cross-site request forgery , and phishing attacks. In contrast to previous TCP injection attacks, we do not require MitM capabilities or malware running on the client machine. Instead, our attacks rely on a weaker assumption, that the user only enters a malicious Web site, but does not download or install any application. Our attacks exploit subtle details of the TCP and HTTP specifications, and features of legitimate (and very common) browser implementations. An empirical evaluation of our techniques with current versions of browsers shows that connections with most popular Web sites are vulnerable. We conclude this work with practical client- and server-end defenses against our attacks.

We study covert channels between a MitM attacker, and her MitE 'malware', running within the protected network of a victim organisation, and how to prevent or limit such channels. Our focus is on advanced timing channels, that allow communication between the MitM and MitE, even when hosts inside the protected network are restricted to only communicate to other (local and remote) hosts in the protected network. Furthermore, we assume communication is encrypted with fixed packet size (padding). We show that these do not suffice to prevent covert channels between MitM and MitE; furthermore, we show that even if we restrict communication to a constant rate, e.g., one packet everysecond, communication from MitE to MitM is still possible.We present efficient traffic shapers against covert channels between MitM and MitE. Our solutions preserve efficiency and bounded delay (QoS), while limiting covert traffic leakage, in both directions.

Recent cache poisoning attacks motivate protecting DNS with strong cryptography, by adopting DNSSEC, rather than with challenge-response 'defenses'. We discuss the state of DNSSEC deployment and obstacles to adoption. We then present an overview of challenges and potential pitfalls of DNSSEC, including: Incremental Deployment: we review deployment status of DNSSEC, and discuss potential for increased vulnerability due to popular practices of incremental deployment, and provide recommendations. Long DNSSEC Responses; Long DNS responses are vulnerable to attacks, we review cache poisoning attack on fragmented DNS responses, and discuss mitigations; Trust Model of DNS: we review the trust model of DNS and show that it may not be aligned with the security model of DNSSEC. We discuss using trust anchor repositories (TARs) to mitigate the trust problem. TARs were proposed to allow transition to DNSSEC and to provide security for early adopters.

We present a new technique, which we call socket overloading, that we apply for off-path attacks on DNS. Socket overloading consists of short, low-rate, bursts of inbound packets, sent by off-path attacker to a victim host. Socket overloading exploits the priority assigned by the kernel to hardware interrupts, and enables an off-path attacker to illicit a side-channel on client hosts, which can be applied to circumvent source port and name server randomisation. Both port and name server randomisation are popular and standardised defenses, recommended in [RFC5452], against attacks by off-path adversaries. We show how to apply socket overloading for DNS cache poisoning and name server pinning against popular systems that support algorithms recommended in [RFC6056] and [RFC4097] respectively.

We present a practical off-path TCP-injection attack for connections between current, non-buggy browsers and web-servers. The attack allows web-cache poisoning with malicious objects; these objects can be cached for long time period, exposing any user of that cache to XSS, CSRF and phishing attacks.

We present the results of the first long-term user study of site-based login mechanisms which force and train users to login safely. We found that interactive site-identifying images received 70% detection rates, which is significantly better than the results received by the typical login ceremony and with passive defense indicators [in: CHI'06: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, ACM, New York, 2006, pp. 601–610; Computers & Security 28(1,2) (2009), 63–71; in: SP'07: Proceedings of the 2007 IEEE Symposium on Security and Privacy, IEEE Computer Society, Washington, 2007, pp. 51–65]. We also found that combining login bookmarks with interactive images and ‘non-working’ buttons/links achieved the best detection rates (82%) and overall resistance rates (93%). We also present WAPP (Web Application Phishing-Protection), an effective server-side solution which combines the login bookmark and the interactive custom image indicators. WAPP provides two-factor and two-sided authentication.

We show that fragmented IPv4 and IPv6 traffic is vulnerable to effective interception and denial-of-service (DoS) attacks by an off-path attacker. Specifically, we demonstrate a weak attacker intercepting more than 80% of the data between peers and causing over 94% loss rate. We show that our attacks are practical through experimental validation on popular industrial and open-source products, with realistic network setups that involve NAT or tunneling and include concurrent legitimate traffic as well as packet losses. The interception attack requires a zombie agent behind the same NAT or tunnel-gateway as the victim destination; the DoS attack only requires a puppet agent, that is, a sandboxed applet or script running in web-browser context. The complexity of our attacks depends on the predictability of the IP Identification (ID) field which is typically implemented as one or multiple counters, as allowed and recommended by the IP specifications. The attacks are much simpler and more efficient for implementations, such as Windows, which use one ID counter for all destinations. Therefore, much of our focus is on presenting effective attacks for implementations, such as Linux, which use per-destination ID counters. We present practical defenses for the attacks presented in this article, the defenses can be deployed on network firewalls without changes to hosts or operating system kernel.

We show efficient, practical (server-aided) securetwo-party computation protocols ensuring privacy, correctnessand fairness in the presence of malicious (Byzantine) faults. Ourrequirements from the server are modest: to ensure privacyand correctness, we only assume offline set-up prior to protocolexecution; and to also ensure fairness, we further assume atrusted-decryption service, providing decryption service usingknown public key. The fairness-ensuring protocol is optimistic, i.e., the decryption service is invoked only in case of faults. Bothassumptions are feasible in practice and formally presented inthe hybrid model. The resulting protocols may be sufficientlyefficient, to allow deployment, in particular for financial appli-cations.

Following to Kaminsky's attack (2008), cachingresolvers were patched with defenses against poisoning. So far, the main improvements were non-cryptographic and easy todeploy (requiring changes only in resolvers). Some of these improvements are widely deployed, and it is believed that they suffice to prevent poisoning, at least by off-path, spoofingattackers. We perform a critical study of the prominent defense mechanisms against poisoning attacks by off-path adversaries. We present weaknesses and limitations, and suggest counter-measures. Our main message is that the DNS infrastructure shouldnot rely on short term, 'easy-to-deploy' defenses, and efforts should be increased towards transition to DNSSEC.

We present Backward Traffic Throttling (BTT), an efficient, decentralized mechanism for congestion and bandwidth-flooding attacks mitigation. Upon congestion, BTT employs three basic mechanisms to throttle excessive traffic, namely: prioritize legitimate flows, shape traffic, and request upstream BTT nodes to similarly prioritize and shape traffic. Flow prioritizing parameters are determined independently by each BTT server, based on typical traffic estimations. BTT is easily deployed: it requires no changes to routers, and does not modify traffic. Instead, BTT configures routers' queuing discipline and traffic shapers. Both simulation and testbed experiments were performed to asses the effectiveness of BTT during distributed denial-of-service (DDoS) attacks. Results show that even limited BTT deployment alleviates attacks damage and allows legitimate TCP traffic to sustain communication, whereas larger deployments maintain larger portions of the original bandwidth.

We present LOT, a lightweight plug and play secure tunneling protocol deployed at network gateways. Two communicating gateways, A and B, running LOT would automatically detect each other and establish an efficient tunnel, securing communication between them. LOT tunnels allow A to discard spoofed packets that specify source addresses in B’s network and vice versa. This helps to mitigate many attacks, including DNS poisoning, network scans, and most notably (Distributed) Denial of Service (DoS). LOT tunnels provide several additional defenses against DoS attacks. Specifically, since packets received from LOT-protected networks cannot be spoofed, LOT gateways implement quotas, identifying and blocking packet floods from specific networks. Furthermore, a receiving LOT gateway (e.g., B) can send the quota assigned to each tunnel to the peer gateway (A), which can then enforce near-source quotas, reducing waste and congestion by filtering excessive traffic before it leaves the source network. Similarly, LOT tunnels facilitate near-source filtering, where the sending gateway discards packets based on filtering rules defined by the destination gateway. LOT gateways also implement an intergateway congestion detection mechanism, allowing sending gateways to detect when their packets get dropped before reaching the destination gateway and to perform appropriate near-source filtering to block the congesting traffic; this helps against DoS attacks on the backbone connecting the two gateways. LOT is practical: it is easy to manage (plug and play, requires no coordination between gateways), deployed incrementally at edge gateways (not at hosts and core routers), and has negligible overhead in terms of bandwidth and processing, as we validate experimentally. LOT storage requirements are also modest.

We present QoSoDoS, a protocol that ensures QoS over a DoS-prone (Best-Effort) network. QoSoDoS ensures timely delivery of time sensitive messages over unreliable network, susceptible to high congestion and network flooding DoS attacks. QoSoDoS is based on scheduling multiple transmissions of packets while attempting to minimize overhead and load, and avoiding self-creation of DoS. We present a model and initial empirical results of QoSoDoS implementation. Our results show that under typical scenarios, QoSoDoS can handle high congestion and DoS attacks quite well.

Cryptographic schemes are often designed as a combination of multiple component cryptographic modules. Such a combiner design is robust for a (security) specification if it meets the specification, provided that a sufficient subset of the components meet their specifications. A folklore combiner for encryption is cascade, i.e. [Formula: see text]. We show that cascade is a robust combiner for cryptosystems, under three important indistinguishability specifications: chosen plaintext attack (IND-CPA), non-adaptive chosen ciphertext attack (IND-CCA1), and replayable chosen ciphertext attack (IND-rCCA). We also show that cascade is not robust for the important specifications adaptive CCA (IND-CCA2) and generalized CCA (IND-gCCA). The IND-rCCA and IND-gCCA specifications are closely related, and this is an interesting difference between them. All specifications are defined within. We also analyze few other basic and folklore combiners. In particular, we show that the following are robust combiners: the parallel combiner [Formula: see text] for one-way functions, the XOR-input combiner [Formula: see text] for cryptosystems, and the copy combiner [Formula: see text] for integrity tasks such as Message Authentication Codes (MAC) and signature schemes. Cascade is also robust for the hiding property of commitment schemes, and the copy combiner is robust for the binding property, but neither is a robust combiner for both properties. We present (new) robust combiners for commitment schemes; these new combiners can be viewed as a composition of the cascade and the copy combiners. Our combiners are simple, efficient and practical.

We present an empirical study of the resistance of several protocols to denial of service (DoS) attacks on client-server communication. We show that protocols that use authentication alone, e.g., IPSec, provide protection to some extent, but are still susceptible to DoS attacks, even when the network is not congested. In contrast, a protocol that uses a changing filtering identifier (FI) is usually immune to DoS attacks, as long as the network itself is not congested. This approach is called FI hopping. We build and experiment with two prototype implementations of FI hopping. One implementation is a modification of IPSec in a Linux kernel, and a second implementation comes as an NDIS hook driver on a Windows machine. We present results of experiments in which client-server communication is subject to a DoS-attack. Our measurements illustrate that FI hopping withstands severe DoS attacks without hampering the client-server communication. Moreover, our implementations show that FI hopping is simple, practical, and easy to deploy.

In spite of the use of standard Web security measures (SSL/TLS), users enter sensitive information such as passwords into fake Web sites. Such fake sites cause substantial damages to individuals and corporations. In this work, we identify several vulnerabilities of browsers, focusing on security and identification indicators. We present improved security and identification indicators, as we implemented in TrustBar, a browser extension we developed. With TrustBar, users can assign a name or logo to identify SSL/TLS-protected sites; if users did not assign a name or logo, TrustBar identifies protected sites by the name or logo of the site, and by the certificate authority (CA) who identified the site. We present usability experiments which compared TrustBar's indicators to the basic indicators available in most browsers (padlock, URL, and https prefix), and some relevant secure-usability principles.

We consider the problem of overcoming (distributed) denial-of-service (DoS) attacks by realistic adversaries that have knowledge of their attack's successfulness, for example, by observing service performance degradation or by eavesdropping on messages or parts thereof. A solution for this problem in a high-speed network environment necessitates lightweight mechanisms for differentiating between valid traffic and the attacker's packets. The main challenge in presenting such a solution is to exploit existing packet-filtering mechanisms in a way that allows fast processing of packets but is complex enough so that the attacker cannot efficiently craft packets that pass the filters. We show a protocol that mitigates DoS attacks by adversaries that can eavesdrop and (with some delay) adapt their attacks accordingly. The protocol uses only available efficient packet-filtering mechanisms based mainly on addresses and port numbers. Our protocol avoids the use of fixed ports and instead performs "pseudorandom port hopping." We model the underlying packet-filtering services and define measures for the capabilities of the adversary and for the success rate of the protocol. Using these, we provide a novel rigorous analysis of the impact of DoS on an end-to-end protocol and show that our protocol provides effective DoS prevention for realistic attack and deployment scenarios.

We present a convergence-function based clock synchronization algorithm, which is simple, efficient and fault-tolerant. The algorithm is tolerant of failures and allows recoveries, as long as less than a third of the processors are faulty 'at the same time'. Arbitrary (Byzantine) faults are tolerated, without requiring awareness of failure or recovery. In contrast, previous clock synchronization algorithms limited the total number of faults throughout the execution, which is not realistic, or assumed fault detection.

The Internet enables connectivity between many strangers: entities that don't know each other. We present the Trust Policy Language (TPL), used to define the mapping of strangers to predefined business roles, based on certificates issued by third parties. TPL is expressive enough to allow complex policies, e.g. non-monotone (negative) certificates, while being simple enough to allow automated policy checking and processing. Issuers of certificates are either known in advance, or provide sufficient certificates to be considered a trusted authority according to the policy. This allows bottom-up, "grass roots" buildup of trust, as in the real world. We extend, rather than replace, existing role based access control mechanisms. This provides a simple, modular architecture and easy migration from existing systems. Our system automatically collects missing certificates from peer servers. In particular this allows use of standard browsers, which pass only one certificate to the server. We describe our implementation, which can be used as an extension of a Web server or as a separate server with interface to applications.

This paper discusses the design, implementation, and deployment of a secure and practical payment system for electronic commerce on the Internet. The system is based on the iKP family of protocols-(i=1,2,3)-developed at IBM Research. The protocols implement credit card-based transactions between buyers and merchants while the existing financial network is used for payment clearing and authorization. The protocols are extensible and can be readily applied to other account-based payment models, such as debit cards. They are based on careful and minimal use of public-key cryptography, and can be implemented in either software or hardware. Individual protocols differ in both complexity and degree of security. In addition to being both a precursor and a direct ancestor of the well-known SET standard, iKP-based payment systems have been in continuous operation on the Internet since mid-1996. This longevity-as well as the security and relative simplicity of the underlying mechanisms-makes the iKP experience unique. For this reason, this paper also reports on, and addresses, a number of practical issues arising in the course of implementation and real-world deployment of a secure payment system.

In most communication networks, pairs of processors communicate by sending messages over a path connecting them. We present communication-efficient protocols that quickly detect and locate any failure along the path. Whenever there is excessive delay in forwarding messages along the path, the protocols detect a failure (even when the delay is caused by maliciously programmed processors). The protocols ensure optimal time for either message delivery or failure detection. We observe that the actual delivery time $\delta$ of a message over a link is usually much smaller than the a priori known upper bound D on that delivery time. The main contribution of this paper is the way to model and take advantage of this observation. We introduce the notion of asynchronously early-terminating protocols, as well as protocols that are asynchronously early-terminating, i.e., time optimal in both worst case and typical cases. More precisely, we present a time complexity measure according to which one evaluates protocols both in terms of D and $\delta$. We observe that asynchronously early termination is a form of competitiveness. The protocols presented here are asynchronously early terminating since they are time optimal both in terms of D and of $\delta$. Previous communication-efficient solutions were slow in the case where $\delta \ll D$. We observe that this is the most typical case. It is suggested that the time complexity measure introduced, as well as the notion of asynchronously early-terminating, can be useful when evaluating protocols for other tasks in communication networks. The model introduced can be a useful step towards a formal analysis of real-time systems. Our protocols have O(n log n) worst-case communication complexity. We show that this is the best possible for protocols that send immediately any acknowledgment they ever send. Then we show an early-terminating protocol which uses timing and delay to reduce the communication complexity in the typical executions where the number of failures is small and $\delta \ll D$. In such executions, its message complexity is linear, as is the complexity of nonfault tolerant protocols.

Existing security mechanisms focus on prevention of penetrations, detection of a penetration and (manual) recovery tools Indeed attackers focus their penetration efforts on breaking into critical modules, and on avoiding detection of the attack. As a result, security tools and procedures may cause the attackers to lose control over a specific module (computer, account), since the attacker would rather lose control than risk detection of the attack. While controlling the module, attacker may learn critical secret information or modify the module that make it much easier for the attacker to regain control over that module later. Recent results in cryptography give some hope of improving this situation; they show that many fundamental security tasks can be achieved with proactive security. Proactive security does not assume that there is any module completely secure against penetration Instead, we assume that at any given time period (day, week,.), a sufficient number of the modules in the system are secure (not penetrated). The results obtained so far include some of the most important cryptographic primitives such as signatures, secret sharing, and secure communication However, there was no usable implementation, and several critical issues (for actual use) were not addressed

Existing technology and standards allow the creation of threedimensional, virtual-reality browsing experience.Such an interface may be more attractive and natural (at least to some).In particular, with the increase in electronic commerce, the creation of virtual reality stores and shopping malls seems of potential value.However, there are substantial challenges in the use of existing virtual reality tools to create any large space, in particular a store or a shopping mall.The main challenges are the substantial size of the representation of the space (communication and processing overhead), difficulties of navigation using typical UI devices, and support for interconnecting separately designed spaces (stores) into one continuous virtual space (mall).We present an approach to address these challenges, based on limiting the spaces to a modular collection of basic architectural elements such as rooms and hallways.We describe our implementation of virtual-reality, three-dimensional e-commerce, and the VR Commerce toolkit, implemented using standard VRML and Java.VRCommerce is an integrated solution for creation, online operation and navigation in three dimensional malls and stores.It enables continuous navigation between separately designed and managed stores and incremental loading of spaces and objects as needed.Furthermore, VRCommerce offers simplified navigation with less decision making via a two-dimensional `mall directory map` and automated walk modes.

Emerging applications like electronic commerce and secure communications over open networks have made clear the fundamental role of public key cryptography as a unique enabler for world-wide scale security solutions. On the other hand, these solutions clearly expose the fact that the protection of private keys is a security bottleneck in these sensitive applications. This problem is further worsened in the cases where a single and unchanged private key must be kept secret for very long time (such is the case of certification authority keys, bank and e-cash keys, etc.). One crucial defense against exposure of private keys is offered by threshold cryptography where the private key functions (like signatures or decryption) are distributed among several parties such that a predetermined number of parties must cooperate in order to correctly perform these operations. This protects keys from any single point of failure. An attacker needs to break into a multiplicity of locations before it c...

We study the problem of maintaining authenticated communication over untrusted communication channels, in a scenario where the communicating parties may be occasionally and repeatedly broken into for limited periods of time.Once a party is broken into, its cryptographic keys are exposed and perhaps modified.We describe a mechanism that allows a party whose security has keen compromised to regain its ability to communicate in an authenticated way.The contribution of this paper is twofold.First we present a mathematical model for analyzing this scenario, and exhibit various properties and parameters of this model.Next we describe a practically-appealing protocol which enables parties to maintain authenticated communication in the presence of such a powerful adversary.For this protocol we use a variation of the proactive distributed signature schemes which were recently described by Herzberg et al.Although these schemes are designed for a model where authenticated communication and broadcast primitives are available, we show how they can be modified to work in our model, where no such primitives are available a-priori.We also present a new proactive distributed signature scheme with improved round and communication complexities.

The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. Clock synchronization algorithms are presented for a large family of delay assumptions. Our algorithms are modular and consist of three major components. The first component holds for any type of delay assumptions; the second component holds for a large, natural family of local delay assumptions; the third component must be tailored for each specific delay assumption. Optimal clock synchronization algorithms are derived for several types of delay assumptions by appropriately tuning the third component. The delay assumptions include lower and upper delay bounds, no bounds at all, and bounds on the difference of the delay in opposite directions. In addition, our model handles systems where some processors are connected by broadcast networks in which every message arrives at all the processors at approximately the same time. A composition theorem allows combinations of different assumptions for different links or even for the same link; such mixtures are common in practice. Our results achieve the best possible precision in each execution. This notion of optimality is stronger than the more common notion of worst-case optimality. The new notion of optimality applies to systems where the worst-case behavior of any clock synchronization algorithm is inherently unbounded.

No abstract available.

An essential function for achieving security in computer networks is reliable authentication of communicating parties and network components. Such authentication typically relies on exchanges of cryptographic messages between the involved parties, which in turn implies that these parties be able to acquire shared secret keys or certified public keys. Provision of authentication and key distribution functions in the primitive and resource-constrained environments of low-function networking mechanisms, portable, or wireless devices presents challenges in terms of resource usage, system management, ease of use, efficiency, and flexibility that are beyond the capabilities of previous designs such as Kerberos or X.509. This paper presents a family of light-weight authentication and key distribution protocols suitable for use in the low layers of network architectures. All the protocols are built around a common two-way authentication protocol. The paper argues that key distribution may require substantially different approaches in different network environments and shows that the proposed family of protocols offers a flexible palette of compatible solutions addressing many different networking scenarios. The mechanisms are minimal in cryptographic processing and message size, yet they are strong enough to meet the needs of secure key distribution for network entity authentication. The protocols presented have been implemented as part of comprehensive security subsystem prototype called KryptoKnight.>

In this paper we formulate the problem of Video on Demand (VOD) from a resource allocation perspective. In particular, we introduce the decision element into a movie vending environment, which complements the current approaches. In contrast with more the traditional resource allocation problems (such as machine scheduling and call control), the problem possesses the distinctive batching property, which stands for the feasibility of several requests being served by one resource (channel). We investigate the problem in an on-line fashion, namely, having to accept or reject a request for a movie without the knowledge of future requests. We show upper and lower bounds on the competitive ratio of deterministic on-line movie scheduling algorithms for a variety of scenarios (an algorithm is called competitive if it performs, up to a constant factor, as well as its off-line, clairvoyant counterparts for the same problem). In particular, for the natural case of refusal by choice with delayed notification, we present a class of algorithms that exhibit, under certain conditions, an asymptotically optimal behavior.

The problem of achieving optimal clock synchronization in a communication network with arbitrary topology and perfect clocks (that do not drift) is studied. Clock synchronization algorithms are presented for a large family of delay assumptions. Our algorithms are modular and consist of three major components. The first component holds for any type of delay assumptions; the second component holds for a large, natural family of local delay assumptions; the third component has to be tailored for each specific delay assumption. Optimal clock synchronization algorithms are derived for several types of delay assumptions by appropriately tuning the third component. The delay assumptions include lower and upper delay bounds, no bounds at all, and bounds on the difference of the delay in opposite directions. In addition, our model handles systems where some processors are connected by broadcast networks in which every message arrives to all processors at approximately the same time. A composition theorem allows combinations of different assumptions for different lins or even for the same link; such mixtures are common in practice. Our results acheive the best possible precision in each execution. This notion of optimality is stronger than the more common notion of worst case optimality. The new notion of optimality applied to systems where the worst case behavior of any clock synchronization algorithm is inherently unbounded.

Most existing designs for two-way cryptographic authentication protocols suffer from one or more limitations. Among other things, they require synchronization of local clocks, they are subject to export restrictions because of the way they use cryptographic functions, and they are not amenable to use in lower layers of network protocols because of the size and complexity of messages they use. Designing suitable cryptographic protocols that cater to large and dynamic network communities but do not suffer from these problems presents substantial problems. It is shown how a few simple protocols, including one proposed by ISO, can easily be broken, and properties that authentication protocols should exhibit are derived. A methodology for systematically building and testing the security of a family of cryptographic two-way authentication protocols that are as simple as possible yet resistant to a wide class of attacks, efficient, easy to implement and use, and amenable to many different networking environments is described. Examples of protocols of that family that presents various advantages in specific distributed system scenarios are discussed.>

We analyze and improve the fault tolerance of practical, efficient end to end communication schemes.We concentrate on connection-based source routing schemes, used in most existing wide-area networks, Formalizing the notion of MTBF.A crash-tolerant, self-stabilized connection pro tocol with bounded storage and messages.

We present a quantitative approach to dynamic networks.Dynamic networks, extensively studied in the last decade, are asynchronous networks with arbitrary topology, in which links and processors repeatedly fail and recover.Loosely speaking, we quantify the reliability of a link at a given moment as the time since the link last recovered.This quantitative definition allows us to iuvestigate protocols that either assume a certain amount of reliability, or provide service only to sufficiently reliable parts of the network.There are several tasks which cannot be solved efficiently when defined in the known (qualitative)approaches, but may be solved efliciently using the new quantitative definitions.We demonstrate this on the broodcast task.Broadcast is basically an order preserving transmission of a sequence of messages from a source processor to all other processors.Every processor which satisfies some fairness condition should accept the messages.This requires unbounded resources, if the fairness is defined using the known (qualitative) approaches.Hence, we give a new

We present a protocol for reliable communication between two processors via an unreliable, and possibly even malicious, communication media.Reliable communication means that all messages are accepted in the same order as sent, with no modifications, omissions, insertions or duplications.Our protocol is resilient to processor crashes (in which the entire memory of the processor is erased), and duplication and reordering on the link.

Article Fast isolation of arbitrary forwarding faults Share on Authors: A. Herzberg Department of Computer Science, Technion, Haifa, Israel Department of Computer Science, Technion, Haifa, IsraelView Profile , S. Kutten IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NY IBM T.J. Watson Research Center, P.O. Box 704, Yorktown Heights, NYView Profile Authors Info & Claims PODC '89: Proceedings of the eighth annual ACM Symposium on Principles of distributed computingJune 1989 Pages 339–353https://doi.org/10.1145/72981.73006Published:01 June 1989 11citation175DownloadsMetricsTotal Citations11Total Downloads175Last 12 Months4Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

One of the overwhelming problems that software producers must contend with is the unauthorized use and distribution of their products. Copyright laws concerning software are rarely enforced, thereby causing major losses to the software companies. Technical means of protecting software from illegal duplication are required, but the available means are imperfect. We present protocols that enable software protection, without causing substantial overhead in distribution and maintenance. The protocols may be implemented by a conventional cryptosystem, such as the DES, or by a public key cryptosystem, such as the RSA. Both implementations are proved to satisfy required security criteria.