How do rolling code fobs and receivers synchronise?

Question

This is a follow-up question to my earlier one: Does pressing a car remote many times offer denial of service attack for rolling codes?

I want to emphasize that I am asking this question more to shore up holes in my academic (mis)understanding of rolling codes than as a practical "How do I start my car?" question.

Many (older) car and garage remotes use a rolling code system, so every time the fob button is pressed, a different code is sent, to protect against replay attacks.

Shared Secret?

My original understanding of rolling codes was that there was a shared secret (perhaps a serial number?) between the fob and the car, and that this was used to cryptographically generate the same infinite sequence of rolling codes on both sides.

That way, a simple replay attack wouldn't work. (The receiver wouldn't accept the same code twice.)

I also thought that an attacker would need to sniff an infeasibly long sequence of codes before they could reverse engineer what the original secret was, and thus generate new items in the sequence.

Security through Obscurity?

I now think that I was over-estimating the technology, because it appears that a receiver can be trained to accept a new fob with a relatively simple process that doesn't require transferring a secret - you just need to push the fob once when the car/garage is in the equivalent of a "change password" mode.

This suggests to me that there is no shared secret, but just one very long (algorithmically generated?) sequence, that the two devices need to synchronise upon.

If the car can listen to the fob once and predict future codes, surely a sniffer can do the same?

If my new understanding is right: * All fobs using the same generating sequence. The algorithm may be obscure, but it isn't customised by a secret - the only "secret" is what the fob's current internal state is, and that is broadcast on every button press. * While a naive sniffer could not use a replay attack, a sophisticated sniffer could generate the entire future sequence from a single code. * I am disappointed in car/garage security systems.

Do car/garage fobs use a shared secret, and generate the sequence based on that? If so, what is the internal process that allows the remote and fob share the secret key during the synchronisation process?

Answer 1

Keeloq is used in many but not all key fobs/garage door openers. This article is writen by microchip who created keeloq Introduction to Ultimate KEELOQ Technology.

tl;dr

The remote(key fob/garage door opener) and receiver(car/garage motor unit) use the same 64 bit key to encrypt and decrypt. A "serial number" is used to identify a specific remote. Every time a button is pressed the remote's "sync counter" is incremented by 1. If the remotes "sync counter" is 0 to ~250 ahead of the receivers "sync counter" then it accepts the code and updates the sync counter for that remote. Since the "sync counter" is encrypted with a key that is only known to the remote and reciever a sniffer cannot forge a code even if it knew the next "sync counter" because it doesn't have the 64 bit key.

My original understanding of rolling codes was that there was a shared secret (perhaps a serial number?) between the fob and the car, and that this was used to cryptographically generate the same infinite sequence of rolling codes on both sides.

The remote encrypts the "Encrypted Portion" of the packet and sends that and the fixed portion to the receiver which then decrypts the "Encrypted Portion" using the same 64 bit key that the remote used. This is a different scheme than one time passwords which is often used for web authentication.

Well it's not infinite. Every time a button is pressed the "Sync Counter" is incremented by 1. The "Sync Counter" can range from 0 to 65535. So after 65536 transmissions you would see the same codes repeat. If you captured 65536 unlock transmissions you'd be able unlock the car/garage by playing the next raw capture in that sequence since it just wraps around.

I now think that I was over-estimating the technology, because it appears that a receiver can be trained to accept a new fob with a relatively simple process that doesn't require transferring a secret - you just need to push the fob once when the car/garage is in the equivalent of a "change password" mode.

Kind of. You're right that no shared-secret is exchanged or communicated. How the remote and receiver end-up using the same 64 bit key depends on the scheme.

There are 3 learning modes "simple" "normal" "secure" described by the pdf.

1. Simple

The Simple key generation scheme is the simplest scheme that a KEELOQ technology system supports. When using simple key generation, one single key is used by all encoders and the transmitters are differen- tiated only by the serial number. It is very important that the user understands exactly what the implications of using such a key generation scheme are. This could be a potential security risk. If any encoder is compromised and the encryption key is found, then all the encoders are compromised, because they use exactly the same key.

All remotes and receivers use EXACTLY the same 64 bit key to encrypt and decrypt packets.

2. normal

The Normal key generation scheme is the common key generation scheme for KEELOQ technology systems. During Normal Learn, a master key is used (known as the “manufacturer code”). When using the normal learning mechanism, the decoder uses the manufacturer code and the serial number to calculate the decryption key for each transmitter. Using the serial number of each encoder and the manufacturer code, the unique encryption key for each encoder is calculated. The encoder stores only the serial number and the calculated encryption key. The decoder needs to be programmed with this manufacturer code in order to be able to calculate individual encryption keys. To calculate the encryption key, the 28-bit serial number is padded with 0x6000000 and 0x20000000 and decrypted using the manufacturer code as the decryption key. This operation is done twice, in order to calculate the high part and the low part (MSB and LSB) of the encryption key.

The 64 bit key is derived using the "serial number" and the "manufacturers code". The remote only stores the derived key not the master key, but the receiver knows the master key so that it can derive any specific remote key. So it "learns" the remotes "serial number" and then derives that remote's 64 bit key.

3. secure

The Secure key generation scheme is a more advanced key generation scheme. When using the normal key generation scheme, the key is generated from the serial number and the manufacturer code. Since the serial number is transmitted in any packet, one part of the key generation scheme is always exposed. But an even more secure method is to generate a random number (called “seed”). Depending on the length of the seed, there are three key generation schemes: 32-bit seed, 48-bit seed and 60-bit seed. During normal operation, the seed is not transmitted. The only time when the seed is transmitted is during the learning/pairing phase. Thus, the information that is used to generate the encryption key is kept confiden- tial. Some implementations take the security level even further, by allowing the seed to be transmitted only for a limited period (in which the system is installed) and then disabling this feature.

A seed is used instead of the "serial number" for deriving the 64 bit key. The only time this seed is transmitted is at learning/pairing time.

As a final note. There are other schemes out there that are better than keeloq. Even the pdf describes a scheme that uses AES instead of keeloq, but there are worse ones too. Some garages still used fixed codes.

I am disappointed in car/garage security systems.

Me too.