Jefferson's Wheel

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.

Bruce Schneier’s blog has another post about the Mifare cryptanalysis: London Tube Smartcard Cracked, Schneier on Security, 14 March 2008.

Some other blogs have picked up on this, and there are some comments.

This article in ComputerWorld has an excellent account of the Mifare cryptanalysis and its implications: RFID hack could crack open 2 billion smart cards: Analyst: One European government sent armed guards to protect facilities using the card by Sharon Gaudin, Computer World, 14 March 2008.

A student at the University of Virginia has discovered a way to break through the encryption code of RFID chips used in up to 2 billion smart cards used to open doors and board public transportation systems.

Karsten Nohl, a graduate student working with two researchers based in Germany, said the problem lies in what he calls weak encryption in the MiFare Classic, an RFID chip manufactured by NXP Semiconductors. Now that he’s broken the encryption, Nohl said he would only need a laptop, a scanner and a few minutes to get the cryptographic key to an RFID door lock and create a duplicate card to open it at will.

And that, according to Ken van Wyk, principal consultant at KRvW Associates, is a big security problem for users of the technology.

“It turns out it’s a pretty huge deal,” said van Wyk. “There are a lot of these things floating around out there. Using it for building locks is the biggy, especially when it’s used in sensitive government facilities — and I know for a fact it’s being used in sensitive government facilities.”
…

The article also includes some interesting comments from a spokesman for NXP Semiconductors.

NXP, the manufacturer of the smart cards we analyzed recently, announced an improved card that could help with the migration to higher security levels. The Tech Herald has more on this.

The Mifare Plus cards implement secure 128-bit AES as well as the proprietary Crypto-1 cipher (that we have shown to be weak), but allow for the latter to be switched off once all cards have been migrated. Since all readers and cards still have to be replaced, the new cards are not necessarily a better choice than alternative cards. And while the Plus card won’t be seen in the market for another year, other cards with strong cryptography such as DESfire are readily available.

One feature of the Plus card that might be worth the wait is its improved privacy protection. Protecting individuals from being tracked has long been a research interest of ours and we are curious to see how industry solved this challenging problem.

In light of our recent results showing the security vulnerabilities in the Mifare Classic chip used in the London Transport Oyster card (and many other systems), this article about how the police use data collected from Oyster card users raises some interesting evidence and privacy concerns:
Police make 3,000 requests for data from Oyster cards, The Evening Standard, 21 February 2008.

Information obtained today by consumer magazine Which? shows that Transport for London received more than 3,100 requests from the police for passenger journey data between January and October last year.

Oyster cards were introduced five years ago and account for millions of journeys each day.

Which? today raised concerns about the apparent failure of Transport for London to make clear to passengers that their travel data will be stored for eight weeks at a time. It claims this is in breach of the Data Protection Act.

TfL says the information is required if journeys have to be refunded.

According to Which?, passengers signing up for an Oyster card are told their personal information is used for “the purposes of administration, customerservices and research”. However-there is no explanation that their bus, Tube and train journeys will be logged for up to two months.

Which? editor Neil Fowler said: “Which? is concerned that some private companies aren’t complying with the Data Protection Act and we urge them to tighten up their processes, so that consumers can be reassured that their data is in safe hands.”

Liberal Democrat mayoral candidate Brian Paddick said: “Companies increasingly have access to more and more of people’s personal details – and the public expect that data to be protected. It’s extremely worrying that every journey you make using Oystercard is recorded on TfL’s computer.

This article in The Register describes Karsten Nohl’s work on the Mifare cryptanalysis:
Microscope-wielding boffins crack Tube smartcard: The keys to London Underground, and plenty more. (12 March 2008)

For non-British readers, here’s how Wikipedia defines a “boffin”:

In the slang of the United Kingdom, Australia, New Zealand and South Africa, boffins are scientists, engineers, and other people who are stereotypically seen as engaged in technical or scientific research. The word conjures up an image of men in thick spectacles and white lab coats, obsessively working with complicated apparatus. Portrayals of boffins emphasize both their eccentric genius and their naive ineptitude in social interaction. They are, in that respect, closer to the “absent-minded professor” stereotype than to the classic mad scientist.

(For the record, Karsten doesn’t usually wear white coats.)

It’s nice to see our research being cited in so many places. Most of the news coverage is accurate and resonates our call for better security through open designs.

We would still like to clarify a few facts and address some points of critique: The focus of our research was on Mifare Classic RFID tags. While these are by far the most popular contactless smart cards, there are plenty of others that may or may not be secure. Using a proprietary cipher is usually evidence of bad design and only cards with standard ciphers such as 3-DES, AES, and ECC should be considered for security applications.

Our results do not apply to contactless credit cards since these do not encrypt data.

The manufacturer of the Mifare cards has repeatedly claimed that we have only broken one layer of security, which is true when looking at systems as a whole. Cryptography can only ever provide one layer of protection, two of the others being automated fraud detection and law enforcement. Computerized systems tend to rely on the cryptography, however, and are much more vulnerable to attacks once this layer of security is lost.

We believe in the potential of RFIDs to improve security in many domains. The current discussion will hopefully provide guidance in building more open, more secure systems.

PC World has an article about Karsten Nohl’s RFID cryptanalysis work: Hackers Find a Way to Crack Popular Smartcard in Minutes: Security on RFID-enabled smartcards is easily broken by young hackers. March 7, 2008.

The team used an inexpensive RFID reader to collect encrypted data, and then reverse-engineered the chip to figure out the encryption key to decipher that data. They examined the chip under an optical microscope and used micro-polishing sandpaper to remove a few microns of the surface at time, photographing each of the five layers of circuitry. Nohl wrote his own optical recognition software to refine and clarify the images, and then patiently worked through the arrangement of the logic gates to deduce the encryption algorithm, a task made possible by the fact that the Mifare Classic relies on a secret key of no more than 48 bits.

“Regardless of the cryptographic strength of the cipher, the small key space therefore permits counterfeiting of any card that is read wirelessly,” the team wrote in a follow-up statement issued on Jan. 8. “Knowing the details of the cipher would permit anyone to try all possible keys in a matter of days,” the researchers noted. “Given basic knowledge of cryptographic trade-offs and sufficient storage, the secret keys of cards can be found in a matter of minutes.”

[Added 12 March] PCWorld has a second article on this: RFID-Hack Hits 1 Billion Digital Access Cards Worldwide: A warning is issued that some security access cards that use RFID technology are vulenarble to hack attacks, 12 March, 2008.

The Boston Herald also has a story: Research: CharlieCard is far from hack-proof, March 6, 2008.

The Boston Globe has a story about Karsten Nohl’s work on cryptanalyzing the Mifare Classic: T card has security flaw, says researcher: Cracked code could lead to counterfeits, study team warns.

A computer science student at the University of Virginia asserts that he has found a security flaw in the technology behind the Massachusetts Bay Transportation Authority’s CharlieCard system.

German-born graduate student Karsten Nohl specializes in computer security. Nohl and two fellow security researchers in Germany say they’ve cracked the encryption scheme that protects the data on the card. The team warns that their breakthrough could be used to make counterfeit copies of the cards, which are used by commuters to pay for MBTA bus and subway rides.

… Nohl said that his team needed only about $1,000 worth of equipment to dismantle the chip and crack the code.

Nohl said that the RFID chip they compromised, the MiFare Classic by NXP Semiconductors of the Netherlands, is the one used in London’s subway system and in the MBTA CharlieCard. But MBTA spokesman Joe Pesaturo refused to confirm or deny this. “It’s MBTA policy not to discuss security measures around its smart card technology,” he said.

A 2004 policy analysis of the CharlieCard system produced by the Massachusetts Institute of Technology said that it would be based on MiFare technology.

NXP Semiconductors issued a statement saying that Nohl’s team breached only one of several security features built into the MiFare Classic chip. “This does not breach the security of the overall system,” the company said. “Even if one layer were to be compromised, other layers will stop the misuse.”

Evans said it might be hard to solve the issue. “There are chips that have a much higher security level available,” he said. “They cost more and it is not a trivial matter to upgrade the system.”

Ari Juels, chief scientist and director of computer security company RSA Laboratories in Bedford, said that Nohl’s research illustrates that there are serious security flaws in many smartcard applications. “The vulnerability is most certainly for real,” Juels said.

I’d be very curious to hear about those mysterious “other layers” the NXP spokesperson is talking about. Perhaps they are using the same amazing “extensive security mechanisms operating behind the scenes” that Facebook’s chief privacy officer was talking about here.