January 8 Organizational meeting
Organizational meeting: Sign up to give a talk!
January 21 Anonymous Credentials
Speaker: Ananth Raghunathan
Abstract: In this talk, I will cover a few selected papers describing anonymous credentials and attestation schemes. The talk will also focus on some of my recent work on getting privacy-preserving attestation schemes on commodity hardware. Some of this is joint work (in progress) with Dirk Balfanz and Marius Schilder at Google.
January 29 Enabling Fine-Grained Permissions for Augmented Reality Applications With Recognizers
Speaker: Suman Jana (UT Austin)
Abstract: Augmented reality (AR) applications sense the environment, then render virtual objects on human senses. Examples include smartphone applications that annotate storefronts with reviews and XBox Kinect games that show "avatars" mimicking human movements. No current OS has special support for such applications. As a result, permissions for AR applications are necessarily coarse-grained: applications must ask for access to raw sensor feeds, such as video and audio. These raw feeds expose significant additional information beyond what applications need, including sensitive information such as the user's location, face, or surroundings.
Instead of exposing raw sensor data to applications directly, we introduce a new OS abstraction: the recognizer. A recognizer takes raw sensor data as input and exposes higher-level objects, such as a skeleton or a face, to applications. We propose a fine-grained permission system where applications request permissions at the granularity of recognizer objects. We analyze 87 shipping AR applications and find that a set of four core recognizers covers almost all current apps. We also introduce privacy goggles, a visualization of sensitive data exposed to an application. Surveys of 962 people establish a clear "privacy ordering" over recognizers and demonstrate that privacy goggles are effective at communicating application capabilities. We build a prototype on Windows that exposes nine recognizers to applications, including the Kinect skeleton tracker. Our prototype incurs negligible overhead for single applications, while improving performance of concurrent applications and enabling secure offloading of heavyweight recognizer computation.
February 5 Somewhat (Practical) Homomorphic Encryption
Speaker: David Wu
Abstract: Since Gentry's breakthrough work on fully homomorphic encryption (FHE) in 2009, there has been much work devoted to developing practical FHE systems. While in theory, FHE enables a wide range of computations to be performed on encrypted data, due to the extremely high overhead of FHE, it is impractical for all but the smallest of problems. In practice then, we resort to using somewhat homomorphic encryption (SWHE) systems that support a limited number of operations over encrypted data. In this work, we develop an implementation of Brakerski's scale-invariant SWHE system and show that with some optimizations, it is possible to perform statistical analysis (linear regression and covariance estimation) over encrypted datasets containing several million elements.
February 12 Data-Oblivious Data Structures
Speaker: Joe Zimmerman
Abstract: An algorithm is called data-oblivious if its control flow and memory access pattern do not depend on its input data. Data-oblivious algorithms play a significant role in secure cloud computing, since programs that are run on secret data—as in fully homomorphic encryption or secure multi-party computation—must be data-oblivious. We formalize three definitions of data-obliviousness that have appeared implicitly in the literature, explore their implications, and show separations. We observe that data-oblivious algorithms often compose well when viewed as data structures. Using this approach, we construct data-oblivious stacks, queues, and priority queues that are considerably simpler than existing constructions, as well as improving constant factors. We also establish a new upper bound for oblivious data compaction, and use this result to show that an "offline" variant of the Oblivious RAM problem can be solved with O(log n log log n) expected amortized time per operation—as compared with O(log^2 n / log log n), the best known upper bound for the standard online formulation.
Joint work with: John Mitchell.
To appear in: STACS 2014.
February 19 Ensuring High-Quality Randomness in Cryptographic Key Generation
Speaker: Henry Corrigan-Gibbs
Abstract: The security of any cryptosystem relies on the secrecy of the system's secret keys. Yet, recent experimental work demonstrates that tens of thousands of devices on the Internet use RSA and DSA secrets drawn from a small pool of candidate values. As a result, an adversary can derive the device's secret keys without breaking the underlying cryptosystem. We introduce a new threat model, under which there is a systemic solution to such randomness flaws. In our model, when a device generates a cryptographic key, it incorporates some random values from an entropy authority into its cryptographic secrets and then proves to the authority, using zero-knowledge-proof techniques, that it performed this operation correctly. By presenting an entropy-authority-signed public-key certificate to a third party (like a certificate authority or SSH client), the device can demonstrate that its public key incorporates randomness from the authority and is therefore drawn from a large pool of candidate values.
Where possible, our protocol protects against eavesdroppers, entropy authority misbehavior, and devices attempting to discredit the entropy authority. To demonstrate the practicality of our protocol, we have implemented and evaluated its performance on a commodity wireless home router. When running on a home router, our protocol incurs a 2.1x slowdown over conventional RSA key generation and it incurs a 4.4x slowdown over conventional EC-DSA key generation.
Joint work with: Wendy Mu, Dan Boneh, and Bryan Ford.
February 26 Testing Web Applications with Custom Crawlers
Speaker: Berkeley Churchill
Abstract: Integration testing checks the interoperability of the entire stack of a web application, including client-side code, the database, server middleware, web services and the application logic itself. Current integration testing practices require tedious development and maintenance. We propose a novel alternative: write a customized web crawler specific for an application. This real-world, flexible approach allows testers to write less code, automatically generate self-maintaining regression test suites, and allows for automatic failure isolation and dynamic analysis. In this talk I will discuss current integration testing, the benefits of this approach, a domain-specific language for writing crawlers and our progress on evaluating our tool.
Joint work in progress with: John Mitchell.
March 5 Mobile Device Vulnerabilities
Speaker: Patrick Mutchler
Abstract: Sophisticated computing on mobile devices is rapidly becoming the norm. In this paper, we identify security concerns and vulnerabilities specific to mobile apps that access the web using an embedded browser (mobile web apps), as distinct from app security and web security. We analyze a large dataset of 737,828 Android apps, representing a snapshot of all of the free apps available on the Google Play store as of October 2013. We find that a large number of apps contain severe vulnerabilities. In particular, because of a security oversight in older versions of Android and slow adoption of safe versions, 37,418 apps are vulnerable to a remote code execution exploit when run on any Android device and 45,689 apps are vulnerable to a remote code execution exploit when run on 73% of the in-use Android devices. Finally, we offer recommendations for developers who wish to avoid these vulnerabilities.
March 12 Switching Lemma for Bilinear Tests and Constant-size NIZK Proofs for Linear Subspaces
Speaker: Arnab Roy (Fujitsu Labs)
Abstract: We state a switching lemma for tests on adversarial inputs involving bilinear pairings in hard groups, where the tester can effectively switch the randomness used in the test from being given to the adversary at the outset to being chosen after the adversary commits its input. The switching lemma can be based on any k-linear hardness assumptions on one of the groups. In particular, this enables convenient information theoretic arguments in the construction of sequence of games proving security of cryptographic schemes, mimicking proofs and constructions in the random oracle model.
As an immediate application, we show that the quasi-adaptive NIZK proofs of Jutla and Roy [AsiaCrypt 2013] for linear subspaces can be further shortened to constant-size proofs, independent of the number of witnesses and equations. In particular, under the XDH assumption, a length n vector of group elements can be proven to belong to a subspace of rank t with a quasi-adaptive NIZK proof consisting of just a single group element. Similar quasi-adaptive aggregation of proofs is also shown for Groth-Sahai NIZK proofs of linear multi-scalar multiplication equations, as well as linear pairing-product equations (equations without any quadratic terms).
Joint work with: Charanjit Jutla.