Security Research at the University of Virginia
Our paper,
Faster Secure Two-Party Computation Using Garbled Circuits by Yan Huang, David Evans, Jonathan Katz, Lior Malka.
was accepted to USENIX Security. Yan will present the paper at the conference in San Francisco in August. If you would like an advance copy, email me and I will let you know when it is available.
Our paper on using lattice ciphers for low-power public-key encryption targeted to RFID tags is now available. Yu Yao will present the paper in Wuxi, China in April.
Yu Yao, Jiawei Huang, Sudhanshu Khanna, abhi shelat, Benton Highsmith Calhoun, John Lach, and David Evans. A Sub-0.5V Lattice-Based Public-Key Encryption Scheme for RFID Platforms in 130nm CMOS. 2011 Workshop on RFID Security (RFIDsec’11 Asia)
Wuxi, China. 6-8 April 2011.
Abstract: Implementing public-key cryptography on passive RFID tags is very challenging due to the limited die size and power available. Typical public-key algorithms require complex logical components such as modular exponentiation in RSA. We demonstrate the feasibility of implementing public-key encryption on low-power, low cost passive RFID tags to large-scale private identification. We use Oded Regev’s Learning-With-Error (LWE) cryptosystem, which is provably secure under the hardness assumption of classic lattice problems. The advantage of using the LWE cryptosystem is its intrinsic computational simplicity (the main operation is modular addition). We leverage the low speed of RFID application by using circuit design with supply voltage close to transistor threshold (Vt) to lower power. This paper presents protocols for using the LWE cipher to provide private identification, evaluates a design for implementing those protocols on passive RFID tags, and reports on simulation experiments that demonstrate the feasibility of this approach.
Full paper (19 pages): [PDF]
We’ve released our code and paper on efficient privacy-preserving biometric identification:
Yan Huang (University of Virginia), Lior Malka (Intel/University of Maryland), David Evans (University of Virginia), and Jonathan Katz (University of Maryland). Efficient Privacy-Preserving Biometric Identification. To appear in 18th Network and Distributed System Security Conference (NDSS 2011), 6-9 February 2011. [PDF, 14 pages]
We present an efficient matching protocol that can be used in many privacy-preserving biometric identification systems in the semi-honest setting. Our most general technical contribution is a new backtracking protocol that uses the by-product of evaluating a garbled circuit to enable efficient oblivious information retrieval. We also present a more efficient protocol for computing the Euclidean distances of vectors, and optimized circuits for finding the closest match between a point held by one party and a set of points held by another. We evaluate our protocols by implementing a practical privacy-preserving fingerprint matching system.
Yan will present the paper at NDSS in February. The code for our system is available under the MIT open source license.
flickr cc: didbygraham
Yuchen Zhou will present a paper [PDF] on HTTP-only cookies and why it is so hard to deploy security technologies at Web 2.0 Security and Privacy (attached to the Oakland conference) on May 20.
HTTP-only cookies were introduced eight years ago as a simple way to prevent cookie-stealing through cross-site scripting attacks. Adopting HTTP-only cookies seems to be an easy task with no significant costs or drawbacks, but many major websites still do not use HTTP-only cookies. This paper reports on a survey of HTTP-only cookie use in popular websites, and considers reasons why HTTP-only cookies are not yet more widely deployed.
UVa Today has an article about our (myself, abhi shelat, John Lach, and Ben Calhoun) recent NSF Cybertrust grant on RFID security and privacy: U.Va. Team Receives $1 Million Grant To Improve RFID Security, by Brevy Cannon, 9 January 2009.
Some excerpts:
To address the problematic use of custom cryptography, the U.Va. research team will develop an encryption scheme that is relatively strong — providing some measure of privacy and security — but that can be implemented at almost zero cost by repurposing the meager hardware resources already available on common RFID tags. Providing a solution that adds virtually no cost is crucial, because these RFIDs are made by the billions, at such low costs (5 cents or less apiece) that there is no margin for any added expense.
…
The team is breaking new ground by using a holistic design approach that considers how all the various levels of the design — the hardware, the encryption algorithm and how it is used — work together, mindful of how an attacker will target the single weakest link in the design.
…
The research team hopes their research will forestall that possibility, enabling RFIDs to be used in countless ingenious applications not yet dreamt of, without sacrificing privacy and security in a Faustian bargain.
The story about Adrienne Felt’s Facebook privacy study made the list of UVA Today Most Popular Stories of 2008.
The University of Virginia Press has published a book, What Should I Read Next?: 70 University of Virginia Professors Recommend Readings in History, Politics, Literature, Math, Science, Technology, the Arts, and More edited by Jessica Feldman and Robert Stilling, University of Virginia Press, 2008.
The premise of the book is to collect essays from UVa professors that introduce their field to a general audience by recommending five books to read about it. I contributed an essay on computer science, How Computing Changes Thinking [HTML, PDF, 4 pages]. Here’s the blurb for the book:
What Should I Read Next? taps seventy University of Virginia professors in an array of fields for suggestions on how to satisfy this nagging intellectual curiosity. Each contributor recommends five titles that speak to their area of inquiry, providing both a general introduction and commentary on each selection. The results read like a series of personal tutorials: Larry Sabato considers how political power is acquired, used, and held onto; climatologist Robert E. Davis provides a timely navigation of global-warming literature; and Michael Levenson offers five ways to approach James Joyce’s Ulysses. Other topics include how computing changes thinking, the life and afterlife of slavery, understanding cities, and ecstatic poetry. The entries convey the contributors’ expertise but also, more importantly, the enthusiasm, the original kernels of curiosity, that drew these scholars to their life’s work.
Designed for the lifelong learner who wants to branch out from his or her own profession or discipline, these explorations–of art, science, history, technology, politics, and much more–offer an inspiring place to start.
UVa Today has an article about the book: Faculty Reading Recommendations May Guide Book Lovers, Oct 14, 2008.
Our upcoming USENIX Security Symposium paper is now available: Reverse-Engineering a Cryptographic RFID Tag by Karsten Nohl, David Evans, Starbug, and Henryk Plötz.
The paper describes the methods used to reverse engineering the encryption on the Mifare Classic RFID tag and some of the things we learned by doing it. Karsten Nohl will present the paper at the USENIX Security Symposium in San Jose on July 31.
Abstract
The security of embedded devices often relies on the secrecy of proprietary cryptographic algorithms. These algorithms and their weaknesses are frequently disclosed through reverse-engineering software, but it is commonly thought to be too expensive to reconstruct designs from a hardware implementation alone. This paper challenges that belief by presenting an approach to reverse-engineering a cipher from a silicon implementation. Using this mostly automated approach, we reveal a cipher from an RFID tag that is not known to have a software or micro-code implementation. We reconstruct the cipher from the widely used Mifare Classic RFID tag by using a combination of image analysis of circuits and protocol analysis. Our analysis reveals that the security of the tag is even below the level that its 48-bit key length suggests due to a number of design flaws. Weak random numbers and a weakness in the authentication protocol allow for pre-computed rainbow tables to be used to find any key in a matter of seconds. Our approach of deducing functionality from circuit images is mostly automated, hence it is also feasible for large chips. The assumption that algorithms can be kept secret should therefore to be avoided for any type of silicon chip.
Our paper, Privacy Protection for Social Networking Platforms by Adrienne Felt and David Evans is now available [PDF]. Adrienne Felt will present the paper at the Web 2.0 Security and Privacy 2008 (in conjunction with 2008 IEEE Symposium on Security and Privacy) in Oakland, CA on May 22, 2008.
Abstract
Social networking platforms integrate third-party content into social networking sites and give third-party developers access to user data. These open interfaces enable popular site enhancements but pose serious privacy risks by exposing user data to third-party developers. We address the privacy risks associated with social networking APIs by presenting a privacy-by-proxy design for a privacy-preserving API. Our design is motivated by an analysis of the data needs and uses of Facebook applications. We studied 150 popular Facebook applications and found that nearly all applications could maintain their functionality using a limited interface that only provides access to an anonymized social graph and placeholders for user data. Since the platform host can control the third party applications’ output, privacy-by-proxy can be accomplished by using new tags and data transformations without major changes to either the platform architecture or applications.
Full paper (8 pages): [PDF]
Project Website
[Added 25 May]: Talk slides (by Adrienne Felt): [PDF]
Our paper, Hiding in Groups: On the Expressiveness of Privacy Distributions by Karsten Nohl and David Evans, is now available: PDF (15 pages). Karsten Nohl will present the paper at the 23rd International Information Security Conference (SEC 2008, Co-located with IFIP World Computer Congress 2008) in Milan, Italy, 8-10 September 2008.
Abstract
Many applications inherently disclose information because perfect privacy protection is prohibitively expensive. RFID tags, for example, cannot be equipped with the cryptographic primitives needed to completely shield their information from unauthorized reads. All known privacy protocols that scale to the anticipated sizes of RFID systems achieve at most modest levels of protection. Previous analyses found the protocols to have weak privacy, but relied on simplifying attacker models and did not provide insights into how to improve privacy. We introduce a new general way to model privacy through probability distributions, that capture how much information is leaked by different users of a system. We use this metric to examine information leakage for an RFID tag from the a scalable privacy protocol and from a timing side channel that is observable through the tag’s random number generator. To increase the privacy of the protocol, we combine our results with a new model for rational attackers to derive the overall value of an attack. This attacker model is also based on distributions and integrates seamlessly into our framework for information leakage. Our analysis points to a new parameterization for the privacy protocol that significantly improves privacy by decreasing the expected attack value while maintaining reasonable scalability at acceptable cost.
Full paper (15 pages): [PDF]
Extended Technical Report (18 pages): [PDF]
Bad Behavior has blocked 243 access attempts in the last 7 days.