Digital Signature Transponder
Encyclopedia
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.
, 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 key
s (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.
Texas Instruments
Texas Instruments Inc. , widely known as TI, is an American company based in Dallas, Texas, United States, which develops and commercializes semiconductor and computer technology...
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
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
to implement a challenge-response authentication
Challenge-response authentication
In computer security, challenge-response authentication is a family of protocols in which one party presents a question and another party must provide a valid answer to be authenticated....
protocol. Each DST tag contains a quantity of non-volatile RAM
NVRAM
Non-volatile random-access memory is random-access memory that retains its information when power is turned off, which is described technically as being non-volatile...
, 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
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
, 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 sizeKey size
In cryptography, key size or key length is the size measured in bits of the key used in a cryptographic algorithm . An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits...
, which rendered it vulnerable to brute-force keysearch. In 2005, a group of students from the Johns Hopkins University
Johns Hopkins University
The Johns Hopkins University, commonly referred to as Johns Hopkins, JHU, or simply Hopkins, is a private research university based in Baltimore, Maryland, United States...
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
Field-programmable gate array
A field-programmable gate array is an integrated circuit designed to be configured by the customer or designer after manufacturing—hence "field-programmable"...
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
Feistel cipher
In cryptography, a Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel who did pioneering research while working for IBM ; it is also commonly known as a Feistel network. A large proportion of block...
, in which L0 is 38 bits, and R0 is 2 bits. The key schedule
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
is a simple linear feedback shift register
Linear feedback shift register
A linear feedback shift register is a shift register whose input bit is a linear function of its previous state.The most commonly used linear function of single bits is XOR...
, which updates every three rounds, resulting in some weak key
Weak key
In cryptography, a weak key is a key, which, used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that, if one generates a random key to encrypt a message, weak keys are very...
s (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
Message authentication code
In cryptography, a message authentication code is a short piece of information used to authenticate a message.A MAC algorithm, sometimes called a keyed hash function, accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC...
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.