Keeloq: 80s nostalgic algorithm

Introduced Mid-1980s

Manufacturer Nanoteq

Key Length 64 bits

Algorithm Proprietary (NLFSR)

Vehicles Chrysler, Daewoo, Fiat, General Motor, Honda, Jaguar, Toyota, Volkswagen, Volvo

Crack Status Broken

Keeloq, shown in Figure 12-8, is a very old algorithm, and there have been many published attacks on its encryption. Keeloq can use both a rolling code and a challenge response, and it uses a block cipher based on non- linear feedback shift register (NLFSR). The manufacturer implementing Keeloq receives a key, which is stored in all receivers. Receivers learn tran- sponder keys by receiving their IDs over a bus line programmed by the auto manufacturer.

The most effective cryptographic attack in Keeloq uses both a slide and a meet-in-the-middle attack. The attack targets Keeloq’s challenge– response mode and requires the collection of 216 known plaintext mes- sages from a transponder—the recording of which can take just over one hour. The attack typically results only in the ability to clone the transpon- der, but if the manufacturer’s key derivation is weak, it may be possible for the attacker to deduce the key used on their transponders. However, attack- ing the crypto has become unnecessary because newer dedicated FPGA clusters make it possible to simply brute-force the key.

Keeloq is also susceptible to a power-analysis attack. A power-analysis attack can be used to extract the manufacturer’s key used on the transpon- ders with only two transponder messages. If successful, such an attack typi- cally results only in the ability to clone a transponder in a few minutes by monitoring the power traces on the transponder. Power analysis can also be used to get the manufacturer key, though such an attack could take several hours to perform. Once the attacker has the master key, they can clone any transponder. Finally, because Keeloq takes varying clock cycles when using its lookup table, it’s also susceptible to timing attacks. (For more on power- analysis and timing attacks, see Chapter 8.)