September 28, 2016 Splinter: Practical Private Queries on Public Data
Speaker: Matei Zaharia
Abstract: Many online services let users query public datasets such as maps, flight prices, or restaurant reviews. Unfortunately, the queries to these services reveal highly sensitive information that can compromise users' privacy. We present Splinter, a system to protect users' queries on public data that can scale to realistic applications. A user splits her query into multiple parts and sends each part to a different provider that holds a copy of the data. As long as any one of the providers is honest and does not collude with the others, the providers cannot determine the query. Splinter uses and extends a cryptographic primitive called Function Secret Sharing (FSS) that makes it significantly more efficient than prior systems based on Private Information Retrieval and garbled circuits. We develop protocols that extend FSS to new types of queries, such as maximum and top-K queries, as well as an optimized implementation of FSS using AES-NI instructions and multicores. Splinter achieves latencies below 1.2 seconds for realistic workloads including a Yelp clone, flight search, and map routing.
Note: Since this is our first meeting of the quarter, we will have a three-minute organizational meeting before the talk begins.
October 05, 2016 Moved to Law School
Note: Henry Corrigan-Gibbs is giving a lunch-time talk at the law school on October 5 at 12:45pm, so we are moving Security Lunch to the law school for the week. Lunch will be served at the talk—please register below.
RSVP using: this link
October 12, 2016 Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds
Speaker: David Wu
Abstract: In the last few years, there has been significant interest in developing methods to search over encrypted data. In the case of range queries, a simple solution is to encrypt the contents of the database using an order-preserving encryption (OPE) or order-revealing encryption (ORE) scheme (i.e., an encryption scheme that enables comparisons on encrypted values). While these encryption schemes have the advantage of being legacy-friendly (i.e., easy to integrate with existing database management systems), a recent line of work beginning with Naveed et al. (CCS 2015) showed that these legacy-friendly solutions are extremely vulnerable to “inference attacks.” Naveed et al. (and subsequently, Durak et al. (CCS 2016) as well as Grubbs et al.) show that an attacker who just obtains a static dump (e.g., offline access) to a database encrypted under an OPE/ORE scheme can actually recover nearly all of the data contained in the database.
In this work, we introduce a new paradigm for constructing order-revealing encryption that can be used to achieve stronger security in the offline setting. When using our new ORE candidate to perform range queries over an encrypted database, the ciphertexts in the database provide semantic security, and thus, provably reveal no information about the underlying contents. In this way, our new ORE scheme is the first practically-viable scheme that is robust against all offline inference attacks. In the online setting, we show that our ORE scheme is more secure than existing (stateless and non-interactive) OPE and ORE schemes which are practical. All of our constructions rely only on symmetric primitives (e.g., AES). Finally, we give a full implementation of our new ORE scheme, and show that not only is our scheme more secure than existing OPE schemes (the current standard that has been deployed in several industry applications), it is also faster: encrypting a 32-bit integer requires just 55 microseconds, which is more than 65 times faster than existing OPE schemes.
Joint work with: Kevin Lewi
To appear at: CCS 2016
October 19, 2016 Blind Seer — Using Bloom filter trees for Searchable Encryption
Speaker: Ben Fisch
Abstract: Blind Seer is a system that supports private querying of an outsourced encrypted database. In contrast to standard searchable symmetric encryption (SSE) schemes, the goal of Blind Seer is to protect both the privacy of a client’s queries and the database itself. In particular, it provides the ability to enforce authorization policies on client queries while maintaining the privacy of both the queries and the policies. Blind Seer’s main achievements are its rich query functionality (arbitrary boolean formulas) and efficiency. On a 100M-record census database with roughly 7B indexed keywords, test queries on Blind Seer completed within 3x of a MySQL baseline. The system is provably secure (for a semi-honest server and malicious client) up to limited leakage in the form of data access patterns, which could be prevented with more expensive techniques like ORAM. An important open line of work is understanding the impact of this leakage.
In this talk we will discuss Blind Seer's core data structure, an encrypted Bloom filter tree that indexes database keywords. In Blind Seer, client queries are evaluated through an interactive search in the Bloom filter tree using Yao’s garbled circuits to maintain privacy. The communication and computation required for the garbled circuits is a major bottleneck in Blind Seer’s performance. We show how Bloom filter trees can be used in the SSE setting without any need for garbled circuits. Furthermore, we can achieve security against a malicious server. This is a work in progress and its performance will be measured against existing SSE schemes that support boolean (conjunctive/disjunctive) queries.
October 26, 2016 Privately Finding Common Friends of Friends in Social Networks
Speaker: Yan Michalevsky
Abstract: We present solutions to a fundamental problem affecting distributed social networks where every user knows his direct friends, but knows nothing about his friends of friends. Since the social graph is distributed, how can the system recommend that a user befriend a common friend of friends? Concretely, suppose three of Alice’s friends are friends with some user Charlie. A centralized social network would suggest to Alice that she might also want to befriend Charlie. We show that the same can be done with a distributed social graph and without leaking any other information about friend relations.
We cast the problem as a secure multi-party computation with a strict communication pattern. We first show that when the common friends threshold is two — that is, Alice should be told about Charlie if Charlie is friends with two of her friends — the problem can be solved efficiently using a direct secret sharing mechanism. When the threshold is three or greater, solving this problem without leaking additional information is much harder. We introduce two notions of security offering different levels of privacy. For the weaker notion, we propose three algorithms with different performance characteristics by exploiting the fact that Reed-Solomon codewords also have secret sharing properties. We experiment with these algorithms and show that they can be used successfully even when all users have hundreds of direct friends. For the stronger security notion, we describe a solution based on decentralized attribute-based encryption.
November 02, 2016 Cancelled due to Law School Event
November 09, 2016 Castor: Record/Replay for Production Systems
Speaker: Ali Mashtizadeh
Abstract: We present Castor, an application record/replay system designed to provide consistently low and predictable overheads, even for demanding multi-core workloads. Low overheads make it practical to leave Castor on by default, allowing developers to record and reproduce bugs production bugs, or recover from hardware failures through fault tolerance.
Castor relies on several observations: First, efficiently logging and replaying non-deterministic events is critical for performance and scalability. Careful use of hardware can result in a 10x or more increase in log throughput e.g., a server could potentially handle 10x more requests per second for the same record overhead. Second, most applications can be recorded without source level modification, and transactional memory can support recording user level synchronization with low predictable overheads. Third, while recording explicit synchronization to capture shared-memory non-determinism as Castor does, cannot deterministically reproducing all data race bugs, it appears this is often unnecessary to provide consistently useful record/replay for production workloads, contrary to what some prior work has assumed.
Castor currently supports applications written in C, C++, and Go on FreeBSD. We have evaluated Castor on parallel and server workloads, including a commercial implementation of memcached in Go, which runs Castor in production.
November 16, 2016 Finding and Fixing Vulnerabilities in the Web Platform
Speaker: Fraser Brown
Abstract: JavaScript runtime systems like Chrome and Node.js rely on binding code---the code that connects C++ to JavaScript---to expose low-level functionality to high-level JavaScript application code. For example, Node.js enables JavaScript applications to use the file system by implementing filesystem utilities in C++ and exposing them to JavaScript in the binding layer. Binding code is hard to get right because of the impedence mismatch between the two languages. In this talk, I'll walk through a suite of checkers that identity instances where developers have mishandled the mismatches between C++ and JavaScript; these checkers identify bugs (like UAF errors) in real systems (like Chrome). I'll also describe a new binding layer API that eliminates these vulnerabilities by construction.
November 24, 2016 Thanksgiving Week
November 30, 2016 Deploying TLS 1.3
Speaker: Nick Sullivan (CloudFlare)
Abstract: A deep dive into the design and implementation of the latest version of the transport layer security protocol.
December 07, 2016 ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications
Speaker: Todd Warszawski
Abstract: In theory, database transactions protect application data from corruption and integrity violations. In practice, database transactions frequently execute under weak isolation that exposes programs to a range of concurrency anomalies, and programmers may fail to correctly employ transactions. While low transaction volumes mask many potential concurrency-related errors under normal operation, determined adversaries can exploit them programmatically for fun and profit. In this work, we formalize a new kind of attack on databse-backed applications called an ACIDRain attack, in which an adversary systematically exploits concurrency-related vulnerabilities via programmatically accessible APIs. To proactively detect the potential for ACIDRain attacks, we extend the theory of weak isolation to analyze latent potential for non-serializable behavior under concurrent web API calls. We introduce a language-agnostic method for detecting potential isolation anomalies in web applications, called Abstract Anomaly Detection (2AD), that uses dynamic traces of database accesses to efficiently reason about the space of possible concurrent interleavings. We apply a prototype 2AD analysis tool to 12 popular self-hosted eCommerce applications written in four languages and with a total deploy base of over 2M websites. We identify and verify 22 critical ACIDRain attacks that allow attackers to corrupt store inventory, over-spend gift cards, and steal inventory.
December 14, 2016 Defending against malicious peripherals with Cinch
Speaker: Riad Wahby
Abstract: Malicious peripherals designed to attack their host computers are a growing problem. Inexpensive and powerful peripherals that attach to plug-and-play buses have made such attacks easy to mount. Making matters worse, commodity operating systems lack coherent defenses, and users are often unaware of the scope of the problem. We present Cinch, a pragmatic response to this threat. Cinch uses virtualization to attach peripheral devices to a logically separate, untrusted machine, and includes an interposition layer between the untrusted machine and the protected one. This layer regulates interaction with devices according to user-configured policies. Cinch integrates with existing OSes, enforces policies that thwart real-world attacks, and has low overhead.
Joint work with: S. Angel, M. Howald, J.B. Leners, M. Spilo, Z. Sun, A.J. Blumberg, and M. Walfish