Jefferson's Wheel

Karsten Nohl, who complete a PhD in our group in 2009, is visiting UVa this week. UVa Today has an article: Renowned ‘White Hat Hacker’ to Speak on Real-World Security Holes:

University of Virginia graduate Karsten Nohl, one of the world’s most famous “white hat computer hackers,” will speak Friday at 3:30 p.m. in Rice Hall, room 130, about lessons learned from the security holes that he and fellow researchers have uncovered in mobile phones, wireless car keys and other technology used by billions of people everyday.

Nohl first made international headlines in 2008, while still a computer engineering doctoral student at U.Va., for research that exposed vulnerabilities in the world’s most popular smartcard, used by millions of people to pay fares on several major mass-transit systems around the world, including the London Underground and the Boston subway.

Such cards utilize miniscule wireless computer chips, about the size of a grain of rice, called RFIDs, short for “radio-frequency identification.” They send and receive information over short distances (generally 10 feet or less) via very low-power radio waves.

As an ethical security researcher, often called a “white hat hacker,” Nohl exposes vulnerabilities to spur improvements in the systems that he researches. He now does such work around the world as the founder and director of research at Security Research Labs in Berlin.

To prevent those with nefarious purposes from exploiting security holes he uncovers, Nohl typically withholds key details of the exploit and discloses his findings only months after sharing his research with the relevant manufacturers or trade organizations to allow them to roll out upgrades or countermeasures to mitigate the security risk.

Since graduating from U.Va. in August 2008, Nohl has gone on to discover and demonstrate two key security vulnerabilities in mobile phones – encryption flaws in both the GSM protocol that most cell phones use to communicate with cell towers, and in SIM cards, the tiny “subscriber identity module” chip in every phone that identifies and authenticates the phone.

Both discoveries generated worldwide media coverage.

As just one example of possible ramifications, the latter security hole could allow a malicious hacker to send a virus through a text message, which could then allow the hacker to eavesdrop on calls or make purchases through mobile payment systems.

“Karsten has had an outstanding impact in analyzing how cryptography gets used in the real world and demonstrating what goes wrong when important engineering principles are not followed carefully,” said computer science professor David Evans, Nohl’s former doctoral adviser and a co-organizer of Friday’s talk. “The vulnerabilities he has identified in RFID algorithms, GSM encryption and SIM cards impact billions of devices most of us use every day, and it’s really important that people understand the security weaknesses in these systems and that vendors work to improve them. Karsten’s work is a fundamental step toward those goals.”

Nohl’s talk will discuss how security exploits with real-world implications are usually enabled by not just one design flaw, but by deviations from best practices on multiple design layers. Protection designs that focus on a single security function and neglect complementary layers are more prone to compromise, Nohl will argue, with examples from his own research on three widely deployed technologies – cell phones, car keys and smartcards.

“Real-world cryptographic systems rarely meet academic expectations, with most systems being shown ‘insecure’ at some point,” Nohl said in an email description of his talk. “At the same time, our IT-driven world has not yet fallen apart, suggesting that many protection mechanisms are ‘secure enough’ for how they are employed.”

The talk will be followed by a reception in the fourth-floor atrium of Rice Hall.

The event is co-sponsored by the departments of Computer Science and Electrical and Computer Engineering, which jointly administer U.Va.’s computer engineering Program in the School of Engineering and Applied Science.

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.

Randolph Yu Yao is joining our research group and the NSF RFID project. He’s a PhD student in Computer Engineering and will be working on something related to security and privacy for RFID systems that integrates cryptographic requirement with circuit-level designs.

His brief bio is below. Please join me in welcoming Randolph to the group!

I was born in a small city in southeast of China, and traveled from south to north during my high school, undergraduate, half-graduate study. I’m very happy to travel to the other half of the planet for my PhD study here in the end.

I was an EE major and love to deal with various aspects of embedded system. I’ve worked on the RoboCup, which forms a robot team to play “football”; the Mobile Satellite Communication Vehicle, which essentially control the attitude of antenna in dynamic circumstance; the Multi-Agent Cooperation via wireless communication etc. I didn’t realize before that the security issues of the embedded system are very challenge problems and becomes a bottleneck for their ubiquitous deployments, no matter for sensor networks or RFID. My ultimate goal is to enable these smart embedded systems acceptable by common people and put into daily service without concern about the security and reliability in the face of expanding network connection.

I also like sports such as swimming, traveling, exploration, basketball, hiking but no running which I think too boring. I enjoy the weather, the blue sky and fresh air here.

Technology Review has an article surveying the state of RFID security: RFID’s Security Problem, Technology Review, January/February 2009. It focuses on security and privacy issues related to RFID-enabled passports and driver’s licenses.

Excerpt: (bolding is mine)

Meanwhile, although experts say that some RFID technologies are quite secure, a University of Virginia security researcher’s analysis of the NXP Mifare Classic (see Hack, November/December 2008), an RFID chip used in fare cards for the public-­transit systems of ­Boston, London, and other cities, has shown that the security of smart cards can’t be taken for granted. “I think we are in the growing-pains phase,” says Johns Hopkins University computer science professor Avi Rubin, a security and privacy researcher. “This happens with a lot of technologies when they are first developed.”

…
As long as the remaining problems are ignored, though, it’s unlikely that the technology will become good enough to protect international borders without compromising the privacy of thousands or millions of people. Tadayoshi Kohno, for one, says that at this point, he is not convinced that RFID even offers security advantages over the old IDs. Technology used on this scale, and for purposes this important, should be clearly better than what it’s replacing: the U.S. experience with electronic voting systems shows what can happen when it’s not. If officials continue to advocate band-aids such as privacy sleeves rather than working to address the full extent of critics’ concerns, they will ultimately undermine the very technology that they hope to promote. While new ID technology seems likely to stay, it could become a fiasco if officials don’t pay attention to the work of hackers and security researchers. These people try to expose weaknesses before they can be exploited maliciously. It’s much less painful to swallow the news from them than to wait until a problem becomes embarrassing–or devastating.

The Daily Progress has an rather odd article juxtaposing our RFID research with a donation from Bob Barker (“Price is Right” host) to the law school to fund animal rights research: Barker’s gift to found animal law program; Science Foundation funds chip research. Perhaps we can combine projects to work on preserving pet privacy when implanting RFID tags in animals.

…
“Animal law is a growing area that is in much discussion,” Riley said. “It is a good way even for a student who has no interest in practicing animal law to enlarge their interest and to understand different ways the law works.”

A recent of example is Leona Helmsley’s will, Riley said.

When the hotelier, dubbed the “queen of mean,” died at 87 in August 2007, she spurred a legal debate by leaving behind a $12 million trust for the care of her dog.

Riley said a group of students at UVa have shown interest in animal law.

Elsewhere at UVa, the National Science Foundation’s grant will enable a team of engineers to create a more secure design for RFID chips, which are commonly found in remote car-locking systems and touchless debit cards.

These tiny chips, which send information over short distances using weak radio waves, are an increasingly popular way to monitor potentially sensitive information.

UVa researchers have been working to create a stronger encryption scheme that would keep information on RFID chips secure while keeping costs low.

[Added: 14 Jan] NetworkWorld has also picked up this story: NSF gives University of Virginia researchers a million good reasons to improve RFID security, privacy, by Alpha Doggs, NetworkWorld, 14 Jan 2009.

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 November/December 2008 Technology Review Hack, How Smart Is a Smart Card?”, describes Karsten Nohl’s work on reverse engineering the Mifare Classic. In includes a video of a card dissolving, and some great images.

The full details of the Crypto-1 cipher (initially exposed back in December) have now been released.

They are published in Appendix A of Henryk Plötz’s thesis report: Mifare Classic – Eine Analyse der Implementierung. The thesis is in German, but the algorithm is published as a C program (by Karsten Nohl, Henryk Plötz and Sean O’Neil), so should be understandable to non-German code readers.

Also yesterday, the paper, Dismantling MIFARE Classic, by Flavio D. Garcia, Gerhard de Koning Gans, Ruben Muijrers, Peter van Rossum, Roel Verdult, Ronny Wichers Schreur, and Bart Jacobs of Radboud University Nijmegen, The Netherlands, appeared at ESORICS 2008. This is the paper that was the subject of NXP’s failed lawsuit.

The publication of these details remove any remaining doubts about the insecurity of the Mifare Classic.

News articles:

D-Day for RFID-based transit card systems, c|net News, 6 October 2008.

“Combining these two pieces of information, attacks can now be implemented by anyone,” RFID researcher Karsten Nohl told CNET News. “All it takes is a $100 (card) reader and a little software.”
…
Security systems like the Mifare Classic that are not peer reviewed are not as trustworthy as systems that can be openly analyzed by researchers looking for flaws, Johanson and Nohl said.

“Developing your own proprietary security mechanisms and not getting public scrutiny on it does not work,” Nohl said.

Boffins (finally) publish hack for world’s most popular smartcard, The Register, 6 October 2008.

Two research papers published Monday have finally made it official: The world’s most widely deployed radio frequency identification (RFID) smartcard – used to control access to transportation systems, military installations, and other restricted areas – can be cracked in a matter of minutes using inexpensive tools.

The two documents combined mean that virtually anyone with the time and determination can carry out the attacks, said Karsten Nohl, a PhD candidate at the University of Virginia and one of the cryptographers who first warned of the weakness in December.

“Now the weakness that we and others have been talking about for months can be verified independently by really anybody,” he said. “The flip side is that everybody can now attack Mifare-based security systems.”

Over the past six months, many organizations that rely on the Mifare Classic have upgraded their systems, but Nohl said he is personally aware of a “handful” of systems used by government agencies or large multinational companies that have been unable to make the necessary changes because of the logistical challenges of issuing new badges to employees.

“One hopes that just based on the announcement, most operators of critical security systems have adopted other technologies besides Mifare,” Nohl said.

Update: (10 Oct) Another article from the CBC: Security flaw in smart cards poses risk for transit, building access, CBC News, 10 October, 2008.

Verayo is the second company to announce the "World’s first unclonable RFID tag" based on a physically unclonable function (PUF), after Veratag announced a similar product based on PUF technology. The security claims of these and other PUF-based products seem dubious since the current realization of PUFs defies basic principles of cryptography. The announcement states:

This new RFID chip is based on recently announced breakthrough technology called Physical Unclonable Functions (PUF). PUF technology is a type of electronic DNA or fingerprinting technology for silicon chips that makes each chip unclonable.

It might be besides the point that neither DNA, nor fingerprints are unclonable. The failure of proprietary security, which has been a constant theme on this blog, has led many to conclude that only well-reviewed security primitives can be strong. PUF technology tries to achieve security in exactly the opposite way: the PUF circuit is designed in a way so that not even the designer understands how outputs are derived from inputs. Security-by-obscurity par excellence.

Every circuit, including PUFs, is a deterministic function; the only difference in PUF circuits is that some inputs to the function vary across different tags. For a PUF to be cryptographically strong, one would hence need to show that

1. the fixed part of the circuit (the cipher) is strong by cryptographic metrics,
2. the number of device-dependent inputs (the secret key) is large and
3. the entropy of these inputs is high.

PUFs are a wonderful idea for using manufacturing variance constructively, but in their current realization, PUFs fail to convince that they are strong building blocks for security systems.