Digital signature transponder

Last updated

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, [1] Lincoln[ citation needed ], Mercury[ citation needed ], Toyota, [2] Nissan, Kia, [2] Hyundai [2] and Tesla [2] vehicles.

Contents

The DST is an unpowered "passive" transponder which uses a proprietary block cipher to implement a challenge–response authentication protocol. [3] 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. [4] Each transponder is factory provisioned with a 24-bit serial number and 8-bit manufacturer code. These values are fixed and cannot be altered if the transponder is locked.

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. Additionally, researchers from the COSIC research group of KU Leuven implemented a time/memory trade-off attack for which a 5.6 TB lookup table has to be precomputed, after which a key can be recovered in two seconds using a Raspberry Pi 3B by sniffing two challenge-response pairs. [4]

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–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.

The DST80 cipher

As a reaction to the discovery that the key size used in DST40 is too short to stop brute-force attacks, TI developed the DST80 cipher, which has a key size of 80 bits. Challenges are still 40 bits in size, however. As, like its predecessor, DST80 documentation was never released to the public either, researchers from the COSIC research group of KU Leuven managed to extract the firmware of several vehicle immobilizer implementations, and reverse-engineer the cipher from these implementations. [2] Additional to the cryptanalysis of DST80, they also found a side-channel attack that can also be used to extract the cryptographic keys.

DST80 is still an unbalanced Feistel network of 200 rounds [2] with the same values for L0 and R0. The key schedule, now updating every round and using 80-bit keys, is still based on an LSFR. While this would fix the brute-force attack used against DST40, the issue of weak keys still persists. Furthermore, several manufacturers improperly configured [2] their DST80-based transponders reducing the security of the overall system against brute-force attacks to hardly any higher than that of DST40 (a downgrade from 280 to 241). Furthermore, as some manufacturers (Kia, Hyundai, and Toyota) used easy-to-guess low-entropy keys, the upper bound is often even lower. Finally, its implementation is vulnerable to side-channel attacks. [2]

Reaction and fixes

It is unclear if the security threats to the DST-based immobilizer systems and Exxon-Mobil Speedpass system have been addressed. It is possible that these systems have been updated with more secure transponders or that additional measures have been put in place to protect against vulnerabilities. It is important for users of these systems to continue to be vigilant in protecting their transponder keys and to carefully review their Speedpass invoices for any signs of fraud. The use of metallic shields may also provide additional protection against unauthorized scanning of DST tags. It is recommended for users to stay informed about the security of these systems and to take necessary precautions to protect themselves.

Related Research Articles

In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called blocks. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage and exchange of data, where such data is secured and authenticated via encryption.

In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm.

<span class="mw-page-title-main">Data Encryption Standard</span> Early unclassified symmetric-key block cipher

The Data Encryption Standard is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryptography.

<span class="mw-page-title-main">Symmetric-key algorithm</span> Algorithm

Symmetric-key algorithms are algorithms for cryptography that use the same cryptographic keys for both the encryption of plaintext and the decryption of ciphertext. The keys may be identical, or there may be a simple transformation to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. The requirement that both parties have access to the secret key is one of the main drawbacks of symmetric-key encryption, in comparison to public-key encryption. However, symmetric-key encryption algorithms are usually better for bulk encryption. With exception of the one-time pad they have a smaller key size, which means less storage space and faster transmission. Due to this, asymmetric-key encryption is often used to exchange the secret key for symmetric-key encryption.

<span class="mw-page-title-main">Brute-force attack</span> Cryptanalytic method for unauthorized users to access data

In cryptography, a brute-force attack consists of an attacker submitting many passwords or passphrases with the hope of eventually guessing correctly. The attacker systematically checks all possible passwords and passphrases until the correct one is found. Alternatively, the attacker can attempt to guess the key which is typically created from the password using a key derivation function. This is known as an exhaustive key search.

<span class="mw-page-title-main">RC6</span> Block cipher

In cryptography, RC6 is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard (AES) competition. The algorithm was one of the five finalists, and also was submitted to the NESSIE and CRYPTREC projects. It was a proprietary algorithm, patented by RSA Security.

Articles related to cryptography include:

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 ciphers use the scheme, including the US Data Encryption Standard, the Soviet/Russian GOST and the more recent Blowfish and Twofish ciphers. In a Feistel cipher, encryption and decryption are very similar operations, and both consist of iteratively running a function called a "round function" a fixed number of times.

In cryptography, Lucifer was the name given to several of the earliest civilian block ciphers, developed by Horst Feistel and his colleagues at IBM. Lucifer was a direct precursor to the Data Encryption Standard. One version, alternatively named DTD-1, saw commercial use in the 1970s for electronic banking.

In cryptography, Camellia is a symmetric key block cipher with a block size of 128 bits and key sizes of 128, 192 and 256 bits. It was jointly developed by Mitsubishi Electric and NTT of Japan. The cipher has been approved for use by the ISO/IEC, the European Union's NESSIE project and the Japanese CRYPTREC project. The cipher has security levels and processing abilities comparable to the Advanced Encryption Standard.

In cryptography, Khufu and Khafre are two block ciphers designed by Ralph Merkle in 1989 while working at Xerox's Palo Alto Research Center. Along with Snefru, a cryptographic hash function, the ciphers were named after the Egyptian Pharaohs Khufu, Khafre and Sneferu.

<span class="mw-page-title-main">EFF DES cracker</span> Cryptographic hardware

In cryptography, the EFF DES cracker is a machine built by the Electronic Frontier Foundation (EFF) in 1998, to perform a brute force search of the Data Encryption Standard (DES) cipher's key space – that is, to decrypt an encrypted message by trying every possible key. The aim in doing this was to prove that the key size of DES was not sufficient to be secure.

SEED is a block cipher developed by the Korea Information Security Agency (KISA). It is used broadly throughout South Korean industry, but seldom found elsewhere. It gained popularity in Korea because 40-bit encryption was not considered strong enough, so the Korea Information Security Agency developed its own standard. However, this decision has historically limited the competition of web browsers in Korea, as no major SSL libraries or web browsers supported the SEED algorithm, requiring users to use an ActiveX control in Internet Explorer for secure web sites.

<span class="mw-page-title-main">Speedpass</span> Keychain radio-frequency identification

Speedpass was a keychain radio-frequency identification (RFID) device introduced in 1997 by Mobil for electronic payment. It was originally developed by Verifone. By 2004, more than seven million people possessed Speedpass tags, which could be used at approximately 10,000 Exxon, Mobil and Esso gas stations worldwide.

<span class="mw-page-title-main">VEST</span> Family of stream ciphers

VEST (Very Efficient Substitution Transposition) ciphers are a set of families of general-purpose hardware-dedicated ciphers that support single pass authenticated encryption and can operate as collision-resistant hash functions designed by Sean O'Neil, Benjamin Gittins and Howard Landman. VEST cannot be implemented efficiently in software.

In cryptography, key whitening is a technique intended to increase the security of an iterated block cipher. It consists of steps that combine the data with portions of the key.

In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking, and key stretching is intended to make such attacks more difficult by complicating a basic step of trying a single password candidate. Key stretching also improves security in some real-world applications where the key length has been constrained, by mimicking a longer key length from the perspective of a brute-force attacker.

KeeLoq is a proprietary hardware-dedicated block cipher that uses a non-linear feedback shift register (NLFSR). The uni-directional command transfer protocol was designed by Frederick Bruwer of Nanoteq (Pty) Ltd., the cryptographic algorithm was created by Gideon Kuhn at the University of Pretoria, and the silicon implementation was by Willem Smit at Nanoteq Pty Ltd in the mid-1980s. KeeLoq was sold to Microchip Technology Inc in 1995 for $10 million. It is used in "code hopping" encoders and decoders such as NTQ105/106/115/125D/129D, HCS101/2XX/3XX/4XX/5XX and MCS31X2. KeeLoq is or was used in many remote keyless entry systems by such companies as Chrysler, Daewoo, Fiat, GM, Honda, Toyota, Volvo, Volkswagen Group, Clifford, Shurlok, and Jaguar.

The following outline is provided as an overview of and topical guide to cryptography:

<span class="mw-page-title-main">Speck (cipher)</span> Family of block ciphers

Speck is a family of lightweight block ciphers publicly released by the National Security Agency (NSA) in June 2013. Speck has been optimized for performance in software implementations, while its sister algorithm, Simon, has been optimized for hardware implementations. Speck is an add–rotate–xor (ARX) cipher.

References

  1. 1 2 Bono, Stephen C.; Green, Matthew; Stubblefield, Adam; Juels, Ari; Rubin, Aviel D.; Szydlo, Michael (August 2005). "Security Analysis of a Cryptographically-Enabled RFID Device" (PDF). Proceedings of the USENIX Security Symposium.
  2. 1 2 3 4 5 6 7 8 Wouters, Lennert; Van den Herrewegen, Jan; Garcia, Flavio D.; Oswald, David; Gierlichs, Benedikt; Preneel, Bart (2020). "Dismantling DST80-based Immobiliser Systems". IACR Transactions on Cryptographic Hardware and Embedded Systems. 2020 (2): 99–127. doi:10.13154/tches.v2020.i2.99-127. S2CID   212671625.
  3. ↑ Kaiser, Ulrich (2008). "Digital Signature Transponder". RFID Security: 177–189. doi:10.1007/978-0-387-76481-8_8. ISBN   978-0-387-76480-1.
  4. 1 2 Wouters, Lennert; Marin, Eduard; Ashur, Tomer; Gierlichs, Benedikt; Preneel, Bart (2019). "Fast, Furious and Insecure: Passive Keyless Entry and Start Systems in Modern Supercars". IACR Transactions on Cryptographic Hardware and Embedded Systems. 2019 (3): 66–85. doi:10.13154/tches.v2019.i3.66-85. S2CID   173992130.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.