Jefferson's Wheel

NXP is suing Radboud University in the Netherlands to prevent them publishing a paper (in ESORICS 2008 in October) containing details on the Mifare classic encryption algorithm (and various flaws they have found in the algorithm). Perhaps the title of the paper, “Dismantling MIFARE Classic”, got NXP’s attention. A hearing is scheduled for July 10.

Articles:

• Dutch chipmaker sues to silence security researchers, c|new News, 9 July 2008.
• NXP sues academic research team – what are they afraid of?, The Tech Herald, 10 July 2008.
• NXP sues to prevent hackers from releasing MIFARE flaws, Secure ID News, 10 July 2008.
• Chipmaker sues to quash research on RFID smart card security flaws, Computer World, 10 July 2008.

[Update 18 July] The judge has denied NXP’s request for an injunction, ruling that “limitations to the freedom of speech are allowed only if there is urgent and obvious threat to society”: Judge denies NXP’s injunction against security researchers, Industry Standard, 18 July 2008.

[Update 21 July] Another article: Dutch court allows publication of Mifare security hole research, CNet News, 18 July 2008. This one includes a picture of Karsten Nohl’s presentation at the Last HOPE Conference.

KIRO TV (Seattle) has a story on RFID privacy issues: Credit Cards Stolen Without Leaving Wallet (it includes a video demonstration).

German-born Karsten Nohl is a security consultant and PhD student at the University of Virginia. He was in Seattle recently to speak at a technology conference and is known worldwide for hacking into transit systems.

He’s exposed significant security problems with transit cards commuters were told held their personal information secure, but Nohl showed, did not

“Is it all that inconvenient to swipe a card? Does it really have to be tapping? Would, for that perhaps tiny added benefit, now expose your data to everybody in your vicinity? Perhaps not. So, that is a discussion that has to be had. And not just by the companies introducing something new and fancy and forcing everybody to use it, but rather by the consumers, too,” said Nohl.

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]

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.

Full paper (15 pages): [PDF]

Extended Technical Report (18 pages): [PDF]

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.

The April 2008 Communications of the ACM includes an article by Hal Berghel,
Faith-Based Security: A tongue-in-cheek look at serious security issues (requires ACM subscription, otherwise see [ungated version]). It includes the MIFARE cryptanalysis (along with Windows buffer overflow vulnerabilities, WEP’s RC4 implementation, Cisco’s LEAP) as an example of the failure of security through obscurity. Its worth reading the whole article, but here are a few excerpts:

IT security has received increased attention over the past few decades primarily, but not exclusively, due to the increased threat from viruses, worms, password crackers, Trojan horses, and a cornucopia of other types of malware and exploits. As a consequence of this increased attention, a variety of security models have been proposed. Security-in-depth (SID) is one such example. Winn Schwartau’s time-based security is another. In this column I offer another modest example extrapolated from popular culture: Faith-Based Security, aka “no network left behind.”
…
I admit that a prima facie case could be made for security-in-depth even in the naïve sense of “more-is-better.” When I propose adding a new vitamin to my diet, my internist tells me “at this point there is no physiological evidence that suggests that this substance is harmful to humans, so knock yourself out.” As with my vitamins, a random application of security applications and systems is unlikely to do any more harm than lure one into a false sense of security, and perhaps slow things down a bit. And like the vitamins, when carefully and judiciously applied and evaluated in a controlled experimental setting, even naive security-in-depth can be of some value.

Such is not the case with our third model: security-through-obscurity. No prima facie case may be made here.
…
My final example came to my attention within the past few weeks. MIFARE is an proprietary encryption technique for RFID (Radio Frequency Identification) developed by Philips and Siemens in the late 1990′s. MIFARE is an attempt to cryptographically secure the now-ubiquitous RFID space which relies on RF transmission for communication between transmitter and receiver.

Following the common theme, the security of the proprietary MIFARE system is predicated on the belief that no one will discover how it works. And, as one might predict, some MIFARE circuits were reverse-engineered down to the gate level. The result was the discovery that the random number generation that drove the encryption resulted from a 16-bit key linear feedback shift register based on a master key and a time signature. With RFID sniffing via an open PICC (proximity integrated contactless chip) card and a logic analyzer, it is possible to discern patterns in the challenge-response authentication procedure that can be used in a replay attack, and from there it is possible to recover the key from the value of the unique identifier and the observed behavior of the shift register in the authentication process. We’ll create STO category III for this MIFARE vulnerability: turning chip designers loose with CAD/CAM software without adequate education and training.

EETimes and RFID-world.com published an op-ed piece by me that discusses the current lack of security in NFC cell phone standards.

Near Field Communication (NFC) phones automatically exchange data with other phones and objects in their vicinity. These phones are the latest example of a new technology developed with a strong focus on potential applications, but without sufficient thought to security and privacy concerns.
…
Adding sound security and privacy protection will slow down the deployment process and most likely increase the cost. Perhaps, security has this intrinsic cost that cannot be avoided as long as technologies create new incentives for thieves. NFC phones will attract misuse and computer fraud unless strong protection is included as a mandatory part of the NFC standards, similar to e-mail that promised simple, cheap, world-wide communication for everyone, but is now spoiled for many by spam, viruses and phishing.

The EETimes reports on our Mifare work after the news had gotten out in Germany through an article in the c’t magazine. Slashdot picked up on it as well and summarizes:

[T]he device is used in many contactless smartcard applications including fare collection, loyalty cards, and access control cards. NXP downplays the significance of the hack, saying that that model of RFID card uses old technology and they do a much better job these days.

One is left wondering why the old technology is then not replaced by those much better products that have been available for many years.