Archive for the 'Papers' Category

Trusted Password Entry

Saturday, April 20th, 2013

Fraudulent mobile applications could trick users into entering sensitive passwords, and then send those passwords to rogue site operators. With current technologies, users have no way of knowing that when they enter a password it is going to the intended application. What is needed is a trusted path for password entry, so when users enter a password they can trust that it will only be visible to the trusted provider.


This paper presents a solution that does not require any modifications to existing apps or application servers, but modifies the Android kernel to establish a shared secret between the user and kernel as part of the boot process, and then uses that shared secret to provide a trusted path for password entry.

Tianhao Tong will present the paper at Moble Security Technologies (MoST) in San Francisco, CA, 23 May 2013.

Paper: Tianhao Tong and David Evans. GuarDroid: A Trusted Path for Password Entry. In Moble Security Technologies (MoST), San Francisco, CA, 23 May 2013. [PDF, 10 pages]

Code: GuarDroid.net

Circuit Structures for Improving Efficiency of Security and Privacy Tools

Monday, March 4th, 2013

Samee Zahur and I have written a paper on Circuit Structures for Improving Efficiency of Security and Privacy Tools. The paper explores ways to design static circuits (as used in garbled circuit protocols and symbolic execution, among other things) to provide reasonable efficiency for algorithms that use common data structures like arrays. By taking advantage of somewhat predictable access patterns, as well as batching, our circuit structures are able to provide operations with amortized cost that is polylogarithmic in the size of the data structure (in contrast to naive approaches that would require effectively copying the entire data structure for each operation). Samee will present the paper at the IEEE Symposium on Security and Privacy (“Oakland”) in San Francisco in May.

Full paper (15 pages): [PDF]
Project: MightBeEvil.com/netlist

Code: http://github.com/samee/netlist

Quid Pro Quo-tocols: Strengthening Semi-Honest Protocols with Dual Execution

Wednesday, March 7th, 2012

Our paper on strengthening secure computation protocols to resist stronger adversaries is now available:

Yan Huang, Jonathan Katz, and David Evans. Quid Pro Quo-tocols: Strengthening Semi-Honest Protocols with Dual Execution. In 33rd IEEE Symposium on Security and Privacy (“Oakland” 2012), San Francisco, CA. 20-23 May 2012. [PDF, 13 pages]

Yan Huang will present the paper at the Oakland conference (which will be held in San Francisco for the first time, after being in Berkeley/Oakland for the first 32 years!) in May.

Abstract: Known protocols for secure two-party computation that are designed to provide full security against malicious behavior are significantly less efficient than protocols intended only to thwart semi-honest adversaries. We present a concrete design and implementation of protocols achieving security guarantees that are much stronger than are possible with semi-honest protocols, at minimal extra cost. Specifically, we consider protocols in which a malicious adversary may learn a single (arbitrary) bit of additional information about the honest party’s input. Correctness of the honest party’s output is still guaranteed. Adapting prior work of Mohassel and Franklin, the basic idea in our protocols is to conduct two separate runs of a (specific) semi-honest, garbled-circuit protocol, with the parties swapping roles, followed by an inexpensive secure equality test. We provide a rigorous definition and prove that this protocol leaks no more than one additional bit against a malicious adversary. In addition, we propose some enhancements to reduce the overall information a cheating adversary learns. Our experiments show that protocols meeting this security level can be implemented at cost very close to that of protocols that only achieve semi-honest security. Our results indicate that this model enables the large-scale, practical applications possible within the semi-honest security model, while providing dramatically stronger security guarantees.

Full paper (13 pages): [PDF]
Project site: MightBeEvil.com

Private Set Intersection

Tuesday, November 29th, 2011

Our paper on using generic garbled circuits to perform private set intersection is now available:

Yan Huang, David Evans, and Jonathan Katz. Private Set Intersection: Are Garbled Circuits Better than Custom Protocols?. In
19th Network and Distributed Security Symposium (NDSS 2012), San Diego, CA. 5-8 February 2012. [PDF, 15 pages]

The paper develops three circuit designs for securely computing the intersection of two sets, where each set is the private input from one protocol participant. We show that for many scenarios, protocols built using only generic garbled circuit secure computation techniques can be competitive with the best custom-designed protocols for private set intersection.



Yan Huang will present the paper at NDSS in San Diego, in February 2012.

Efficient Secure Computation with Garbled Circuits

Saturday, November 19th, 2011

Our paper on Efficient Secure Computation with Garbled Circuits (by Yan Huang, Chih-hao Shen, David Evans, Jonathan Katz, and abhi shelat) is now available (Abstract, Paper [PDF, 21 pages]).

The paper is connected with a keynote talk I will give at the Seventh International Conference on Information Systems Security (ICISS 2011) in Kolkata (previously known as Calcutta), India on 17 December 2011.

Abstract. Secure two-party computation enables applications in which participants compute the output of a function that depends on their private inputs, without revealing those inputs or relying on any trusted third party. In this paper, we show the potential of building privacy-preserving applications using garbled circuits, a generic technique that until recently was believed to be too inefficient to scale to realistic problems. We present a Java-based framework that uses pipelining and circuit-level optimizations to build efficient and scalable privacy-preserving applications. Although the standard garbled circuit protocol assumes a very week, honest-but-curious adversary, techniques are available for converting such protocols to resist stronger adversaries, including fully malicious adversaries. We summarize approaches to producing malicious-resistant secure computations that reduce the costs of transforming a protocol to be secure against stronger adversaries. In addition, we summarize results on ensuring fairness, the property that either both parties receive the result or neither party does. Several open problems remain, but as theory and pragmatism advance, secure computation is approaching the point where it offers practical solutions for a wide variety of important problems.

Auditing Information Leakage for Distance Metrics

Tuesday, August 30th, 2011

Yikan Chen and I are releasing a paper today on Auditing Information Leakage for Distance Metrics. The paper is a first step towards the goal of developing self-auditing secure computations that can determine when the output of a secure computation would leak too much information to be safe to release. Yikan will present the paper at the Third IEEE Conference on Privacy, Security, Risk and Trust in Boston, 9-11 October 2011.

Abstract. Many useful scenarios involve allowing untrusted users to run queries against secret data, so long as the results do not leak too much information. This problem has been studied widely for statistical queries, but not for queries with more direct semantics. In this paper, we consider the problem of auditing queries where the result is a distance metric between the query input and some secret data. We develop an efficient technique for estimating a lower bound on the entropy remaining after a series of query-responses that applies to a class of distance functions including Hamming distance. We also present a technique for ensuring that no individual bits of the secret sequence is leaked. In this paper, we formalize the information leakage problem, describe our design for a query auditor, and report on experiments showing the feasibility and effectiveness of our approach for sensitive sequences up to thousands of bits.

Full paper: [PDF, 10 pages]

Side-Channel Analysis Paper

Sunday, August 14th, 2011

Our paper on side-channel analysis of web applications is now available:

Peter Chapman and David Evans. Automated Black-Box Detection of Side-Channel Vulnerabilities in Web Applications. In 18th ACM Conference on Computer and Communications Security (CCS 2011), Chicago, IL. 17-21 October 2011. [PDF, 12 pages]

The paper describes a black-box tool for detecting side-channel vulnerabilities by analyzing network traffic over repeated crawls of a web application. Our tool quantifies the severity of side-channel leaks in a web application, and gives web application developers a measure of the risk of information leakage against different types of adversaries. The frequent and highly dynamic client-server communication that is characteristic of modern web applications leaves them vulnerable to side-channel leaks where an adversary can learn about the state of the application and visitor’s choices, even over encrypted connections. Our approach provides a new way to quantify the severity of these vulnerabilities based on analyzing the results of traces of the web traffic using the Fisher criterion.


System Overview

Peter will present the paper at CCS in Chicago in October.

Project Site

Protecting Private Web Content from Embedded Scripts

Thursday, June 16th, 2011

Our paper on protecting private web content from embedded scripts is now available:

Yuchen Zhou and David Evans. Protecting Private Web Content from Embedded Scripts. European Symposium on Research in Computer Security (ESORICS 2011). Lueven, Belguim. 12-14 September 2011. [PDF, 20 pages]

The paper addresses the problem of when web pages embed scripts from third parties (such as advertising networks or analytics tools) in their pages that contain user’s personal content. Since many such scripts must be embedded directly (that is, not in a separate iframe), they have access to the full page DOM and can access and manipulate this data. Our solution adopts the isolated worlds mechanism to isolate embedded scripts and provide a policy-limited access model. We also present a technique for automatically learning which nodes in a web page may contain sensitive data that should be protected from third-party scripts.

Yuchen will present the paper at ESORICS in Belgium in September.



Source Code

Modified Chromium: https://github.com/Treeeater/Chromium_on_windows

Policy Learner Proxy: https://github.com/Treeeater/GreasySpoon-proxy-script

Secure Computation Framework

Monday, June 13th, 2011


Today, we are releasing our secure computation framework. Our Java-based framework and library enable programmers to build efficient and scalable privacy-preserving applications using Yao’s garbled circuit techniques.

This paper describes the framework in more detail:

Yan Huang, David Evans, Jonathan Katz, and Lior Malka. Faster Secure Two-Party Computation Using Garbled Circuits, 20th USENIX Security Symposium, San Francisco, CA. 8-12 August 2011. [PDF, 16 pages]

Abstract. Secure two-party computation enables two parties to evaluate a function cooperatively without revealing to either party anything beyond the function’s output. The garbled-circuit technique, a generic approach to secure two-party computation for semi-honest participants, was developed by Yao in the 1980s, but has been viewed as being of limited practical significance due to its inefficiency. We demonstrate several techniques for improving the running time and memory requirements of the garbled-circuit technique, resulting in an implementation of generic secure two-party computation that is significantly faster than any previously reported while also scaling to arbitrarily large circuits. We validate our approach by demonstrating secure computation of circuits with over 109 gates at a rate of roughly 10 microseconds per garbled gate, and showing order-of-magnitude improvements over the best previous privacy-preserving protocols for computing Hamming distance, Levenshtein distance, Smith-Waterman genome alignment, and AES.

The framework and applications are available under the MIT open source license: Download Fast Garbled Circuits Framework.

Yan Huang will present the paper at USENIX Security Symposium in San Francisco this August.

Private Editing Using Untrusted Cloud Services

Wednesday, May 4th, 2011

Our paper on how to use untrusted cloud services like Google Docs to edit and manage documents, without trusting them with your content, is now available:

Yan Huang and David Evans. Private Editing Using Untrusted Cloud Services. Second International Workshop on Security and Privacy in Cloud Computing. Minneapolis, Minnesota. 24 June 2011. [PDF, 10 pages]

Yan will present the paper at the workshop on June 24.

Abstract

We present a general methodology for protecting the confidentiality and integrity of user data for a class of on-line editing applications. The key insight is that many of these applications are designed to perform most of their data-dependent computation on the client side, so it is possible to maintain their functionality while only exposing an encrypted version of the document to the server. We apply our methodology to Google Documents and describe a prototype extension tool that enables users to use a cloud application to manage their documents without sacrificing confidentiality or integrity. To provide adequate performance, we employ an incremental encryption scheme and extend it to support variable-length blocks. We analyze the security of our scheme and report on experiments that show our extension preserves most of the cloud application’s functionality with less than 10% overhead for typical use.

http://www.mightbeevil.com/securedocs/