KeeLoq: Basics

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)

Introduction

KeeLoq is a lightweight block cipher owned by Microchip and it was invented in the 1980’s at the South-African company Nanoteq Ltd by Frederick Bruwer (uni-directional command transfer protocol), Gideon Kuhn (cryptographic algorithm) and Willem Smit (silicon implementation). 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. 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

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 k_Man, which makes cloning of senders an easy task.

KeeLoq Decryption/Encryption Algorithm

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

Hopping Code Message Format

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

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:

1. Reaction on Buttonpress
2. Encryption of the synchronization counter, discrimination value and button information
3. Encryption using Hopping Code, thereby this code portion will change every transmission.

Decoder Operation:

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

1. Validation: For the validation, wait for the transmission, check the serial number, and compare it to determine if the transmitter is already learned.

Synchronization of Encoder and Decoder:

1. It might come to a desynchronization between encoder and decoder because the encoder can transmit while being out-of-range of the decoder.
2. To counteract against this eventualities, different ranges of counter values are defined by the counter.

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

Further Documentation

KeeLoq: Attacks and Example

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