KeeLoq: Attacks and Example

Basics

To read about the basics of KeeLoq visit KeeLoq: Basics.

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, this 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 this 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, they are 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.

Example: Pentesting with PandwaRF Rogue Pro and Kaiju Gate Openers Pack

Step 1

1. Install the application on your Android Phone. It can be downloaded from the Google Play Store.
2. Open the Device and attach the antenna.
3. 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.
4. Open the application.

Step 2

1. 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.
2. 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).
3. 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

1. Click on "Analyze".
2. Further choose "Fixed Code (local). There the information about the gate opener can be seen.
3. 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.
4. 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.
5. 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

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