Logging is a key mechanism in the security of computer systems. Beyond supporting important forward security properties, it is critical that logging withstands both failures and intentional tampering to prevent subtle attacks leaving the system in an inconsistent state with inconclusive evidence. We propose new techniques combining forward security with crash recovery for secure log data storage. As the support of specifically forward integrity and the online nature of logging prevent the use of conventional coding, we propose and analyze a coding scheme resolving these unique design constraints. Specifically, our coding enables forward integrity, online encoding, and most importantly a constant number of operations per encoding. It adds a new log item by 𝖷𝖮𝖱 ing it to k cells of a table. If up to a certain threshold of cells is modified by the adversary, or lost due to a crash, we still guarantee recovery of all stored log items. The main advantage of the coding scheme is its efficiency and compatibility with forward integrity. The key contribution of the paper is the use of spectral graph theory techniques to prove that k is constant in the number n of all log items ever stored and small in practice, e.g., k = 5. Moreover, we prove that to cope with up to \(\sqrt {n}\) modified or lost log items, storage expansion is constant in n and small in practice. For k = 5, the size of the table is only 12% more than the simple concatenation of all n items. We propose and evaluate original techniques to scale the computation cost of recovery to several GBytes of security logs. We instantiate our scheme into an abstract data structure which allows to either detect adversarial modifications to log items or treat modifications like data loss in a system crash. The data structure can recover lost log items, thereby effectively reverting adversarial modifications.

We introduce and investigate the privacy-preserving version of collaborative data cleaning. With collaborative data cleaning, two parties want to reconcile their data sets to filter out badly classified, misclassified data items. In the privacy-preserving (private) version of data cleaning, the additional security goal is that parties should only learn their misclassified data items, but nothing else about the other party’s data set. The problem of private data cleaning is essentially a variation of private set intersection (PSI), and one could employ recent circuit-PSI techniques to compute misclassifications with privacy. However, we design, analyze, and implement three new protocols tailored to the specifics of private data cleaning that outperform a circuit-PSI-based approach. With the first protocol, we exploit the idea that a small additional leakage (the differentially private size of the intersection of data items) allows for a reduction in complexity over circuit-PSI. The other two protocols convert the problem of finding a mismatch in data classifications into finding a match, and then follow the standard technique of using oblivious pseudorandom functions (OPRF) for computing PSI. Depending on the number of data classes, this leads to a concrete runtime improvement over circuit-PSI.

We introduce and investigate the privacy-preserving version of collaborative data cleaning. With collaborative data cleaning, two parties want to reconcile their data sets to filter out badly classified, misclassified data items. In the privacy-preserving (private) version of data cleaning, the additional security goal is that parties should only learn their misclassified data items, but nothing else about the other party’s data set. The problem of private data cleaning is essentially a variation of private set intersection (PSI), and one could employ recent circuit-PSI techniques to compute misclassifications with privacy. However, we design, analyze, and implement three new protocols tailored to the specifics of private data cleaning that outperform a circuit-PSI-based approach. With the first protocol, we exploit the idea that a small additional leakage (the differentially private size of the intersection of data items) allows for a reduction in complexity over circuit-PSI. The other two protocols convert the problem of finding a mismatch in data classifications into finding a match, and then follow the standard technique of using oblivious pseudorandom functions (OPRF) for computing PSI. Depending on the number of data classes, this leads to a concrete runtime improvement over circuit-PSI.

In 2020, Apple introduced the Find My protocol, which allows owners to crowdsource the location of their lost Apple devices even when the lost device has no active internet connection (e.g., Wi-Fi, Cellular). The Find My protocol is the basis for Apple's AirTag tracking tokens which were released later in 2021. In order to prevent malicious use of these tokens, Apple also implemented ``item safety alerts'' which can warn a person if they are being tracked by an AirTag without their knowledge. However, researchers have recently identified several shortcomings with these alerts that allow modified AirTags to track unsuspecting victims indefinitely without being detected. Making matters worse, while recognizing the observed malicious use of AirTags, news reports, Apple's press releases, and their intended anti-tracking improvements to the protocol do not consider the potential surreptitious use of the Find My network by custom built AirTag clones. In this work, we present an improved Find My protocol which effectively limits the capabilities of malicious AirTags and guarantees that they can be detected while tracking. We accomplish this by adding additional cryptographic verification into the protocol, which restricts tags to only using a bounded set of keys while tracking. In order to maintain - and exceed - the privacy guarantees of the current Find My protocol, we make use of specialized partial blind signatures. To demonstrate the practicality of this protocol, we implement it end-to-end using a programmable device with the same SoC (nRF52832) as in current AirTags. We also benchmark the cryptographic operations of our protocol and show that they require only modest overhead during the initial pairing procedure.

We consider the problem of a client querying an encrypted binary tree structure, outsourced to an untrusted server. While the server must not learn the contents of the binary tree, we also prevent the client from maliciously crafting a query that traverses the tree out-of-order. That is, the client should not be able to retrieve nodes outside one contiguous path from the root to a leaf. Finally, the server should not learn which path the client accesses, but is guaranteed that the access corresponds to one valid path in the tree. This is an extension of protocols such as structured encryption, where it is only guaranteed that the tree's encrypted data remains hidden from the server.

Drones are increasingly associated with incidents disturbing air traffic at airports, invading privacy, and even terrorism. Wireless Direction of Arrival (DoA) techniques, such as the MUSIC algorithm, can localize drones, but deploying a system that systematically localizes RF emissions can lead to intentional or unintentional (e.g., if compromised) abuse. Multi-Party Computation (MPC) provides a solution for controlled computation of the elevation of RF emissions, only revealing estimates when some conditions are met, such as when the elevation exceeds a specified threshold. However, we show that a straightforward implementation of MUSIC, which relies on costly computation of complex matrix operations such as eigendecomposition, in state of the art MPC frameworks is extremely inefficient requiring over 20 seconds to achieve the weakest security guarantees. In this work, we develop a set of MPC optimizations and extensions of MUSIC. We extensively evaluate our techniques in several MPC protocols achieving a speedup of 300-500 times depending on the security model and specific technique used. For instance a Malicious Shamir execution providing security against malicious adversaries enables 536 DoA estimations per second, making it practical for use in real-world setups.

Over-Threshold Multi-Party Private Set Intersection (OT-MP-PSI) is the problem where several parties, each holding a set of elements, want to know which elements appear in at least t sets, for a certain threshold t, without revealing any information about elements that do not meet this threshold. This problem has many practical applications, but current solutions require a number of expensive operations exponential in t and thus are impractical.

We focus on securely computing the ranks of sealed integers distributed among n parties. For example, we securely compute the largest or smallest integer, the median, or in general the kth-ranked integer. Such computations are a useful building block to securely implement a variety of sealed-bid auctions. Our objective is efficiency, specifically low interactivity between parties to support blockchains or other scenarios where multiple rounds are time-consuming. Hence, we dismiss powerful, yet highly-interactive MPC frameworks and propose BOREALIS, a special-purpose protocol for secure computation of ranks among integers. BOREALIS uses additively homomorphic encryption to implement core comparisons, but computes under distinct keys, chosen by each party to optimize the number of rounds. By carefully combining cryptographic primitives, such as ECC Elgamal encryption, encrypted comparisons, ciphertext blinding, secret sharing, and shuffling, BOREALIS sets up systems of multi-scalar equations which we efficiently prove with Groth-Sahai ZK proofs. Therewith, BOREALIS implements a multi-party computation of pairwise comparisons and rank zero-knowledge proofs secure against malicious adversaries. BOREALIS completes in at most 4 rounds which is constant in both bit length l of integers and the number of parties n. This is not only asymptotically optimal, but surpasses generic constant-round secure multi-party computation protocols, even those based on shared-key fully homomorphic encryption. Furthermore, our implementation shows that BOREALIS is very practical. Its main bottleneck, ZK proof computations, is small in practice. Even for a large number of parties (n=200) and high-precision integers (l=32), computation time of all proofs is less than a single Bitcoin block interval.

The objective of the 3rd ACM Workshop on Information Sharing and Collaborative Security is to advance the scientific foundations for sharing security-related data. Improving information sharing remains an important theme in the computer security community. A number of new sharing communities have been formed. Also, so called "threat intelligence" originating from open, commercial or governmental sources has by now become an important, commonly used tool for detecting and mitigating attacks in organizations. Security vendors are offering novel technologies for sharing, managing and consuming such data. The OASIS Technical Committee for Cyber Threat Intelligence (CTI) is creating a standard for structured sharing of information. This is the largest TC within OASIS attesting to the broad interest in the topic. As progress in real-life deployment of information sharing makes clear, the creation, analysis, sharing, and effective use of security data continues to raise intriguing technical problems. Addressing these problems will be critical for the ultimate success of sharing efforts and will benefit greatly from the diverse knowledge and techniques the scientific community brings. The 3rd ACM Workshop on Information Sharing and Collaborative Security (WISCS'16) brings together experts and practitioners from academia, industry, and government to present innovative research, case studies, and legal and policy issues. WISCS'16 is held in Vienna, Austria on October 24, 2016 in conjunction with the 23rd ACM Conference on Computer and Communications Security (ACM CCS 2016).

Wi-Fi connectivity using open hotspots hosted on untrusted Access Points (APs) has been a staple of mobile network deployments for many years as mobile providers seek to offload smartphone traffic to Wi-Fi. Currently, the available hotspot solutions allow for mobility patterns and client identities to be monitored by the parties hosting the APs as well as by the underlying service provider. We propose a protocol and system that allows a service provider to authenticate its clients, and hides the client identity from both AP and service provider at the time of authentication. Particularly, the client is guaranteed that either the provider cannot do better than to guess their identity randomly or they obtain proof that the provider is trying to reveal their identity by using different keys. Our protocol is based on Private Information Retrieval (PIR) with an augmented cheating detection mechanism based on our extensions to the NTRU encryption scheme. The somewhat-homomorphic encryption makes auditing of multiple rows in a single query possible, and optimizes PIR for highly parallel GPU computations with the use of the Fast Fourier Transform (FFT).

There have been several attempts recently at using homomorphic encryption to increase the efficiency of Oblivious RAM protocols. One of the most successful has been Onion ORAM, which achieves O(1) communication overhead with polylogarithmic server computation. However, it has two drawbacks. It requires a large block size of B = Ω(log6 N) with large constants. Moreover, while it only needs polylogarithmic computation complexity, that computation consists mostly of expensive homomorphic multiplications. In this work, we address these problems and reduce the required block size to Ω(log4 N). We remove most of the homomorphic multiplications while maintaining O(1) communication complexity. Our idea is to replace their homomorphic eviction routine with a new, much cheaper permute-and-merge eviction which eliminates homomorphic multiplications and maintains the same level of security. In turn, this removes the need for layered encryption that Onion ORAM relies on and reduces both the minimum block size and server computation.

Abstract We revisit the problem of privacy-preserving range search and sort queries on encrypted data in the face of an untrusted data store. Our new protocol RASP has several advantages over existing work. First, RASP strengthens privacy by ensuring forward security: after a query for range [a, b], any new record added to the data store is indistinguishable from random, even if the new record falls within range [a, b]. We are able to accomplish this using only traditional hash and block cipher operations, abstaining from expensive asymmetric cryptography and bilinear pairings. Consequently, RASP is highly practical, even for large database sizes. Additionally, we require only cloud storage and not a computational cloud like related works, which can reduce monetary costs significantly. At the heart of RASP, we develop a new update-oblivious bucket-based data structure. We allow for data to be added to buckets without leaking into which bucket it has been added. As long as a bucket is not explicitly queried, the data store does not learn anything about bucket contents. Furthermore, no information is leaked about data additions following a query. Besides formally proving RASP’s privacy, we also present a practical evaluation of RASP on Amazon Dynamo, demonstrating its efficiency and real world applicability.

Abstract We present a new, general data structure that reduces the communication cost of recent tree-based ORAMs. Contrary to ORAM trees with constant height and path lengths, our new construction r-ORAM allows for trees with varying shorter path length. Accessing an element in the ORAM tree results in different communication costs depending on the location of the element. The main idea behind r-ORAM is a recursive ORAM tree structure, where nodes in the tree are roots of other trees. While this approach results in a worst-case access cost (tree height) at most as any recent tree-based ORAM, we show that the average cost saving is around 35% for recent binary tree ORAMs. Besides reducing communication cost, r-ORAM also reduces storage overhead on the server by 4% to 20% depending on the ORAM’s client memory type. To prove r-ORAM’s soundness, we conduct a detailed overflow analysis. r-ORAM’s recursive approach is general in that it can be applied to all recent tree ORAMs, both constant and poly-log client memory ORAMs. Finally, we implement and benchmark r-ORAM in a practical setting to back up our theoretical claims.

With sensitive data being increasingly stored on mobile devices and laptops, hard disk encryption is more important than ever. In particular, being able to plausibly deny that a hard disk contains certain information is a very useful and interesting research goal. However, it has been known for some time that existing ``hidden volume'' solutions, like TrueCrypt, fail in the face of an adversary who is able to observe the contents of a disk on multiple, separate occasions. In this work, we explore more robust constructions for hidden volumes and present HiVE, which is resistant to more powerful adversaries with multiple-snapshot capabilities. In pursuit of this, we propose the first security definitions for hidden volumes, and prove HiVE secure under these definitions. At the core of HiVE, we design a new write-only Oblivious RAM. We show that, when only hiding writes, it is possible to achieve ORAM with optimal O(1) communication complexity and only poly-logarithmic user memory. This is a significant improvement over existing work and an independently interesting result. We go on to show that our write-only ORAM is specially equipped to provide hidden volume functionality with low overhead and significantly increased security. Finally, we implement HiVE as a Linux kernel block device to show both its practicality and usefulness on existing platforms.

Modern workstations and servers implicitly trust hard disks to act as well-behaved block devices. This paper analyzes the catastrophic loss of security that occurs when hard disks are not trustworthy. First, we show that it is possible to compromise the firmware of a commercial off-the-shelf hard drive, by resorting only to public information and reverse engineering. Using such a compromised firmware, we present a stealth rootkit that replaces arbitrary blocks from the disk while they are written, providing a data replacement back-door. The measured performance overhead of the compromised disk drive is less than 1% compared with a normal, non-malicious disk drive. We then demonstrate that a remote attacker can even establish a communication channel with a compromised disk to infiltrate commands and to ex-filtrate data. In our example, this channel is established over the Internet to an unmodified web server that relies on the compromised drive for its storage, passing through the original webserver, database server, database storage engine, filesystem driver, and block device driver. Additional experiments, performed in an emulated disk-drive environment, could automatically extract sensitive data such as /etc/shadow (or a secret key file) in less than a minute. This paper claims that the difficulty of implementing such an attack is not limited to the area of government cyber-warfare; rather, it is well within the reach of moderately funded criminals, botnet herders and academic researchers.

Wireless networks are an integral part of today's cyber-physical infrastructure. Their resiliency to jamming is critical not only for military applications, but also for civilian and commercial applications. In this paper, we design, prototype, and evaluate a system for cancelling jammers that are significantly more powerful than the transmitting node. Our system combines a novel mechanical beam-forming design with a fast auto-configuration algorithm and a software radio digital interference cancellation algorithm. Our mechanical beam-forming uses a custom-designed two-elements architecture and an iterative algorithm for jammer signal identification and cancellation. We have built a fully functional prototype (using 3D printers, servos, USRP-SDR) and demonstrate a robust communication in the presence of jammers operating at five orders of magnitude stronger power than the transmitting node. Similar performance in traditional phased arrays and radar systems requires tens to hundreds of elements, high cost and size

Hard disk encryption is known to be vulnerable to a number of attacks that aim to directly extract cryptographic key material from system memory. Several approaches to preventing this class of attacks have been proposed, including Tresor [18] and LoopAmnesia [25]. The common goal of these systems is to confine the encryption key and encryption process itself to the CPU, such that sensitive key material is never released into system memory where it could be accessed by a DMA attack.

Counterfeit detection in RFID-based supply chains aims at preventing adversaries from injecting fake products that do not meet quality standards. This paper introduces CHECKER, a new protocol for counterfeit detection in RFID-based supply chains through on-site checking. While RFID-equipped products travel through the supply chain, RFID readers can verify product genuineness by checking the validity of the product's path. CHECKER uses a polynomial-based encoding to represent paths in the supply chain. Each tag T in CHECKER stores an IND-CCA encryption of T's identifier ID and a signature of ID using the polynomial encoding of T's path as secret key. CHECKER is provably secure and privacy preserving. An adversary can neither inject fake products into the supply chain nor trace products. Moreover, RFID tags in CHECKER can be cheap read/write only tags that do not perform any computation. Per tag, only 120 Bytes storage are required.

As RFID applications are entering our daily life, many new security and privacy challenges arise. However, current research in RFID security focuses mainly on simple authentication and privacy-preserving identification. In this paper, we discuss the possibility of widening the scope of RFID security and privacy by introducing a new application scenario. The suggested application consists of computing statistics on private properties of individuals stored in RFID tags. The main requirement is to compute global statistics while preserving the privacy of individual readings. PPS assures the privacy of properties stored in each tag through the combination of homomorphic encryption and aggregation at the readers. Re-encryption is used to prevent tracking of users. The readers scan tags and forward the aggregate of their encrypted readings to the back-end server. The back-end server then decrypts the aggregates it receives and updates the global statistics accordingly. PPS is provably privacy-preserving. Moreover, tags can be very simple as they are not required to perform any computation, but only to store data.

In this paper, we present the design of the lightweight F_f family of privacy-preserving authentication protocols for RFID-systems. F_f results from a systematic design based on a new algebraic framework focusing on the security and privacy of RFID authentication protocols. F_f offers user-adjustable, strong authentication, and privacy against known algebraic attacks and recently popular SAT-solving attacks. In contrast to related work, F_f achieves these security properties without requiring an expensive cryptographic hash function. F_f is designed for a challenge-response protocol, where the tag sends random nonces and the results of HMAC-like computations of one of the nonces together with its secret key back to the reader. In this paper, the authentication and privacy of F_f is evaluated using analytical and experimental methods.

In-network data aggregation allows energy-efficient communication within a sensor network. However, such data aggregation introduces new security challenges. As sensor nodes are prone to node-compromise, a fraction of nodes might act maliciously and forge aggregated data. For arbitrary aggregation functions, the verification of authenticity of aggregated data, i.e., its correctness, integrity, and origin, is impossible. Thus, one can either aggregate data and save energy or verify authenticity, not both. We present "ESAWN", a protocol that probabilistically relaxes authenticity in the presence of a fraction of compromised nodes. This enables a trade-off between probabilistic authenticity and probabilistic, energy-saving data aggregation. Besides theoretical analysis, we present MICA2-based simulation results. They indicate that even for high probabilities of authenticity and fraction of compromised nodes, ESAWN is more energy-efficient compared to (100%-)secure but non-aggregating communication. For example, with a fraction of 20% compromised nodes and 90% authenticity, ESAWN saves up to 40% energy.

In various sensor network scenarios, data of low entropy is measured and transported towards a data-sink. For example, sensor networks monitor temperature, air pressure, or humidity. As periodic sensor measurements rarely change over time, a receiver can often predict them. Therefore, energy-expensive periodic radio transmission of the measurement can often be omitted. Instead, the node taking and sending a measurement S and the node receiving the measurement R agree on a model. This work states that model updates for data prediction in wireless sensor networks must take the reliability of underlying communication as well as computational overhead into account.

Key establishment is a fundamental prerequisite for secure communication in wireless sensor networks. A new node joining the network needs to efficiently and autonomously set up secret keys with his communication partners without the use of a central infrastructure. Most cited current research papers focus on a probabilistic distribution of sets of keys from larger key pools to new nodes. This results in unnecessary expensive communication and memory consumption, growing linearly with the size of the network, and guarantees secure connections only with a certain probability. This work presents a novel approach for efficient and secure key establishment of nodes joining the network by utilizing the fact that communication in sensor networks follows a paradigm called aggregation. Keys are split into shares and forwarded using disjoint paths in the network. The approach is self-organizing and minimizes memory consumption as well as radio transmissions efficiently -- down to logarithmic behavior.