About 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:
- Vehicle Immobilizers: More than 150 million vehicle immobilizer keys shipped with many current automobiles, including e.g. 2005 model Fords, use Texas Instruments low-frequency RFID transponders. This number includes systems with fixed-code transponders that provide no cryptographic security, as well as newer models equipped with DSTs. Immobilizers deter vehicle theft by interrogating an RFID transponder embedded in the ignition key as a condition of enabling the fuel-injection system of the vehicle. The devices have been credited with significant reductions in auto theft rates, as much as 90%.
- Electronic Payment: DSTs are used in the ExxonMobil SpeedPass system, with more than seven million cryptographically-enabled keychain tags accepted at 10,000 locations worldwide.
A DST consists of a small microchip and antenna coil encapsulated in a plastic or glass capsule. It is a passive device, which is to say that it does not contain an on-board source of power, but rather receives its power from the interrogation signal transmitted by the reading device via electromagnetic inductance. This design choice allows for a compact design and long transponder life.
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.
At left, an ExxonMobile SpeedPass both inside and outside its casing. At right, an immobilizer equipped car key. The small chip is embedded into the plastic head of the key.
Our Attacks
The encryption algorithm used in the TI DST tags is an unpublished, proprietary cipher that uses a 40-bit key. The algorithm was designed in the early 1990's by engineers at Texas Instruments, but is still being deploying in current systems. By today's standards, a 40-bit key is unacceptably short: advances in computing power have made such keys susceptible to brute-force key guessing attacks. Therefore, the actual security of the DST system rests with the secrecy of the proprietary algorithm used in the tags. One of the most important principles in cryptographic design states, however, that the security of a system should be based only on the secrecy of the keys, never on the secrecy of the algorithm.
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 challenges. 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 further, 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.
The parallel cracker. Data is entered using the keyboard at front, and results are read off the LEDs on each board.
The equipment we used to simulate a DST. From bottom, a battery, an uninterruptable power supply, a small form factor PC with data aquisition card, and a BNC breakout box. The round black antenna can be seen hanging at right.
Practical Signifigance
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 equipment needed to capture the data required to clone a DST tag at close range. From left, a microreader, a laptop, and a serial cable.
The first mode of attack is active scanning: The attacker brings a reader in her control within scanning range of the target DST. DSTs of the type found in SpeedPass and automobile ignition keys are designed for short range scanning - on the order of a few centimeters. In practice, however, a longer range is achievable. In preliminary experiments, we have achieved an effective range of several inches for a DST on a keyring in the pocket of a simulated victim using a tiny antenna. A DST may respond to as many as eight queries per second. Thus, it is possible to perform the two scans requisite for our simulation attacks in as little as one-quarter of a second. At the limit of the range achievable by a given antenna, however, scanning becomes somewhat unreliable, and can require more time.
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.
