Jefferson's Wheel

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.

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.

The SecureIDNews podcast has an interview with Karsten Nohl about the Mifare cryptanalysis, as well representatives from NXP and the Smart Card Alliance: Episode 8: Interview with Mifare hacker Karsten Nohl, SecureIDNews Podcast, 2 April 2008.

Karsten Nohl is presenting talks this week in Vancouver:

Proprietary RFID Systems (with Jan “starbug” Krissler) at CanSecWest, Vancouver, Thursday, March 27.

and Seattle (at the University of Washington):

The (Im)possibility of Hardware Obfuscation, Monday, March 31

Here is the abstract for the talk at UW:

We will discuss several different approaches to reverse-engineering proprietary algorithms from hardware. The focus will be on a mostly automated approach I developed to reconstructing functionality by using a combination of image analysis of circuits and protocol analysis. The cryptography my approach finds on a widely deployed “secure” RFID token has several vulnerabilities including weaknesses in the random number generator and very low resistance against brute-force attacks. I will further raise the question of how small cryptography can be implemented and present our design for a small hash function that reuses circuitry already found on RFID tags.

(I believe the talk is open to the general public, but if you are interested in attending from outside the UW community, check with Evan Welbourne.)

This article in Computer World provides an excellent detailed description of how the Mifare reverse-engineering was done:
How they hacked it: The MiFare RFID crack explained, by Geetal Dayal, ComputerWorld, 19 March 2008. (It follows an earlier ComputerWorld article.)

NXP has released two statments about Mifare security: Information for end users and Information for system integrators.

The statements appear to be nearly identical. The excerpt below is from the statement for end users:

In December 2007 a group of researchers at the 24th Chaos Computer Club in Berlin claimed that they reverse engineered a MIFARE Classic chip and partially discovered the encryption algorithm of the chip. At the same time, they stated that they were not yet able to recover any keys from the chip.

NXP has come to the conclusion that two research groups have by now retrieved the algorithm and developed attacks which can be done with faster means of breaking keys than brute force. Although we are trying to prevent this, there is a risk of the full algorithm becoming publicly known and we feel it is appropriate to inform you about the potential consequences and necessary measures to be taken to minimize the impact of such eventuality for your system infrastructure.

Although we trust that you have worked with a system integrator who has implemented in your systems effective mechanisms to detect fraudulent cards (which we understand is possible in a number of ways), we want to inform you that we are investigating scenarios how MIFARE Classic systems can be protected Mindful of the above, we ask you to contact your system integrator to assess whether your systems would need any additional security measures.

It is our assessment that for transport ticketing installations, end-to-end security systems can be designed with the MIFARE Classic chip such that the residual risk of fraud not being detected in time can be drastically reduced. Whether or not those scenarios are acceptable in your risk assessment depends on the assets to be protected which only you and your system integrator can determine.

End to end measures should also be applied for access management infrastructures, which are often complemented by additional measures e.g. camera surveillance, security personnel, etc. when valuable assets need to be protected. We recommend that your assessment of the impact of the recent and expected developments takes into account the particular way that the system is implemented and used, its relation to other protection in place, and specifically whether there is a need to prevent unauthorized single time access or access during a limited period of time.
…

RFID Journal has an article about NXP’s new Mifare Plus chip, which supports AES encryption and is backward-compatible with the Mifare Classic:
NXP Announces New, More Secure Chip for Transport, Access Cards by Mary Catherine O’Connor, 14 March 2008.

This is an interesting development, but its not clear to me exactly what “backward-compatible” means: readers need to be upgraded to interact with the new tags. According to the article,

An RFID interrogator can employ the AES encryption deployed on the Mifare Plus chip to authenticate that chip before accepting its data and triggering a function, such as opening a locked door or allowing a commuter to pass through a transit turnstile. A number of additional security features, through the support of secure random identifiers, can prevent individuals from being identified and tracked by nefarious parties with RFID readers, NXP reports.

The chip’s encryption scheme uses a 128-bit key, whereas the Mifare Classic’s security algorithm employs a 48-bit key. The larger an encryption key, the longer it will take hackers to determine the key through reverse engineering.

NXP declines to reveal pricing for the Mifare Plus chip, but a chip’s price generally increases in step with its security features, so it will most likely cost more than the Classic chip. NXP says it will continue to manufacture and sell the Mifare Classic chip. Compared with other chips in the Mifare product family, the Classic supports the fewest security features. According to Manuel Albers, NXP’s director of regional marketing in the Americas, the Plus is more secure than the Classic but less secure than the Mifare DESfire chip, which uses a very robust data protection scheme called triple-DES.

Note: the comment that, “The larger an encryption key, the longer it will take hackers to determine the key through reverse engineering.” isn’t quite technically correct. If the key is larger, the time required to do a brute force key search is longer (it scales exponentially with the key size). The time to reverse engineer the algorithm scales with the complexity of the logic. The key size gives some minimum size for this complexity, and ciphers with longer keys are likely to have more complex logic, but this is not necessarily the case.