Could somebody explain how rolling code protocols such as KeeLoq work? I understand the basic premise that they use a different code each time so you can't just use replay attack, but I don't understand how one side verifies the correct code etc.
Furthermore, how do they perform an initial synchronization if the index into the rolling codes isn't known/shared beforehand?
If you have to use Keeloq as an example to explain that is fine, but I would rather a general explanation of rolling codes.
Answer
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.
No comments:
Post a Comment