Jefferson's Wheel

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 (V_t) 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]

Karsten Nohl is in the news again, this time for demonstrating how bad the proprietary crypto used for car immobilizers is. Here are a few articles:

• NewScientist, Criminals find the key to car immobilisers, 6 December 2010. (Note that the criminals in the title refers to evidence that actual car theft is increasing, after many years of steady decline, not to Karsten!)
• Schneier on Security, Proprietary Encryption in Car Immobilizers Cracked, 23 December 2010.
• The Register, Car immobilisers easily circumvented by crafty carjackers: Crap crypto to blame, 20 December 2010. (British publications as so much better at titling than American ones!)

Karsten presented the technical aspects in a talk at the 8th Embedded Security in Cars conference in Berlin.

Even if car manufacturers get the crypto right, relay attacks pose a serious threat, especially for modern cars that do away with the mechanical key completely. See the upcoming NDSS paper by Aurelien Francillon, Boris Danev, and Srdjan Capkun: Relay Attacks on Passive Keyless Entry and Start Systems in Modern Cars.

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 18^th 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

Jonathan Burket, Patrick Mutchler, Michael Weaver and Muzzammil Zaveri will present GuardRails at AppSec DC on Wednesday, 10 November. The conference is at the Walter E. Washington Convention Center in Washington, DC.

GuardRails is a framework for automating many of the tasks necessary to build a security web application. For more, see the talk abstract: GuardRails: A Nearly Painless Solution to Insecure Web Applications. (and video and slides will appear there soon)

Update 9 December: The slides are here [PDF].

I’m a judge for the Deutsche Post “Security Cup” contest being organized by our former student, Karsten Nohl. The goal of the contest is to incentivize enterprising students and practitioners to bash on the Deutsche Post’s E-Postbrief web application. They are offering some fairly significant prizes (up to 5,000 Euro per bug) to teams that identify vulnerabilities in their application, as well as providing up-front funding to qualified teams that enter the contest.

Deutsche Post Page
EPostal News

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.

Nate Paul, who finished a PhD in our group a few years ago and is now a research scientist at Oak Ridge National Labs, is the focus of this CNN story: Scientists work to keep hackers out of implanted medical devices, CNN, 16 April 2010.

Nathanael Paul likes the convenience of the insulin pump that regulates his diabetes. It communicates with other gadgets wirelessly and adjusts his blood sugar levels automatically.

But, a few years ago, the computer scientist started to worry about the security of this setup.

What if someone hacked into that system and sent his blood sugar levels plummeting? Or skyrocketing? Those scenarios could be fatal.

“If your computer fails, no one dies,” he said in a phone interview. “If your insulin pump fails, you have problems.”

As sci-fi as it sounds, Paul’s fears are founded in reality.
…

Oakland 2010 submissions closed last week. We received 269 total submissions (of which 30 were Systematization of Knowledge papers). The program should be available by early February, for the conference that will be held May 16-19, 2010 at the Claremont Resort in Berkeley, CA.

IEEE Spectrum has an article on Karsten Nohl’s efforts to lead an open-source GSM hacking project: Open-Source Effort to Hack GSM, IEEE Spectrum, 30 November 2009.

If you’re still using a cellphone based on early digital standards, you better be careful what you say. The encryption technology used to prevent eavesdropping in GSM (Global System for Mobile communications), the world’s most widely used cellphone system, has more security holes than Swiss cheese, according to an expert who plans to poke a big hole of his own.

Karsten Nohl, chief research scientist with H4RDW4RE, a Sunnyvale, Calif.-based security research firm, is mounting what could be the most ambitious attempt yet to compromise the GSM phone system, which is used by over 3 billion people around the world. Others have cracked the A5/1 encryption technology used in GSM before, but their results have remained secret. However, Nohl, who earned a Ph.D. in computer science at the University of Virginia and is a member of Germany’s Chaos Computer Club (CCC), intends to go one big step further: By the end of the year, he plans to make the keys available to everyone on the Internet.

…

GSM cracking has a long history, which began in the late 1990s in academic circles and has since sprouted a handful of commercial businesses. Today, these companies legally sell GSM call-interception solutions–which are relatively expensive–mostly to government intelligence agencies. In general, supplying and using this software is illegal in the wider market, but no one can say for certain how many groups have illegally gained access to the technology.

That’s the point Nohl hopes to drive home: The A5/1 algorithm is a broken 64-bit encryption technology, a relic of the Cold War era, when laws prohibited the export of strong encryption technology from the United States. It needs to be replaced–ideally by the much stronger, 128-bit A5/3 system, which is already being used in newer-generation digital cellular systems, such as Universal Mobile Telecommunications System (UMTS). “If you go from the 64 bits of the A5/1 cipher to the 128 bits of A5/3,” says Nohl, cracking requires an amount of memory storage that is beyond what “is available on earth.”

A big problem with plugging the GSM encryption hole, according to the security expert, is that operators are unwilling to admit that a problem even exists. Many want to avoid spending additional money on upgrading aging and amortized GSM infrastructure, he says. The GSM Association, which represents the interests of GSM mobile operators around the world, says only that it is aware of various eavesdropping projects. In the same breath, it points to the complexities of identifying and recording calls from RF signals.

On his recent visit to England, President Obama presented the Queen with an iPod loaded with showtunes. Although one might question the diplomatic and musical judgment behind such a gift, it also raises some interesting questions about copyright law and computer security.

The EFF has an interesting article about the copyright issues: iPods, First Sale, President Obama, and the Queen of England, Fred von Lohmann, 2 April 2009. It starts,

President Obama reportedly gave an iPod, loaded with 40 show tunes, to England’s Queen Elizabeth II as a gift. Did he violate the law when he did so?

You know your copyright laws are broken when there is no easy answer to this question.

The other question this raises is how effective of a malware vector this is when the Queen attaches the iPod to her PC (okay, the Queen probably runs ubuntu). I don’t know if there are any known vulnerabilities in the iPod/iTunes interface, but its a wide enough interface that it would be very unsurprising if there are ways to get malware from an iPod to a host machine. Perhaps, this is all part of a clever strategy to make heads of less friendly states than the Queen expect to receive electronic gadgets from our President and connect them to their systems.