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.

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.)

From Trend Micro’s Malware Blog: Hacked RFIDs Render Smart Cards Less Smarter [sic]:

Falling into the wrong hands, this security loophole can be and will surely be used in high profile heists and break-ins, seemingly straight from a James Bond movie.

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.

Our paper on using data diversity in a redundant execution framework is now available:

• Anh Nguyen-Tuong, David Evans, John C. Knight, Benjamin Cox, Jack W. Davidson. Security through Redundant Data Diversity. 38^th IEEE/IFPF International Conference on Dependable Systems and Networks, Anchorage, Alaska, June 2008. (PDF, 10 pages; Abstract)

Anh Nguyen-Tuong will present the paper in Anchorage at the DSN conference in June.

This paper builds on our pervious work on N-Variant Systems. It includes the earliest systems-related technical related work in any paper I’ve been involved in, and I doubt we’ll be able to get an earlier one anytime soon. It turns out efforts Nevil Maskelyne led back in the 1700s to compute astronomical tables is closely related to the techniques we describe in this paper.

The Tech Herald has posted an interview with Karsten Nohl: Interview: Karsten Nohl – Mifare Classic researcher speaks up, by Steve Ragan, 14 March 2008.

This follows three earlier articles:

• University students in Virginia crack smartcard chips, 4 March 2008.
• U.VA. researchers crack smartcard chips – Mifare Classic security proven weak, 12 March 2008.
• Did NXP finally acknowledge security problems in their Mifare chip?, 12 March 2008.

Peter Lee, head of Computer Science at CMU, has posted an article about undergraduate research awards on his blog: CRA Outstanding Undergraduate Awards. It includes a ranking of schools based on the number of their students who have been recognized by the CRA Outstanding Undergraduate Awards, which is “the most competitive award recognizing extraordinary research potential in undergraduate computer science”. The top four schools are: CMU and University of Washington, with 29 total awards; UVa, with 28 total awards; followed by Berkeley, with 22 total awards. Peter writes,

Looking through the top-25, UW and UVa should feel pretty good about this. We’ve always had the sense that those programs were doing something right, based on how applicants to our Ph.D. program tend to look.

I’m very proud of the recent CRA Awardees in our research group including Adrienne Felt (finalist in 2008, currently on a whirlwind graduate school tour), Salvatore Guarnieri (finalist in 2006, currently a PhD student at the University of Washington), and Jonathan McCune (honorable mentionee in 2003, nearly finished with a PhD at CMU).

I do feel the need to defend my Alma Mater in response to this comment in Peter’s post:

Notably absent from the top-25 are MIT and Stanford. Now, one might try to argue that CRA undergrad awards aren’t indicative of program quality. Perhaps. But given how competitive this is, I would say it is pretty clear that CRA awards show either (a) that faculty are good enough and care enough to get undergrad students involved in high-level research or (b) that faculty care enough to make sure their best students are nominated. Either way, especially in an era when everyone is worried about the CS pipeline (meaning that good departments should be cultivating good young researchers), the best programs simply should have lots of CRA winners.

I don’t know about Stanford, but for MIT the reason definitely is not (a). I was an undergraduate at MIT from 1989-1993, and the faculty there were very committed to involving undergraduates in research and making sure they had a good experience with it. Nearly every student in EECS got some high-level research experience, and at least half the students I knew got involved in a research group within their first year as an undergraduate. (The others often complained that many professors seemed to teach the intro-level courses with the primary goal being to recruit students into their research groups.) MIT estimates that “at least a quarter of EECS undergraduates eventually receive a PhD from some university”, which I suspect is the highest rate of any CS program. If it was possible to produce a table of whose undergraduates eventually become CS professors, I guess MIT would be at the top of that list also. While I was an undergraduate at MIT, I had the privlege of working in research groups led by Marc Raibert and Arvind, both of whom were great influences towards an eventual research career.  I was also an undergraduate teaching assistant for John Guttag, who became my graduate research advisor. So, I don’t know why MIT isn’t winning more CRA awards, but it definitely isn’t because the faculty are not doing a great job involving undergraduates in high-level research.

When you visit Peter’s blog, make sure to also check out the hilarious video of Bill Gates’ last day at Microsoft from a talk he gave at CMU: Notes from the Bill Gates Visit.