KeeLoq Remake

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

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

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 k_dev 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 k_man 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 k_man 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 k_dev 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 2¹⁵ times.

In 2009 about the same team presented another attack based on SPA (Simple Power Analyses) which is more efficient and able to recover k_man 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

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