February 26, 2008 — If you hold a credit card issued in the past 18 months, or use a touchless keycard to open doors at your office, or ride the subway with a reusable fare card, chances are good that you have used a card or ticket with a tiny wireless security chip embedded in it.
A trio of young computer experts, including a student at the University of Virginia, recently demonstrated that the encryption used by over a billion such "smart cards" is much easier to break than previously thought. Their research shows that a tech-savvy thief with only a personal computer and about $1,000 worth of readily available equipment could make fake access cards to gain entry into high-security areas, could produce counterfeit mass-transit fare cards, and could even gain entry to cars by cloning certain wireless car keys that can open or lock the car from 20 feet away by clicking a button. (In order to drive the car, the would-be thief would still need to defeat the mechanical ignition system.)
In order to prevent those with nefarious purposes from exploiting this security hole, the trio — including U.Va. graduate student Karsten Nohl — have not publicly disclosed the full details of how they defeated the wireless security. But their demonstration of the vulnerability of these widely used chips is a wake-up call to the millions of people already using these chips.
Security experts knew that it was feasible to break the encryption of this type of wireless chip, explained Nohl, but most assumed that it was difficult enough to do so that the chips were unprofitable to attack. Companies that do so for legitimate purposes (such as checking chip designs for patent infringement) would charge from $100,000 to $500,000 and use esoteric (and expensive) research laboratory equipment — a high threshold to steal information from a wireless computer chip that is about the size of a grain of sand and costs less than a dollar.
Like many doing academic research on cryptography, Nohl looks for vulnerabilities in existing security systems in order to help build better systems in the future.
"In order to build more secure systems, you have to understand why previous systems failed," said David Evans, an associate professor of computer science in U.Va.'s School of Engineering and Applied Science, who is Nohl's adviser for his doctoral studies in computer security. "Analyzing systems and understanding how to break them gives you a lot of insight into how to build better systems."
Originally from Germany, Nohl and his two Germany-based partners presented their research at a conference in Berlin in December that demonstrated for the first time — publicly, at least — that the costs of breaking this wireless security are much lower than previously thought. How many malicious hackers have done so already, or will do so in the future, is anybody's guess.
The miniscule computer chips at issue are called RFIDs, short for "radio-frequency identification." They send and receive information over short distances (generally 10 feet or less) via very low-power radio waves.
RFIDs were first used commercially in the 1960s on a small scale, but as the costs of RFID tags have dropped precipitously over the past two decades, RFIDs have become widely deployed and there are now billions of them in use. Their use has grown exponentially since 2000, and some experts predict it will continue to grow explosively in the near future. RFIDs may one day effectively replace (or at least augment) the ubiquitous bar codes that currently identify all our products. In such uses, the information held on the RFID is often unencrypted.
But in other more demanding applications — including credit cards, car keys, high-dollar event tickets, subway fare cards and high-security building access control keycards — the RFID's information is encrypted to prevent it from being read and potentially exploited by anyone with an RFID reader device.
Nohl and his collaborators broke the encryption on one particular RFID chip – the MiFare Classic, created by Philips, the global electronics giant. First introduced in 1994, sales in the intervening 13 years have purportedly made it the most popular single RFID chip for security applications in the world, with over a billion sold worldwide, according to NXP Semiconductors, the Philips spin-off that now manufactures the chip.
Thanks to their low cost (around 50 cents apiece) and reliability, MiFare Classic chips are used in thousands of applications, in smart cards and tickets with dozens of different brand names. The MiFare Classic chip is used by millions of people to pay fares on several major mass-transit systems around the world, including the London Underground (known there as the Oyster card) and the Boston subway (where it's called the CharlieCard). A similar RFID chip from Philips powers some keyless car entry systems.
The first barrier to breaking the encryption of RFID chips like the MiFare Classic was being able to "listen" to the information that such chips broadcast, in encrypted or unencrypted form. Until 2006, one could not buy an RFID reader that could "read" the information from any RFID. All prior RFID readers were quite specialized, like an FM radio that could only listen to one station.
The advent in 2006 of affordable (under $150) and commercially available RFID readers was the beginning of a new era of scrutiny — and vulnerability — of the security used in RFIDs. Suddenly the door to RFIDs was thrown open, and those with expertise in the sophisticated security techniques used in modern personal computers could easily study the comparatively primitive encryption used by many low-cost RFIDs. (Higher-cost RFIDs, including other models from NXP Semiconductors, use very strong encryption, but their high cost limits their applications.)
"You can't consider the RFID world separate from the world of computers anymore, as manufacturers have in the past," said Nohl. "People have and will, as we have, taken security expertise from the world of computers and applied it to RFIDs, whose designers had been operating under the assumption that their world was apart from such scrutiny."
Once Nohl's team could read the raw information transmitted by the MiFare Classic, breaking its encryption involved surmounting several technical challenges.
Nohl and his colleagues "dissected" the MiFare chip to reveal each of the five layers of circuitry that make up the chip and produce the encryption. To do so, they looked at the chip under a conventional optical microscope, and used micro-polishing sandpaper to remove a few microns of material at a time to reveal each layer of circuitry, which then was digitally photographed.
Since their imaging equipment was so rudimentary, Nohl wrote custom optical recognition software that recognized and clarified the different elements that made up each circuit. The team then combined the clarified pictures from each of the chip's layers to produce a clear, three-dimensional picture of the entire circuitry, much like medical magnetic resonance imaging forms a 3-D image of a brain or knee by combining many slices of images.
Drawing on his training in computer hardware design, Nohl painstakingly looked at the shapes that made up the details of the circuit and deduced the algorithm (a mathematical formula involving many steps) created by the long series of hundreds of "logic gates." Knowing the algorithm defined the relatively narrow range of possible keys that would unlock the encryption, allowing Nohl to find the right key in a matter of hours by trying all the possible keys until he found the right one. Having done that once or twice, he could pre-compute the possible keys and break the encryption on other examples of the MiFare chip in a matter of minutes.
Nohl and colleague Henryk Plötz presented their research in December at the Chaos Communication Congress in Berlin, a major annual meeting of the international hacker scene. Their presentation demonstrated that "with very little resources and starting from scratch, this can be done," Nohl noted.
(NXP Semiconductors declined requests to comment.)
The Nohl team's revelations come at an interesting time. The Netherlands are currently in the midst of rolling out a new $3 billion national transit fare system that relies on the MiFare Classic chip to store fares to ride the subways and buses. In the wake of the Nohl group's research, the Dutch media reported extensively on the vulnerability of the system's smart card, that stores fares and can even be linked, on request, to a customer's bank account in order to automatically reload the fare balance when it drops under a certain threshold. With the security of such a costly system called into question, the Dutch government has convened several hearings. Since special RFID card readers designed specifically to talk to the MiFare Classic are deployed in thousands of locations throughout the transit system, switching to a higher-security RFID chip may be difficult and costly.
The idea of keeping secret the design of a security system is known in the trade as "security by obscurity." It almost never works; the secret invariably leaks out and then the security is gone, Evans and Nohl said.
As a result, most security professionals espouse Kerckhoffs Principle — first published by the Dutch cryptographer Auguste Kerckhoffs in 1883 — the idea that the design of all security systems should be fully public, with the security dependent only on a secret key. Public review of security designs also tends to catch flaws during the design process, rather than after the flaws are inherent in expensive systems, such as in the Netherlands transit system, noted Nohl and Evans.
For the millions of MiFare Classic-powered smart cards used in thousands of applications, this research from Nohl's group proves that little stands in the way of future security breaks. Other RFID chips that rely on similar proprietary encryption are similarly vulnerable, said Nohl, who is currently investigating similar chips.
If more consumers understand the fundamental flaw of "proprietary security algorithms" and other marketing-speak that touts what amounts to security by obscurity, then manufacturers may start opening up more of their security designs to the light of public scrutiny, which will ultimately result in better security in our digital age.
At least that's the hope of Nohl, Evans and others.