A short note on KeeLoq: how the end-user can protect himself against the recently published attack on the manufacturer key

All the keyless entry applications (car remotes, garage door openers, etc.) based on the Keeloq cipher (known under the marketing names "code hopping", "floating code", "rolling code", etc.) were long claimed to be secure. I would estimate that tens of millions of such devices might have been sold worldwide. Actually, already in 2004 I was wondering how my wireless car lock functions and finding the data sheet of HCS200 chip employed in my remote control, I tried to use google a bit more extensively and indeed I have discovered the AN642.pdf file (normally provided only to Microchip corporate customers under signing a non-disclosure agreement), which describes details of the Keeloq cipher, on some russian server back in july 2004. The knowledge of russian alphabet learnt unwilingly during the communist regime in our country was finally useful! Based on that application note I developed an Atmel AVR assembly language implementation of Keeloq (see below) and used it privately together with HCS200-based remotes for a homebrew burglar alarm.

Taking into account that in the real-world rolling code applications the attacker can eavesdrop only a few ciphertexts but no plaintext is available to him, it seemed that the Keeloq cipher should be reasonably secure for this purpose. Actually, the cipher itself has been broken from a mathematical point of view, however, the best direct attack known (cf. the wiki) still requires 2^16 plaintext/ciphertext pairs and is thus not useful for attacking the rolling code applications in practice.

Till 2008 nobody did consider a side-channel analysis on a physical Keeloq implementation, which recently turned out to be very fruitful. Still, if each device sold to the end-user would use a random device key, rather than one derived in a standard way from a manufacturer key (which is constant for a large production series), or if each device would use a 60-bit seed, the attacker would need a physical access to the remote control from your keyring to clone it. Unfortunately, it seems that a vast majority of the devices on market use either no or a short seed and support the (for the end-user convenient) learning method based on the manufacturer key.

Recently it has been demonstrated how the manufacturer key can be extracted from a receiver device by a physical side-channel cryptanalysis and how a particular remote control can be cloned (either knowing a matching manufacturer key without physical access to the remote, or without manufacturer key but requiring physical access to the remote) (see the wiki and references therein). For convenience I list here some of the relevant papers: Power side channel cryptanalysis of Keeloq hardware implementations in HCS chips and Power side channel cryptanalysis of PIC implementation of Keeloq and Security analysis of Pervasice Wireless Devices and Cryptanalysis of Keeloq using Xilinx FPGA and A practical attack on Keeloq . Very nice summary is given also in chapter 8 of the recent Timo Kasper's PhD thesis on Security analysis of pervasive wireless devices.
Once the manufacturer key is known, any remote control belonging to ANY receiver sharing the same "manufacturer key" can be cloned, after eavesdroping one or two communications transmitted from the particular remote control. So, it might be the case that for example all Audi cars produced in Europe during, say, 2005-2007 share the same manufacturer key and if you analyze the central locking unit of one of them, you can open any of them after eavesdropping the owner while locking his car at a parking place (using a simple 433 or 868 MHz code grabber). (Unless a 60-bit random seed has been used in the learning algorithm, which, however, is not supported by a majority of chips implementing Keeloq.) I expect a lot of cars and garages to be broken into without physical traces, once tech-savvy criminals study the relevant literature. I can imagine, that explaining to the insurer, that a burglary really happened, rather than an insurance fraud, would not be an enjoyable experience in this case.

So, for the end-user the situation is dire, but not entirely hopeless :-). How to solve the problem? If your receiver device contains a specialized hardware KeeLoq decoder, it should be possible to flash your own randomly selected device code into that chip and matching remotes, following the instructions in appropriate data sheets. In this way you circumvent the problem with the learning algorithm and manufacturer key. If a MCU is employed to implement the decryption, you will need to reverse-engineer how the receiver controls the power parts (locks, motors, etc.) and build your own replacement unit (unless you are able to generate modified firmware for that particular MCU in the context of the surrounding hardware) and again employ your own device key unrelated to any manufacturer (or choose your own manufacturer key for a production series consisting of one unit :-)). In any case, you also have to protect your remote control from an unauthorized physical access to prevent its cloning.

If you decide to use ATmega microcontrollers, you can download my

KeeLoq implementation in the Atmel AVR assembler (inlined in C) keeloq.c and header file keeloq.h

The source code is freely available under the GPLv3 license.

For hacking and tinkering with Keeloq remotes, you will certainly need a receiver/transmitter (Keeloq sniffer). These can be easily built, since 433.92MHz (or 866MHz) amplitude shift keying RX/TX modules (e.g. from Aurel wireless or similar) are available in electronic component shops. The schematics is trivial - just look at the datasheets of ATmega and of the RX/TX modules - and it can be built on a universal PCB. To facilitate your effort, I make here a

KeeLoq receiver/transmitter C source code

available. It is a bit messy experimental code, however, it includes also a routine for programming the HCS200 chip.
Depending on the version of avr-gcc and headers you might need the header backward.h

The "take home message" of this whole story is that once again it has turned out that "security through obscurity" is not a good solution. Relying that non-disclosure agreements will forever protect an obscured algorithm, which is in widespread use, is really naive. If the cipher and its hardware implementations were subject to scrutiny of expert cryptanalysts immediately after or even before being placed on the market and having a chance to become so widespread, perhaps the flaw could have been discovered much sooner and a lot of (potential) damage might have been prevented.

P.S. 1 I found recently some application note from which it seems that Microchip recently started to produce hopping code chips implementing the AES cipher instead of Keeloq, so they probably take this threat seriously. Note, however, that a physical implementation of mathematically secure ciphers still can be vulnerable to side-channel (typically power analysis) attacks. Also the key distribution/management, when wrongly implemented like with the Keeloq's manufacturer key, can introduce a single point of failure into the commercial cryptosystem. In other words, the chain is as strong as its weakest element, so the marketing headword 'employes AES' does by far not mean that the product as whole is secure.

P.S. 2 To use some more modern ciphers in your own devices, you might find this port of AES and elliptic curves cipher to small MCUs useful.

P.S. 3 The situation with security of garage door openers in real life can be even worse, since there are still devices with a fixed code on the market! I have recently constructed a new garage and the construction company used motors with remote control Marantec Comfort 220.2 . I did not care about the choice of the opener, since I planned to construct my own remote control with an appropriate security level. However, I was still surprized by the fact that this Marantec device uses a fixed code! I thought that such solutions are long obsolete and out of the market! They use the frequency 868.3MHz, however, RX/TX modules for this band can easily be obtained e.g. from Aurel, too. In my device which runs the aforementioned rxtx433.c code I have a socket which allows to swap the modules. I was able in this way to easily clone the Marantec remote control for my garage; the updated source code provided here now also contains 'rx general' and 'tx general' routines which I used for this purpose. So unless you want to invite burglars, avoid products of Marantec (and possibly other vendors of fixed-code openers). Btw., for their achievements in security the Marantec company should change its name to ``Morontec''!



Receiving Keeloq remotes using USRP and Gnuradio

Some time ago I became interested in the software radio technology and for this purpose purchased the USRP and some daughterboards. The free software Gnuradio can be easily installed on a linux machine. Of course, using these tools for receiving Keeloq remotes is a kind of overkill, but actually it can be viewed as a simple excercise to get accustomed to these powerful tools. Moreover, USRP provides you much better selectivity than the simple RX modules, so you can pick up the exact frequency of a particular remote from the whole band. Due to the very simple circuitry, remotes of different manufacturers transmit at somewhat varying frequencies (cf. the two smaller peaks in the captured RF spectrum), which slightly depend even on the way how you hold them in the hand (cf. the broad dominant peak in the below screenshot).
Recently another SDR device compatible with GNUradio has become available, the OZ9AEC. Since I did not have time yet to learn how to properly implement Gnuradio blocks and make them available in GRC, I have decided to follow the AM demodulation by a file sink, where the file is actually a named pipe, and to run an external program to implement the conversion to digital data (ASK demodulation followed by decoding the pulsed width modulated signal) and decryption.
The hardware setup is: USRP with WBX or TVRX, variable attenuator (needed if the transmitter is very close to the antenna), antenna (about 17cm long piece of wire is sufficient for experimenting, to eavesdrop your neighbor you might need a yagi on the roof :-)).
To run it, prepare a named pipe (mkfifo /tmp/fifo), compile and run the Keeloq decoder, and simultaneously run the receiver in Gnuradio companion (or the generated Python program).

Here you can download the amplitude shift keying receiver Gnuradio GRC schematics

and the Keeloq decoding C program.

The program is not very fancy, it was just quickly adapted from the AVR version to Linux. The threshold value has to be estimated from the scope plot.

NEW:
A have adapted the ASK receiver GRC schematics for Funcube dongle: ask_rx_fcd.grc and for the REALTEC USB DVB-T stick: ask_rx_rtl.grc . Both of them feed gnuradio_keeloq_rx with sampling rate 48000.

For transmitting Keeloq messages with USRP, you can use the

Keeloq encoding C program

together with the

amplitude shift keying transmitter Gnuradio GRC schematics.


To compile both C programs, you will need the keeloq.c and keeloq.h files, which are the same as for the microcontroller implementation described above (if AVR_SOURCE is NOT defined, a generic C implementation of Keeloq is used instead of AVR assembly).
On the screenshot below you can see the the beginning of a Keeloq transmisssion (50% duty pulses), followed by a short pause and then the data (see e.g. the HCS200 datasheet for a detailed description).


My notes on experimenting with RFID using Proxmark3


Back to my electronics page


Back to my main page


TOP