Digital Signature Transponder

The Texas Instruments Digital Signature Transponder (DST) is a cryptographically-enabled radio-frequency identification (RFID) device used in a variety of wireless authentication applications. The largest deployments of the DST include the Exxon-Mobil Speedpass payment system (approximately 7 million transponders), as well as a variety of vehicle immobilizer systems used in many late model Ford, Lincoln, Mercury, Toyota, and Nissan vehicles.

The DST is an unpowered "passive" transponder which uses a proprietary block cipher to implement a challenge-response authentication protocol. Each DST tag contains a quantity of non-volatile RAM, which stores a 40-bit encryption key. This key is used to encipher a 40-bit challenge issued by the reader, producing a 40-bit ciphertext, which is then truncated to produce a 24-bit response transmitted back to the reader. Verifiers (who also possess the encryption key) verify this challenge by computing the expected result and comparing it to the tag response. Transponder encryption keys are user programmable, using a simple over-the-air protocol. Once correctly programmed, transponders may be "locked" through a separate command, which prevents further changes to the internal key value. Each transponder is factory provisioned with a 24-bit serial number and 8-bit manufacturer code. These values are fixed, and cannot be altered.

The DST40 Cipher

Until 2005, the DST cipher (DST40) was a trade secret of Texas Instruments, made available to customers under non-disclosure agreement. This policy was likely instituted due to the cipher's non-standard design and small key size, which rendered it vulnerable to brute-force keysearch. In 2005, a group of students from the Johns Hopkins University Information Security Institute and RSA Laboratories reverse-engineered the cipher using an inexpensive Texas Instruments evaluation kit, through schematics of the cipher leaked onto Internet, and black-box techniques [1] (i.e., querying transponders via the radio interface, rather than dismantling them to examining the circuitry). Once the cipher design was known, the team programmed several FPGA devices to perform brute-force key searches based on known challenge/response pairs. Using a single FPGA device, the team was able to recover a key from two known challenge/response pairs in approximately 11 hours (average case). With an array of 16 FPGA devices, they reduced this time to less than one hour.

DST40 is a 200-round unbalanced Feistel cipher, in which L0 is 38 bits, and R0 is 2 bits. The key schedule is a simple linear feedback shift register, which updates every three rounds, resulting in some weak keys (e.g., the zero key). Although the cipher is potentially invertible, the DST protocol makes use of only the encipher mode. When used in the protocol with the 40-to-24-bit output truncation, the resulting primitive is more aptly described as a Message Authentication Code rather than an encryption function. Although a truncated block cipher represents an unusual choice for such a primitive, this design has the advantage of precisely bounding the number of collisions for every single key value.

The DST40 cipher is one of the most widely-used unbalanced Feistel ciphers in existence.

Reaction and fixes

The vulnerability exposed by the Hopkins team indicates potential security threats to millions of vehicles which are protected using DST-based immobilizer systems, and to the Exxon-Mobil Speedpass system. The ideal solution to this problem is to replace the DST transponder in these systems with a device provisioned with a more robust cryptographic circuit utilizing a longer key length. However, the cost of recalling these security systems is prohibitively high, and-- as of October 2005-- neither Texas Instruments, Exxon-Mobil or any vehicle manufacturer has announced such a recall. Currently the most effective protections against this attack rely on user vigilance, e.g., protecting transponder keys, auditing Speedpass invoices for fraud, and optionally using a metallic shield (such as aluminum foil) to prevent unauthorized scanning of DST tags. This vulnerability has also spawned the creation of the RSA Blocker Tag and RFID Blocking Wallets.

References

[1] S. Bono, M. Green, A. Stubblefield, A. Rubin, A. Juels, M. Szydlo. "Security Analysis of a Cryptographically-Enabled RFID Device". In Proceedings of the USENIX Security Symposium, August 2005. (pdf)