Jefferson’s Wheel

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.

Full paper (9 pages): [PDF] [HTML]

Nathanael Paul’s PhD dissertation has been approved! He will graduate this Sunday.

The dissertation is available here: Disk-Level Malware Detection [Abstract] [Full text: PDF, 155 pages].

Congratulations, Nate! (That is, “Dr. Paul”.) Nate is currently a post-doctoral fellow at Vrije Universiteit, Amsterdam working with Andrew Tanenbaum.

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

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 23^rd 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.

The Associated Press has an article by Martha Irvine, Social networking applications can pose security risks, that is based on Adrienne Felt’s analysis of Facebook platform privacy.

Still, it’s an honor system, says Adrienne Felt, a computer science major at the University of Virginia. A Facebook user herself, she decided to research the site’s applications and even created her own so she could see how it worked.

Most of the developers Felt polled said they either didn’t need or use the information available to them and, if they did, accessed it only for advertising purposes.

But, in the end, Felt says there’s really nothing stopping them from matching profile information with public records. It also could be sold or stolen. And all of that could lead to serious matters such as identity theft.

“People seem to have this idea that, when you put something on the Internet, there should be some privacy model out there — that there’s somebody out there that’s enforcing good manners. But that’s not true,” Felt says.

(Note: there wasn’t actually any “polling” of developers, just examining what applications do to determine how they appeared to use information.)

The story has been picked up by some other places including BusinessWeek, CNNMoney (From games to virtual gifts, social networking applications popular — but at what risk?), Forbes, International Herald Tribune, National Public Radio, San Jose Mercury News, Philadelphia Inquirer, Las Vegas Sun, Fort Worth Star-Telegram, Houston Chronicle, San Francisco Chronicle, Seattle Post-Intelligencer, MyFOX, and The Sydney Morning Herald.

The Colorado Daily wins the best title award for MySpace is your space (and yours, and yours…) (but its the same story).

Pantagraph (Central Illinois) has it currently as their top article and includes a picture their front page.

[Added 13 May] Pew Internet and American Life Project has a post on this: Securing Private Data from Network ‘Zombies’ by Mary Madden.

My shameless self-searching google alert occasionally turns up interesting things, like this letter to the editor of the Huntington News (West Virginia) by Gary Hurd. It refutes an op-ed piece that made all sorts of crazy pseudo-scientific arguments for “intelligent design”. The letter refutes one of the specific claims in the argument about the complexity of DNA using some material found in a lecture for my CS201J course:

And is this notion that human DNA is more complex than “any program ever devised” actually factual? The book by Watson was published in 1965, and the book by Gates that Ashby is misquoting was published in 1995, before the human genome project when we did not even know how many genes humans had! At the time, Gates’ statement was entirely reasonable, even though there was no actual data to test it. But Ashby makes a further claim, “… it is a well known fact that human DNA contains more organized information than the largest set of encyclopedias ever in print.”

David Evans, Professor of Computer Science at the University of Virginia has made some interesting comparisons between DNA and today’s computer software as part of his Computer Science 201: Engineering Software course. Let’s begin with his observation that complexity of computer software has grown at an amazing rate in the last 40 years (about since Watson’s book on the gene was published). The Apollo mission guidance programs had about 36,000 instructions, but today’s Windows XP made by Bill Gates’ Microsoft has about fifty million instructions! Professor Evans then compares this to what we now know about genes. For example, the smallest known set of genes of an organism belong to a bacterial parasite called Nanoarchaeum equitans which has 522 genes representing about 40,000 bytes of information. In other terms, it is slightly larger than the Apollo guidance system. The human genome, or as Evans called it “The Make-Human Program,” has a total of about 3 billion base pairs, which entail about 35 thousand genes. The total information content counting all of the bases is 750 megabytes, or just larger than the 650 megabytes that fit on your CDs at home. But, we have learned that massive amounts of human DNA are genetic “left overs,” non-coding segments and duplications. In short, Human DNA has fewer working instructions than Windows software, and even its total 3 billion bases are tiny compared to Wal-Mart’s 280 terabyte database (the equivalent of 1,120,000 billion DNA bases).

Like most antiscience, Ashby’s “well known facts” are not facts.

The lecture he is referring to is here: Lecture 23: Everything Else You Should Know (but won’t see on Exam 2) [PPT] (slides 18-26). Although I am happy to have anything I’ve done used to debunk intelligent design, the point I meant to make here is a bit different from what Dr. Hurd’s letter is claiming — I am not intending to suggest that the genome is not a complex program (since one could still claim it results in executions that are still far more complex, resillient, and sophisticated than anything humans have created), just that its encoding is incredibly expressive in order for such complex outcomes to be encoded with so little information. Of course, a lot of the information is not in the genome itself, but in the very complex biochemical operating system in which it is interpreted.

The specific claim from the original op-ed piece, that “DNA contains more organized information than the largest set of encyclopedias ever in print”, of course, is blatantly false. A few image-laden pages of a World Book volume contain far more information that the entire human genome.

Congratulations to two of our students who received awards yesterday!

Adrienne Felt received the Outstanding Student Award for the School of Engineering and Applied Science from the Virginia Engineering Foundation. This is an annual school-wide award for the graduating fourth-year student who has “demonstrated outstanding academic performance, leadership and service”.

Karsten Nohl won the Department of Electrical and Computer Engineering’s Louis T. Rader Graduate Research Award recognizing his outstanding research as a Computer Engineering PhD student.

Even I won an award this week.

Congratulations to Karsten and Adrienne for their much-deserved awards.

ComputerWorld has an article about the new cryptanalysis of Crypto-1 results:
MiFare RFID crack more extensive than previously thought: Seconds, not hours, to effect; plus version tappable too, ComputerWorld, 15 April 2008.

The ubiquitous MiFare Classic RFID chip — used daily by millions worldwide in access control keys, subway passes and other applications — is even easier to crack than previously thought, according to security researchers who announced the development Tuesday at EuroCrypt, an international cryptography conference in Istanbul.

Mere seconds are all that is required to crack the chip’s security — not a few hours, as estimated last month. Karsten Nohl, a computer science graduate student and one of the masterminds behind reverse-engineering MiFare security, said in an interview that it now takes only 12 seconds to recover the key on a MiFare Classic card on an ordinary laptop.

On Monday, the Dutch government issued a final report arriving at the decisive conclusion that the chips, used by millions of citizens in the Netherlands, must be replaced. An earlier Dutch report had stated that a security breach on the MiFare cards was possible, but would be too unwieldy for the average attacker to accomplish.

There is also a series of articles in the Brisbane Times (Austrailia):

• Go cards ‘doomed’ over security, Brisbane Times, April 11, 2008.
• Reveal contract details: Opposition, Brisbane Times, April 11, 2008. (This one is mostly political.)
• New report slams go card security, Brisbane Times, April 16, 2008.

Other articles include: Dutch transit card crippled by multihacks, The Register, 16 April 2008.

An external assessment of the Dutch OV-Chipkaart found the card to be vulnerable to various attacks and recommends additional protections as well as the migration to better cards. The report concludes that proprietary ciphers like the Mifare Crypto-1 stream cipher are hardly ever secure:

Indeed, the security of proprietary stream ciphers has a reputation of “falling apart” once exposed to scrutiny by the cryptographic expert community.

The report also recommends that public transport systems should be more open about their security measures to enable independent reviews. Similarly, the migration of current systems to more secure cards should be discussed publicly:

Providing open communication on progress towards the [migration] may have a deterrent effect on attackers and the independent review of draft versions of the plan should provide added confidence that migration will succeed.

We are certainly looking forward to reviewing new systems (and perhaps to suggesting improvements).

The Crypto-1 stream cipher used in Mifare Classic smart cards has been broken yet again. The new attack is the most efficient one yet taking only 12 seconds to recover the secret key. In this algebraic attack, we construct a system of linear equations that describe the cipher and then solve this system for a given authentication using MiniSAT to recover the secret state and ultimately the secret key. The attack can operate on passively sniffed data which enables an attacker to gather the required data from meters away. Unlike previous attacks, it also works regardless of the quality of random numbers.

The Mifare Plus card that is meant to replace Mifare Classic in legacy installation is only marginally affected by the new results. Mifare Plus includes AES encryption—an open cipher that is generally assumed to be very secure.