We present the first formally-verified Internet router, which is part of the SCION Internet architecture. SCION routers run a cryptographic protocol for secure packet forwarding in an adversarial environment. We verify both the protocol's network-wide security properties and the low-level properties of its implementation. Namely, we develop a series of protocol models by refinement in Isabelle/HOL and we use an automated program verifier to prove that the router's Go code satisfies crash freedom, freedom from data races, and adheres to the most concrete model in our series of refinements. Both verification efforts are soundly linked together.

Measuring the frequency of items in data streams is a relevant and wide-spread problem in stream analysis and Internet traffic monitoring. This paper studies the problem of sketch-based frequency estimation from a Bayesian statistics point of view which captures uncertainties regarding the frequencies of items in a more flexible and quantitative way compared to the state of the art. We design and implement, based on Markov chain Monte Carlo, a Bayesian frequency estimation sketch that provides both state of the art accuracy, as well as greater functionality compared to other sketches such as confidence bounds for arbitrary levels, and error-function aware frequency estimates. In our theoretical work we derive information-theory related equations such as the expected information gain of a sketch, as well as the optimal least-squares Bayesian frequency estimator. In benchmarks comparing the state of the art, the proposed method achieves the lowest absolute error across all real world data streams, as well as outperforming all sketches on 4 out of 5 metrics on synthetic data. We also show that our method can provide, for multiple confidence levels simultaneously, good confidence levels on both synthetic as well as real data.

Reducing our society's energy demand is critical to address the sustainability challenge. While the Internet currently accounts for 1–-1.5% of global electricity consumption and continues to grow, the energy demands of one of its core components---routers---remain poorly understood. The available power data is limited and not fine-grained enough, offering little actionable insight into strategies for effectively reducing the Internet's energy consumption.

Path-aware networking (PAN) enables endpoints to locally select end-to-end network paths based on path properties. This approach contrasts with the traditional Internet architecture, where routers determine the next hop towards the destination based on the routing information provided by the Border Gateway Protocol (BGP). By providing this additional transparency and control, PAN opens up opportunities to optimize path selection, with the potential to enhance network performance and user experience metrics. In this paper, we evaluate the potential benefits of PAN for enhancing end-to-end performance. We design Polaris, a concrete feedback-driven path optimization mechanism for PAN, and study its impact on Quality of Service (QoS) as compared to current Internet mechanisms. Our extensive simulation results show the viability and effectiveness of Polaris, revealing that it outperforms the current Internet mechanisms by an average of${4 2 \%}$improvement in receiving rate and${8 1 \%}$reduction in median loss, in the presence of background traffic.

With the rapid evolution and diversification of Internet applications, their communication-quality criteria are continuously evolving. To globally optimize communication quality, the Internet's control plane thus needs to optimize inter-domain paths on diverse criteria, and should provide extensibility for adding new criteria or modifying existing ones. However, current inter-domain routing protocols and proposals satisfy these requirements at best to a limited degree.

The SCION Next-Generation Network (NGN) architecture has expanded steadily since 2017, with today 20+ ISPs offering SCION connectivity. In production, IP-to-SCION-to-IP translation by SCION-IP-Gateways (SIGs) is used, such that applications are unaware of the NGN communication. To accelerate innovation and deployments, our aim is to increase the number of native SCION use cases, where the application is fully SCION-aware and optimizes communication across all path choices offered by the network. We set out to achieve two core objectives: (1) facilitating simple native connectivity for applications, and (2) enhancing the scalability of SCION deployment at academic sites.

To realize the long-standing vision of providing quality-of-service (QoS) guarantees on a public Internet, this paper introduces Hummingbird: a lightweight QoS-system that provides fine-grained inter-domain reservations for end hosts.

Numerous vital applications depend on accurately synchronized time, and disruptions can yield severe consequences in terms of safety and security. Yet, establishing cost-efficient and robust synchronization across geographically distributed devices is challenging. Many solutions for global time synchronization require placing trust in a single entity or system, for example in Global Navigation Satellite Systems (G NSSes) or leased infrastructure providers, constituting a single point of failure and often incurring high costs. An alternative, cost-effective solution is to run time synchronization over the Internet. However, this approach faces challenges in achieving (i) precise time synchronization, (ii) robustness to failing, misconfigured, or compromised nodes, and (iii) robustness to congestion-related issues such as volumetric DDoS attacks. Existing proposals mostly attempt to solve challenges (i) and (ii), but none provide robustness against congestion and volumetric DDoS. We address the challenges identified in previous work with Everdeen. Everdeen minimizes costs by running on existing Internet infrastructure and avoids relying on any single en-tity by enabling nodes to mutually synchronize time. The core innovation of Everdeen is its weighted neighbor-based (WNB) synchronization mode, where participants synchronize exclusively with their direct neighbors. Our evaluation shows that Everdeen provides better time synchronization quality at lower communication overhead compared to prior work. It is also considerably more robust against failing, misconfigured, or compromised hosts. Most importantly, we experimentally demonstrate that time synchronization traffic protected with Everdeen is unaffected by network congestion, including vol-umetric DDoS attacks.

In just a few decades, the Internet has evolved from a research prototype to a cyber-physical infrastructure of critical importance for modern society and the global economy. Surprisingly, despite its new role, the survivability of the Internet-its ability to fulfill its mission in the presence of large-scale failures-has received limited attention. We introduce Domino, our initial design and implementation of a testbench tool for stress testing the Internet's routing system, a key element of the critical Internet infrastructure. The simulation-based testbench consists of a comprehensive and flexible framework that allows for the incorporation of diverse survivability metrics, provides a platform for specifying, evaluating, and comparing different topologies of the underlying Internet infrastructure, and can account for modifications to networking protocols and architectural components. By demonstrating the utility of the proposed testbench with a number of illustrative examples, we make a case for stress testing as a viable approach to evaluating the Internet's survivability in the face of evolving challenges.

With the proliferation of blockchain technology in high-value sectors, consensus protocols are becoming critical infrastructures. The rapid innovation cycle in Byzantine fault tolerant (BFT) consensus protocols has culminated in HotStuff, which provides linear message complexity in the partially synchronous setting. To achieve this, HotStuff leverages a leader that collects, aggregates, and broadcasts the messages of other validators. This paper analyzes the security implications of such approaches in practice, from the perspective of liveness and availability.

Popular consumer Internet of Things (IoT) devices provide increasingly diverse sensing and actuation capabilities. Despite their benefits, such devices prompt numerous security concerns. Typically, security is attained at device-level granularity, which relies upon device trustworthiness. However, if a device is compromised (e.g., via remote exploits), this approach fails. To this end, we construct SA4P: Sensing and Actuation as a Privilege, a framework that decouples IoT devices from their physical environment. In SA4P, whenever any software on a device wants to access a sensing or actuation peripheral, it must be authorized to do so. This is achieved by the inclusion of an on-board component, Peripheral Guard (PEG), that physically guards peripherals. Besides providing strong security guarantees, SA4P motivates developers to consider sensing and actuation as valuable resources. SA4P' design is modular, lightweight, and formally verified. It also does not require any hardware modifications for trusted execution environment (TEE)-equipped devices, while imposing only modest changes for other devices.

On today's Internet, end-user debugging is largely limited to simple tools such as ping and traceroute, supplemented by purpose-built services such as bandwidth measurement, and website uptime monitors. Unfortunately, these tools do not provide sufficient data to isolate specific network faults, nor do they give the user results that can be validated by external entities. Furthermore, since networks disparately treat measurement packets, as our empirical results confirm, measurement packets need to be indistinguishable from data packets. In this paper, we argue for a distributed network debugging infrastructure and describe Debuglet, a deployable and incentivized architecture that allows inter-domain network debugging using real data packets and user-defined code, which facilitates accurate and flexible measurements of the network performance experienced by data packets. We implement the Debuglet system, and demonstrate its feasibility by deploying it on a network testbed, evaluating its measurement accuracy, and analyzing its deployment costs.

In just a few decades, the Internet has evolved from a research prototype to a critical infrastructure for modern society and the global economy. Despite its importance, the Internet's survivability amid large-scale failures has received limited attention. We present a testbench design for stress testing the Internet's routing system. This simulation-based framework allows for flexible integration of survivability metrics, evaluation of different topologies, and assessment of protocol and architectural changes. With several illustrative examples, we show the effectiveness of our proposed testbench and make a case for stress testing as a viable approach to evaluating the survivability of inter-domain routing against evolving challenges.

We instigate the study of adversarial congestion in the context of the Domain Name System (DNS). By strategically choking inter-server channels, this new type of DoS attack can disrupt a large user group's access to target DNS servers at a low cost. In reminiscence of classic network congestion control, we propose a DNS congestion control (DCC) framework as a fundamental yet practical mitigation measure for such attacks. With an optimized fair-queuing message scheduler, DCC ensures benign clients fair access to inter-server channels regardless of an attacker's behavior; with a set of extensible anomaly detection and signaling mechanisms, it minimizes collateral damage to innocuous clients. We architect DCC in a non-invasive style so that it can readily augment existing DNS servers. Our prototype evaluation demonstrates that DCC effectively mitigates adversarial congestion while incurring minor performance overheads.

Network flow measurement is an integral part of modern high-speed applications for network security and data-stream processing. However, processing at line rate while maintaining the required data structure within the on-chip memory of the hardware platform is a challenging task for measurement algorithms, especially when accuracy is of primary importance, such as in network security applications. Most of the existing measurement algorithms are no exception to such issues when deployed in high-speed networking environments and are also not tailored for efficient hardware implementation. Sketch-based measurement algorithms minimize the memory requirement and are suitable for high-speed networks but possess a low memory-accuracy trade-off and lack the versatility of individual flow mapping. To address these challenges, we present a hardware-friendly data structure named Sketch-based Pseudo-associative array Architecture (SPArch). SPArch is highly accurate and extremely memory-efficient, making it suitable for network flow measurement and security applications. The parallelism in SPArch ensures minimal and constant memory access cycles. Unlike other sketch architectures, SPArch provides the functionality of individual flow mapping similar to associative arrays, and the optimized version of SPArch allows the organization of counters in multiple buckets based on the flow sizes. An in-depth analysis of SPArch is carried out in this article and implemented SPArch on the Alveo data center accelerator card, demonstrating its suitability for high-speed networks.

Designing access control policies is often expensive and tedious due to the heterogeneous systems, services, and diverse user demands. Although ABAC policy and decision engine creation methods based on machine learning have been proposed, they cannot make good access decisions for applications and situations not envisioned by the decision-makers who provide training examples. It results in over-and under-permissiveness. In this paper, we propose a framework that refines pre-developed policies. It creates a decision engine that makes better decisions than those policies. Inspired by multiple criteria decision theory, our method uses the policy manager's qualitative intentions behind their judgments to guide access decisions so that more benefits are expected. In the evaluation, we prepare a coarse and relatively elaborate policy. We refine the coarse policy to obtain a decision engine that is compared for the similarity in access decisions with the elaborate policy using AUC as a measure. The results show that our method improves the coarse policy by a difference of 12-26% in AUC and outperforms the conventional machine learning methods by a difference of 3-11% in AUC.

Despite the central importance of DNS, numerous attacks and vulnerabilities are regularly discovered. The root of the problem is the ambiguity and tremendous complexity of DNS protocol specifications, amid a rapidly evolving Internet infrastructure. To counteract the vicious break-and-fix cycle for improving DNS infrastructure, we instigate a foundational approach: we construct the first formal semantics of end-to-end name resolution, a collection of components for the formal analyses of both qualitative and quantitative properties, and an automated tool for discovering DoS attacks. Our formal framework represents an important step towards a substantially more secure and reliable DNS infrastructure.

Modern DDoS defense systems rely on probabilistic monitoring algorithms to identify flows that exceed a volume threshold and should thus be penalized. Commonly, classic sketch algorithms are considered sufficiently accurate for usage in DDoS defense. However, as we show in this paper, these algorithms achieve poor detection accuracy under burst-flood attacks, i.e., volumetric DDoS attacks composed of a swarm of medium-rate sub-second traffic bursts. Under this challenging attack pattern, traditional sketch algorithms can only detect a high share of the attack bursts by incurring a large number of false positives. In this paper, we present ALBUS, a probabilistic monitoring algorithm that overcomes the inherent limitations of previous schemes: ALBUS is highly effective at detecting large bursts while reporting no legitimate flows, and therefore improves on prior work regarding both recall and precision. Besides improving accuracy, ALBUS scales to high traffic rates, which we demonstrate with an FPGA implementation, and is suitable for programmable switches, which we showcase with a P4 implementation.

Internet service providers (ISPs) have a variety of quality attributes that determine their attractiveness for data transmission, ranging from quality-of-service metrics such as jitter to security properties such as the presence of DDoS defense systems. ISPs should optimize these attributes in line with their profit objective, i.e., maximize revenue from attracted traffic while minimizing attribute-related cost, all in the context of alternative offers by competing ISPs. However, this attribute optimization is difficult not least because many aspects of ISP competition are barely understood on a systematic level, e.g., the multi-dimensional and cost-driving nature of path quality, and the distributed decision making of ISPs on the same path. In this paper, we improve this understanding by analyzing how ISP competition affects path quality and ISP profits. To that end, we develop a game-theoretic model in which ISPs (i) affect path quality via multiple attributes that entail costs, (ii) are on paths together with other selfish ISPs, and (iii) are in competition with alternative paths when attracting traffic. The model enables an extensive theoretical analysis, surprisingly showing that competition can have both positive and negative effects on path quality and ISP profits, depending on the network topology and the cost structure of ISPs. However, a large-scale simulation, which draws on real-world data to instantiate the model, shows that the positive effects will likely prevail in practice: If the number of selectable paths towards any destination increases from 1 to 5, the prevalence of quality attributes increases by at least 50%, while 75% of ISPs improve their profit.

Today's industrial networks heavily rely on perimeter-based security. Although this has worked well in the past, the advent of the industrial IoT is blurring the network boundary, and thereby undermining the effectiveness of perimeter-based network defences. To address this, we propose Hopper: an industrial IoT security protocol that places each network host in its own access-controlled nano segment, thus minimizing the attack surface introduced by connecting devices to the network. Because Hopper enforces nano segmentation in-fabric, it does not require modifications to how packets are routed. Hopper achieves this by allowing each network node to verify that each packet it processes is part of a desired flow and was generated by an authorized host. Packets that fail any of these checks are dropped en route. By leveraging prevalent industrial network features, Hopper accomplishes low management and bandwidth overhead while being suitable for a wide range of networks. Our implementation on IoT-class hardware demonstrates that Hopper achieves high throughput and scalability, even in constrained environments.

This paper presents a security analysis of the InfiniBand architecture, a prevalent RDMA standard, and NVMe-over-Fabrics (NVMe-oF), a prominent protocol for industrial disaggregated storage that exploits RDMA protocols to achieve low-latency and high-bandwidth access to remote solid-state devices. Our work, NeVerMore, discovers new vulnerabilities in RDMA protocols that unveils several attack vectors on RDMA-enabled applications and the NVMe-oF protocol, showing that the current security mechanisms of the NVMe-oF protocol do not address the security vulnerabilities posed by the use of RDMA. In particular, we show how an unprivileged user can inject packets into any RDMA connection created on a local network controller, bypassing security mechanisms of the operating system and its kernel, and how the injection can be used to acquire unauthorized block access to NVMe-oF devices. Overall, we implement four attacks on RDMA protocols and seven attacks on the NVMe-oF protocol and verify them on the two most popular implementations of NVMe-oF: SPDK and the Linux kernel. To mitigate the discovered attacks we propose multiple mechanisms that can be implemented by RDMA and NVMe-oF providers.

To protect against naturally occurring or adversely induced congestion in the Internet, we propose the concept of flyover reservations, a fundamentally new approach for addressing the availability demands of critical low-volume applications. In contrast to path-based reservation systems, flyovers are fine-grained "hop-based" bandwidth reservations on the level of individual autonomous systems. We demonstrate the scalability of this approach experimentally through simulations on large graphs. Moreover, we bring the flyovers' potential to full fruition by introducing Helia, a protocol for secure flyover reservation setup and data transmission. We evaluate Helia's performance based on an implementation in DPDK, demonstrating authentication and forwarding of reservation traffic at 160 Gbps. Our security analysis shows that Helia can resist a large variety of powerful attacks against reservation admission and traffic forwarding. Despite its simplicity, Helia outperforms current state-of-the-art reservation systems in many key metrics.

We present N-Tube, a novel, provably secure, inter-domain bandwidth reservation algorithm that runs on a network architecture supporting path-based forwarding. N-Tube reserves global end-to-end bandwidth along network paths in a distributed, neighbor-based, and tube-fair way. It guarantees that benign bandwidth demands are granted available allocations that are immutable, stable, lower-bounded, andfair, even during adversarial demand bursts. We formalize N-Tube and powerful adversaries as a labeled transition system, and inductively prove its safety and security properties. We also apply statistical model checking to validate our proofs and perform an additional quantitative assessment of N-Tube, providing strong guarantees for protection against DDoS attacks. We are not aware of any other complex networked system designs that have been subjected to a comparable analysis of both their qualitative properties (such as correctness and security) and their quantitative properties (such as performance).

The question at which layer network functionality is presented or abstracted remains a research challenge. Traditionally, network functionality was either placed into the core network, middleboxes, or into the operating system - but recent developments have expanded the design space to directly introduce functionality into the application (and in particular into the browser) as a way to expose it to the user.

In today’s Internet, the security of data transfers largely depends on the forwarding path: on-path adversaries can launch powerful attacks against the confidentiality, integrity, and availability of Internet communication. Moreover, current routing protocols give little path control to end hosts; at best, a multi-homed host can choose the first hop of the forwarding path. In short, communicating hosts are facing the problem that they need to trust the entities which forward their packets but can barely choose the forwarding path. Recent research in networking has shown that path-aware network architectures can give the sender control over the path selection while increasing the overall efficiency and security of the network. Still, only half of the trust problem is solved: in these architectures, path selection is up to the sender’s judgment, even though the sender and the receiver have the same vital interest in choosing the forwarding path for their communication. In this paper, we introduce consent routing, a new routing paradigm in which the consent of both the sender and the receiver is required prior to using a forwarding path. The novelty of consent routing is to make path selection a cooperative process between the distributed communicating parties, enabling new opportunities for security and trust, e.g., mitigation of surveillance, censorship, and traffic analysis. Our implementation shows that consent routing is feasible in practice and can be incrementally deployed without changes to the underlying network architecture.

Google's BBR is the most prominent result of the recently revived quest for efficient, fair, and flexible congestion-control algorithms (CCAs). While BBR has been investigated by numerous studies, previous work still leaves gaps in the understanding of BBR performance: Experiment-based studies generally only consider network settings that researchers can set up with manageable effort, and model-based studies neglect important issues like convergence.

In the face of the ever-increasing power consumption of the information and communication technology sector, next-generation Internet architectures offer an opportunity to improve the energy consumption of the Internet. The SCION architecture is unique in that it has reached commercial deployment and thus opens up opportunities for estimating and understanding the promised energy efficiency from a realistic perspective. In this work, we introduce a method that uses the available energy consumption models for the current Internet architecture to estimate the energy efficiency of SCION's data plane. By applying this method to the best available power consumption models of the Internet, we show that while providing advanced security and availability guarantees, SCION can reduce global data plane power consumption by around 700 MW. We further investigate the impact of the SCION's quality of service (QoS) extension on data plane's power consumption and conclude that SCION with its QoS extension can reduce the power consumption of the Internet by up to 2.88 GW. Therefore, SCION, with its QoS extension, reduces the power consumption of the Internet and the whole ICT sector by up to 9.4% and 1.3%, respectively.

In recent years, much progress has been made in the field of Internet bandwidth reservation systems. While early designs were neither secure nor scalable, newer proposals promise attack resilience and Internet-wide scalability by using cryptographic access tokens (capabilities) that represent permissions to send at a guaranteed rate. Once a capability-based bandwidth reservation is established, the corresponding traffic is protected from both naturally occurring congestion and distributed denialof-service attacks, with positive consequences on the end-to-end quality of service (QoS) of the communication. However, high network utilization—possibly caused by adversaries—can still preclude the initial unprotected establishment of capabilities. To prevent such denial-of-capability (DoC) attacks, we present DoCile, a framework for the protection of capability establishment on Internet paths, irrespective of network utilization. We believe that DoCile, deployed alongside a capability-based bandwidth reservation system, can be the foundation of the next generation of secure and scalable QoS protocols.

Many critical computing applications rely on secure and dependable time which is reliably synchronized across large distributed systems. Today's time synchronization architectures are commonly based on global navigation satellite systems at the considerable risk of being exposed to outages, malfunction, or attacks against availability and accuracy. This paper describes a practical instantiation of a new global, Byzantine fault-tolerant clock synchronization approach that does not place trust in any single entity and is able to tolerate a fraction of faulty entities while still maintaining synchronization on a global scale among otherwise sovereign network topologies. Leveraging strong resilience and security properties provided by the path-aware SCION networking architecture, the presented design can be implemented as a backward compatible active standby solution for existing time synchronization deployments. Through extensive evaluation, we demonstrate that over 94 % of time servers reliably minimize the offset of their local clocks to real-time in the presence of up to 20 % malicious nodes, and all time servers remain synchronized with a skew of only 2 ms even after one year of reference clock outage.

Given large data streams of items, each attributable to a certain key and possessing a certain volume, the aggregate volume associated with a key is difficult to estimate in a way that is both efficient and accurate. On the one hand, exact counting with dedicated counters incurs unacceptable overhead during stream processing. On the other hand, sketch algorithms, i.e., approximate-counting techniques that share counters among keys, have suffered from a trade-off between accuracy and query efficiency: Classic sketch algorithms allow to compute rough estimates in an efficient way, whereas more recent proposals yield highly accurate estimates at the cost of greatly increased computation time. In this work, we propose three sketch algorithms that overcome this trade-off, computing highly accurate estimates with lightweight procedures. To reconcile these desiderata, we employ novel estimation methods that rely on Bayesian probability theory, counter-cardinality information, and basic machine-learning techniques. The combination of these techniques enables highly accurate estimates, which we demonstrate by both a theoretical worst-case analysis and an experimental evaluation. Concretely, our sketches allow to efficiently produce volume estimates with an average relative error of < 4%, which previous methods could only achieve with computations that are several orders of magnitude more expensive.

Guarantees for traffic traversing the public Internet are hard to come by, as service-level agreements are typically only available for traffic within a single autonomous system or towards direct neighbors. This deficiency leads to unpredictable performance already under normal conditions and can cause outages in the face of networklevel distributed-denial-of-service (DDoS) attacks. In this paper, we present an architecture achieving guaranteed bandwidth properties for global inter-domain network traffic. The control plane of our architecture is based on a distributed server infrastructure, while the data plane enables efficient packet forwarding on per-flow stateless routers. Our implementation demonstrates the technical feasibility and scalability of the design.

Path aware networking (PAN) is a promising approach that enables endpoints to participate in end-to-end path selection. PAN unlocks numerous benefits, such as fast failover after link failures, application-based path selection and optimization, and native interdomain multi-path. The utility of PAN hinges on the availability of a large number of high-quality path options. In an inter-domain context, two core questions arise. Can we deploy such an architecture natively in today's Internet infrastructure without creating an overlay relying on BGP? Can we build a scalable multi-path routing system that provides a large number of high-quality paths?

Path-aware networks (PANs) are emerging as an intriguing new paradigm with the potential to significantly improve the dependability and efficiency of networks. However, the benefits of PANs can only be realized if the adoption of such architectures is economically viable. This paper shows that PANs enable novel interconnection agreements among autonomous systems, which allow to considerably improve both economic profits and path diversity compared to today's Internet. Specifically, by supporting packet forwarding along a path selected by the packet source, PANs do not require the Gao-Rexford conditions to ensure stability. Hence, autonomous systems can establish novel agreements, creating new paths which demonstrably improve latency and bandwidth metrics in many cases. This paper also expounds two methods to set up agreements which are Pareto-optimal, fair, and thus attractive to both parties. We further present a bargaining mechanism that allows two parties to efficiently automate agreement negotiations.

Network traffic measurement keeps track of the amount of traffic sent by each flow in the network. It is a core functionality in applications such as traffic engineering and network intrusion detection. In high-speed networks, it is impossible to keep an exact count of the flow traffic, due to limitations with respect to memory and computational speed. Therefore, probabilistic data structures, such as sketches, are used. This paper proposes Approximate Count-Min sketch or ACM sketch, a novel variant of the Count-Min sketch algorithm that uses less memory and has a higher throughput compared to other FPGA-based sketch implementations. A-CM sketch relies on optimizations at two levels: (1) it uses approximate counters and the newly proposed Hardware-oriented Simple Active Counter algorithm to efficiently implement these counters; (2) it uses a distribution of the embedded memory, optimized towards maximum operating frequency. To the best of our knowledge, A-CM sketch outperforms all other FPGA-based sketch implementations.

In a world with increasing simplicity to store, transfer, and analyze large volumes of data, it becomes more and more important that data confidentiality and integrity be preserved in transit by default. Unfortunately, a large security gap exists between unprotected or low-security communication, such as opportunistic encryption and trust-on-first-use (TOFU) security, and high-security communication, such as TLS using server certificates or DNSSEC. Our goal is to reduce this gap and achieve a base layer for authentication and secrecy that is strictly better than TOFU security. We achieve this by designing PILA, a novel authentication method with dynamic trust anchors, which leverages irrefutable cryptographic proof of misbehavior to incentivize benign behavior. We implement PILA extensions for SSH, TLS, and DNS and show that the overhead for a typical SSH and TLS connection establishment is negligible, and that PILA only causes a marginal processing overhead of $\sim 100\ \mu \mathrm{s}$ per DNS response at the endpoints.

With the proliferation of online payment systems, the emergence of globally distributed consensus algorithms, and the increase of remotely managed critical IoT infrastructure, the need for critical-yet-frugal communication—high-availability and low-rate—is becoming increasingly pressing. For many of these applications, the use of leased lines or SD-WAN solutions is impractical due to their inflexibility and high costs, while standard Internet communication lacks the necessary reliability and attack resilience.To address this rising demand for strong quality-of-service (QoS) guarantees, we develop the GMA-based light-weight communication protocol (GLWP), building on a recent theoretical result, the GMA algorithm. GLWP is a capability-based protocol which is able to bootstrap network-wide bandwidth allocations in single round-trip times, and achieves high availability even under active attacks. Due to its clever use of cryptographic mechanisms, GLWP introduces minimal state in the network and causes low computation and communication overhead. We implement a GLWP prototype using Intel DPDK and show that it achieves line rate on a 40 Gbps link running on commodity hardware, thus showing that GLWP is a viable solution to provide strong QoS guarantees for critical-yet-frugal communications.

Current probabilistic flow-size monitoring can only detect heavy hitters (e.g., flows utilizing 10 times their permitted bandwidth), but cannot detect smaller overuse (e.g., flows utilizing 50-100 % more than their permitted bandwidth). Thus, these systems lack accuracy in the challenging environment of high-throughput packet processing, where fast-memory resources are scarce. Nevertheless, many applications rely on accurate flow-size estimation, e.g., for network monitoring, anomaly detection and Quality of Service. We design, analyze, implement, and evaluate LOFT, a new approach for efficiently detecting overuse flows that achieves dramatically better properties than prior work. LOFT can detect 1.50x overuse flows in one second, whereas prior approaches can only reliably detect flows that overuse their allocation by at least 3x. We demonstrate LOFT's suitability for high-speed packet processing with implementations in the DPDK framework and on an FPGA.

In various contexts of networking research, end-host path selection has recently regained momentum as a design principle. While such path selection has the potential to increase performance and security of networks, there is a prominent concern that it could also lead to network instability (i.e., flow-volume oscillation) if paths are selected in a greedy, load-adaptive fashion. However, the extent and the impact vectors of instability caused by path selection are rarely concretized or quantified, which is essential to discuss the merits and drawbacks of end-host path selection. In this work, we investigate the effect of end-host path selection on various metrics of networks both qualitatively and quantitatively. To achieve general and fundamental insights, we leverage the recently introduced axiomatic perspective on congestion control and adapt it to accommodate joint algorithms for path selection and congestion control, i.e., multi-path congestion-control protocols. Using this approach, we identify equilibria of the multi-path congestion-control dynamics and analytically characterize these equilibria with respect to important metrics of interest in networks (the “axioms”) such as efficiency, fairness, and loss avoidance. Moreover, we analyze how these axiomatic ratings for a general network change compared to a scenario without path selection, thereby obtaining an interpretable and quantitative formalization of the performance impact of end-host path-selection. Finally, we show that there is a fundamental trade-off in multi-path congestion-control protocol design between efficiency, stability, and loss avoidance on one side and fairness and responsiveness on the other side.

Abstract With the meteoric rise of the QUIC protocol, the supremacy of TCP as the de facto transport protocol underlying web traffic will soon cease. HTTP/3, the next version of the HTTP protocol, will not support TCP. Current website-fingerprinting literature has ignored the introduction of this new protocol to all modern browsers. In this work, we investigate whether classifiers trained in the TCP setting generalise to QUIC traces, whether QUIC is inherently more difficult to fingerprint than TCP, how feature importance changes between these protocols, and how to jointly classify QUIC and TCP traces. Experiments using four state-of-theart website-fingerprinting classifiers and our combined QUIC-TCP dataset of ~117,000 traces show that while QUIC is not inherently more difficult to fingerprint than TCP, TCP-trained classifiers may fail to detect up to 96% of QUIC visits to monitored URLs. Furthermore, classifiers that take advantage of the common information between QUIC and TCP traces for the same URL may outperform ensembles of protocol-specific classifiers in limited data settings.

DDoS attacks have been plaguing the Internet for over 20 years. For every defense mechanism invented, attackers find a new way to circumvent it. Is it possible to fundamentally prevent DDoS attacks and achieve global communication guarantees? Since the Internet is a public resource, what does it even mean to prevent DDoS -- since the adversary can also claim to be communicating "legitimately". In this talk we will unravel the different forms of DDoS attacks by first discussing how to construct meaningful definitions, and second showing how to achieve communication guarantees. This talk then demonstrates how global communication guarantees can be achieved in the SCION secure Internet architecture.

Denial-of-service attacks have become increasingly prevalent in the Internet. In many cases they are enabled or facilitated by the lack of source authentication?it is often easy for an attacker to spoof its own IP address and thus launch reflection attacks or evade detection. There have been attempts in the past to resolve this issue through filtering or cryptography-based techniques; however, there is still no sufficiently strong system in place today-all proposals either provide weak security guarantees, are not efficient enough, or lack incentives for deployment. In this paper we present PISKES, a pragmatic Internet-scale key-establishment system enabling firstpacket authentication. Through the PISKES infrastructure, any host can locally obtain a symmetric key to enable a remote service to perform source-address authentication. The remote service can itself locally derive the same key with efficient cryptographic operations. PISKES thus enables packet authentication for a wide variety of systems including high-throughput applications like DNS. We have implemented a prototype system that enables a DNS server to verify the source of every received packet within 85 ns, which is over 220 times faster than a system based on asymmetric cryptography. PISKES has been developed for the SCION secure Internet architecture but is also applicable to today's Internet. With its strong source-authentication properties and highly efficient operation it has the potential to finally bring network-layer authentication to the Internet

The ability to quickly revoke a compromised key is critical to the security of any public-key infrastructure. Regrettably, most traditional certificate revocation schemes suffer from latency, availability, or privacy problems. These problems are exacerbated by the lack of a native delegation mechanism in TLS, which increasingly leads domain owners to engage in dangerous practices such as sharing their private keys with third parties. We analyze solutions that address the longstanding delegation and revocation shortcomings of the web PKI, with a focus on approaches that directly affect the chain of trust (i.e., the X.509 certification path). For this purpose, we propose a 19-criteria framework for characterizing revocation and delegation schemes. We also show that combining short-lived delegated credentials or proxy certificates with an appropriate revocation system would solve several pressing problems.

Network testbeds have empowered networking re-search and facilitated scientific progress. However, current testbeds focus mainly on experiments involving the current Inter-net. In this paper, we propose SCIONLAB, a novel global network testbed that enables exciting research opportunities and experimentation with the SCION next-generation Internet architecture. New users can join SCIONLAB as a full-fledged autonomous system with minimal effort and administrative overhead, and directly gain unfettered access to its inter-domain routing system. Based on a well-connected network topology consisting of globally distributed nodes, SCIONLAB enables new experiments, such as inter-domain multipath communication, path-aware networking, exploration of novel routing policies, and new approaches for DDoS defense. SCIONLAB has been operational since 2016 and has supported diverse research projects. We describe the design and implementation of SCIONLAB, and present use cases that illustrate exciting research opportunities.

Byzantine fault tolerant protocols enable state replication in the presence of crashed, malfunctioning, or actively malicious processes. Designing such protocols without the assistance of verification tools, however, is remarkably error-prone. In an adversarial environment, performance and flexibility come at the cost of complexity, making the verification of existing protocols extremely difficult. We take a different approach and propose a formally verified consensus protocol designed for a specific use case: secure logging. Our protocol allows each node to propose entries in a parallel subroutine, and guarantees that correct nodes agree on the set of all proposed entries, without leader election. It is simple yet practical, as it can accommodate the workload of a logging system such as Certificate Transparency. We show that it is optimal in terms of both required rounds and tolerable faults. Using Isabelle/HOL, we provide a fully machine-checked security proof based upon the Heard-Of model, which we extend to support signatures. We also present and evaluate a prototype implementation.

By delegating path control to end-hosts, future Internet architectures offer flexibility for path selection. However, a concern arises that the distributed routing decisions by endhosts, in particular load-adaptive routing, can lead to oscillations if path selection is performed without coordination or accurate load information. Prior research has addressed this problem by devising local path-selection policies that lead to global stability. However, little is known about the viability of these policies in the Internet context, where selfish end-hosts can deviate from a prescribed policy if such a deviation is beneficial from their individual perspective. In order to achieve network stability in future Internet architectures, it is essential that end-hosts have an incentive to adopt a stability-oriented path-selection policy. In this work, we perform the first incentive analysis of the stability-inducing path-selection policies proposed in the literature. Building on a game-theoretic model of end-host path selection, we show that these policies are in fact incompatible with the self-interest of end-hosts, as these strategies make it worthwhile to pursue an oscillatory path-selection strategy. Therefore, stability in networks with selfish endhosts must be enforced by incentive-compatible mechanisms. We present two such mechanisms and formally prove their incentive compatibility.

Today's IoT deployments commonly resemble walled gardens: they are closed ecosystems in which manufacturers maintain significant control over devices after they have been deployed. This is typically the result of a centralized design approach where devices heavily rely on a monolithic, vendor-operated cloud service. We propose a distributed architecture that liberates these devices-and their data-by considering IoT devices as first-class network citizens and by grouping them in trusted network zones. These network zones support the devices contained in them by allowing tasks to be delegated from the device to the zone. However, devices are considered to be independent by default, and a task is only delegated when it is impossible or undesirable for the device to perform this task itself. We demonstrate how our architecture allows for novel access-control methods and context-dependent network views.

The lack of transparency for Internet communication prevents effective mitigation of today's security threats: i) Source addresses cannot be trusted and enable untraceable reflection attacks. ii) Malicious communication is opaque to all network entities, except for the receiver; and although ISPs are control points that can stop such attacks, effective detection and mitigation requires information that is available only at the end hosts. We propose TRIS, an architecture that bootstraps transparency for Internet communication. TRIS enables the definition of misbehavior according to the unique requirements of hosts, and then it constructs verifiable evidence of misbehavior. First, hosts express desired traffic properties for incoming traffic; a deviation from these properties signifies misbehavior. Second, ISPs construct verifiable evidence of misbehavior for the traffic they forward. If misbehavior is detected, it can then be proven to the ISPs of the communicating hosts. We implement our architecture on commodity hardware and demonstrate that verifiable proof of misbehavior introduces little overhead with respect to bandwidth and packet processing in the network: our prototype achieves line-rate performance for common packet sizes, saturating a 10 Gbps link with a single CPU core. In addition, we tackle incremental deployment issues and describe interoperability with today's Internet architecture.

Motivated by the weaknesses of today's TLS public-key infrastructure (PKI), recent studies have proposed numerous enhancements to fortify the PKI ecosystem. Deploying one particular enhancement is no panacea, since each one solves only a subset of the problems. At the same time, the high deployment barrier makes the benefit-cost ratio tilt in the wrong direction, leading to disappointing adoption rates for most proposals.

Modern low-latency anonymity systems, no matter whether constructed as an overlay or implemented at the network layer, offer limited security guarantees against traffic analysis. On the other hand, high-latency anonymity systems offer strong security guarantees at the cost of computational overhead and long delays, which are excessive for interactive applications. We propose TARANET, an anonymity system that implements protection against traffic analysis at the network layer, and limits the incurred latency and overhead. In TARANET's setup phase, traffic analysis is thwarted by mixing. In the data transmission phase, end hosts and ASes coordinate to shape traffic into constant-rate transmission using packet splitting. Our prototype implementation shows that TARANET can forward anonymous traffic at over 50 Gbps using commodity hardware.

The Internet will undergo a major transformation as satellite-based Internet service providers start to disrupt the market. Constellations of hundreds to thousands of satellites promise to offer low-latency Internet to even the most remote areas. We anticipate exciting business and research opportunities.

The current Transport Layer Security (TLS) Public-Key Infrastructure (PKI) is based on a weakest-link security model that depends on over a thousand trust roots. The recent history of malicious and compromised Certification Authorities has fueled the desire for alternatives. Creating a new, secure infrastructure is, however, a surprisingly challenging task due to the large number of parties involved and the many ways that they can interact. A principled approach to its design is therefore mandatory, as humans cannot feasibly consider all the cases that can occur due to the multitude of interleavings of actions by legitimate parties and attackers, such as private key compromises (e.g., domain, Certification Authority, log server, other trusted entities), key revocations, key updates, etc. We present ARPKI, a PKI architecture that ensures that certificate-related operations, such as certificate issuance, update, revocation, and validation, are transparent and accountable. ARPKI efficiently supports these operations, and gracefully handles catastrophic events such as domain key loss or compromise. Moreover ARPKI is the first PKI architecture that is co-designed with a formal model, and we verify its core security property using the TAMARIN prover. We prove that ARPKI offers extremely strong security guarantees, where compromising even n - 1 trusted signing and verifying entities is insufficient to launch a man-in-the-middle attack. Moreover, ARPKI's use deters misbehavior as all operations are publicly visible. Finally, we present a proof-of-concept implementation that provides all the features required for deployment. Our experiments indicate that ARPKI efficiently handles the certification process with low overhead. It does not incur additional latency to TLS, since no additional round trips are required.

We make a case for packet-replay suppression at the network layer, a concept that has been generally neglected. Our contribution is twofold. First, we demonstrate a new attack, the router-reflection attack, that can be launched using compromised routers. In this attack, a compromised router degrades the connectivity of a remote Internet region just by replaying packets. The attack is feasible even if all packets are attributed to their sources, i.e., source authentication is in place, and our evaluation shows that the threat is pervasive---candidate routers for compromise are in the order of hundreds or thousands. Second, we design an in-network mechanism for replay suppression. We start by showing that designing such a mechanism poses unsolved challenges and simple adaptations of end-to-end solutions are not sufficient. Then, we devise, analyze, and implement a highly efficient protocol that suppresses replayed traffic at the network layer without global time synchronization. Our software-router prototype can saturate a 10 Gbps link using only two CPU cores for packet processing.

Multipath communication not only allows improved throughput but can also be used to leverage different path characteristics to best fulfill each application's objective. In particular, certain delay-sensitive applications, such as real-time voice and video communications, can usually withstand packet loss and aim to maximize throughput while keeping latency at a reasonable level. In such a context, one hard problem is to determine along which path the data should be transmitted or retransmitted. In this paper, we formulate this problem as a linear optimization, show bounds on the performance that can be obtained in a multipath paradigm, and show that path diversity is a strong asset for improving network performance. We also discuss how these theoretical limits can be approached in practice and present simulation results.

Abstract We identify two vulnerabilities for existing highspeed network-layer anonymity protocols, such as LAP and Dovetail. First, the header formats of LAP and Dovetail leak path information, reducing the anonymity-set size when an adversary launches topological attacks. Second, ASes can launch session hijacking attacks to deanonymize destinations. HORNET addresses these problems but incurs additional bandwidth overhead and latency. In this paper, we propose PHI, a Path-HIdden lightweight anonymity protocol that solves both challenges while maintaining the same level of efficiency as LAP and Dovetail. We present an efficient packet header format that hides path information and a new back-off setup method that is compatible with current and future network architectures. Our experiments demonstrate that PHI expands anonymity sets of LAP and Dovetail by over 30x and reaches 120 Gbps forwarding speed on a commodity software router.

In this article, we address the problem of scaling authentication for naming, routing, and end-entity (EE) certification to a global environment in which authentication policies and users’ sets of trust roots vary widely. The current mechanisms for authenticating names (DNSSEC), routes (BGPSEC), and EE certificates (TLS) do not support a coexistence of authentication policies, affect the entire Internet when compromised, cannot update trust root information efficiently, and do not provide users with the ability to make flexible trust decisions. We propose the Scalable Authentication Infrastructure for Next-generation Trust (SAINT), which partitions the Internet into groups with common, local trust roots and isolates the effects of a compromised trust root. SAINT requires groups with direct routing connections to cross-sign each other for authentication purposes, allowing diverse authentication policies while keeping all entities’ authentication information globally discoverable. SAINT makes trust root management a central part of the network architecture, enabling trust root updates within seconds and allowing users to make flexible trust decisions. SAINT operates without a significant performance penalty and can be deployed alongside existing infrastructures.

Future Internet proposals have employed edge-directed routing to realize the benefits of path choice by the sources (e.g., end users). However, economic issues hamper the adoption by ISPs: 1) ISPs' costs increase when sources choose paths that are not economically optimal for ISPs, and 2) ISPs have to overprovision their links aggressively since traffic engineering is shifted to the users and congestion is more likely to occur. We implement a path-based dynamic pricing scheme that addresses these challenges. ISPs can dynamically adjust the prices of paths in order to compensate for potential losses incurred by users' choices and to incentivize users to switch paths in case of congestion. We describe our implementation in the context of future Internet architectures and demonstrate a mutually beneficial situation for ISPs and users.

This study stems from the premise that we need to break away from the "reactive" cycle of developing defenses against new DDoS attacks (e.g., amplification) by proactively investigating the potential for new types of DDoS attacks. Our specific focus is on pulsating attacks, a particularly debilitating type that has been hypothesized in the literature. In a pulsating attack, bots coordinate to generate intermittent pulses at target links to significantly reduce the throughput of TCP connections traversing the target. With pulsating attacks, attackers can cause significantly greater damage to legitimate users than traditional link flooding attacks. To date, however, pulsating attacks have been either deemed ineffective or easily defendable for two reasons: (1) they require a central coordinator and can thus be tracked; and (2) they require tight synchronization of pulses, which is difficult even in normal non-congestion scenarios. This paper argues that, in fact, the perceived drawbacks of pulsating attacks are in fact not fundamental. We develop a practical pulsating attack called CICADAS using two key ideas: using both (1) congestion as an implicit signal for decentralized implementation, and (2) a Kalman-filter-based approach to achieve tight synchronization. We validate CICADAS using simulations and wide-area experiments. We also discuss possible countermeasures against this attack.

We propose a demonstration of SCION, a future Internet Architecture designed for the 21st century. We demonstrate SCION's various rich features (including DDoS defense, native multipath communication, high-speed anonymous routing) and its ease of deployment.

In an ideal Internet, every packet would be attributable to its sender, while host identities and transmitted content would remain private. Designing such a network is challenging because source accountability and communication privacy are typically viewed as conflicting properties. In this paper, we propose an architecture that guarantees source accountability and privacy-preserving communication by enlisting ISPs as accountability agents and privacy brokers. While ISPs can link every packet that originates from their network to their customers, customer identity remains unknown to the rest of the Internet. In our architecture, network communication is based on Ephemeral Identifiers (EphIDs)---cryptographic tokens that can be linked to a source only by the source's ISP. We demonstrate that EphIDs can be generated and processed efficiently, and we analyze the practical considerations for deployment.

In a public-key infrastructure (PKI), clients must have an efficient and secure way to determine whether a certificate was revoked (by an entity considered as legitimate to do so), while preserving user privacy. A few certification authorities (CAs) are currently responsible for the issuance of the large majority of TLS certificates. These certificates are considered valid only if the certificate of the issuing CA is also valid. The certificates of these important CAs are effectively too big to be revoked, as revoking them would result in massive collateral damage. To solve this problem, we redesign the current revocation system with a novel approach that we call PKI Safety Net (PKISN), which uses publicly accessible logs to store certificates (in the spirit of Certificate Transparency) and revocations. The proposed system extends existing mechanisms, which enables simple deployment. Moreover, we present a complete implementation and evaluation of our scheme.

SDN promises to make networks more flexible, programmable, and easier to manage. Inherent security problems in SDN today, however, pose a threat to the promised benefits. First, the network operator lacks tools to proactively ensure that policies will be followed or to reactively inspect the behavior of the network. Second, the distributed nature of state updates at the data plane leads to inconsistent network behavior during reconfigurations. Third, the large flow space makes the data plane susceptible to state exhaustion attacks. This paper presents SDNsec, an SDN security extension that provides forwarding accountability for the SDN data plane. Forwarding rules are encoded in the packet, ensuring consistent network behavior during reconfigurations and limiting state exhaustion attacks due to table lookups. Symmetric-key cryptography is used to protect the integrity of the forwarding rules and enforce them at each switch. A complementary path validation mechanism allows the controller to reactively examine the actual path taken by the packets. Furthermore, we present mechanisms for secure link-failure recovery.

Although TLS is used on a daily basis by many critical applications, the public-key infrastructure that it relies on still lacks an adequate revocation mechanism. An ideal revocation mechanism should be inexpensive, efficient, secure, and privacypreserving. Moreover, rising trends in pervasive encryption pose new scalability challenges that a modern revocation system should address. In this paper, we investigate how network nodes can deliver certificate-validity information to clients. We present RITM, a framework in which middleboxes (as opposed to clients, servers, or certification authorities) store revocation-related data. RITM provides a secure revocation-checking mechanism that preserves user privacy. We also propose to take advantage of content-delivery networks (CDNs) and argue that they would constitute a fast and cost-effective way to disseminate revocations. Additionally, RITM keeps certification authorities accountable for the revocations that they have issued, and it minimizes overhead at clients and servers, as they have to neither store nor download any messages. We also describe feasible deployment models and present an evaluation of RITM to demonstrate its feasibility and benefits in a real-world deployment.

The act of communication on the Internet inevitably leaks information. In particular, network headers reveal information (e.g., source address, flow information); yet, protecting the header has proven challenging. Past research successfully protected certain fields of the headers (e.g., source address), but no proposal has attempted to eliminate flow information from the header so that packets cannot be linked to flows; flow information is systematically used to subvert privacy. Hence, we investigate the following questions: Can we design an architecture that eliminates flow-packet linkability? Can we do so without imposing impractical requirements on the network infrastructure? Our proposed architecture is based on per-packet One Time Address (OTA)-an address that a host uses to send or receive exactly one packet. Furthermore, the architecture eliminates any implicit (e.g., the standard five-tuple in TCP/UDP packets) or explicit (e.g., flow identifier) flow information from packet headers. Yet, the architecture allows the communicating hosts to demultiplex seemingly unrelated packets to flows. We have implemented the proposed architecture, and our evaluation shows that it can satisfy today's packet forwarding requirements.

Data-plane fault localization enhances network availability and reliability by enabling localization and circumvention of malicious entities on a network path. Algorithms for data-plane fault localization exist for intra-domain settings, however, the per-flow or per-source state required at intermediate routers makes them prohibitively expensive in inter-domain settings. We present Faultprints, the first secure data-plane fault localization protocol that is practical for inter-domain settings. Faultprints enables a source to precisely localize malicious network links that drop, delay, or modify packets. We implemented an efficient version of Faultprints on a software router by taking advantage of the parallelism in the AES-NI module of Intel CPUs. Our evaluation on real-world traffic shows fast forwarding on a commodity server at 116.95 Gbps out of 120 Gbps capacity, and a goodput of 94 Gbps. Additionally, Faultprints achieves a high failure localization rate, while incurring a low communication overhead.

We present HORNET, a system that enables high-speed end-to-end anonymous channels by leveraging next-generation network architectures. HORNET is designed as a low-latency onion routing system that operates at the network layer thus enabling a wide range of applications. Our system uses only symmetric cryptography for data forwarding yet requires no per-flow state on intermediate routers. This design enables HORNET routers implemented on off-the-shelf hardware to process anonymous traffic at over 93 Gb/s. HORNET is also highly scalable, adding minimal processing overhead per additional anonymous channel.

The technical community has so far defined network neutrality in terms of specific mechanisms, e.g., policing or shaping. We argue that these definitions are problematic: according to them, a non-neutral network may be preferable (for all users) to a neutral one; moreover, these mechanisms can have the same effect on the target traffic as legitimate ISP practices like traffic engineering or peering agreements. We argue that we should not try to define or enforce network neutrality through technical means at all. Instead, the network layer should provide transparency, i.e., low-level loss and delay information that is admissible in court and can be used as a building block by regulators to reason about ISP neutrality at a higher level. We close by outlining challenges and possible solutions.

The flexibility of the current Domain Name System (DNS) has been stretched to its limits to accommodate new applications such as content delivery networks and dynamic DNS. In particular, maintaining cache consistency has become a much larger problem, as emerging technologies require increasingly-frequent updates to DNS records. Though Time-To-Live (TTL) is the most widely used method of controlling cache consistency, it does not offer the fine-grained control necessary for handling these frequent changes. In addition, TTLs are too static to handle sudden changes in traffic caused by Internet failures or social media trends, demonstrating their inflexibility in the face of unforeseen events. To address these problems, we first propose a metric called Expected Aggregate Inconsistency (EAI), which allows us to consider important factors such as a record's update frequency and popularity when quantitatively measuring inconsistency. We then design ECO-DNS, a lightweight system that leverages the information provided by EAI to optimize a record's TTL. This value can be tuned to individual cache servers' preferences between better consistency and bandwidth overhead. Further-more, our optimization model's flexibility allows us to easily adapt ECO-DNS to handle various caching hierarchies such as multi-level caching while considering the trade off among consistency, overhead, latency, and server load.

With the growing incidents of flash crowds and sophisticated DDoS attacks mimicking benign traffic, it becomes challenging to protect Internet-based services solely by differentiating attack traffic from legitimate traffic. While fair-sharing schemes are commonly suggested as a defense when differentiation is difficult, they alone may suffer from highly variable or even unbounded waiting times. We propose RainCheck Filter (RCF), a lightweight primitive that guarantees bounded waiting time for clients despite server flooding without keeping per-client state on the server. RCF achieves strong waiting time guarantees by prioritizing clients based on how long the clients have waited - as if the server maintained a queue in which the clients lined up waiting for service. To avoid keeping state for every incoming client request, the server sends to the client a raincheck, a timestamped cryptographic token that not only informs the client to retry later but also serves as a proof of the client's priority level within the virtual queue. We prove that every client complying with RCF can access the server in bounded time, even under a flash crowd incident or a DDoS attack. Our large-scale simulations confirm that RCF provides a small and predictable maximum waiting time while existing schemes cannot. To demonstrate its deployability, we implement RCF as a Python module such that web developers can protect a critical server resource by adding only three lines of code.

This paper presents FAIR, a forwarding accountability mechanism that incentivizes ISPs to apply stricter security policies to their customers. The Autonomous System (AS) of the receiver specifies a traffic profile that the sender AS must adhere to. Transit ASes on the path mark packets. In case of traffic profile violations, the marked packets are used as a proof of misbehavior. FAIR introduces low bandwidth overhead and requires no per-packet and no per-flow state for forwarding. We describe integration with IP and demonstrate a software switch running on commodity hardware that can switch packets at a line rate of 120 Gbps, and can forward 140M minimum-sized packets per second, limited by the hardware I/O subsystem. Moreover, this paper proposes a "suspicious bit" for packet headers -- an application that builds on top of FAIR's proofs of misbehavior and flags packets to warn other entities in the network.

We present ARPKI, a public-key infrastructure that ensures that certificate-related operations, such as certificate issuance, update, revocation, and validation, are transparent and accountable. ARPKI is the first such infrastructure that systematically takes into account requirements identified by previous research. Moreover, ARPKI is co-designed with a formal model, and we verify its core security property using the Tamarin prover. We present a proof-of-concept implementation providing all features required for deployment. ARPKI efficiently handles the certification process with low overhead and without incurring additional latency to TLS.

The Internet has been successful beyond even the most optimistic expectations. It permeates and intertwines with almost all aspects of our society and economy. The success of the Internet has created a dependency on communication as many of the processes underpinning the foundations of modern society would grind to a halt should communication become unavailable. However, much to our dismay, the current state of safety and availability of the Internet is not commensurate with its importance.

The recently proposed concept of publicly verifiable logs is a promising approach for mitigating security issues and threats of the current Public-Key Infrastructure (PKI). Although much progress has been made towards a more secure infrastructure, the currently proposed approaches still suffer from security vulnerabilities, inefficiency, or incremental deployment challenges.

A secure routing infrastructure is vital for secure and reliable Internet services. Source authentication and path validation are two fundamental primitives for building a more secure and reliable Internet. Although several protocols have been proposed to implement these primitives, they have not been formally analyzed for their security guarantees. In this paper, we apply proof techniques for verifying cryptographic protocols (e.g., key exchange protocols) to analyzing network protocols. We encode LS2, a program logic for reasoning about programs that execute in an adversarial environment, in Coq. We also encode protocol-specific data structures, predicates, and axioms. To analyze a source-routing protocol that uses chained MACs to provide origin and path validation, we construct Coq proofs to show that the protocol satisfies its desired properties. To the best of our knowledge, we are the first to formalize origin and path authenticity properties, and mechanize proofs that chained MACs can provide the desired authenticity properties.

In-network source authentication and path validation are fundamental primitives to construct higher-level security mechanisms such as DDoS mitigation, path compliance, packet attribution, or protection against flow redirection. Unfortunately, currently proposed solutions either fall short of addressing important security concerns or require a substantial amount of router overhead. In this paper, we propose lightweight, scalable, and secure protocols for shared key setup, source authentication, and path validation. Our prototype implementation demonstrates the efficiency and scalability of the protocols, especially for software-based implementations.

With the increasing popularity of mobile devices, drivers and passengers will naturally want to connect their devices to their cars. Malicious entities can and likely will try to attack such systems in order to compromise other vehicular components or eavesdrop on privacy-sensitive information. It is imperative, therefore, to address security concerns from the onset of these technologies. While guaranteeing secure wireless vehicle-to-mobile communication is crucial to the successful integration of mobile devices in vehicular environments, usability is of equally critical importance. With MVSec, we propose novel approaches to secure vehicle-to-mobile communication tailored specifically for vehicular environments. We present novel security protocols and provide complete implementation and user study results.

Datacenter networking has gained increasing popularity in the past few years. While researchers paid considerable efforts to enhance the performance and scalability of datacenter networks, achieving reliable data delivery in these emerging networks with misbehaving routers and switches received far less attention. Unfortunately, documented incidents of router compromise underscore that the capability to identify adversarial routers and switches is an imperative and practical need rather than merely a theoretical exercise. To this end, data-plane fault localization (FL) aims to identify faulty links and is an effective means of achieving high network availability. However, existing secure FL protocols assume that the source node knows the entire outgoing path that delivers the source node's packets and that the path is static and long-lived. These assumptions are invalidated by the dynamic traffic patterns and agile load balancing commonly seen in modern datacenter networks. We propose the first secure FL protocol, DFL, with no requirements on path durability or the source node knowing the outgoing paths. Through a core technique we named delayed function disclosure, DFL incurs little communication overhead and a small, constant router state independent of the network size or the number of flows traversing a router.

We propose STRIDE, a new DDoS-resilient Internet architecture that isolates attack traffic through viable bandwidth allocation, preventing a botnet from crowding out legitimate flows. This new architecture presents several novel concepts including tree-based bandwidth allocation and long-term static paths with guaranteed bandwidth. In concert, these mechanisms provide domain-based bandwidth guarantees within a trust domain - administrative domains grouped within a legal jurisdiction with enforceable accountability; each administrative domain in the trust domain can then internally split such guarantees among its endhosts to provide (1) connection establishment with high probability, and (2) precise bandwidth guarantees for established flows, regardless of the size or distribution of the botnet outside the source and the destination domains. Moreover, STRIDE maintains no per-flow state on backbone routers and requires no key establishment across administrative domains. We demonstrate that STRIDE achieves these DDoS defense properties through formal analysis and simulation. We also show that STRIDE mitigates emerging DDoS threats such as Denial-of-Capability (DoC) [6] and N2 attacks [22] based on these properties that none of the existing DDoS defense mechanisms can achieve.

We present OASIS, a CPU instruction set extension for externally verifiable initiation, execution, and termination of an isolated execution environment with a trusted computing base consisting solely of the CPU. OASIS leverages the hardware components available on commodity CPUs to achieve a low-cost, low-overhead design.

IP spoofing is attractive to amplify network attacks and to provide anonymity. Many approaches have to prevent IP spoofing attacks; however, they do not address a significant deployment issue: filtering inefficiency caused by lack of incentives for early adopters. Practically, no mechanism has been widely deployed and none successfully blocks IP spoofing attacks. We propose a universal anti-spoofing (UAS) mechanism that incorporates existing mechanisms to thwart IP spoofing attacks. In the proposed mechanism, intermediate routers utilize any existing anti-spoofing mechanism that ascertains whether a packet is spoofed or not, and inscribes this information in the packet header. The edge routers at a victim network can estimate the forgery of a packet based on the information sent by the upstream routers. The results of experiments conducted with Internet topologies indicate that UAS reduces false alarms up to 84.5% compared to cases where each mechanism operates separately. Our evaluation shows that incorporating multiple anti-spoofing mechanisms reduces false alarms significantly.

Users regularly experience a crisis of confidence on the Internet. Is that email or instant message truly originating from the claimed individual? Such doubts are commonly resolved through a leap of faith, expressing the desperation and helplessness of users. To establish a secure basis for online communication, we propose SafeSlinger, a system leveraging the proliferation of smartphones to enable people to securely and privately exchange their public keys. Through the exchanged authentic public keys, SafeSlinger establishes a secure channel offering secrecy and authenticity, which we use to support secure messaging and file exchange. SafeSlinger also provides an API for importing applications' public keys into a user's contact information. By slinging entire contact entries to others, we propose secure introductions, as the contact entry includes the SafeSlinger public keys as well as other public keys that were imported. We present the design and implementation of SafeSlinger for Android and iOS, which is available from the respective app stores. An overview video of SafeSlinger is available at: http://www.youtube.com/watch?v=IFXL8fUqNKY

Outsourced computation services should ideally only charge customers for the resources used by their applications. Unfortunately, no verifiable basis for service providers and customers to reconcile resource accounting exists today. This leads to undesirable outcomes for both providers and consumers-providers cannot prove to customers that they really devoted the resources charged, and customers cannot verify that their invoice maps to their actual usage. As a result, many practical and theoretical attacks exist, aimed at charging customers for resources that their applications did not consume. Moreover, providers cannot charge consumers precisely, which causes them to bear the cost of unaccounted resources or pass these costs inefficiently to their customers.

Recent trends in public-key infrastructure research explore the tradeoff between decreased trust in Certificate Authorities (CAs), resilience against attacks, communication overhead (bandwidth and latency) for setting up an SSL/TLS connection, and availability with respect to verifiability of public key information. In this paper, we propose AKI as a new public-key validation infrastructure, to reduce the level of trust in CAs. AKI integrates an architecture for key revocation of all entities (e.g., CAs, domains) with an architecture for accountability of all infrastructure parties through checks-and-balances. AKI efficiently handles common certification operations, and gracefully handles catastrophic events such as domain key loss or compromise. We propose AKI to make progress towards a public-key validation infrastructure with key revocation that reduces trust in any single entity.

Malware continues to thrive on the Internet. Besides automated mechanisms for detecting malware, we provide users with trust evidence information to enable them to make informed trust decisions. To scope the problem, we study the challenge of assisting users with judging the trustworthiness of software downloaded from the Internet.

Much effort has been spent to reduce the software Trusted Computing Base (TCB) of modern systems. However, there remains a large and complex hardware TCB, including memory, peripherals, and system buses. There are many stronger, but still realistic, adversary models where we need to consider that this hardware may be malicious or compromised. Thus, there is a practical need to determine whether we can achieve secure program execution in the presence of not only malicious software, but also malicious hardware.

Popular anonymous communication systems often require sending packets through a sequence of relays on dilated paths for strong anonymity protection. As a result, increased end-to-end latency renders such systems inadequate for the majority of Internet users who seek an intermediate level of anonymity protection while using latency-sensitive applications, such as Web applications. This paper serves to bridge the gap between communication systems that provide strong anonymity protection but with intolerable latency and non-anonymous communication systems by considering a new design space for the setting. More specifically, we explore how to achieve near-optimal latency while achieving an intermediate level of anonymity with a weaker yet practical adversary model (i.e., protecting an end-host's identity and location from servers) such that users can choose between the level of anonymity and usability. We propose Lightweight Anonymity and Privacy (LAP), an efficient network-based solution featuring lightweight path establishment and stateless communication, by concealing an end-host's topological location to enhance anonymity against remote tracking. To show practicality, we demonstrate that LAP can work on top of the current Internet and proposed future Internet architectures.

Compromised and misconfigured routers are a well-known problem in ISP and enterprise networks. Data-plane fault localization (FL) aims to identify faulty links of compromised and misconfigured routers during packet forwarding, and is recognized as an effective means of achieving high network availability. Existing secure FL protocols are path-based, which assume that the source node knows the entire outgoing path that delivers the source node's packets and that the path is static and long-lived. However, these assumptions are incompatible with the dynamic traffic patterns and agile load balancing commonly seen in modern networks. To cope with real-world routing dynamics, we propose the first secure neighborhood-based FL protocol, DynaFL, with no requirements on path durability or the source node knowing the outgoing paths. Through a core technique we named delayed key disclosure, DynaFL incurs little communication overhead and a small, constant router state independent of the network size or the number of flows traversing a router. In addition, each DynaFL router maintains only a single secret key, which based on our measurement results represents 2 - 4 orders of magnitude reduction over previous path-based FL protocols.

Based on the advances in laptop technologies and the mobility characteristics, laptops have become a vital device used at various places. Usually, numerous sensitive files such as credit card numbers and Web cookies are stored on laptops for convenient usage. However, if a laptop is stolen, the data stored on it is easily leaked; which may cause serious consequences. Encrypting files by encryption keys is a general solution; however, if the decryption keys are also stored on laptops, the files can also be decrypted by adversaries easily. To solve this problem, this paper proposes the Mobile Encryption for Laptop data Protection (MELP) system. MELP includes the design of an online server and mobile phone, and encrypts each sensitive file by a file system encryption key, which is further sequentially encrypted twice by the phone's and server's encryption keys. The reason of adopting a mobile phone is that at least one simple confirmation of execution must be performed by a user, and the reason of adopting an online server is that if both user's laptop and mobile phone are stolen, users can still disable the online decryption process on the server.

It is often appealing to assume that existing solutions can be directly applied to emerging engineering domains. Unfortunately, careful investigation of the unique challenges presented by new domains exposes its idiosyncrasies, thus often requiring new approaches and solutions. In this paper, we argue that the “smart” grid, replacing its incredibly successful and reliable predecessor, poses a series of new security challenges, among others, that require novel approaches to the field of cyber security. We will call this new field cyber-physical security. The tight coupling between information and communication technologies and physical systems introduces new security concerns, requiring a rethinking of the commonly used objectives and methods. Existing security approaches are either inapplicable, not viable, insufficiently scalable, incompatible, or simply inadequate to address the challenges posed by highly complex environments such as the smart grid. A concerted effort by the entire industry, the research community, and the policy makers is required to achieve the vision of a secure smart grid infrastructure.

Jamming attacks are especially harmful to the reliability of wireless communication, as they can effectively disrupt communication between any node pairs. Existing jamming defenses primarily focus on repairing connectivity between adjacent nodes. In this paper, we address jamming at the network level and focus on restoring the end-to-end data delivery through multipath routing. As long as all paths do not fail concurrently, the end-to-end path availability is maintained. Prior work in multipath selection improves routing availability by choosing node-disjoint paths or link-disjoint paths. However, through our experiments on jamming effects using MicaZ nodes, we show that disjointness is insufficient for selecting fault-independent paths. Thus, we address multipath selection based on the knowledge of a path's availability history. Using Availability History Vectors (AHVs) of paths, we present a centralized AHV-based algorithm to select fault-independent paths, and a distributed AHV-based routing protocol built on top of a classic routing algorithm in ad hoc networks. Our extensive simulation results validate that both AHV-based algorithms are effective in overcoming the jamming impact by maximizing the end-to-end availability of the selected paths.

Recent research demonstrates that malware can infect peripherals' firmware in a typical x86 computer system, e.g., by exploiting vulnerabilities in the firmware itself or in the firmware update tools. Verifying the integrity of peripherals' firmware is thus an important challenge. We propose software-only attestation protocols to verify the integrity of peripherals' firmware, and show that they can detect all known software-based attacks. We implement our scheme using a Netgear GA620 network adapter in an x86 PC, and evaluate our system with known attacks.

Recent statistics show that the number of online shoppers are increasing where the majority of them use online recommendation systems for product/service reviews. Although online reviews are becoming increasingly important, consumers face two major challenges of usability and robustness when they make purchase decisions based on the available reviews. More specifically, usability issues arise when consumers need to be able to extract relevant information given a high volume of data with uncertainty due to high variance. For robustness, judging the degree of truthfulness of the available recommendations can be a daunting task for consumers. In this paper, we propose a post-purchase tracking system as an enhancement to current online recommendation systems by embracing a peer review process and ask each consumer to score the reviews that previous consumers have posted. Furthermore, we propose to visualize the peer review processes such that people find the recommendation systems more efficient and useful to learn information. Our preliminary user study results indicate that our post-purchase tracking system is a promising approach that can help online consumers determine what information to trust with high confidence.

Clear evidence indicates the existence of compromised routers in ISP and enterprise networks. Fault localization (FL) protocols enable a network to localize specific links of compromised routers sabotaging network data delivery and are recognized as an essential means to enhancing network availability in the face of targeted attacks. However, theoretically proven lower bounds have shown that secure FL protocols in the current network infrastructure inevitably incur prohibitive overhead. We observe the current limits are due to a lack of trust relationships among network nodes. We demonstrate that we can achieve much higher FL efficiency by leveraging trusted computing technology to design a trusted network-layer architecture, Tru eN et, with a small Trusted Computing Base (TCB). We intend Tru e N e t to serve as a case study that demonstrates trusted computing's ability in yielding tangible and measurable benefits for secure network protocol designs.

Distributed denial-of-service (DDoS) attacks continue to pose an important challenge to current networks. DDoS attacks can cause victim resource consumption and link congestion. A filter-based DDoS defense is considered as an effective approach, since it can defend against both attacks: victim resource consumption and link congestion. However, existing filter-based approaches do not address necessary properties for viable DDoS solutions: how to practically identify attack paths, how to propagate filters to the best locations (filter routers), and how to manage many filters to maximize the defense effectiveness. We propose a novel mechanism, termed PFS (Probabilistic Filter Scheduling), to efficiently defeat DDoS attacks and to satisfy the necessary properties. In PFS, filter routers identify attack paths using probabilistic packet marking, and maintain filters using a scheduling policy to maximize the defense effectiveness. Our experiments show that PFS achieves 44% higher effectiveness than other filter-based approaches. Furthermore, we vary PFS parameters in terms of the marking probability and deployment ratio, and find that 30% marking probability and 30% deployment rate maximize the attack blocking rate of PFS.

Digital signatures are one of the fundamental security primitives in Vehicular Ad-Hoc Networks (VANETs) because they provide authenticity and non-repudiation in broadcast communication. However, the current broadcast authentication standard in VANETs is vulnerable to signature flooding: excessive signature verification requests that exhaust the computational resources of victims. In this paper, we propose two efficient broadcast authentication schemes, Fast Authentication (FastAuth) and Selective Authentication (SelAuth), as two countermeasures to signature flooding. FastAuth secures periodic single-hop beacon messages. By exploiting the sender's ability to predict its own future beacons, FastAuth enables 50 times faster verification than previous mechanisms using the Elliptic Curve Digital Signature Algorithm. SelAuth secures multi-hop applications in which a bogus signature may spread out quickly and impact a significant number of vehicles. SelAuth pro- vides fast isolation of malicious senders, even under a dynamic topology, while consuming only 15%--30% of the computational resources compared to other schemes. We provide both analytical and experimental evaluations based on real traffic traces and NS-2 simulations. With the near-term deployment plans of VANET on all vehicles, our approaches can make VANETs practical.

We present the first Internet architecture designed to provide route control, failure isolation, and explicit trust information for end-to-end communications. SCION separates ASes into groups of independent routing sub-planes, called trust domains, which then interconnect to form complete routes. Trust domains provide natural isolation of routing failures and human misconfiguration, give endpoints strong control for both inbound and outbound traffic, provide meaningful and enforceable trust, and enable scalable routing updates with high path freshness. As a result, our architecture provides strong resilience and security properties as an intrinsic consequence of good design principles, avoiding piecemeal add-on protocols as security patches. Meanwhile, SCION only assumes that a few top-tier ISPs in the trust domain are trusted for providing reliable end-to-end communications, thus achieving a small Trusted Computing Base. Both our security analysis and evaluation results show that SCION naturally prevents numerous attacks and provides a high level of resilience, scalability, control, and isolation.

Determining whether the number of vehicles reporting an event is above a threshold is an important mechanism for VANETs, because many applications rely on a threshold number of notifications to reach agreement among vehicles, to determine the validity of an event, or to prevent the abuse of emergency alarms. We present the first efficient and secure threshold-based event validation protocol for VANETs. Quite counter-intuitively, we found that the z-smallest approach [3] offers the best tradeoff between security and efficiency since other approaches perform better for probabilistic counting. Analysis and simulation shows that our protocol provides > 99% accuracy despite the presence of attackers, collection and distribution of alerts in less than 1 second, and negligible impact on network performance.

Jamming attacks are especially harmful to the reliability of wireless communication, as they can effectively disrupt communication. Existing jamming defenses primarily focus on repairing connectivity between adjacent nodes. In this paper, we address jamming at the network level and focus on restoring the end-to-end data delivery through multipath routing. As long as all paths do not fail concurrently, the end-to-end path availability is maintained. Prior work in multipath selection improves routing by choosing node-disjoint paths or link-disjoint paths. However, through our experiments on jamming effects using MicaZ nodes, we show that topological disjointness is insufficient for selecting fault-independent paths. Thus, we address multipath selection based on the knowledge of a path's availability history. Using Availability History Vectors (AHVs) of paths, we present an AHV-based Link-State (ALS) algorithm to select fault-independent paths. Our extensive simulation results validate that the ALS algorithm is effective in overcoming the jamming impact by maximizing the end-to-end availability of the selected paths.

Monitoring a process and its file I/O behaviors is important for security inspection for a data center server against intrusions, malware infection and information leakage. In the case of the Linux kernel 2.6, a set of hook functions called the Linux Security Module (LSM) has been implemented in order to monitor and control the system calls. By using the LSM we can inspect the activity of unknown malicious processes. However, a sophisticated attacker could breach the kernel configurations using the rootkits. Furthermore since the monitoring results of the malicious process activity are stored as a file on Hard Disk Drive (HDD), it will be easily manipulated by the attacker. In this paper, we propose a secure monitoring scheme that addresses the attacks against the monitoring module and its result for security inspection of the data center server. The monitoring module is implemented as a LSM-based function and protected by the kernel protection technique. The integrity of the monitoring result is guaranteed by using a Mandatory Access Control (MAC) of the Linux kernel and a mechanism of the trusted process invocation. This mechanism can serve as an infrastrucuture of secure inspection platform for data center server because the integrity of the monitoring module and its result is guaranteed.

Congestion control algorithms seek to optimally utilize network resources by allocating a certain rate for each user. However, malicious clients can disregard the congestion control algorithms implemented at the clients and induce congestion at bottleneck links. Thus, in an adversarial environment, the network must enforce the congestion control algorithm in order to attain the optimal network utilization offered by the algorithm. Prior work protects only a single link incident on the enforcement routers neglecting damage inflicted upon other downstream links. We present CRAFT, a capability-based scheme to secure all downstream links of a deploying router. Our goal is to enforce a network-wide congestion control algorithm on all flows. As a reference design, we develop techniques to enforce the TCP congestion control. Our design regulates all flows to share bandwidth resources in a TCP-fair manner by emulating the TCP state machine in a CRAFT router. As a result, once a flow passes a single CRAFT router, it is TCP-fair on all downstream links of that router.

Network-layer capabilities offer strong protection against link flooding by authorizing individual flows with unforgeable credentials (i.e., capabilities). However, the capability-setup channel is vulnerable to flooding attacks that prevent legitimate clients from acquiring capabilities; i.e., in Denial of Capability (DoC) attacks. Based on the observation that the distribution of attack sources in the current Internet is highly non-uniform, we provide a router-level scheme that confines the effects of DoC attacks to specified locales or neighborhoods (e.g., one or more administrative domains of the Internet). Our scheme provides precise access guarantees for capability schemes, even in the face of flooding attacks. The effectiveness of our scheme is evaluated by ns2 simulations under different attack scenarios.

Multi-path routing is effective to enhance network availability, by selecting multiple failure-independent paths for reaching one destination in the hope to survive individual path failures. Researchers suggest to select IP-layer topologically disjoint paths, assuming that they are failure-independent and can hardly fail simultaneously. Unfortunately, failure correlations lurking behind the IP-layer topology can surreptitiously squash availability gained through multi-path routing because selected paths can fail simultaneously. Spurred by this observation, we propose a new path metric and selection scheme resilient to failure correlations between topologically disjoint paths, by utilizing path availability history to reveal failure correlations. This paper presents a first stride towards the new direction of availability-oriented multi-path selection, with formal and systematic problem definition, modeling, and algorithms.

A remote attestation that measures files on a hard disk drive (HDD) is important for intrusion detection on a data center server. When the server is infected by a rootkit or when a file measurement application is manipulated, the response of the kernel or the measurement application is not reliable. A trusted platform module (TPM) that achieves a chain of trust from BIOS to kernel upon booting is proposed to provide the remote attestation. However, as the data center server is rarely rebooted, the TPM is ill suited for file measurements of the running server. In this paper, we propose an on-demand remote attestation scheme for HDD files of the server. We designed and implemented a trust chain from the BIOS via the kernel and the file measurement application to the HDD files on a running server for secure integrity measurement. A memory virtualization technique is applied to guarantee the integrity of the running kernel, and the file measurement application is verified using a code signature. Also, we implement a mechanism that attaches the server's signature to a measurement result in a trusted kernel. Finally, our proposed scheme achieves a result whereby the remote verifier can measure the integrity of the server files securely at any time.

We consider resource-constrained broadcast authentication for n receivers in a static, known network topology. There are only two known broadcast authentication protocols that do not use asymmetric cryptography, one-time signatures, multi-receiver MACs, or time synchronization. Both these protocols require three passes of a message front traversing the network. We investigate whether this amount of interaction can be improved efficiently for specific common topology classes, namely, linear topologies, tree topologies and fully connected topologies. We show modifications to the protocols allowing them to complete in just two passes in the linear and fully connected cases with a small constant factor increase in per-node communication overhead, and a further optimization that achieves the equivalent of just a single pass in the linear case with O(log n) increase in per-node communication overhead. We also prove new lower bounds for round complexity, or the maximum number of consecutive interactions in a protocol. We show that protocols with efficient per-node communication overhead (polylogarithmic in n) must require at least 2 log n rounds in any topology; this implies that our two-pass protocol in the fully-connected topology requires the fewest possible passes, and this bound is asymptotically tight for the full-duplex communication model. Furthermore, we show that communication-efficient protocols must take asymptotically more than 2 log n rounds on trees; this implies that that there are some tree topologies for which two passes do not suffice and the existing three-pass algorithms may be optimal.

An important security challenge is to protect the execution of security-sensitive code on legacy systems from malware that may infect the OS, applications, or system devices. Prior work experienced a tradeoff between the level of security achieved and efficiency. In this work, we leverage the features of modern processors from AMD and Intel to overcome the tradeoff to simultaneously achieve a high level of security and high performance. We present TrustVisor, a special-purpose hypervisor that provides code integrity as well as data integrity and secrecy for selected portions of an application. TrustVisor achieves a high level of security, first because it can protect sensitive code at a very fine granularity, and second because it has a very small code base (only around 6K lines of code) that makes verification feasible. TrustVisor can also attest the existence of isolated execution to an external entity. We have implemented TrustVisor to protect security-sensitive code blocks while imposing less than 7% overhead on the legacy OS and its applications in the common case.

Trusting a computer for a security-sensitive task (such as checking email or banking online) requires the user to know something about the computer's state. We examine research on securely capturing a computer's state, and consider the utility of this information both for improving security on the local computer (e.g., to convince the user that her computer is not infected with malware) and for communicating a remote computer's state (e.g., to enable the user to check that a web server will adequately protect her data). Although the recent "Trusted Computing" initiative has drawn both positive and negative attention to this area, we consider the older and broader topic of bootstrapping trust in a computer. We cover issues ranging from the wide collection of secure hardware that can serve as a foundation for trust, to the usability issues that arise when trying to convey computer state information to humans. This approach unifies disparate research efforts and highlights opportunities for additional work that can guide real-world improvements in computer security.

Data breaches due to stolen laptops are a major problem. Solutions exist to secure sensitive files on laptops, but are rarely deployed because users view them as inconvenient. This work examines how to provide an unobtrusive system to securely encrypt files on laptops. We observe that only a fraction of users' files contain sensitive information. In addition, the majority of users' accesses to these sensitive files occur while in a trusted location that malicious parties are unable to access. Rather than protecting all of the user's files, we secure user designated sensitive files that are rarely accessed outside of specified trusted locations. Our approach is to use information and services available only in a trusted location to assist in key derivation without user involvement and without authenticating the laptop to any outside service. We study two settings: home use where zero management overhead is needed (i.e., a plug-and-play solution) and a corporate setting where staff management of a whitelist of acceptable devices allows a higher level of security. We have implemented both systems and found automatic key derivation introduces a five second delay during the initial access to sensitive files.

Establishing trust between a group of individuals remains a difficult problem. Prior works assume trusted infrastructure, require an individual to trust unknown entities, or provide relatively low probabilistic guarantees of authenticity (95 percent for realistic settings). This work presents SPATE, a primitive that allows users to establish trust via mobile devices and physical interaction. Once the SPATE protocol runs to completion, its participants' mobile devices have authentic data that their applications can use to interact securely (i.e., the probability of a successful attack is 2-24). For this work, we leverage SPATE as part of a larger system to facilitate efficient, secure, and user-friendly collaboration via e-mail, file-sharing, and text messaging services. Our implementation of SPATE on Nokia N70 smartphones allows users to establish trust in small groups of up to eight users in less than one minute. The example SPATE applications provide increased security with little overhead noticeable to users once keys are established.

Several security protocols require a human to compare two hash values to ensure successful completion. When the hash values are represented as long sequences of numbers, humans may make a mistake or require significant time and patience to accurately compare the hash values. To improve usability during comparison, a number of researchers have proposed various hash representations that use words, sentences, or images rather than numbers. This is the first work to perform a comparative study of these hash comparison schemes to determine which scheme allows the fastest and most accurate comparison. To evaluate the schemes, we performed an online user study with more than 400 participants. Our findings indicate that only a small number of schemes allow quick and accurate comparison across a wide range of subjects from varying backgrounds.

Online reviews are widely used for purchase decisions. Their trustworthiness is limited, however, by fake reviews. Fortunately, opinions from friends in a social network are more reliable but less convenient to obtain. Combining the advantages purchase decisions of online reviews and opinions from friends can be achieved by enabling users to recognize the online reviews originating from their friends. By leveraging buyerspsila trust to nearby friends within their social network, it is possible to provide them in some cases with online reviews they can entirely trust. In this paper we present techniques to enable users to recognize the online reviews from their friends in a privacy-preserving manner. Our approach has many applications such as Internet auctions and online gaming.

In this paper, we consider the design of a policy-based routing system and the role that link state might play. Looking at the problem from a link-state perspective, we propose Centaur, a hybrid routing protocol combining the benefits of both link state and path vector. Through analytical and experimental studies, we demonstrate Centaur's potential in achieving rich policy expressiveness and high network availability. Our work shows that it is possible to combine link-state and path-vector approaches into a practical and efficient algorithm for policy-based routing.

Establishing trust between a group of individuals remains a difficult problem. Prior works assume trusted infrastructure, require an individual to trust unknown entities, or provide relatively low probabilistic guarantees of authenticity (95% for realistic settings). This work presents SPATE, a primitive that allows users to establish trust via device mobility and physical interaction. Once the SPATE protocol runs to completion, its participants' mobile devices have authentic data that their applications can use to interact securely (i.e., the probability of a successful attack is 2-24). For this work, we leverage SPATE as part of a larger system to facilitate efficient, secure, and user-friendly collaboration via email and file-sharing services. Our implementation of SPATE on Nokia N70 smartphones allows users to establish trust in small groups of up to eight users in less than one minute. The two example SPATE applications provide increased security with no overhead noticeable to users once keys are established.

Vehicular ad hoc networks (VANETs) require a mechanism to help authenticate messages, identify valid vehicles, and remove malevolent vehicles. A public key infrastructure (PKI) can provide this functionality using certificates and fixed public keys. However, fixed keys allow an eavesdropper to associate a key with a vehicle and a location, violating drivers' privacy. In this work we propose a VANET key management scheme based on temporary anonymous certified keys (TACKs). Our scheme efficiently prevents eavesdroppers from linking a vehicle's different keys and provides timely revocation of misbehaving participants while maintaining the same or less overhead for vehicle-to-vehicle communication as the current IEEE 1609.2 standard for VANET security.

Providing online access to sensitive data makes web servers lucrative targets for attackers. A compromise of any of the web server's scripts, applications, or operating system can leak the sensitive data of millions of customers. Unfortunately, many systems for stopping data leaks require considerable effort from application developers, hindering their adoption.In this work, we investigate how such leaks can be prevented with minimal developer effort. We propose CLAMP, an architecture for preventing data leaks even in the presence of web server compromises or SQL injection attacks. CLAMP protects sensitive data by enforcing strong access control on user data and by isolating code running on behalf of different users. By focusing on minimizing developer effort, we arrive at an architecture that allows developers to use familiar operating systems, servers, and scripting languages, while making relatively few changes to application code -- less than 50 lines in our applications.

Abstract Multi‐hop routing is essential to the operation of wirelessad hocnetworks. Unfortunately, it is very easy for an adversary to forge or modify routing messages to inflict severe damage on the underlying routing protocol. In this paper, we present SEAR, a secure efficientad hocrouting (SEAR) protocol forad hocnetworks that is mainly based on efficient symmetric cryptography, with asymmetric cryptography used only for the distribution of initial key commitments. SEAR uses one‐way hash functions to protect the propagation of the routing messages. Intermediate nodes verify the routing messages by applying one‐way functions, while malicious nodes cannot construct beneficial false routing messages when forwarding them. Route error (RERR) messages are protected through a variation of the TESLA broadcast authentication scheme. The SEAR protocol does not require any additional routing packet formats, and thus follows the same basic design asad hocon‐demand distance vector (AODV). We show, through both theoretical examination and simulations, that SEAR provides better security with significantly less overhead than other existing secure AODV (SAODV) protocols. Copyright © 2008 John Wiley & Sons, Ltd.

We explore the extent to which newly available CPU-based security technology can reduce the Trusted Computing Base (TCB) for security-sensitive applications. We find that although this new technology represents a step in the right direction, significant performance issues remain. We offer several suggestions that leverage existing processor technology, retain security, and improve performance. Implementing these recommendations will finally allow application developers to focus exclusively on the security of their own code, enabling it to execute in isolation from the numerous vulnerabilities in the underlying layers of legacy code.

By functionally decomposing a specific algorithm (the hierarchical secure aggregation algorithm of Chan et al. [3] and Frikken et al. [7]), we uncover a useful general functionality which we use to generate various efficient network security primitives, including: a signature scheme ensuring authenticity, integrity and non-repudiation for arbitrary node-to-node communications; an efficient broadcast authentication algorithm not requiring time synchronization; a scheme for managing public keys in a sensor network without requiring any asymmetric cryptographic operations to verify the validity of public keys, and without requiring nodes to maintain node revocation lists. Each of these applications uses the same basic data aggregation primitive and thus have O(log n) congestion performance and require only that symmetric secret keys are shared between each node and the base station. We thus observe the fact that the optimizations developed in the application area of secure aggregation can feed back into creating more optimized versions of highly general, basic security functions.

Multi-hop routing is essential to the operation of wireless ad hoc networks. Unfortunately, it is very easy for an adversary to forge or modify routing messages to inflict severe damage on the underlying routing protocol. In this paper, we present SEAR, a Secure Efficient Ad hoc Routing protocol for ad hoc networks that is mainly based on efficient symmetric cryptography, with asymmetric cryptography used only for the distribution of initial key commitments. We show, through both theoretical examination and simulations, that SEAR provides better security with significantly less overhead than other existing secure AODV protocols.

This paper examines a new building block for next-generation networks: SNAPP, or Stateless Network-Authenticated Path Pinning. SNAPP-enabled routers securely embed their routing decisions in the packet headers of a stream of traffic, effectively pinning a flow's path between sender and receiver. A sender can use the pinned path (even if routes subsequently change) by including the path embedding in later packet headers. This architectural building block decouples routing from forwarding, which greatly enhances the availability of a path in the face of routing misconfigurations or malicious attacks. To demonstrate the extreme flexibility of SNAPP, we show how it can support a wide range of applications, including sender-controlled paths, expensive route lookups, sender anonymity, and sender accountability. Our analysis shows that SNAPP's overhead is low, and the system is easily implemented in hardware. We believe that SNAPP is a worthy addition to the network architect's toolbox, enabling a variety of new designs and trade-offs.

Until recently, the design of packet dropping adversary identification protocols that are robust to both benign packet loss and malicious behavior has proven to be surprisingly elusive. In this paper, we propose a secure and practical packet-dropping adversary localization scheme that is robust and achieves a high detection rate and low communication and storage overhead -- the three key performance metrics for such protocols in realistic settings. Other recent work just optimizes either the detection rate or the communication overhead.

We present Flicker, an infrastructure for executing security-sensitive code in complete isolation while trusting as few as 250 lines of additional code. Flicker can also provide meaningful, fine-grained attestation of the code executed (as well as its inputs and outputs) to a remote party. Flicker guarantees these properties even if the BIOS, OS and DMA-enabled devices are all malicious. Flicker leverages new commodity processors from AMD and Intel and does not require a new OS or VMM. We demonstrate a full implementation of Flicker on an AMD platform and describe our development environment for simplifying the construction of Flicker-enabled code.

Secure wireless communications is a challenging problem due to the shared nature of the wireless medium. Most existing security protocols apply cryptographic techniques for bit scrambling at the application layer by exploiting a shared secret key between pairs of communicating nodes. However, more recent research argues that multipath propagation - a salient feature of wireless channels - provides a physical resource for secure communications. In this context, we propose a protocol that exploits the inherent randomness in multipath wireless channels for generating secret keys through channel estimation and quantization. Our approach is particularly attractive in wideband channels which exhibit a large number of statistically independent degrees of freedom (DoF), thereby enabling the generation of large, more-secure, keys. We show that the resulting keys are distinct for distinct pairwise links with a probability that increases exponentially with the key-size/channel DoF. We also characterize the probability that the two users sharing a common link generate the same key. This characterization is used to analyze the energy consumption in successful acquisition of a secret key by the two users. For a given key size, our results show that there is an optimum transmit power, and an optimum quantization strategy, that minimizes the energy consumption. The proposed approach to secret key generation through channel quantization also obviates the problem of key pre-distribution inherent to many existing cryptographic approaches.

Establishing secure communication among a group of physically collocated people is a challenge. This problem can be reduced to establishing authentic public keys among all the participants - these public keys then serve to establish a shared secret symmetric key for encryption and authentication of messages. Unfortunately, in most real-world settings, public key infrastructures (PKI) are uncommon and distributing a secret in a public space is difficult. Thus, it is a challenge to exchange authentic public keys in a scalable, secure, and easy to use fashion.

In this paper, we propose and evaluate Use Your Illusion, a novel mechanism for user authentication that is secure and usable regardless of the size of the device on which it is used. Our system relies on the human ability to recognize a degraded version of a previously seen image. We illustrate how distorted images can be used to maintain the usability of graphical password schemes while making them more resilient to social engineering or observation attacks. Because it is difficult to mentally "revert" a degraded image, without knowledge of the original image, our scheme provides a strong line of defense against impostor access, while preserving the desirable memorability properties of graphical password schemes.

Deploying large-scale wireless citywide networks with strong authentication mechanisms has received considerable interest in industry and academic circles. In this paper, we present modified Transport Layer Security (TLS) protocols which leverage Trusted Platform Module (TPM) technologies to achieve both user and device authentication. The first protocol leverages TPM attestation capabilities, while the other uses TPM sealed storage to achieve our goals. The proposed user and device authentication schemes can provide mutual proof between supplicants and servers not only on Wi-Fi and WiMAX interworked wireless cities, but also on any heterogeneous wireless networks which is based on the Extensible Authentication Protocol.

Group communication is inherently a social activity. However, existing protocols for group key establishment often fail to consider important social dynamics. This paper examines the human requirements for wireless group key establishment. We identify seven social and situational factors which impact group formation. Using these factors, we examine the requirements of four common classes of group communications. Each scenario imposes a unique set of requirements on wireless group key establishment.

Article An inquiry into the nature and causes of the wealth of internet miscreants Share on CCS '07: Proceedings of the 14th ACM conference on Computer and communications securityOctober 2007 Pages 375–388https://doi.org/10.1145/1315245.1315292Online:28 October 2007Publication History 66citation1,671DownloadsMetricsTotal Citations66Total Downloads1,671Last 12 Months59Last 6 weeks14 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

DoS attacks use IP spoofing to forge the source IP address of packets, and thereby hide the identity of the source. This makes it hard to defend against DoS attacks, so IP spoofing will still be used as an aggressive attack mechanism even under distributed attack environment. While many IP spoofing prevention techniques have been proposed, none have achieved widespread real-world use. One main reason is the lack of properties favoring incremental deployment, an essential component for the adoption of new technologies. A viable solution needs to be not only technically sound but also economically acceptable. An incrementally deploy-able protocol should have three properties: initial benefits for early adopters, incremental benefits for subsequent adopters, and effectiveness under partial deployment. Since no previous anti-spoofing solution satisfies all three of these properties, we propose a new mechanism called "BGP Anti-Spoofing Extension" (BASE). The BASE mechanism is an anti-spoofing protocol designed to fulfill the incremental deployment properties necessary for adoption in current Internet environments. Based on simulations we ran using a model of Internet AS connectivity, BASE shows desirable IP spoofing prevention capabilities under partial deployment. We find that just 30% deployment can drop about 97% of attack packets. Therefore, BASE not only provides adopters' benefit but also outperforms previous anti-spoofing mechanisms.

Secure sensor network communication protocols need to provide three basic properties: data secrecy, authentication, and replay protection. Secure sensor network link layer protocols such as Tiny-Sec [10] and ZigBee [24] enjoy significant attention in the community. However, TinySec achieves low energy consumption by reducing the level of security provided. In contrast, ZigBee enjoys high security, but suffers from high energy consumption.

Existing protocols for secure key establishment all rely on an unspecified mechanism for initially deploying secrets to sensor nodes. However, no commercially viable and secure mechanism exists for initial setup. Without a guarantee of secure key deployment, the traffic over a sensor network cannot be presumed secure.

Systems using capabilities to provide preferential service to selected flows have been proposed as a defense against large-scale network denial-of-service attacks. While these systems offer strong protection for established network flows, the Denial-of-Capability (DoC) attack, which prevents new capability-setup packets from reaching the destination, limits the value of these systems.

We propose SecVisor, a tiny hypervisor that ensures code integrity for commodity OS kernels. In particular, SecVisor ensures that only user-approved code can execute in kernel mode over the entire system lifetime. This protects the kernel against code injection attacks, such as kernel rootkits. SecVisor can achieve this propertyeven against an attacker who controls everything but the CPU, the memory controller, and system memory chips. Further, SecVisor can even defend against attackers with knowledge of zero-day kernel exploits.

We propose an architecture that allows code to execute in complete isolation from other software while trusting only a tiny software base that is orders of magnitude smaller than even minimalist virtual machine monitors. Our technique also enables more meaningful attestation than previous proposals, since only measurements of the security-sensitive portions of an application need to be included. We achieve these guarantees by leveraging hardware support provided by commodity processors from AMD and Intel that are shipping today.

We design an encryption scheme called Multi-dimensional Range Query over Encrypted Data (MRQED), to address the privacy concerns related to the sharing of network audit logs and various other applications. Our scheme allows a network gateway to encrypt summaries of network flows before submitting them to an untrusted repository. When network intrusions are suspected, an authority can release a key to an auditor, allowing the auditor to decrypt flows whose attributes (e.g., source and destination addresses, port numbers, etc.) fall within specific ranges. However, the privacy of all irrelevant flows are still preserved. We formally define the security for MRQED and prove the security of our construction under the decision bilinear Diffie-Hellman and decision linear assumptions in certain bilinear groups. We study the practical performance of our construction in the context of network audit logs. Apart from network audit logs, our scheme also has interesting applications for financial audit logs, medical privacy, untrusted remote storage, etc. In particular, we show that MRQED implies a solution to its dual problem, which enables investors to trade stocks through a broker in a privacypreserving manner.

In sensor networks, data aggregation is a vital primitive enabling efficient data queries. An on-site aggregator device collects data from sensor nodes and produces a condensed summary which is forwarded to the off-site querier, thus reducing the communication cost of the query. Since the aggregato r is on-site, it is vulnerable to physical compromise attacks. A compromised aggregator may report false aggregation results. Hence, it is essential that techniques are available to allow the querier to verify the integrity of the result returned by the aggregator node. We propose a novel framework for secure information aggregation in sensor networks. By constructing efficient random sampling mechanisms and interactive proofs, we enable the querier to verify that the answer given by the aggregator is a good approximation of the true value, even when the aggregator and a fraction of the sensor nodes are corrupted. In particular, we present efficient protocols for secure computation of the median and average of the measurements, for the estimation of the network size, for finding the minimum and maximum sensor reading, and for random sampling and leader election. Our protocols require only sublinear communication between the aggregator and the user.

In-network aggregation is an essential primitive for performing queries on sensor network data. However, most aggregation algorithms assume that all intermediate nodes are trusted. In contrast, the standard threat model in sensor network security assumes that an attacker may control a fraction of the nodes, which may misbehave in an arbitrary (Byzantine) manner.We present the first algorithm for provably secure hierarchical in-network data aggregation. Our algorithm is guaranteed to detect any manipulation of the aggregate by the adversary beyond what is achievable through direct injection of data values at compromised nodes. In other words, the adversary can never gain any advantage from misrepresenting intermediate aggregation computations. Our algorithm incurs only O(Δ log2 n) node congestion, supports arbitrary tree-based aggregator topologies and retains its resistance against aggregation manipulation in the presence of arbitrary numbers of malicious nodes. The main algorithm is based on performing the sum aggregation securely by first forcing the adversary to commit to its choice of intermediate aggregation results, and then having the sensor nodes independently verify that their contributions to the aggregate are correctly incorporated. We show how to reduce secure median, count, and average to this primitive.

The deployment of sensor networks in security- and safety-critical environments requires secure communication primitives. In this paper, we design, implement, and evaluate a new secure routing protocol for sensor networks. Our protocol requires no special hardware and provides message delivery even in an environment with active adversaries. We adopt a clean-slate approach and design a new sensor network routing protocol with security and efficiency as central design parameters. Our protocol is efficient yet highly resilient to active attacks. We demonstrate the performance of our algorithms with simulation results as well as an implementation on Telos sensor nodes.

Security is of critical importance for the successful deployment of sensor networks, since it can ensure properties such as data integrity, secrecy, and availability. We have the unique opportunity to ensure security even for early deployments of sensor networks, which could avoid alarming news articles and help fend off corporate and consumer security and privacy fears. In this talk, I will discuss the most important security issues in sensor networks, present realistic attacker models, comment on industry trends for achieving security, and highlight present and future research directions.

Despite the existence of several secure BGP routing protocols, there has been little progress to date on actual adoption. Although feasibility for widespread adoption remains the greatest hurdle for BGP security, there has been little quantitative research into what properties contribute the most to the adoptability of a security scheme. In this paper, we provide a model for assessing the adoptability of a secure BGP routing protocol. We perform this evaluation by simulating incentives compatible adoption decisions of ISPs on the Internet under a variety of assumptions. Our results include: (a) the existence of a sharp threshold, where, if the cost of adoption is below the threshold, complete adoption takes place, while almost no adoption takes place above the threshold; (b) under a strong attacker model, adding a single hop of path authentication to origin authentication yields similar adoptability characteristics as a full path security scheme; (c) under a weaker attacker model, adding full path authentication (e.g., via S-BGP [9]) significantly improves the adoptability of BGP security over weaker path security schemes such as soBGP [16]. These results provide insight into the development of more adoptable secure BGP protocols and demonstrate the importance of studying adoptability of protocols.

As mobile ad hoc network applications are deployed, security emerges as a central requirement. In this paper, we introduce the wormhole attack, a severe attack in ad hoc networks that is particularly challenging to defend against. The wormhole attack is possible even if the attacker has not compromised any hosts, and even if all communication provides authenticity and confidentiality. In the wormhole attack, an attacker records packets (or bits) at one location in the network, tunnels them (possibly selectively) to another location, and retransmits them there into the network. The wormhole attack can form a serious threat in wireless networks, especially against many ad hoc network routing protocols and location-based wireless security systems. For example, most existing ad hoc network routing protocols, without some mechanism to defend against the wormhole attack, would be unable to find routes longer than one or two hops, severely disrupting communication. We present a general mechanism, called packet leashes, for detecting and, thus defending against wormhole attacks, and we present a specific protocol, called TIK, that implements leashes. We also discuss topology-based wormhole detection, and show that it is impossible for these approaches to detect some wormhole topologies.

Today's Internet hosts are threatened by large-scale distributed denial-of-service (DDoS) attacks. The path identification (Pi) DDoS defense scheme has recently been proposed as a deterministic packet marking scheme that allows a DDoS victim to filter out attack packets on a per packet basis with high accuracy after only a few attack packets are received (Yaar , 2003). In this paper, we propose the StackPi marking, a new packet marking scheme based on Pi, and new filtering mechanisms. The StackPi marking scheme consists of two new marking methods that substantially improve Pi's incremental deployment performance: Stack-based marking and write-ahead marking. Our scheme almost completely eliminates the effect of a few legacy routers on a path, and performs 2–4 times better than the original Pi scheme in a sparse deployment of Pi-enabled routers. For the filtering mechanism, we derive an optimal threshold strategy for filtering with the Pi marking. We also develop a new filter, the PiIP filter, which can be used to detect Internet protocol (IP) spoofing attacks with just a single attack packet. Finally, we discuss in detail StackPi's compatibility with IP fragmentation, applicability in an IPv6 environment, and several other important issues relating to potential deployment of StackPi.

The establishment of shared cryptographic keys between communicating neighbor nodes in sensor networks is a challenging problem due to the unsuitability of asymmetric key cryptography for these resource-constrained platforms. A range of symmetric-key distribution protocols exist, but these protocols do not scale effectively to large sensor networks. For a given level of security, each protocol incurs a linearly increasing overhead in either communication cost per node or memory per node. We describe peer intermediaries for key establishment (PIKE), a class of key-establishment protocols that involves using one or more sensor nodes as a trusted intermediary to facilitate key establishment. We show that, unlike existing key-establishment protocols, both the communication and memory overheads of PIKE protocols scale sub-linearly (O(/spl radic/n)) with the number of nodes in the network yet achieving higher security against node compromise than other protocols.

Traceback mechanisms are a critical part of the defense against IP spoofing and DoS attacks, as well as being of forensic value to law enforcement. Currently proposed IP traceback mechanisms are inadequate to address the traceback problem for the following reasons: they require DDoS victims to gather thousands of packets to reconstruct a single attack path; they do not scale to large scale distributed DoS attacks; and they do not support incremental deployment. We propose fast Internet traceback (FIT), a new packet marking approach that significantly improves IP traceback in several dimensions: (1) victims can identify attack paths with high probability after receiving only tens of packets, a reduction of 1-3 orders of magnitude compared to previous packet marking schemes; (2) FIT performs well even in the presence of legacy routers, allowing every FIT-enabled router in path to be identified; and (3) FIT scales to large distributed attacks with thousands of attackers. Compared with previous packet marking schemes, FIT represents a step forward in performance and deployability.

We propose a primitive, called Pioneer, as a first step towards verifiable code execution on untrusted legacy hosts. Pioneer does not require any hardware support such as secure co-processors or CPU-architecture extensions. We implement Pioneer on an Intel Pentium IV Xeon processor. Pioneer can be used as a basic building block to build security systems. We demonstrate this by building a kernel rootkit detector.

Current mechanisms for authenticating communication between devices that share no prior context are inconvenient for ordinary users, without the assistance of a trusted authority. We present and analyze seeing-is-believing, a system that utilizes 2D barcodes and camera-telephones to implement a visual channel for authentication and demonstrative identification of devices. We apply this visual channel to several problems in computer security, including authenticated key exchange between devices that share no prior context, establishment of a trusted path for configuration of a TCG-compliant computing platform, and secure device configuration in the context of a smart home.

So far sensor network broadcast protocols assume a trustworthy environment. However in safety and mission-critical sensor networks this assumption may not be valid and some sensor nodes might be adversarial. In these environments, malicious sensor nodes can deprive other nodes from receiving a broadcast message. We call this attack a denial-of-message attack (DoM). In this paper we model and analyze this attack, and present countermeasures. We present SIS, a secure implicit sampling scheme that permits a broadcasting base station to probabilistically detect the failure of nodes to receive its broadcast, even if these failures result from an attacker motivated to induce these failures undetectably. SIS works by eliciting authenticated acknowledgments from a subset of nodes per broadcast, where the subset is unpredictable to the attacker and tunable so as to mitigate acknowledgment implosion on the base station. We use a game-theoretic approach to evaluate this scheme in the face of an optimal attacker that attempts to maximize the number of nodes it denies the broadcast while remaining undetected by the base station, and show that SIS significantly constrains such an attacker even in sensor networks exhibiting high intrinsic loss rates. We also discuss extensions that permit more targeted detection capabilities.

The low-cost, off-the-shelf hardware components in unshielded sensor-network nodes leave them vulnerable to compromise. With little effort, an adversary may capture nodes, analyze and replicate them, and surreptitiously insert these replicas at strategic locations within the network. Such attacks may have severe consequences; they may allow the adversary to corrupt network data or even disconnect significant parts of the network. Previous node replication detection schemes depend primarily on centralized mechanisms with single points of failure, or on neighborhood voting protocols that fail to detect distributed replications. To address these fundamental limitations, we propose two new algorithms based on emergent properties (Gligor (2004)), i.e., properties that arise only through the collective action of multiple nodes. Randomized multicast distributes node location information to randomly-selected witnesses, exploiting the birthday paradox to detect replicated nodes, while line-selected multicast uses the topology of the network to detect replication. Both algorithms provide globally-aware, distributed node-replica detection, and line-selected multicast displays particularly strong performance characteristics. We show that emergent algorithms represent a promising new approach to sensor network security; moreover, our results naturally extend to other classes of networks in which nodes can be captured, replicated and re-inserted by an adversary.

In this paper we propose BIND (binding instructions and data), a fine-grained attestation service for securing distributed systems. Code attestation has recently received considerable attention in trusted computing. However, current code attestation technology is relatively immature. First, due to the great variability in software versions and configurations, verification of the hash is difficult. Second, the time-of-use and time-of-attestation discrepancy remains to be addressed, since the code may be correct at the time of the attestation, but it may be compromised by the time of use. The goal of BIND is to address these issues and make code attestation more usable in securing distributed systems. BIND offers the following properties: (1) BIND performs fine-grained attestation. Instead of attesting to the entire memory content, BIND attests only to the piece of code we are concerned about. This greatly simplifies verification. (2) BIND narrows the gap between time-of-attestation and time-of-use. BIND measures a piece of code immediately before it is executed and uses a sandboxing mechanism to protect the execution of the attested code. (3) BIND ties the code attestation with the data that the code produces, such that we can pinpoint what code has been run to generate that data. In addition, by incorporating the verification of input data integrity into the attestation, BIND offers transitive integrity verification, i.e., through one signature, we can vouch for the entire chain of processes that have performed transformations over a piece of data. BIND offers a general solution toward establishing a trusted environment for distributed system designers.

Key management has two important aspects: key distribution, which describes how to disseminate secret information to the principals so that secure communications can be initiated, and key revocation, which describes how to remove secrets that may have been compromised. Key management in sensor networks face constraints of large scale, lack of a priori information about deployment topology, and limitations of sensor node hardware. While key distribution has been studied extensively in recent works, the problem of key and node revocation in sensor networks has received relatively little attention. Yet, revocation protocols that function correctly in the presence of active adversaries pretending to be legitimate protocol participants via compromised sensor nodes are essential. In their absence, an adversary could take control of the sensor network's operation by using compromised nodes which retain their network connectivity for extended periods of time. In this paper, we present an overview of key-distribution methods in sensor networks and their salient features to provide context for understanding key and node revocation. Then, we define basic properties that distributed sensor-node revocation protocols must satisfy and present a protocol for distributed node revocation that satisfies these properties under general assumptions and a standard attacker model.

Future distributed systems may include large self-organizing networks of locally communicating sensor nodes, any small number of which may be subvened by an adversary. Providing security for these sensor networks is important, but the problem is complicated by the fact that managing cryptographic key material is hard: low-cost nodes are neither tamper-proof nor capable of performing public key cryptography efficiently. We show how the key distribution problem can be dealt with in environments with a partially present, passive adversary: a node wishing to communicate securely with other nodes simply generates a symmetric key and sends it in the clear to its neighbours. Despite the apparent insecurity of this primitive, we can use mechanisms for key updating, multipath secrecy amplification and multihop key propagation to build up extremely resilient trust networks where at most a fixed proportion of communications links can be eavesdropped. We discuss applications in which this assumption is sensible. Many systems must perforce cope with principals who are authenticated weakly, if at all; the resulting issues have often been left in the 'too hard' tray. One particular interest of sensor networks is that they present a sufficiently compact and tractable version of this problem. We can perform quantitative analyses and simulations of alternative strategies, some of which we present here. We also hope that This work may start to challenge the common belief that authentication is substantially about bootstrapping trust. We argue that, in distributed systems where the opponent can subvert any small proportion of nodes, it is more economic to invest in resilience than in bootstrapping.

Security is important for many sensor network applications. A particularly harmful attack against sensor and ad hoc networks is known as the Sybil attack [6], where a node illegitimately claims multiple identities. This paper systematically analyzes the threat posed by the Sybil attack to wireless sensor networks. We demonstrate that the attack can be exceedingly detrimental to many important functions of the sensor network such as routing, resource allocation, misbehavior detection, etc. We establish a classification of different types of the Sybil attack, which enables us to better understand the threats posed by each type, and better design countermeasures against each type. We then propose several novel techniques to defend against the Sybil attack, and analyze their effectiveness quantitatively.

Designing a flexible, yet secure communication infrastructure has long been an elusive goal. Most of the proposals that seek to address the problem of flexibility have opened up the system for new forms of attacks. In this paper, we consider one particular proposal, i3 [2], a flexible indirection infrastructure that provides natural support for a multitude of communication primitives such as multicast, anycast and mobility. We systematically identify the attacks on i3, and propose techniques that address the security problems without sacrificing the flexibility that i3 offers. Our techniques, ranging from cryptographically constraining the forwarding entries to challenge-based mechanisms for inserting forwarding entries, while being simple, both conceptually and to implement, make most of the attacks provably hard. We believe that this paper represents an important step towards designing communication infrastructures that are both secure and flexible.

As our economy and critical infrastructure increasingly relies on the Internet, the insecurity of the underlying border gateway routing protocol (BGP) stands out as the Achilles heel. Recent misconfigurations and attacks have demonstrated the brittleness of BGP. Securing BGP has become a priority.In this paper, we focus on a viable deployment path to secure BGP. We analyze security requirements, and consider tradeoffs of mechanisms that achieve the requirements. In particular, we study how to secure BGP update messages against attacks. We design an efficient cryptographic mechanism that relies only on symmetric cryptographic primitives to guard an ASPATH from alteration, and propose the Secure Path Vector (SPV) protocol. In contrast to the previously proposed S-BGP protocol, SPV is around 22 times faster. With the current effort to secure BGP, we anticipate that SPV will contribute several alternative mechanisms to secure BGP, especially for the case of incremental deployments.

We expect a future where we are surrounded by embedded devices, ranging from Java-enabled cell phones to sensor networks and smart appliances. An adversary can compromise our privacy and safety by maliciously modifying the memory contents of these embedded devices. In this paper, we propose a softWare-based attestation technique (SWATT) to verify the memory contents of embedded devices and establish the absence of malicious changes to the memory contents. SWATT does not need physical access to the device's memory, yet provides memory content attestation similar to TCG or NGSCB without requiring secure hardware. SWATT can detect any change in memory contents with high probability, thus detecting viruses, unexpected configuration settings, and Trojan Horses. To circumvent SWATT, we expect that an attacker needs to change the hardware to hide memory content changes. We present an implementation of SWATT in off-the-shelf sensor network devices, which enables us to verify the contents of the program memory even while the sensor node is running.

One of the fundamental limitations of the Internet is the inability of a packet flow recipient to halt disruptive flows before they consume the recipient's network link resources. Critical infrastructures and businesses alike are vulnerable to DoS attacks or flash-crowds that can incapacitate their networks with traffic floods. Unfortunately, current mechanisms require per-flow state at routers, ISP collaboration, or the deployment of an overlay infrastructure to defend against these events. In this paper, we present SIFF, a Stateless Internet Flow Filter, which allows an end-host to selectively stop individual flows from reaching its network, without any of the common assumptions listed above. We divide all network traffic into two classes, privileged (prioritized packets subject to recipient control) and unprivileged (legacy traffic). Privileged channels are established through a capability exchange handshake. Capabilities are dynamic and verified statelessly by the routers in the network, and can be revoked by quenching update messages to an offending host. SIFF is transparent to legacy clients and servers, but only updated hosts will enjoy the benefits of it.

In recent years, collaborative and group-oriented applications and protocols have gained popularity. These applications typically involve communication over open networks; security thus is naturally an important requirement. Group key management is one of the basic building blocks in securing group communication. Most prior research in group key management focused on minimizing computation overhead, in particular minimizing expensive cryptographic operations. However, continued advances in computing power have not been matched by a decrease in network communication delay. Thus, communication latency, especially in high-delay long-haul networks, increasingly dominates the key setup latency, replacing computation delay as the main latency contributor. Hence, there is a need to minimize the size of messages and, especially, the number of rounds in cryptographic protocols. Since most previously proposed group key management techniques optimize computational (cryptographic) overhead, they are particularly impacted by high communication delay. In this work, we discuss and analyze a specific group key agreement technique which supports dynamic group membership and handles network failures, such as group partitions and merges. This technique is very communication-efficient and provably secure against hostile eavesdroppers as well as various other attacks specific to group settings. Furthermore, it is simple, fault-tolerant, and well-suited for high-delay networks.

Secure and reliable group communication is an active area of research. Its popularity is fueled by the growing importance of group-oriented and collaborative applications. The central research challenge is secure and efficient group key management. While centralized methods are often appropriate for key distribution in large multicast-style groups, many collaborative group settings require distributed key agreement techniques. This work investigates a novel group key agreement approach which blends key trees with Diffie--Hellman key exchange. It yields a secure protocol suite called Tree-based Group Diffie--Hellman (TGDH) that is both simple and fault-tolerant. Moreover, the efficiency of TGDH appreciably surpasses that of prior art.

As mobile ad hoc network applications are deployed, security emerges as a central requirement. In this paper, we introduce the wormhole attack, a severe attack in ad hoc networks that is particularly challenging to defend against. The wormhole attack is possible even if the attacker has not compromised any hosts, and even if all communication provides authenticity and confidentiality. In the wormhole attack, an attacker records packets (or bits) at one location in the network, tunnels them (possibly selectively) to another location, and retransmits them there into the network. The wormhole attack can form a serious threat in wireless networks, especially against many ad hoc network routing protocols and location-based wireless security systems. For example, most existing ad hoc network routing protocols, without some mechanism to defend against the wormhole attack, would be unable to find routes longer than one or two hops, severely disrupting communication. We present a new, general mechanism, called packet leashes, for detecting and thus defending against wormhole attacks, and we present a specific protocol, called TIK, that implements leashes.

Sensor networks promise viable solutions to many monitoring problems. However, the practical deployment of sensor networks faces many challenges imposed by real-world demands. Sensor nodes often have limited computation and communication resources and battery power. Moreover, in many applications sensors are deployed in open environments, and hence are vulnerable to physical attacks, potentially compromising the sensor's cryptographic keys.One of the basic and indispensable functionalities of sensor networks is the ability to answer queries over the data acquired by the sensors. The resource constraints and security issues make designing mechanisms for information aggregation in large sensor networks particularly challenging.In this paper, we propose a novel framework for secure information aggregation in large sensor networks. In our framework certain nodes in the sensor network, called aggregators, help aggregating information requested by a query, which substantially reduces the communication overhead. By constructing efficient random sampling mechanisms and interactive proofs, we enable the user to verify that the answer given by the aggregator is a good approximation of the true value even when the aggregator and a fraction of the sensor nodes are corrupted. In particular, we present efficient protocols for secure computation of the median and the average of the measurements, for the estimation of the network size, and for finding the minimum and maximum sensor reading. Our protocols require only sublinear communication between the aggregator and the user. To the best of our knowledge, this paper is the first on secure information aggregation in sensor networks that can handle a malicious aggregator and sensor nodes.

Key establishment in sensor networks is a challenging problem because asymmetric key cryptosystems are unsuitable for use in resource constrained sensor nodes, and also because the nodes could be physically compromised by an adversary. We present three new mechanisms for key establishment using the framework of pre-distributing a random set of keys to each node. First, in the q-composite keys scheme, we trade off the unlikeliness of a large-scale network attack in order to significantly strengthen random key predistribution's strength against smaller-scale attacks. Second, in the multipath-reinforcement scheme, we show how to strengthen the security between any two nodes by leveraging the security of other links. Finally, we present the random-pairwise keys scheme, which perfectly preserves the secrecy of the rest of the network when any node is captured, and also enables node-to-node authentication and quorum-based revocation.

Distributed denial of service (DDoS) attacks continue to plague the Internet. Defense against these attacks is complicated by spoofed source IP addresses, which make it difficult to determine a packet's true origin. We propose Pi (short for path identifier), a new packet marking approach in which a path fingerprint is embedded in each packet, enabling a victim to identify packets traversing the same paths through the Internet on a per packet basis, regardless of source IP address spoofing. Pi features many unique properties. It is a per-packet deterministic mechanism: each packet traveling along the same path carries the same identifier This allows the victim to take a proactive role in defending against a DDoS attack by using the Pi mark to filter out packets matching the attackers' identifiers on a per packet basis. The Pi scheme performs well under large-scale DDoS attacks consisting of thousands of attackers, and is effective even when only half the routers in the Internet participate in packet marking. Pi marking and filtering are both extremely lightweight and require negligible state. We use traceroute maps of real Internet topologies (e.g. CAIDA's Skitter (2000) and Burch and Cheswick's Internet Map (1999, 2002)) to simulate DDoS attacks and validate our design.

a secure on-demand routing protocol for ad hoc networks.

We introduce the BiBa signature scheme, a new signature construction that uses one-way functions without trapdoors. BiBa features a low verification overhead and a relatively small signature size. In comparison to other one-way function based signature schemes, BiBa has smaller signatures and is at least twice as fast to verify (which probably makes it one of the fastest signature scheme to date for verification). On the downside, the BiBa public key is large, and the signature generation overhead is higher than previous schemes based on one-way functions without trapdoors (although it can be trivially parallelized).One of the main challenges of securing broadcast communication is source authentication, which allows all receivers to verify the origin of the data. An ideal broadcast authentication protocol should be efficient for the sender and the receiver, have a small communication overhead, allow the receiver to authenticate each individual packet, provide perfect robustness to packet loss, scale to large numbers of receivers, and provide instant authentication (no buffering of data at the sender or receiver side). We are not aware of any previous protocol that satisfies all these properties. We present the BiBa broadcast authentication protocol, a new construction based on the BiBa signature, that achieves all our desired properties, with the tradeoff that it requires a moderate computation overhead for the sender to generate the authentication information, and that it requires loose time synchronization between the sender and receivers.

Defending against distributed denial-of-service attacks is one of the hardest security problems on the Internet today. One difficulty to thwart these attacks is to trace the source of the attacks because they often use incorrect, or spoofed IP source addresses to disguise the true origin. In this paper, we present two new schemes, the advanced marking scheme and the authenticated marking scheme, which allow the victim to trace-back the approximate origin of spoofed IP packets. Our techniques feature low network and router overhead, and support incremental deployment. In contrast to previous work, our techniques have significantly higher precision (lower false positive rate) and fewer computation overhead for the victim to reconstruct the attack paths under large scale distributed denial-of-service attacks. Furthermore the authenticated marking scheme provides efficient authentication of routers' markings such that even a compromised router cannot forge or tamper markings from other uncompromised routers.

Increasing numbers of economic transactions are conducted through on-line auctions. Nevertheless, most current auction implementations fail to address important security concerns. In particular, most auction systems force buyers and sellers to trust the auctioneer; alternative secure systems are inflexible and have a high computational and/or communication overhead. To overcome these limitations, we propose a secure auction marketplace (SAM) architecture, based on the recently available tool of high-performance, programmable secure coprocessors. Unlike previous schemes, this approach provides a general framework that can incorporate arbitrary auction schemes by using different evaluation programs, as well as provide complex security properties by using the secure coprocessor and our auction protocols. Our approach features strong security guarantees for the buyers and sellers without trusting the auctioneer, precise definition of the information disclosed during and after the auction, and high exibility to adapt to new types of auctions.

As sensor networks edge closer towards wide-spread deployment, security issues become a central concern. So far, much research has focused on making sensor networks feasible and useful, and has not concentrated on security.

Secure media broadcast over the Internet poses unique security challenges. One problem is access control to a large number of subscribers in a public broadcast. A common solution is to encrypt the broadcast data and to disclose the decryption key to legitimate receivers only. However, how do we securely and efficiently establish a shared secret among the legitimate receivers? And most importantly, how can we efficiently update the group key securely if receivers join or leave? How can we provide reliability for key update messages in a way that scales up to large groups? Recent research makes substantial progress to address these challenges. Current schemes feature efficient key update mechanisms assuming that the key updates are communicated reliably to the receivers. In practice, however the principal impediment to achieve a scalable system is to distribute the key updates reliably to all receivers. We have designed and implemented ELK, a novel key distribution protocol, to address these challenges with the following features: ELK features perfectly reliable, super-efficient member joins; ELK uses smaller key update messages than previous protocols; ELK features a mechanism that allows short hint messages to be used for key recovery allowing a tradeoff of communication overhead with member computation; ELK proposes to append a small amount of key update information to data packets, such that the majority of receivers can recover from lost key update messages; and ELK allows to trade off security with communication overhead.

We propose a new efficient automatic verification technique, Athena, for security protocol analysis. It uses a new efficient representation – our extension to the Strand Space Model, and utilizes techniques from both model checking and theorem proving approaches. Athena is fully automatic and is ab le to prove the correctness of many security protocols with arbitrary number of concurrent runs. The run time for a typical protocol from the literature, like the Needham–Schroeder protocol, is often a fraction of a second. Athena exploits several different techniques that enable it to analyze infinite sets of protocol runs and achieve such efficiency. Our extended Strand Space Model is a natural and efficient representation for the problem domain. The security properties are specified in a simple logic which permits both efficient proof search algorithms and has enough expressive power to specify interesting properties. The automatic proof search procedure borrows some efficient techniques from both model checking and theorem proving. We believe that it is the right combination of the new compact representation and all the techniques that actually makes Athena successful in fast and automatic verification of security protocols.

Secure group communication is an increasingly popular research area having received much attention in recent years. The fundamental challenge revolves around secure and efficient group key management. While centralized methods are often appropriate for key distribution in large groups, many collaborative group settings require distributed key agreement techniques. This work investigates a novel approach to group key agreement by blending binary key trees with Diffie-Hellman key exchange. The resultant protocol suite is very simple, secure and fault-tolerant. Moreover, its efficiency surpasses that of prior art.

We describe our new results in developing and extending Automatic Protocol Generation (APG), an approach to automatically generate security protocols. We explore two-party mutual authentication and key agreement protocols, with a trusted third party (TTP) which shares a symmetric key with each of the two principals. During the process, we experienced the challenge of a gigantic protocol space. Facing this challenge, we develop more powerful reduction techniques for the protocol generator. We also develop new pruning theorems and probabilistic methods of picking goal orderings for the protocol screener, Athena, which greatly improve the efficiency and worst-case performance of Athena. In our first experiment, APG found new protocols for two-party mutual authentication with a TTP using symmetric keys. In our second experiment, APG also found new protocols for three different sets of security properties for two-party authentication and key agreement. Our new list of security properties for key agreement also uncovered an undocumented deficiency in the Yahalom protocol.

Multicast stream authentication and signing is an important and challenging problem. Applications include the continuous authentication of radio and TV Internet broadcasts, and authenticated data distribution by satellite. The main challenges are fourfold. First, authenticity must be guaranteed even when only the sender of the data is trusted. Second, the scheme needs to scale to potentially millions of receivers. Third, streamed media distribution can have high packet loss. Finally the system needs to be efficient to support fast packet rates. We propose two efficient schemes, TESLA and EMSS, for secure lossy multicast streams. TESLA (Timed Efficient Stream Loss-tolerant Authentication), offers sender authentication, strong loss robustness, high scalability and minimal overhead at the cost of loose initial time synchronization and slightly delayed authentication. EMSS (Efficient Multi-chained Stream Signature), provides nonrepudiation of origin, high loss resistance, and low overhead, at the cost of slightly delayed verification.

It is desirable to store data on data storage servers such as mail servers and file servers in encrypted form to reduce security and privacy risks. But this usually implies that one has to sacrifice functionality for security. For example, if a client wishes to retrieve only documents containing certain words, it was not previously known how to let the data storage server perform the search and answer the query, without loss of data confidentiality. We describe our cryptographic schemes for the problem of searching on encrypted data and provide proofs of security for the resulting crypto systems. Our techniques have a number of crucial advantages. They are provably secure: they provide provable secrecy for encryption, in the sense that the untrusted server cannot learn anything about the plaintext when only given the ciphertext; they provide query isolation for searches, meaning that the untrusted server cannot learn anything more about the plaintext than the search result; they provide controlled searching, so that the untrusted server cannot search for an arbitrary word without the user's authorization; they also support hidden queries, so that the user may ask the untrusted server to search for a secret word without revealing the word to the server. The algorithms presented are simple, fast (for a document of length n, the encryption and search algorithms only need O(n) stream cipher and block cipher operations), and introduce almost no space and communication overhead, and hence are practical to use today.