Rolling Code Explanation

Rolling codes require several part to function correctly. Here I'll describe a generic implementation that uses all the parts in a specific way. Other systems are variations on this theme, but generally employ many of the same techniques in a similar way. Rather than try to describe the complete implementation and how it works at once, I'll describe a simple system, and add complexity as we go until we reach a cryptographically secure system.

A non cryptographic rolling code is simply a transmitter and receiver that both use the same pseudo random number generator (PRNG). This generator has two pieces of important information: a calculation, and the previously generated number. The calculation is generally a linear feedback equation that can be represented by a single number. By feeding the PRNG with the previous number, and keeping the feedback number the same a specific sequence of numbers is generated. The sequence has no repeated sequences until it's gone through every number it can generate, and then it starts over again with the same sequence.

If both remote and transmitter know the feedback number, and the current number, then when the remote transmits the next number, the receiver can test it against its own generator. If it matches, it activates. If it doesn't, it rolls through the sequence until it finds the number the remote sent. If you press the remote again, then it should match, and it'll activate because the previous transmission already synchronized the number generators. This is why you sometimes have to press the unlock button twice - your receiver or transmitter are out of sync.

That's the rolling part of the code. If the PRNG is long enough, it's very hard to find out the feedback number without many numbers in the sequence in a row, which is hard to obtain in normal use. But it's not cryptographically secure.

On top of that you add typical encryption. The vehicle manufacturer uses a specific secret key for the transmitter and receiver. Depending on the manufacturer you might find that each model and year have a different code, or they might share the code among several models of vehicles and over several years. The trade off is that each one then requires a different remote to be stocked, but the problem with sharing a code over many models is that if it's broken then more cars are vulnerable.

Behind the encryption you have button info, the PRNG generated number, and a little information about the feedback number. Not enough to make the PRNG from scratch, but enough that after a certain number of button presses, and with some inside information about the limited space a feedback number can involve (again, manufacturer, line specific) then the receiver can, after several training transmissions, determine the feedback number, and start tracking the PRNG for that remote.

The rolling code is meant only to stop replay attacks. The encryption is meant to secure the rolling code to avoid it being broken. With only one or the other the system would be too easy to break. Since the manufacturer controls both the transmitter and receiver, training doesn't involve public key cryptography or anything particularly involved. It also prevents aftermarket fobs from working in cars with this type of system.

Rolling code isn't impervious, though. The old keeloq system was successfully attacked just a few years ago (after a decade of use) so the manufacturer encryption code can be found, and the rolling codes can be found more easily. Earlier than that it has been attacked in ways that allowed people to take vehicles without actually breaking the code. In response the new encryption key is 60 bits. Not as secure as many modern encryption systems, but secure enough that it'll probably last many more years before it's broken.

I first encountered KeeLoq when researching the chip in a garage door opener. The Microchip datasheet does a good job of explaining how it works.

In a nutshell:

• the receiver maintains a database of all transmitters, keyed on their serial number.
• each transmitter is associated with a symmetric encryption key (64 bit), which is on the chip, and also in the receiver's database.
• each transmitter is associated with a 16 bit cyclic sequence number, also stored on the chip and in the database.
• when the transmitter is activated, it increments its sequence number modulo 65536 (wraparound 16 bits), and sends a packet consisting of a bitmask representing what buttons are pressed, its serial ID, and an encrypted version of the serial number.
• the receiver matches the serial number in the database, pulls out the key and decrypts the serial number.
• the serial number has to be new; it cannot be a recently used serial number, which guards against replay attacks. (See Fig. 7.3 in the datasheet).
• if the serial number verifies, then the receiver can activate functionality based on the bit mask of what buttons are pressed.
• if the new serial number is ahead by more than 16 values (the user pushed the buttons many times accidentally while away from the receiver) then an extra hand-shake has to take place to resynchronize, which requires an extra button press. (The user will perform the extra button press, believing there is bad reception).

Adding a new transmitter to the receiver database is vaguely analogous, on a high level, to the button-press configuration method for adding clients to a Wi-Fi access point. The receiver is somehow told put into a mode whereby it accepts a new transmitter.

A new transmitter can be accepted from information passed in ordinary activation messages, if the receiver and transmitter share the same secret manufacturer ID. This is because the 64 bit encryption key is derived from the manufacturer ID and serial information of the receiver. (See Sec. 7.1).

There is a more secure alternative to this: the "Secure Learn". This is initiated in a special way on the transmitter (three buttons pressed at once). The transmitter sends a special packet: a 60 bit seed value from which the encryption key is derived, presumably not depending on the manufacturer ID or serial number.

When the receiver is not in learn mode, it of course rejects transmissions from transmitters that it does not know about.