Archive for the 'Papers' Category

Horcrux Is a Password Manager Designed for Security and Paranoid Users

Friday, July 7th, 2017

Bleeping Computer has an article about our work on a more secure password manager: Horcrux Is a Password Manager Designed for Security and Paranoid Users, 4 July 2017.

Two researchers from the University of Virginia have developed a new password manager prototype that works quite differently from existing password manager clients.

The research team describes their password manager — which they named Horcrux — as “a password manager for paranoids,” due to its security and privacy-focused features and a unique design used for handling user passwords, both while in transit and at rest.

There are two main differences between Horcrux and currently available password manager clients.

The first is how Horcrux inserts user credentials inside web pages. Regular password managers do this by filling in the login form with the user’s data.

The second feature that makes Horcrux stand out compared to other password manager clients is how it stores user credentials.

Compared to classic solutions, Horcrux doesn’t trust one single password store but spreads user credentials across multiple servers. This means that if an attacker manages to gain access to one of the servers, he won’t gain access to all of the user’s passwords, limiting the damage of any security incident.

More details about the Horcrux design and implementation are available in the research team’s paper, entitled “Horcrux: A Password Manager for Paranoids”.

Feature Squeezing: Detecting Adversarial Examples

Monday, April 10th, 2017

Although deep neural networks (DNNs) have achieved great success in many computer vision tasks, recent studies have shown they are vulnerable to adversarial examples. Such examples, typically generated by adding small but purposeful distortions, can frequently fool DNN models. Previous studies to defend against adversarial examples mostly focused on refining the DNN models. They have either shown limited success or suffer from expensive computation. We propose a new strategy, feature squeezing, that can be used to harden DNN models by detecting adversarial examples. Feature squeezing reduces the search space available to an adversary by coalescing samples that correspond to many different feature vectors in the original space into a single sample.

By comparing a DNN model’s prediction on the original input with that on the squeezed input, feature squeezing detects adversarial examples with high accuracy and few false positives. If the original and squeezed examples produce substantially different outputs from the model, the input is likely to be adversarial. By measuring the disagreement among predictions and selecting a threshold value, our system outputs the correct prediction for legitimate examples and rejects adversarial inputs.

So far, we have explored two instances of feature squeezing: reducing the color bit depth of each pixel and smoothing using a spatial filter. These strategies are straightforward, inexpensive, and complementary to defensive methods that operate on the underlying model, such as adversarial training.

The figure shows the histogram of the L1 scores on the MNIST dataset between the original and squeezed sample, for 1000 non-adversarial examples as well as 1000 adversarial examples generated using both the Fast Gradient Sign Method and the Jacobian-based Saliency Map Approach. Over the full MNIST testing set, the detection accuracy is 99.74% (only 22 out of 5000 fast positives).

For more information, see the paper:

Weilin Xu, David Evans, Yanjun Qi. Feature Squeezing: Detecting Adversarial Examples in Deep Neural Networks. arXiv preprint, 4 April 2017. [PDF]

Project Site: EvadeML

Growth of MPC Research

Friday, January 13th, 2017

I led a discussion breakout at the NSF SaTC PIs meeting on Secure Computation: Progress, Methods, Challenges, and Open Questions. To set up the session, I looked at the number of papers in Google scholar that match "secure computation" OR "multi-party computation" (which seems like a fairly good measure of research activity in the area):

There were 1800 MPC papers published in 2015! This means in one year, there are most papers published on MPC than there were from the beginning of time through the end of 2004. Gotta get reading…

Secure Stable Matching at Scale

Tuesday, August 30th, 2016

Our paper on secure stable matching is now available [PDF, 12 pages]:

Jack Doerner, David Evans, abhi shelat. Secure Stable Matching at Scale. 23rd ACM Conference on Computer and Communications Security (CCS). Vienna, Austria. 24-28 October 2016.

See the site for the code and data. Jack Doerner will present the paper at CCS in October.


When a group of individuals and organizations wish to compute a stable matching — for example, when medical students are matched to medical residency programs — they often outsource the computation to a trusted arbiter to preserve the privacy of participants’ preference rankings. Secure multi-party computation presents an alternative that offers the possibility of private matching processes that do not rely on any common trusted third party. However, stable matching algorithms are computationally intensive and involve complex data-dependent memory access patterns, so they have previously been considered infeasible for execution in a secure multiparty context on non-trivial inputs.

We adapt the classic Gale-Shapley algorithm for use in such a context, and show experimentally that our modifications yield a lower asymptotic complexity and more than an order of magnitude in practical cost improvement over previous techniques. Our main insights are to design new oblivious data structures that exploit the properties of the matching algorithms. We then apply our secure computation techniques to the instability chaining algorithm of Roth and Peranson, currently in use by the National Resident Matching Program. The resulting algorithm is efficient enough to be useful at the scale required for matching medical residents nationwide, taking just over 17 hours to complete an execution simulating the 2016 NRMP match with more than 35,000 participants and 30,000 residency slots.

NDSS Talk: Automatically Evading Classifiers (including Gmail’s)

Wednesday, February 24th, 2016

Weilin Xu presented his work on Automatically Evading Classifiers today at the Network and Distributed Systems Security Symposium in San Diego, CA (co-advised by Yanjun Qi and myself). The work demonstrates an automated approach for finding evasive variants of malicious PDF files using genetic programming techniques. Starting with a malicious seed file (that is, a PDF file with the intended malicious behavior, but that is correctly classified as malicious by the target classifier), it heuristically searches for an evasive variant that preserves the malicious behavior of the seed sample but is now classified as benign. The method automatically found an evasive variant for every seed in our test set of 500 malicious PDFs for both of the target classifiers used in the experiment (PDFrate and Hidost).

Slides from the talk are below, the full paper and code is available on the website.

In addition to the results in the paper, Weilin found some new results examining gmail’s PDF malware classifier. We had hoped the classifier used by gmail would be substantially better than what we found in the research prototype classifiers used in the original experiments, and the initial cross-evasion experiments supported this. Of the 500 evasive variants found for Hidost in the original experiment, 387 were also evasive variants against PDFrate, but only 3 of them were evasive variants against Gmail’s classifier.

From those 3, and some other manual tests, however, Weilin was able to find two very simple transformations (any change to JavaScript such as adding a variable declaration, and adding padding to the file) that are effective at finding evasive variants for 47% of the seeds.

The response we got from Google about this was somewhat disappointing (and very inconsistent with my all previous experiences raising security issues to Google):

Its true, of course, that any kind of static program analysis is theoretically impossible to do perfectly. But, that doesn’t mean the dominant email provider shouldn’t be trying to do better to detect one of the main vectors for malware distribution today (and there are, we believe, many fairly straightforward and inexpensive things that could be done to do dramatically better than what Gmail is doing today).

The other new result in the talk that isn’t in the paper is the impact of adjusting the target classifier threshold. The search for evasive variants can succeed even at lower thresholds for defining maliciousness (as shown in the slide below, finding evasive variants against PDFrate at the 0.25 maliciousness threshold).

Evading Machine Learning Classifiers

Monday, December 21st, 2015

Today we’re releasing our paper on evading machine learning classifiers:

Weilin Xu, Yanjun Qi, and David Evans. Automatically Evading Classifiers: A Case Study on PDF Malware Classifiers Network and Distributed System Security Symposium (NDSS). San Diego, CA. 21-24 February 2016. [PDF, 15 pages]

The main idea behind the paper is to explore how an adaptive adversary can evade a machine learning-based malware classifier by using techniques from genetic programming to automatically explore the space of potential evasive variants.

In a case study using two PDF malware classifiers as targets, we find that it is possible to automatically find evasive variants (that is, variants that preserve the desired malicious behavior while being (mis)classified as benign) for all 500 seeds in our test dataset.

Weilin Xu will present the work at the Network and Distributed Systems Security Symposium in San Diego in February.

For more, see or the full paper (PDF).

SRG at Oakland 2015

Sunday, May 24th, 2015

Several SRGers were at IEEE Symposium on Security and Privacy (“Oakland” in San Jose).

Yuchen Zhou presented his work on Understanding and Monitoring Embedded Web Scripts. Yuchen graduated with his PhD the day before the conference, and will be joining Palo Alto Networks.

Samee Zahur is a co-author (along with Benjamin Kreuter, who is an “in-progress UVa PhD student” diverted by Google, and several researchers from Microsoft Research) on the paper, Geppetto: Versatile Verifiable Computation, which was presented by Bryan Parno.

Samee also presented a poster on Obliv-C.

Weilin Xu presented a poster on Automatically Evading Classifiers

It was also great to see SRG alums Yan Huang (who is not at Indiana University, and was a co-author on the paper about ObliVM), Jon McCune (who is now working on trusted computing at Google) and Adrienne Felt (who was the keynote speaker for the W2SP workshop, and gave a very interesting talk about user-facing security design and experiments in Google Chrome; Adrienne’s first paper was in W2SP 2008 when she was an undergraduate at UVa).

Understanding and Monitoring Embedded Web Scripts

Thursday, March 26th, 2015

Modern web applications make frequent use of third-party scripts, often in ways that allow scripts loaded from external servers to make unrestricted changes to the embedding page and access critical resources including private user information. Our paper describing tools to assist site administrators in understanding, monitoring, and restricting the behavior of third-party scripts embedded in their site, and what we’ve learned by using them, is now available: Yuchen Zhou and David Evans, Understanding and Monitoring Embedded Web Scripts, IEEE Symposium on Security and Privacy 2015.

Yuchen will present the paper at the Oakland conference (in San Jose) this May.

Project Site:

Two Halves Make a Whole!

Monday, September 29th, 2014

Surprisingly, it is possible to reduce the data needed for a garbled gate to only two ciphertexts per gate, while preserving free xors. The scheme for doing that is described in our paper, Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates by Samee Zahur and Mike Rosulek and David Evans (now available on eprint).

Abstract. The well-known classical constructions of garbled circuits use four ciphertexts per gate, although various methods have been proposed to reduce this cost. The best previously known methods for optimizing AND gates (two ciphertexts; Pinkas et al., ASIACRYPT 2009) and XOR gates (zero ciphertexts; Kolesnikov & Schneider, ICALP 2008) were incompatible, so most implementations used the best known method compatible with free-XOR gates (three ciphertexts; Kolesnikov & Schneider, ICALP 2008). In this work we show how to simultaneously garble AND gates using two ciphertexts and XOR gates using zero ciphertexts, resulting in smaller garbled circuits than any prior scheme. The main idea behind our construction is to break an AND gate into two half-gates — AND gates for which one party knows one input. Each half-gate can be garbled with a single ciphertext, so our construction uses two ciphertexts for each AND gate while being compatible with free-XOR gates. The price for the reduction in size is that the evaluator must perform two cryptographic operations per AND gate, rather than one as in previous schemes. We experimentally demonstrate that our garbling scheme leads to an overall decrease in time (up to 25%), bandwidth (up to 33%), and energy use (up to 20%) over several benchmark applications. We also initiate a study of lower bounds for garbled gate size, and show that our construction is optimal for a large class of garbling schemes encompassing all known practical garbling techniques.

Symmetric Cut-and-Choose

Friday, June 14th, 2013

Our paper on symmetric cut-and-choose is now available. The paper will be presented at CRYPTO 2013 in August.

Abstract. Beginning with the work of Lindell and Pinkas, researchers have proposed several protocols for secure two-party computation based on the cut-and-choose paradigm. In existing instantiations of this paradigm, one party generates k garbled circuits; some fraction of those are “checked” by the other party, and the remaining fraction are evaluated. We introduce here the idea of symmetric cut-and-choose protocols, in which both parties generate k circuits to be checked by the other party. The main advantage of our technique is that k can be reduced by a factor of 3 while attaining the same statistical security level as in prior work. Since the number of garbled circuits dominates the costs of the protocol, especially as larger circuits are evaluated, our protocol is expected to run up to 3 times faster than existing schemes. Preliminary experiments validate this claim.

Full paper (16 pages): [PDF]