Rolling codes and vehicle locks

Go over to Microchip's site and readup on 'Keelock(sp)' technology. They have(had) all the dope on how it works in an app note. It's basically 'bulletproof unlike the DES algorithm... :)

hth jay

From a crypto perspective, I'd expect it's to prevent replay attacks, where the code is "snooped" from RF and then played back later verbatim.

Speculating... you've got 4 data elements: fob serial number, keypress code, sequence number (rolling code), and a "secret" (if any).

Unless the car transmits a unique shared secret key to the fob (very unlikely), the secret isn't really secret (since it'd be identical in every car and fob) - someone will have compromised the "secret", whether it's a proprietary algorithm or the manufacturer's crypto key. It's likely that they didn't bother with a secret, for this very reason.

Consider this - will one keyfob work on two cars at once if properly "programmed"? (Likewise with garage door openers.) If so, there's your answer.

I'd wager that the burden of logic is on the car's side to track the last-used sequence number for each fob. For each fob (serial number), simply accept any sequence number geater than the last used, and the fob just increments with each button press.

So, I doubt the process is as secure as people think (it rarely is) - you just need a smarter "snooper" that increments the sequence number on playback.

Richard

Yes, it will - I have the same make of car, though four years newer, and I tried this. It's definite that the car does not program the fob (I doubt the fob contains a receiver) - the car *learns* the fob.

But the point of the code sequencing (as I understood it from Microchip's docs) is that you shouldn't be able to determine the (internal, incremented-each-button-press) state of the fob from RF-snooping a single event, or even from a reasonably long string of known-sequential button presses. The way it's supposed to work is that the fob has a serial number (unique, unknown by external entities, and nonvolatile) and an internal counter. Each button press, the serial number and the internal counter are algorithmically combined to generate the rolling code. Then the internal counter is incremented. The output sequence is supposed to look pseudorandom. A silly case would be to use code like this:

const unsigned int serial_number = 0x12345678; unsigned int internal_counter = 0; unsigned int output_code; unsigned int button_code;

while(1) { button_code = read_keyboard(); srand(serial_number ^ internal_counter); output_code = rand(); internal_counter++; transmit(output_code); transmit(button_code); }

So I'm left wondering if this particular model of vehicle really does use a rolling-code system (in which case how did they make the programming system work this way without doing something silly like actually transmitting the current sequence number in cleartext?).

The Microchip Keeloq rolling code system relies on a "secret" sequence in the key fob too, such as pressing all 3 function buttons at once. Then and only then does the the fob send key-related info for learning by the receiver. Alternatively, there could be a fixed manufacturer-dependent key that is shared by all receivers and keyfobs for a certain brand of car. That is quite weak, because eventually any such secret will become known to attackers. Are you sure that you didn't have to press several fob buttons at once to perform the learning?

-Robert Scott Ypsilanti, Michigan (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

Another thing to consider, if you hit the key fob, but the car doesn't hear it... won't it be on the wrong number? I mean, the point is for the car and the fob to be in sync. I can't see how you do this without feedback from the car (an ACK). Now there could be a certain case, where the car has a list (of say 256) public keys (or rather the decode keys) and the units all use a public key encrypted output value (which sends an id + counter value). In listen mode, it receives the fobs code, trys all 256 keys and the one that makes sense is the one it uses from then on. Tony

I haven't tested this behavior out, but I can see at least a couple of ways around this problem:

1. Have an "acceptance threshhold" T. If the car receives an unknown code, it looks ahead T iterations in the sequence for all known remotes [these cars can keep track of up to four remotes]. If it matches, it updates its internal counter for that remote and thereby gets back in sync. IIRC Keeloq does this.
2. Have a "sync mode". If the car receives an unknown code, it does nothing and waits for the user to press a button again. It then compares the two sequence codes received, and analyzes to see if they would be valid in-sequence codes for any of the remotes it knows.

I'm inclined to believe that the car uses option 2, because it's probably more secure [assuming a good cryptosystem] and it works intuitively right; if the car doesn't unlock when you press a button, your instinct is just to press the button again and assume some temporary radio problem.

Hi,

No, I didn't. These are Ford vehicles. Many Ford factory RKE systems are programmed using a variant of this method:

1. Ensure that you have all the remotes you intend to use with this car in your hands :)
2. Turn ignition from OFF (0) to RUN (II) times within seconds. (E.g. for 1998 Escort, n=8, t=10 - for 2002 Focus, n=6, t=20).
3. Car cycles all locks up and down to signal programming mode.
4. Within 20 seconds, press any button on first remote to be learned. Car cycles locks once to confirm code receipt.
5. Repeat step 3 for all remotes.
6. Turn ignition to OFF. Car cycles locks once to indicate programming mode complete.

Interestingly, I see from disassembly that there is a fifth, undocumented button on the PCB of the older remotes (which can't be accessed while the fob is closed). This button is not present on the newer remote that came with my Focus.

hear

the

Ok, if that is the situation, how does it get the first code programmed in? For that system to work, there has to be a valid stick in the mud for the random seed. Otherwise it could be a long time trying out seed values until they match up. Tony

My understanding is the idea was to 'defeat' simple Record/replay snooping devices. Without rolling code, any replay of the last-access is instant access.

Rolling codes must tolerate skipped codes, where the TXMIT may have been pressed out of range, or corrupted, or someone elses key was heard. But it is also vital to have to have a 'learn mode' for all those lost/damaged key fobs, so security is generic not specific. ( eg someone with brief, but unsupervised access to your car, 'adds' their remote to your list and you would never know ).

The rolling code must reject 'recent historical' sequences, but also be able to resync over arbitary skipped sequences.

-jg

Well, on our cars you WOULD know because all memories get cleared during the programming sequence - our remotes would stop working if you programmed yours without all of ours present! :)

Nearly. Consider the US valet parking - they have one legit remote, so your first indication would be when a _second_ remote no longer worked. Since the main remote never stopped, the first reaction might be 'dud remote, lets try re-learn'. Might not even consider/realise that vehicle access was compromised.

This is why much more secure electronic keys/immoblisers are being deployed. Remotes are token security.

-jg

I sincerely doubt it's that advanced, though that's not a difficult scheme to develop. But if the car can learn a fob and validate it's future sequences in only one press, then so can a determined snoop.

Public-key encryption could be applied to make a rock-solid scheme. The public key could be routinely transmitted in the clear along with the sequence code and fob serial number, which have been hashed using the private key stored in the fob. Anyone could validate the code came from that fob's unique private key, but nobody could generate the next hash, even if they knew the serial number and next sequence number. However... the computational power required would kill the battery life of the fob (and users would need to be extremely patient).

Really, locks on a car are only a theft deterrent, and "strength" is only practical up to a point. To any determined thief, windows are much easier to "open".

Now, the ignition's another matter, and with the electronic keys in electrical contact with the car, I imagine all sorts of solid 2-way schemes could be applied.

Richard

p.s. - if digital security and crypto are areas of interest, I encourage reading Bruce Schneier's writings - he's very respected in InfoSec and crypto circles. His Applied Crypto is a great practical text for laymen and math geeks alike (though lacking newer AES info), and his irregular Crypto-Gram newsletter is also entertaining. He also sells a source disc with most popular algorithms implemented in C.

No only is it possible, but it has been standard practice for all commercial rolling code applications since rolling codes came out. Just thinking about how kids play with keyfobs when out of range of the receiver means that recognizing two consecutive codes way in the "future" is absolutely required for any practical system.

-Robert Scott Ypsilanti, Michigan (Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

Kind of the point of my original posting - I wanted to see if anyone could fathom some subtle trickery whereby, given a very low-end microcontroller (that PIC sure isn't doing any asymmetric-key algorithm worth using!) and unidirectional communications, it could be "learning" in a single step AND secure against single-event snoops.

Well, they used to be :) I used to work in the field, but left for greener pastures about five years ago.

What you state below is essentially how one form of event-synchronous tokens for 2 factor authentication works in networking. I suspect the modern key fob deal is similar.

It could look 16 codes ahead (an example from a real token implementation). That's the window that then determines the probability of defeating it, e.g. 16

• 1/1,000,000 for a 6 digit code.

If someone entered the PIN, etc, on the token 16 times (say showing off the token to someone, or OCD fumbling with the keyfob), then it's beyond the window. Then the authentication would fail if the next code was used on the network. However, the system would compare the next code to the previous, and if they were successive codes, then it proceeds. The likehood is high of an attacker being able to guess a single code in the sequence (but not in the 16 code window), however 2 in succession would be almost impossible.

While the risk would be slim with a keyfob, with a token used for network access there might be a possible attack. Get ahold of the token (or keyfob) and log several successive codes. (PIN hopefully makes this harder.) These could be used until the token holder logs into the system and increments the counter. (I hope I'm wrong and this doesn't work). Time-dependent tokens wouldn't have this avenue of attack, however there are other problems with them.

On a network, you'd almost certainly use an encrypted protocol to prevent sniffing. Without encryption, anyone owning a box (or network device) along the comm path could take over the session. This reduces it down to the attacker having to crack crypto, or keylog the token, then hijack the session. (One very good reason for good AV and personal firewalls.) In the case of RSA securID there were some attacks on the underlying algorithm used to generate codes.

Michael