KeeLoq

Last updated

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 (South Africa) in the mid-1980s. KeeLoq was sold to Microchip Technology Inc in 1995 for $10 million. [1] It is used in 'hopping code' encoders and decoders such as NTQ105/106/115/125D/129D, HCS101/2XX/3XX/4XX/5XX and MCS31X2. KeeLoq has been used in many remote keyless entry systems by such companies like Chrysler, [2] Daewoo, Fiat, Ford, [3] GM, Honda, Mercedes-Benz, [3] Toyota, Volvo, Volkswagen Group, Clifford, Shurlok, and Jaguar. [3]

Contents

Description

KeeLoq Encryption Kodirovka.png
KeeLoq Encryption

KeeLoq "code hopping" encoders encrypt a 0-filled 32-bit block with KeeLoq cipher to produce a 32-bit "hopping code". A 32-bit initialization vector is linearly added (XORed) to the 32 least significant bits of the key prior to encryption and after decryption.

KeeLoq cipher accepts 64-bit keys and encrypts 32-bit blocks by executing its single-bit NLFSR for 528 rounds. The NLFSR feedback function is 0x3A5C742E or

KeeLoq uses bits 1, 9, 20, 26 and 31 of the NLFSR state as its inputs during encryption and bits 0, 8, 19, 25 and 30 during decryption. Its output is linearly combined (XORed) with two of the bits of the NLFSR state (bits 0 and 16 on encryption and bits 31 and 15 on decryption) and with a key bit (bit 0 of the key state on encryption and bit 15 of the key state on decryption) and is fed back into the NLFSR state on every round.

Versions

This article describes the Classic KeeLoq protocol, but newer versions has been developed. The Ultimate KeeLoq system [4] is a timer-based algorithm enhancing the Classic KeeLoq system. The goal of this newer version is to contain stronger, industry standard AES-128 cipher which replaces KeeLoq cipher algorithm, and have a timer-driven counter which continuously increments, which is the opposite of the Classic KeeLoq where the counter increments based on the button press. This provides protection against brute-force attack and capture and replay attack, known as RollJam for Samy Kamkar's work.

Attacks

Replay attack

For simplicity, individual "code hopping" implementations typically do not use cryptographic nonces or timestamping. This makes the protocol inherently vulnerable to replay attacks: For example, by jamming the channel while intercepting the code, a thief can obtain a code that may still be usable at a later stage. [5] This sort of "code grabber," [6] while theoretically interesting, does not appear to be widely used by car thieves. [7]

A detailed description of an inexpensive prototype device designed and built by Samy Kamkar to exploit this technique appeared in 2015. The device about the size of a wallet could be concealed on or near a locked vehicle to capture a single keyless entry code to be used at a later time to unlock the vehicle. The device transmits a jamming signal to block the vehicle's reception of rolling code signals from the owner's fob, while recording these signals from both of his two attempts needed to unlock the vehicle. The recorded first code is forwarded to the vehicle only when the owner makes the second attempt, while the recorded second code is retained for future use. [8] A demonstration was announced for DEF CON 23. [9]

Cryptanalysis

KeeLoq Decryption Dekodirovka.png
KeeLoq Decryption

KeeLoq was first cryptanalyzed by Andrey Bogdanov using sliding techniques and efficient linear approximations. Nicolas Courtois attacked KeeLoq using sliding and algebraic methods. The attacks by Bogdanov and Courtois do not pose any threat to the actual implementations that seem to be much more vulnerable to simple brute-force of the key space that is reduced in all the code-hopping implementations of the cipher known to date. Some KeeLoq "code grabbers" use FPGA-based devices to break KeeLoq-based keys by brute force within about two weeks due to the reduced key length in the real world implementations.[ citation needed ]

In 2007, researchers in the COSIC group at the university at Leuven, Belgium, (K.U.Leuven) in cooperation with colleagues from Israel found a new attack against the system. [10] Using the details of the algorithm that were leaked in 2006, the researchers started to analyze the weaknesses. After determining the part of the key common to cars of a specific model, the unique bits of the key can be cracked with only sniffed communication between the key and the car.

Microchip introduced in 1996 [11] a version of KeeLoq ICs which use a 60-bit seed. If a 60-bit seed is being used, an attacker would require approximately 1011 days of processing on a dedicated parallel brute force attacking machine before the system is broken. [12]

Side-channel attacks

In March 2008, researchers from the Chair for Embedded Security of Ruhr University Bochum, Germany, presented a complete break of remote keyless entry systems based on the KeeLoq RFID technology. [13] [14] Their attack works on all known car and building access control systems that rely on the KeeLoq cipher.

The attack by the Bochum team allows recovering the secret cryptographic keys embedded in both the receiver and the remote control. It is based on measuring the electric power consumption of a device during an encryption. Applying what is called side-channel analysis methods to the power traces, the researchers can extract the manufacturer key from the receivers, which can be regarded as a master key for generating valid keys for the remote controls of one particular manufacturer. Unlike the cryptanalytic attack described above which requires about 65536 chosen plaintext-ciphertext pairs and days of calculation on a PC to recover the key, the side-channel attack can also be applied to the so-called KeeLoq Code Hopping mode of operation (a.k.a. rolling code) that is widely used for keyless entry systems (cars, garages, buildings, etc.).

The most devastating practical consequence of the side-channel analysis is an attack in which an attacker, having previously learned the system's master key, can clone any legitimate encoder by intercepting only two messages from this encoder from a distance of up to 100 metres (330 ft). Another attack allows one to reset the internal counter of the receiver (garage door, car door, etc.), which makes it impossible for a legitimate user to open the door. [15]

Related Research Articles

<span class="mw-page-title-main">Advanced Encryption Standard</span> Standard for the encryption of electronic data

The Advanced Encryption Standard (AES), also known by its original name Rijndael, is a specification for the encryption of electronic data established by the U.S. National Institute of Standards and Technology (NIST) in 2001.

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.

<span class="mw-page-title-main">Cipher</span> Algorithm for encrypting and decrypting information

In cryptography, a cipher is an algorithm for performing encryption or decryption—a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. To encipher or encode is to convert information into cipher or code. In common parlance, "cipher" is synonymous with "code", as they are both a set of steps that encrypt a message; however, the concepts are distinct in cryptography, especially classical cryptography.

<span class="mw-page-title-main">Cryptanalysis</span> Study of analyzing information systems in order to discover their hidden aspects

Cryptanalysis refers to the process of analyzing information systems in order to understand hidden aspects of the systems. Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages, even if the cryptographic key is unknown.

<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">Encryption</span> Process of converting plaintext to ciphertext

In cryptography, encryption is the process of encoding information. This process converts the original representation of the information, known as plaintext, into an alternative form known as ciphertext. Ideally, only authorized parties can decipher a ciphertext back to plaintext and access the original information. Encryption does not itself prevent interference but denies the intelligible content to a would-be interceptor.

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

In cryptography, linear cryptanalysis is a general form of cryptanalysis based on finding affine approximations to the action of a cipher. Attacks have been developed for block ciphers and stream ciphers. Linear cryptanalysis is one of the two most widely used attacks on block ciphers; the other being differential cryptanalysis.

<span class="mw-page-title-main">Ciphertext</span> Encrypted information

In cryptography, ciphertext or cyphertext 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 to decrypt it. This process prevents the loss of sensitive information via hacking. Decryption, the inverse of encryption, is the process of turning ciphertext into readable plaintext. Ciphertext is not to be confused with codetext because the latter is a result of a code, not a cipher.

Cryptography, the use of codes and ciphers to protect secrets, began thousands of years ago. Until recent decades, it has been the story of what might be called classical cryptography — that is, of methods of encryption that use pen and paper, or perhaps simple mechanical aids. In the early 20th century, the invention of complex mechanical and electromechanical machines, such as the Enigma rotor machine, provided more sophisticated and efficient means of encryption; and the subsequent introduction of electronics and computing has allowed elaborate schemes of still greater complexity, most of which are entirely unsuited to pen and paper.

The Common Scrambling Algorithm (CSA) is the encryption algorithm used in the DVB digital television broadcasting for encrypting video streams.

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

In cryptography, DES-X is a variant on the DES symmetric-key block cipher intended to increase the complexity of a brute-force attack. The technique used to increase the complexity is called key whitening.

Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts. The term "probabilistic encryption" is typically used in reference to public key encryption algorithms; however various symmetric key encryption algorithms achieve a similar property, and stream ciphers such as Freestyle which are inherently random. To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

In cryptography, FROG is a block cipher authored by Georgoudis, Leroux and Chaves. The algorithm can work with any block size between 8 and 128 bytes, and supports key sizes between 5 and 125 bytes. The algorithm consists of 8 rounds and has a very complicated key schedule.

In cryptanalysis, attack models or attack types are a classification of cryptographic attacks specifying the kind of access a cryptanalyst has to a system under attack when attempting to "break" an encrypted message generated by the system. The greater the access the cryptanalyst has to the system, the more useful information they can get to utilize for breaking the cypher.

A rolling code is used in keyless entry systems to prevent a simple form of replay attack, where an eavesdropper records the transmission and replays it at a later time to cause the receiver to 'unlock'. Such systems are typical in garage door openers and keyless car entry systems.

<span class="mw-page-title-main">Cryptography</span> Practice and study of secure communication techniques

Cryptography, or cryptology, is the practice and study of techniques for secure communication in the presence of adversarial behavior. More generally, cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, information security, electrical engineering, digital signal processing, physics, and others. Core concepts related to information security are also central to cryptography. Practical applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, and military communications.

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.

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

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

References

  1. ↑ USpatent 5517187,Bruwer, Frederick J.; Smit, Willem& Kuhn, Gideon J.,"Microchips and remote control devices comprising same",issued 1996-05-14, assigned to Microchip Technology Inc .
  2. ↑ Some evidence that Chrysler indeed uses KeeLoq can be found in (this video).
  3. 1 2 3 Researchers Crack KeeLoq Code for Car Keys. WIRED. Retrieved 2024-05-21.
  4. ↑ MicroChip - MCS3142 - Security - KeeLoq Encoder Devices
  5. ↑ Analysis of RF Remote Security Using Software Defined Radio
  6. ↑ http://www.microchip.com/stellent/idcplg?IdcService=SS_GET_PAGE&nodeId=2075&param=en001022#P108_5361 stating, "It is a simple matter to build a circuit to record such transmissions for reply at the later time. Such a system is known as a code or key grabber."
  7. ↑ "FACT CHECK: Are Car Thieves Using 'Code Grabbers' to Steal Automobiles?". 2 July 2008.
  8. ↑ Thompson, Cadie (2015-08-06). "A hacker made a $30 gadget that can unlock many cars that have keyless entry". Tech Insider . Retrieved 2015-08-11.
  9. ↑ Kamkar, Samy (2015-08-07). "Drive It Like You Hacked It: New Attacks and Tools to Wirelessly Steal Cars". DEF CON 23. Retrieved 2015-08-11.
  10. ↑ How To Steal Cars — A Practical Attack on KeeLoq
  11. ↑ (Will be in Web archive backup later): a Microchip press release on Dec 11, 1996 Quote: "...HCS410 KEELOQ Code Hopping Transponder and Encoder..."
  12. ↑ Martin Novotny; Timo Kasper. "Cryptanalysis of KeeLoq with COPACOBANA" (PDF). SHARCS 2009 Conference: 159–164.{{cite journal}}: Cite journal requires |journal= (help)
  13. ↑ "A complete break of the KeeLoq access control system". Archived from the original on 2015-09-24. Retrieved 2015-08-10.
  14. ↑ Thomas Eisenbarth; Timo Kasper; Amir Moradi; Christof Paar; Mahmoud Salmasizadeh; Mohammad T. Manzuri Shalmani (2008-02-29). "Physical Cryptanalysis of KeeLoq Code Hopping Applications" (PDF). Ruhr University of Bochum, Germany. Retrieved 2009-03-22.{{cite journal}}: Cite journal requires |journal= (help)
  15. ↑ Kasper, Timo (November 2012). Security Analysis of Pervasive Wireless Devices—Physical and Protocol Attacks in Practice (Ph.D.). Ruhr University Bochum, Germany. Retrieved 2023-07-03.
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.