KeeloQ

Summary

This article provides an overview of KeeLoq and three popular attacks, i.e., Side channel, Slide and Algebraic attacks. It also provides a quick overview of the KeeLoq protocols and procedures. Block Cipher will be mentioned as well. Following these, KeeLoq's cryptanalysis will take place. Finally, you'll find the "Versions" section.

Requirements

• Basic knowledge of Block Cipher
• Basic understanding of Power Analysis
• Basic grasp of Symmetric Cryptography

Description

KeeLoq

KeeLoq is used for access authorization in electronic access systems, distributed by Microchip Technology Inc. The system consists of a sender and a receiver, like a car remote key and a car. In order to get access with the remote key, the receiver must first learn about the remote key. To perform the registration process, the sender has a unique serial number and secret key and the receiver has a secret manufacturer key. This process can be described as followed:

• 1) The sender sends his serial number in plaintext to the receiver
• 2) The receiver’s secret manufacturer key will then be used for the encryption of the serial number.
• 3) To decrypt the message, the sender’s secret key works as a pair to the manufacturer key. From this point on, the sender’s key is used to encrypt and decrypt the messages.

Encrypted 32-bit blocks are used for communication. Each block contains a code for a specific action. As these codes remain unchanged during a communication, every encrypted message would technically be identical. To prevent this behavior, the hopping code algorithm is used.

The hopping code adds a counter to the encrypted messages. When the receiver decrypts a message, the counter is read. If the received counter, is a number within a range of 16 values different from the last counted counter, the action is executed.

To ensure that the received message is from the same remote key and is not a resent message from someone else, the friend or foe algorithm is used. This algorithm is a challenge response algorithm. To verify the remote key, the receiver first sends a message in plaintext to the sender. The sender encrypts the message and sends it back. If the receiver can successfully decrypt the message, the remote key is verified.

KeeLoq is a block cipher that uses 64-bit keys on 32-bit plaintext blocks. To encrypt messages, KeeLoq uses a 64-bit long secret key on a 32-bit long plaintext message. The encryption process takes 5 bits from the plaintext register and uses them to calculate a single bit with a nonlinear function. To create a single bit for an encrypted message, a nonlinear function is applied, that XORs with one bit from the key, and two bits from the plaintext register. After that, the plaintext register, and the key register are shifted one bit to the right. This process is repeated 527 more times to create one block of an encrypted message. To decrypt a message a similar routine is used.

Block Cipher

A block cipher is an encryption technique that applies a symmetric key to a block of text of a fixed size, as opposed to a stream cipher, which encrypts only one bit at a time. The same secret public key is used to encrypt the plaintext and is also used in the decryption phase of the ciphertext. Block ciphers are particularly used in the development of several cryptographic protocols, such as pseudo-random number generators and general-purpose hash functions. It is also commonly used to encrypt huge amounts of data, such as communication protocols. Data Encryption Standard (DES) and Advanced Encryption Standard (AES) are the most common and well-known examples of government-adopted block cipher algorithms. Functions used in block ciphers do not differ from completely random permutations and are therefore considered reliable until proven to be untrustworthy.

Code Hopping

Code hopping, also known as rolling code, is a commonly used security mechanism to provide a new code for each Remote Keyless Entry (RKE) system authentication. Code hopping prevents replay attacks in which an interceptor accesses the transmitted code, writes it, and then reattempts to compromise the system. In a non-cryptographic code hopping system, the sender and receiver use the same pseudo-random number generator (PRNG), which contains information about the last code used and the calculation to be performed. Calculations produce a defined series of numbers that are not repeated. One end of the communication, such as a car's key fob or module, sends the next number in sequence, and the other end can identify itself as a PRNG. If the code matches, the system is authenticated and the car door is unlocked. Otherwise, the system looks at the serial number and finds the number sent. Each time the system is successfully used, the endpoint is synchronized, which means the next time the system should work on the first attempt. The code hopping technology benefits greatly from theso-called Avalanche Effect, which guarantess that by modifying a single input bit, at least half of the output bits are changed.

Identify Friend or Foe

Decoders employing KeeLoq technology also integrate the Identify Friend or Foe (IFF) protocol within the challenge-response framework, enhancing security. In this protocol, receivers can send challenges to senders, requiring a mastered response for verification. When a code is received, the original sender generates a reply using an encoder key. The same calculation is performed on the receiver, which initially sent the challenge, and the results are compared for equality. For instance, the HCS412 microchip implements a 32-bit IFF using one of two possible encryption algorithms. While older RKE systems used unidirectional data transmissions, modern systems commonly utilize bidirectional data transfers to enhance security and functionality.

Vulnerabilities

Hopping Code and IFF are two strong protocols that provide the basic security of KeeLoq. Naturally, these two authentication protocols are prime targets for attack. The hopping code using a 16-bit secret counter prevents intrusion into the system without pressing a button on the sending side. In contrast, IFF is triggered when the transponder receives power and activation signals without user intervention. Thus, no batteries or keystrokes are required to activate the transponder and run a protocol that is completely transparent to the user. With this in mind, it can be concluded that, despite two reliable protocols, KeeLoq is still vulnerable to attack. The attack can be used, for example, on car immobilizers by placing a decoder next to the ignition switch. Then the transponder will be within reach of the decoder when the car key is inserted into the ignition. Depending on the success of the authentication, the vehicle turns off the immobilizer or turns on the alarm.

Security Threats

Side channel

In this attack, a side channel is used to obtain the secret sender key. This side channel can be applied on the entirety of the hardware. Some side channel attacks measure the current consumption of a semiconductor chip or analyze the emitting electromagnetic field. Side channel attacks can obtain both of the secret and manufacturer keys. They are also effective even when code hopping mechanism is used.

Slide attack

This attack uses the weakness of the block cipher, that is the 528 cycles long process to decrypt or encrypt a message. With enough slide pairs, which is essentially plaintext and the matching encrypted text, the steps to get the encrypted message can be traced back to get the sender secret key. Slide attacks cannot pass through code hopping mechanism.

Algebraic attack

In this approach the attacker tries to solve multivariate equations. These equations must be solved for every encryption step. Each encryption step requires a new hopping code, thus, algebraic attacks also cannot pass code hopping mechanism. They are only applicable when XOR key derivation is used.

Cryptanalysis

The KeeLoq algorithm has received many effective attacks since its launch. The KeeLoq algorithm is difficult to hack in the real world as it reduces time complexity while increasing spatial complexity and requires a known set of prerequisites. However, it is still safe to use and is used quite often in practice.

Social Engineering Attack

Contrary to the common belief that code grabbing is impractical due to unique codes for each transmission, a specific attack method is discussed, closely tied to social engineering. In this scenario, an attacker employs a jammer to block the receiver's access to a valid signal, preventing e.g. a car from receiving the necessary code for locking. To counteract vigilant targets, the attacker attempts to capture the code broadcasted when a person locks their car, using the jammer to obstruct the code reception. Upon the victim's realization and attempts to secure their belongings, the attacker repeats the process during the second transmission, using the initially obtained code to lock the car. This leaves the attacker with an extra valid code, usable for unlocking the car at a later time.

Versions of KeeLoq

Dual KeeLoq

The Classic KeeLoq protocol is described in this article, however newer versions have been developed. The Dual KeeLoq system improves on the Classic KeeLoq system by using a timer-based algorithm. The purpose of this current version is to have a timer-driven counter that increments continually, as opposed to the Classic KeeLoq, which increments based on the events it receives. This is provided by the new MCS3142 Encoder (embedded in the reciever, not in keyfob!) and safeguards against capture and replay attacks.

References

• Microchip. Keeloq R decryption routines in c tb041. microchip.https://www.microchip.com
• Nicolas T. Courtois, Gregory V. Bard, and David Wagner. Algebraic and slide attacks on keeloq. In Kaisa Nyberg, editor, Fast Software Encryption, pages 97{115, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
• Thomas Eisenbarth, Timo Kasper, Amir Moradi, Christof Paar, Mahmoud Salmasizadeh, and Mohammad T. Manzuri Shalmani. On the power of power analysis in the real world: A complete break of the keeloq code hopping scheme. In David Wagner, editor, dvances in Cryptology { CRYPTO 2008, pages 203{220, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
• Sebastiaan Indesteege, Nathan Keller, Orr Dunkelman, Eli Biham, and Bart Preneel. A practical attack on keeloq. In Nigel Smart, editor, Advances in Cryptology { EUROCRYPT 2008, pages 1{18, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg
• C. Paar, T. Eisenbarth, M. Kasper, T. Kasper, and A. Moradi. Keeloq and side-channel analysis-evolution of an attack. In 2009 Workshop on Fault Diagnosis and Tolerance in Cryptography (FDTC), pages 65{69, Sep. 2009.
• Orr Dunkelman Eli Biham Sebastiaan Indesteege, Nathan Keller and Bart Preneel. A practical attack on keeloq. Computer Science Department, Technion. Haifa 32000, Israel, 8(1):1{18, Oktober 2008.
• Christof Paar Thomas Eisenbarth, Timo Kasper. Sicherheit moderner Funktüröffnersysteme. Datenschutz und Datensicherheit, 28(1):508{510, Oktober 2008.
• Nicolas T. CourtoisGregory V. BardDavid Wagner. Algebraic and Slide Attacks on KeeLoq. International Workshop on Fast Software Encryption. Springer-Verlag Berlin Heidelberg 2008, 2008.
• Microchip. MCS3142 Dual KeeLoq Encoder in c tb041.https://www.microchip.com/en-us/product/MCS3142
• Yue-li Hu, Yan Zhang, and Bin Sun. Design of rke system based on keeloq encryption technology. In 2009 International Conference on Artificial Intelligence and Computational Intelligence, volume 1, pages 324–327, 2009
• Unknown. Bypassing rolling code systems. https://www.andrewmohawk.com/2016/02/05/bypassing-rolling-code-systems/. Accessed: 2023-12-10
• Microchip Technology Inc. KeeLoq Copde Hopping, 2000