Elvis Wiki - User contributions [en]

KeeLoq: Attacks and Example

2024-01-08T20:40:49Z

MLindner:

== Introduction ==
KeeLoq was invented at Nanoteq (South Africa) in the 1980's by Frederick Bruwer (uni-directional command transfer protocol), Gideon Kuhn (cryptographic algorithm) and Willem Smit (silicon implementation). The specifications of KeeLoq are patented and can only be used under license. In November 1995 Microchip Technology Inc. acquired the KeeLoq code hopping technology patents along with the worldwide marketing rights. Typical applications for the KeeLoq encoders and decoders include remote keyless entry (RKE) systems, alarm systems, immobilizers, car alarms, garage door openers, burglar alarms, secure communications such as in smoke/carbon monoxide/radon detectors, remote-control toys, model cars/airplanes, appliances, identity tokens and tracking of parts/packages. Also allows KeeLoq block cipher a low cost hardware implementation with low power consumption. Having such a broad field of application, also mainly in security related topics, KeeLoq became interesting for researchers, as well criminals all over the world. After releasing implementation details on a Russian website in 2006, first successful attacks on the algorithm are published in 2007, were the weakness of self similarity of the key schedule, combined with a quite short key length, allowed to mount a slide attack.
Over the years many flavours of attack strategies got developed, from attacking the cipher directly using mathematical methods, or the protocol using replay or man-in-the-middle attacks. Also the implementation offers attack vectors using side-channel-attack methods by measuring power consumption, temperature, electromagnetic fields on the chips or by measuring response times. The weaknesses within KeeLoq and its implementation will be presented in this document.

== KeeLoq Basics ==
[[File:Keeloq_encryption.png|thumb|KeeLoq Encryption]]
This section begins with an introduction to the basic concepts of KeeLoq cipher, which is in principle an unbalanced Feistel-network used for decoding and encoding. Later in this section the authentication protocols are covered, which both use KeeLoq. Further is shown how synchronization between sender and receiver works, were an attacker could also see a potential security hole. Finally this section presents how the key derivation is managed, and show that all devices from a manufacturer use the same key kMan, which makes cloning of senders an easy task.

=== KeeLoq Decryption/Encryption Algorithm ===
[[File:Keeloq_decryption.png|thumb|KeeLoq Decryption]]
KeeLoq block cipher uses a 64 bit key register which operates as simple circular shift register, that becomes initialized with the secret key, and a 32 bit state register implemented as a nonlinear feedback shift register (NLFSR), that is initialized with the first 32 bits of the clear text. Each round ''i'' of the total 528 rounds, the NLF feedback depends on five bits (b31, b26, b20, b9, b1) of the state register combined (XOR) with the state bits b17, b0 and a bit of the secret key ki mod(64) and shifted to the right. After 528 rounds the cipher can be read from the state register.
When decoding the state register is initially filled with the cipher text, and five different bits of the state register are used (b30, b25, b19, b8, b0) and state bits b31, b15 get combined with the key bit k(15-''i'') mod 64 and shifted to the left in each round ''i''. After 528 rounds the corresponding clear text can be read from the state register.

=== Authentication Protocols ===
[[File:Hopping_Code_Message_Format.png|thumb|Hopping Code Message Format]]
[[File:Hopping_Code_Windows.png|thumb|Hopping Code Synchronization Window]]
This section discusses two authentication protocols, which both have KeeLoq algorithm involved. A simple bidirectional challenge-response protocol, used in identify-friend-foe (IFF) systems, were the transponder and receiver both share the same 64 bit key k. To authenticate the decoder sends a 32 bit random challenge to the transponder, which needs to respond with the challenge encrypted using k. After the decoder decrypted and compared the response with the original challenge successfully the device is authenticated. The other, in practice more often used, code-hopping (or rolling code) mode is a unidirectional protocol, which has the advantage that the remote device, which is naturally limited in power, never listens to the radio channel. Since first remote key-less entry systems had a fixed code, configurable with jumper settings, which was an easy target for replay attacks, the rolling code was invented to guard against such an easy attack. In principle it is a 16 bit counter value, stored on the remote device, which is concatenated with a discrimination value and four function bits, then encrypted. By modifying a single input bit, the so-called Avalanche Effect guarantees, that at least half of the output bits are changed as well. Remotes serial number has to be in clear text and is appended including a copy of the function bits and some flag bits. Every time a function button on the remote device is pressed the counter gets incremented. The receiver will decode the message and compare the counter ''cnt'' with its own synchronization counter, which is incremented every time a message is received and successfully decoded. The receiver first compares the serial number to its list of paired devices, and picks the corresponding key kdev and decodes the message.

If the decoded value of the synchronization counter is within the open window, the receiver executes the function and sets its synchronization counter to the last value received. Is the received value in the re-synchronization window, the remote has to send another message with a subsequent cnt value. This is for the case the remote was be pressed accidentally without being in range of the receiver. In that case the remotes function button has to be pressed again. If the received cnt value is in the blocked window, function will not be executed at all.

=== Key Management ===
In KeeLoq applications two type of keys are involved. A unique device key for each remote control which is shared by transmitter and receiver, and a manufacturer key which is only stored in the receiver and is mainly used to derive device keys. Microchips suggests four schemes to derive the unique device keys, which all include the manufacturer key, which is identical for all receivers of a given manufacturer. This fact makes the manufacturer key an interesting target, since it enables an attacker to clone a remote control from distance, just by eavesdropping at most two messages.

== Some Attacks on KeeLoq ==

=== Slide Attack ===

The first slide attack found, was the work of Bodganov in 2007, which was the first paper describe and cryptoanalyze the KeeLoq block cipher. As stated already previously, his attack is based on a self similar key schedule, relative short block length (32 bit) and the fact that an efficient linear approximation of the NLF exists. Through the property of the slide attack, the computational complexity is independent from the number of encryption cycles. The attack carried out can be split into three main steps. A sliding step calculating the first bits k0 .. k15, a correlation step determining k47 .. k16 and the remaining bits k15 .. k0 by a linear step. The recovery complexity of his attack is about 252 computational steps and requires 232 plaintext-ciphertext pairs and 232 32 bit words (~17 GByte) in memory.

=== Power Analyses ===
The next attack, from the work of Eisenbarth, was published in 2008 as the first successful DPA (Differnential Power Analyses) attack on KeeLoq. They presented in their work three key recovery attacks, which allow someone to reveal the secret key from the transmitter, and if a weak key derivation method was used, also the manufacturer key stored on the receiver, which enables key cloning. Also this attack is suitable to target both modes, IFF and hopping code. Based on their work they presented four attack methods with more or less implications on the real world:

; Cloning a Transmitter : An attacker needs access to the transmitter and the time to take about 10 to 30 power traces. Once kdev is revealed, the messages can be decrypted and read out and with that values (serial number, counter and discrimination value of the master) a copy of the remote can be produced.

; Recover Manufacturer Key : Requires physical access to one receiver of that manufacturer and several thousands power traces. Knowing kman someone can produce valid device keys, which are not able open anything, since they must first be paired with a receiver device. But this key recovery method is relevant in the context of product piracy.

; Cloning a Transmitter without Physical Access : Knowing kman and the key derivation method, enables an attacker to copy a remote from a distance. While the previous methods must be carried out from a specialist, this attack can be carried out by a non skilled person just using a hacking device built from a criminal cryptographer, that automatically recovers kdev and opens the target.

; Denial of Service : As explained in section "Authentication Protocols", the counters of receiver and transmitter have to be synchronized, to execute the function pressed on the remote. If an attacker possesses a cloned remote by one of the attacks mentioned above, he is also able to set the counter to the maximum of the re-synchronization window. After sending more valid hopping codes using the cloned and optimized remote, the receiver synchronizes with the counter value of the pirate device which renders the original remote useless, unless the owner of the original remote presses the button 215 times.
In 2009 about the same team presented another attack based on SPA (Simple Power Analyses) which is more efficient and able to recover kman with a single power trace. The computation of the keys does not even require any knowledge about the inputs (clear text) or outputs (cipher text), instead all information can be derived from the power measurements.

=== Jam and Listen, Replay Attack ===
[[File:JamAndListen.png|thumb|Hopping Code, Jam Signal, Receive Windows]]
The security researcher, Samy Kamkar, presented a small hacking device on DEF CON 23 in 2015, called Rolljam, which was able to open most cars using KeeLoq technology. For the attack the device has to be in range of the remote transmitter. Once the car owner presses the function button to unlock the car, the hacking device jams the radio transmission while it is recording the original message, which was not heard by the receiver due to the radio jam signal. The jam signal is slightly below the frequency of the transmitters operating frequency. Since the car's receiver window is much wider, the car is not able to receive the message, while the Rolljam device with its fine tuned receive window, is perfectly able to capture the message and keep it for later. In the meantime the owner of the car notice that the car did not open and press the function button once again. This time Rolljam will again jam and record the new message, but this time it also sends the previously recorded signal to the car, which will open this time, but leaves the eavesdropper with a valid hopping code behind. Of course, pressing a function button again on the remote will immediately invalidate the hopping code stored on the attackers device. But the small device could be battery powered and mounted at a hidden spot on the car or garage, and just keep on recording, so the device has always a valid hopping code stored, and is just waiting for the attacker to come back.

== References ==

* Wikipedia contributors, “Keeloq — Wikipedia, the free encyclopedia,” 2019, [Online; accessed 28-October-2020].[Online]. Available: https://en.wikipedia.org/w/index.php?title=KeeLoq&oldid=917022477

* R. R. Enderlein, “Keeloq,” EPFL / LASEC, January 2010.

* A. Bogdanov, “Cryptanalysis of the keeloq block cipher,” International Association for Cryptologic Research, 2007.

* Thomas Eisenbarth and Timo Kasper and Amir Moradi and Christof Paar and 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,” LNCS, 2008.

* “Drive it like you hacked it: New attacks and tools to wirelessly steal cars,” 2015. [Online]. Available: https://www.defcon.org/html/defcon-23/dc-23-speakers.html#Kamkar
* 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

[[Category:Basic]]

KeeloQ

2024-01-08T20:35:39Z

MLindner:

== 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
[[Category:Basic]]
* 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

KeeloQ

2024-01-08T20:32:49Z

MLindner:

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

== 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
[[Category:Basic]]
* 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

KeeLoq: Basics

2024-01-08T20:22:59Z

MLindner:

== Summary ==

This documentation includes a brief introduction into KeeLoq and pentesting with the PandwaRF Rogue Pro on garage doors.

== Requirements ==

* PandwaRF Rogue Pro
* PandwaRF App for Android (updated Android Version)
* Kaiju Gate Openers Pack (Pro License)

== Description ==

KeeLoq is a lightweight block cipher owned by Microchip and it was invented in the 1980’s at the South-African company Nanoteq Ltd.
Keeloq is implemented in a wide range of security applications. It is widely used as a remote key-less entry system. A remote keyless entry is an electronic access system that can be controlled from the distance, which means remote.

=== Registers ===

A register in general is a device which is used to store information.

Keeloq consists of two different registers:
* 64 bit key register – Circular-Shift Register and
* 32 bit text register – Nonlinear-Feedback-Shift Register.

''' Circular-Shift Registers

The information and data is stored in the format of multiple bits.
The transformation of these information is made with the help of shift registers.
Circular-shift registers calculate the bits of the register around the two ends without any loss.

''' Nonlinear-Feedback-Shift Register

A nonlinear-feedback shift register is a shift-register with an input bit that is a non-linear function of its previous state.
It executes the single-bits for 528 rounds.
The output sequence is an output sequence of the feedback shift register given by the function.

=== Block Ciphers ===

Keeloq is a lightweight block cipher for remote keyless entry systems.
A block cipher is a method of data encryption, which uses a cryptographic key and algorithm to produce ciphertext.
The block cipher processes fixed-size blocks at once, as alternate to a stream cipher, which encrypts data one bit at a time. Most modern block ciphers are invented to encrypt data in fixed-size blocks of either 64 or 128 bits.
A block cipher uses a symmetric key to encrypt and decrypt a block of data. Additionally,it requires an initialization vector which is added to the input plaintext in order to increase the keyspace of the cipher and make it more difficult to use brute force to break the key.
Block ciphers are built in the ’Feistel’ cipher structure. Block cipher has a specific number of rounds and keys for generating ciphertext.

=== Protocols ===

Keeloq consists of two different protocols:
* Hopping Code and
* Identification Friend or Foe (IFF).

''' Hopping Code

When hopping code is used, the code transmitted from the transmitter to the receiver is unique every time.
At the core of this code hopping technology is a counter that increments with each button press. The so-called Avalance Effect, which is satisfied when altering a single input bit results in modifying at least half of the output bits, helps generate individually unique signals.
The en- and the decoder share a 16-bit synchronized counter value and a
64-bit symmetric key. The encoder encrypts the next counter value for authentication and sends it afterwards to the decoder.
The decoder decrypts the message and verifies the received counter value if it is inside the open window of length 16.

Encoder Operation:
#Reaction on Buttonpress
#Encryption of the synchronization counter, discrimination value and button information
#Encryption using Hopping Code, thereby this code portion will change every transmission.
[[File:Encoder.png | 400px]]

Decoder Operation:
#Learn and store information: Check value of the serial number, encoder decryption key, current synchronization counter value, manufacturer’s code. If two nonsequential codes were received or if two codes were not decoded within 30 seconds, the learning will be terminated. To enter the learning sequence, the transmitter is activated two times. After the learning a learn-status-string will be transmitted.
[[File:Learning Sequence.png | 400px]]
#Validation: For the validation, wait for the transmission, check the serial number, and compare it to determine if the transmitter is already learned.
[[File:Validation.png | 400px]]

Synchronization of Encoder and Decoder:
#It might come to a desynchronization between encoder and decoder because the encoder can transmit while being out-of-range of the decoder.
#To counteract against this eventualities, different ranges of counter values are defined by the counter.
[[File:Window Hopping Code.png | 400px]]
* In blocked Window the decoder does not perform anything because the decoder rejects the transmission.
* In resynchronization window the decoder stores the value and waits for the value increased by one.
* In open window the decoder accepts the transmission and performs the requisite function.

''' Identification Friend or Foe (IFF)

The IFF protocol is an effective anti-cloning technique and it is a challenge-response protocol.
Thereby the main processor sends a large random number, called “challenge” (x), to the replaceable module. The replaceable module is a module which applies a formula to the challenge.
Afterwards it computes a response and send it back to the main processor. The main processor compares the different values, the returned value and the computed value.
The main processor accepts the new module as compatible (authenticated) if the formula which is used in the replaceable module is correct.
The Keeloq IFF is based on the block cipher which is a 64-bit key encryption engine and on the 32-bit data blocks, which are represented as challenge and response.

[[File:IFF.png | 400px]]

=== Pentesting with PandwaRF Rogue Pro and Kaiju Gate Openers Pack ===

''' Step 1 '''

#Install the application on your Android Phone. It can be downloaded from the Google Play Store.
#Open the Device and attach the antenna.
#Connect the PandwaRF via USB-C to your phone. The connection to the device should be established automatically, once it is connected to the phone.
#Open the application.

''' Step 2 '''

#Open the Spectrum Analyser and press the button Start. Then use the gate opener and press the button to open the gate. The Spectrum Analyser captures the frequency and additional information.
#Open the RX/TX Radio Data and scroll down to the end. Press the button Capture and additionally a ctivate the gate opener several times until enough data is captured (it is seen on RX progress).
#The captured data can be seen on the end of the screen. Additionally the analyser knows the used pattern, which is KeeLoq (rolling code).

''' Step 3 '''

#Click on "Analyze".
#Further choose "Fixed Code (local). There the information about the gate opener can be seen.
#To open the gate with PandwaRF Rogue Pro, click on "Rolling Code". The analysis of the rolling code should start with Kaiju automatically. It can last for several minutes.
#If Kaiju is finished with the analysis, several codes can be seen on the screen. This are the rolling codes, which are used to open the gate. The first one is marked as already used and cannot be taken to open the gate.
#Click on one subjacent codes and use it to open the garage door.

Side Notes:
* The execution of the analysis with Kaiju Gate Openers Pack is only possible at a few garage doors, it depends on the manufacturer and type.
* Since only the PandwaRF Rogue Pro is available, it is not possible to show the analysed rolling code after the analysis of Kaiju. To show the cracked encryption, the PandwaRF Rogue Gov with the Kaiju license would be necessary.
* Further, it is not possible to open car doors with the Kaiju Gate Openers Pack.

== Used Hardware ==

* Android Smartphone
* PandwaRF Rogue Pro

== References ==

* https://www.techtarget.com/whatis/definition/Remote-keyless-entry-RKE
* Nicolas T. Courtois. Self-similarity attacks on block ciphers and application to keeloq. In Cryptography and Security: From Theory to Applications, pages 55–66, 2012. 17, 18
* Steven Dawson. Code hopping decoder using a pic16c56. In Microchip, AN661, pages 2–6. 13
* Lucio Di Jasio. Using keeloq® to validate subsystem compatibility. In Microchip, AN827, pages 1–4. 14, 15, 26
* Sushil Jajodia Henk C.A. van Tilborg. Keeloq. In Encyclopedia of Cryptography and Security, page 671–673, 2011. 1, 2
* Sushil Jajodia Henk C.A. van Tilborg. Keeloq. In Encyclopedia of Cryptography and Security, pages 846–848, 2011. 4
* Microchip. Keeloq® code hopping decoder. In Microchip, HCS515, pages 2–6. 8, 10, 11, 12, 13, 26
* Microchip. Keeloq® code hopping encoder. In Microchip, HCS301, pages 4–16. 7, 8, 9, 13, 26
* Oleksandr Potii, Nikolay Poluyanenko, Igor Stelnyk, Iryna Revak, Sergii Kavun, and Tetiana Kuznetsova. Nonlinear-feedback shift registers for stream ciphers. In 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON), pages 906–911, 2019. 3
* Tomasz Rachwalik, Janusz Szmidt, Robert Wicik, and Janusz Zab locki. Generation of nonlinear feedback shift registers with special-purpose hardware. In 2012 Military Communications and Information Systems Conference (MCC), pages 1–4, 2012. 3, 26
* Christian Toma. Introduction to ultimate keeloq® technology. In Microchip, AN1683, pages 2–17. 7, 8
* 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.

[[Category:Documentation]]

KeeLoq: Basics

2024-01-08T20:21:22Z

MLindner:

== Summary ==

This documentation includes a brief introduction into KeeLoq and pentesting with the PandwaRF Rogue Pro on garage doors.

== Requirements ==

* PandwaRF Rogue Pro
* PandwaRF App for Android (updated Android Version)
* Kaiju Gate Openers Pack (Pro License)

== Description ==

KeeLoq is a lightweight block cipher owned by Microchip and it was invented in the 1980’s at the South-African company Nanoteq Ltd.
Keeloq is implemented in a wide range of security applications. It is widely used as a remote key-less entry system. A remote keyless entry is an electronic access system that can be controlled from the distance, which means remote.

=== Registers ===

A register in general is a device which is used to store information.

Keeloq consists of two different registers:
* 64 bit key register – Circular-Shift Register and
* 32 bit text register – Nonlinear-Feedback-Shift Register.

''' Circular-Shift Registers

The information and data is stored in the format of multiple bits.
The transformation of these information is made with the help of shift registers.
Circular-shift registers calculate the bits of the register around the two ends without any loss.

''' Nonlinear-Feedback-Shift Register

A nonlinear-feedback shift register is a shift-register with an input bit that is a non-linear function of its previous state.
It executes the single-bits for 528 rounds.
The output sequence is an output sequence of the feedback shift register given by the function.

=== Block Ciphers ===

Keeloq is a lightweight block cipher for remote keyless entry systems.
A block cipher is a method of data encryption, which uses a cryptographic key and algorithm to produce ciphertext.
The block cipher processes fixed-size blocks at once, as alternate to a stream cipher, which encrypts data one bit at a time. Most modern block ciphers are invented to encrypt data in fixed-size blocks of either 64 or 128 bits.
A block cipher uses a symmetric key to encrypt and decrypt a block of data. Additionally,it requires an initialization vector which is added to the input plaintext in order to increase the keyspace of the cipher and make it more difficult to use brute force to break the key.
Block ciphers are built in the ’Feistel’ cipher structure. Block cipher has a specific number of rounds and keys for generating ciphertext.

=== Protocols ===

Keeloq consists of two different protocols:
* Hopping Code and
* Identification Friend or Foe (IFF).

''' Hopping Code

When hopping code is used, the code transmitted from the transmitter to the receiver is unique every time.
At the core of this code hopping technology is a counter that increments with each button press. The so-called Avalance Effect, which is satisfied when altering a single input bit results in modifying at least half of the output bits, helps generate individually unique signals.
The en- and the decoder share a 16-bit synchronized counter value and a
64-bit symmetric key. The encoder encrypts the next counter value for authentication and sends it afterwards to the decoder.
The decoder decrypts the message and verifies the received counter value if it is inside the open window of length 16.

Encoder Operation:
#Reaction on Buttonpress
#Encryption of the synchronization counter, discrimination value and button information
#Encryption using Hopping Code, thereby this code portion will change every transmission.
[[File:Encoder.png | 400px]]

Decoder Operation:
#Learn and store information: Check value of the serial number, encoder decryption key, current synchronization counter value, manufacturer’s code. If two nonsequential codes were received or if two codes were not decoded within 30 seconds, the learning will be terminated. To enter the learning sequence, the transmitter is activated two times. After the learning a learn-status-string will be transmitted.
[[File:Learning Sequence.png | 400px]]
#Validation: For the validation, wait for the transmission, check the serial number, and compare it to determine if the transmitter is already learned.
[[File:Validation.png | 400px]]

Synchronization of Encoder and Decoder:
#It might come to a desynchronization between encoder and decoder because the encoder can transmit while being out-of-range of the decoder.
#To counteract against this eventualities, different ranges of counter values are defined by the counter.
[[File:Window Hopping Code.png | 400px]]
* In blocked Window the decoder does not perform anything because the decoder rejects the transmission.
* In resynchronization window the decoder stores the value and waits for the value increased by one.
* In open window the decoder accepts the transmission and performs the requisite function.

''' Identification Friend or Foe (IFF)

The IFF protocol is an effective anti-cloning technique and it is a challenge-response protocol.
Thereby the main processor sends a large random number, called “challenge” (x), to the replaceable module. The replaceable module is a module which applies a formula to the challenge.
Afterwards it computes a response and send it back to the main processor. The main processor compares the different values, the returned value and the computed value.
The main processor accepts the new module as compatible (authenticated) if the formula which is used in the replaceable module is correct.
The Keeloq IFF is based on the block cipher which is a 64-bit key encryption engine and on the 32-bit data blocks, which are represented as challenge and response.

[[File:IFF.png | 400px]]

=== Pentesting with PandwaRF Rogue Pro and Kaiju Gate Openers Pack ===

''' Step 1 '''

#Install the application on your Android Phone. It can be downloaded from the Google Play Store.
#Open the Device and attach the antenna.
#Connect the PandwaRF via USB-C to your phone. The connection to the device should be established automatically, once it is connected to the phone.
#Open the application.

''' Step 2 '''

#Open the Spectrum Analyser and press the button Start. Then use the gate opener and press the button to open the gate. The Spectrum Analyser captures the frequency and additional information.
#Open the RX/TX Radio Data and scroll down to the end. Press the button Capture and additionally a ctivate the gate opener several times until enough data is captured (it is seen on RX progress).
#The captured data can be seen on the end of the screen. Additionally the analyser knows the used pattern, which is KeeLoq (rolling code).

''' Step 3 '''

#Click on "Analyze".
#Further choose "Fixed Code (local). There the information about the gate opener can be seen.
#To open the gate with PandwaRF Rogue Pro, click on "Rolling Code". The analysis of the rolling code should start with Kaiju automatically. It can last for several minutes.
#If Kaiju is finished with the analysis, several codes can be seen on the screen. This are the rolling codes, which are used to open the gate. The first one is marked as already used and cannot be taken to open the gate.
#Click on one subjacent codes and use it to open the garage door.

Side Notes:
* The execution of the analysis with Kaiju Gate Openers Pack is only possible at a few garage doors, it depends on the manufacturer and type.
* Since only the PandwaRF Rogue Pro is available, it is not possible to show the analysed rolling code after the analysis of Kaiju. To show the cracked encryption, the PandwaRF Rogue Gov with the Kaiju license would be necessary.
* Further, it is not possible to open car doors with the Kaiju Gate Openers Pack.

== Used Hardware ==

* Android Smartphone
* PandwaRF Rogue Pro

== References ==

* https://www.techtarget.com/whatis/definition/Remote-keyless-entry-RKE
* Nicolas T. Courtois. Self-similarity attacks on block ciphers and application to keeloq. In Cryptography and Security: From Theory to Applications, pages 55–66, 2012. 17, 18
* Steven Dawson. Code hopping decoder using a pic16c56. In Microchip, AN661, pages 2–6. 13
* Lucio Di Jasio. Using keeloq® to validate subsystem compatibility. In Microchip, AN827, pages 1–4. 14, 15, 26
* Sushil Jajodia Henk C.A. van Tilborg. Keeloq. In Encyclopedia of Cryptography and Security, page 671–673, 2011. 1, 2
* Sushil Jajodia Henk C.A. van Tilborg. Keeloq. In Encyclopedia of Cryptography and Security, pages 846–848, 2011. 4
* Microchip. Keeloq® code hopping decoder. In Microchip, HCS515, pages 2–6. 8, 10, 11, 12, 13, 26
* Microchip. Keeloq® code hopping encoder. In Microchip, HCS301, pages 4–16. 7, 8, 9, 13, 26
* Oleksandr Potii, Nikolay Poluyanenko, Igor Stelnyk, Iryna Revak, Sergii Kavun, and Tetiana Kuznetsova. Nonlinear-feedback shift registers for stream ciphers. In 2019 IEEE 2nd Ukraine Conference on Electrical and Computer Engineering (UKRCON), pages 906–911, 2019. 3
* Tomasz Rachwalik, Janusz Szmidt, Robert Wicik, and Janusz Zab locki. Generation of nonlinear feedback shift registers with special-purpose hardware. In 2012 Military Communications and Information Systems Conference (MCC), pages 1–4, 2012. 3, 26
* Christian Toma. Introduction to ultimate keeloq® technology. In Microchip, AN1683, pages 2–17. 7, 8
* Kobus Marneweck. An introduction to keeloq® code hopping. Microchip
App Notes, https://bit. ly/3BVV5qs, 1996

[[Category:Documentation]]