Steve Bono, Matthew Green, Adam Stubblefield, and Avi Rubin Johns Hopkins University Ari Juels and Michael Szydlo RSA Laboratories The Texas Instruments DST tag is a cryptographically enabled RFID transponder used in several wide-scale systems including vehicle immobilizers and the ExxonMobil SpeedPass system. This page serves as an overview of our successful attacks on DST enabled systems. A preliminary version of the full academic paper describing our attacks in detail is also available below.
Draft Academic Paper: PDF Table of ContentsAbout RFIDs and the Texas Intruments DST Radio-Frequency IDentification (RFID) is a general term for small, wireless devices that emit unique identifiers upon interrogation by RFID readers. Ambitious deployment plans by Wal-mart and other large organizations over the next couple of years have prompted intense commercial and scientific interest in RFID. The form of RFID device likely to see the broadest use, particularly in commercial supply chains, is known as an EPC (Electronic Product Code) tag. This is the RFID device specified in the Class 1 Generation 2 standard recently ratified by a major industry consortium known as EPCglobal. EPC tags are designed to be very inexpensive -- and may soon be available for as little as five cents/unit in large quantities according to some projections. They are sometimes viewed in effect as wireless barcodes: They aim to provide identification, but not digital authentication. Indeed, a basic EPC tag lacks sufficient circuitry to implement even symmetric-key cryptographic primitives. The term RFID, however, denotes not just EPC tags, but a spectrum of wireless devices of varying capabilities. More sophisticated and expensive RFID devices can offer cryptographic functionality and therefore support authentication protocols. One of the most popular of such devices is known as a Digital Signature Transponder (DST). Manufactured by Texas Instruments, DSTs are deployed in several applications that are notable for wide-scale deployment and the high costs (financial and otherwise) of a large-scale security breach. These include:
A DST contains a secret, 40-bit cryptographic key which is field-programmable
via RF command. In its interaction with a reader, a DST emits a
factory-set (24-bit) identifier, and then authenticates itself by engaging
in a challenge-response protocol. The reader initiates the protocol by
transmitting a 40-bit challenge. The DST encrypts this challenge under
its key and returns a 24-bit response.
It is thus the secrecy of the key that ultimately protects the DST against
cloning and simulation.
We used some new special-purpose cryptanalytic techniques to reconstruct the algorithm used in the DST tags, by simply observing the responses that actual DST tags computed when presented with a large number of specially chosen challeneges. Using this black-box reverse-engineering method, we were able to implement a software program that, when given the same challenge and key as an actual tag, would compute the same response. Our next step was to recover the secret key from a deployed DST device, using a brute-force key search. Unfortunately, it would have taken more than 2 weeks for our software implementation to find a key when running on 10 very fast PCs. We therefore implemented our key-search on a field programmable gate array (FPGA). The FPGA evaluation board we used is available online for under $200 in single quantities with all of the neccesary development software and cabling. Our implementation cracks 32 keys in parallel on a single FPGA running at 100MHz. At this rate, a single FPGA is expected to crack a key in just over 10 hours. To decrease this key-cracking time even furthur, we connected 16 FPGAs together at a total cost of under $3,500. Texas Instruments provided us with 5 DST tags whose keys we did not know. The 16-way parallel cracker was able to recover all 5 keys in well under 2 hours. We are currently developing and testing even faster and cheaper methods for recovering DST keys and will update this page with these results when they become available. The details are available in our academic paper. After recovering a key, in order to attack a real DST system, we needed to create a radio device that could speak the same protocol as a hardware DST tag. This device would allow us to quickly extract the information needed to recover a key from a target DST device, and once the key was cracked, completely emulate the DST to a legitimate reader. To accomplish this, we equipped a small and easily portable PC with a Measurement Computing digital-to-analog conversion (DAC) board; this board is also capable of analog-to-digital conversion. The DAC board can perform 12-bit A/D conversions on an input signal at a rate of 1.25 MHz and can perform D/A conversions and generate an output signal at a rate of 1 MHz. We connected the input and output channels on our DAC board to an antenna tuned to the correct frequency range. We wrote modulation and demodulation software routines to decode and produce the analog AM signals transmitted by the TI reader as well as FM-FSK analog signals transmitted by the transponders. Using these routines, our equipment can eavesdrop on the communication protocol between a DST reader and transponder, or participate actively in a protocol by emulating either device. More details on this software radio solution are available in the academic paper.
To validate our attack, we extracted the key from our own SpeedPass
token and simulated it in our independent programmable RF device. We purchased
gasoline successfully at an ExxonMobil station multiple times in the course of
a single day using this digital simulator.
Similarly, we recovered the cryptographic key from a DST in the ignition key of our 2005 model Ford Escape SUV. By simulating the DST, we
spoofed the immobilizer authentication system and started the vehicle with a
bare ignition key, that is, with one that possessed no DST at all. Viewed
another way, we created the pre-conditions for hot-wiring the vehicle.
Our attack on the DST cipher by no means implies wholesale dismantling of the security of the SpeedPass network, nor easy theft of automobiles. The cryptographic challenge-response protocols of DST devices constitute only one of several layers of security in these systems. The SpeedPass network has on-line fraud detection mechanisms loosely analogous to those employed for traditional credit-card transaction processing. Thus an attacker that simulates a target DST cannot do so with complete impunity; suspicious usage patterns may result in flagging and disabling of a SpeedPass device in the network. The most serious system-wide threat lies in the ability of an attacker to target and simulate multiple DSTs, as suggested in our example scenarios below. In some sense, the threat to automobile immobilizers is more serious, as: (1) An automobile is effectively an off-line security system and (2) A single successful attack on an automobile immobilizer can result in full compromise of the vehicle. While compromise of a DST does not immediately permit theft of an automobile, it renders an automobile with an immobilizer as vulnerable to theft as an automobile without one. Such a rollback in automobile security has serious implications. As noted above, significant declines in automobile theft rates - up to 90% - have been attributed to immobilizers during their initial introduction. Even now, automobile theft is an enormous criminal industry, with 1,260,471 automobile thefts registered by the FBI in 2003 in the United States alone, for a total estimated loss of $8.6 billion. Extracting the key from a DST device requires the harvesting of two challenge-response pairs. As a result, there are certain physical obstacles to successful attack. Nonetheless, bypassing the cryptographic protections in DST devices results in considerably elevated real-world threats. There are effectively two different methods by which an attacker may harvest signals from a target DST, and two different corresponding physical ranges.
The second mode of attack is passive eavesdropping. Limitations on the effective range of active scanning stem from the requirement that a reader antenna furnish power to the target DST. An attacker might instead eavesdrop on the communication between a legitimate reader and a target DST during a valid authentication session. In this case, the attacker need not furnish power to the DST; the effective eavesdropping range then depends solely on the ability to intercept the signal emitted by the DST. We have not performed any experiments to determine the range at which this attack might be mounted. It is worth noting purported U.S. Department of Homeland Security reports, however, of successful eavesdropping of this kind on 13.56 Mhz tags at a distance of some tens of feet. The DST, however, operates at 134 kHz. Signals at this considerably lower frequency penetrate obstacles more effectively, which may facilitate eavesdropping; on the other hand, larger antennas are required for effective signal interception.
Only careful experimentation will permit accurate assessment of the degree of
these two threats. Our cursory experiments, however, suggest that the threats
are well within the realm of practical execution.
The most straightforward architectural fix to the problems we describe here is simple: The underlying cryptography should be based on a standard, publicly scrutinized algorithm with an adequate key length, e.g., the Advanced Encryption Standard (AES) in its 128-bit form, or more appropriately for this application, HMAC-SHA1. From a commercial standpoint, this approach may be problematic in two respects. First, the required circuitry would result in a substantially increased manufacturing cost, and might have other impacts on the overall system architecture due to increased power consumption. Second, there is the problem of backwards compatability. It would be expensive to replace all existing DST-based immobilizer keys. Indeed, given the long production cycles for automobiles, it might be difficult to introduce a new cipher into the immobilizers of a particular make of vehicle for a matter of years. TI has indicated to the authors that they have more secure RFID products available at present; in lieu of specifying these products, they refer to the site www.ti-rfid.com for information. In fact, RFID chips with somewhat longer key-lengths are already available in the marketplace and used in a range of automobile immobilizers. Philips offers two cryptographically enabled RFID chips for immobilizers. The Philips HITAG 2, however, has a 48-bit secret key, and thus offers only marginally better resistance to a brute-force attack-- certainly not a comfortable level for long-term security. The Philips SECT, in contrast, has a 128-bit key. The HITAG 2 algorithm is proprietary, while Philips data sheets do not appear to offer information about the cryptographic algorithm underpinning their SECT device. It is difficult to say, therefore, whether these algorithms are well designed. Faraday shielding offers a short-term, partial remedy. In particular, users may encase their DSTs in aluminum foil or some suitable radio-reflective shielding when not using them. This would defend against active scanning attacks, but not against passive eavesdropping. Moreover, this approach is rather inconvenient, and would probably prove an unworkable imposition on most users. A different measure worth investigation is the placement of metal shielding in the form of a partial cylinder around the ignition-key slot in automobiles. This could have the effect of attenuating the effective eavesdropping range.
In the long-term, the best approach is, of course, the development of solid,
well-modeled cryptographic protocols predicated on industry-standard algorithms,
with key lengths suitable for long-term hardware deployment.
All of these videos are real, nothing has been faked. Please excuse our production values.
Sniffing a DST tag in a victim's pocket. Mirror 1: Quicktime (3 MB) Mirror 2: Quicktime (3 MB) Mirror 3: Quicktime (3 MB)
|