Rolling codes and vehicle locks

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
I'm puzzled. I thought the whole point behind rolling-code keyless
entry devices was that a single capture won't reveal the current state
of the engine in the transmitter.

Yet, the other day I had occasion to program a new remote to my wife's
car - or to be accurate, to program the car to recognize the remote -
and I find that the programming mode involves a "secret" sequence to
get the car into a listening mode, and then a single button press on
each remote to be used with that vehicle.

I can't identify the microcontroller - it's an unmarked 8-pin part -
but an older version of the same series remote control has two parts
(both Microchip): a 24AA01I/SN 128x8 EEPROM, and an 18-pin SOIC marked
"150318-1 R54A04IS0001," date code 9751CAN, which I guess is a
PIC16CR54.

Is it possible this type of remote just transmits a static serial
number along with the button code? I thought all reasonably modern
vehicles used rolling-code systems (this is a '98 model year).

Re: 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



Re: Rolling codes and vehicle locks
Quoted text here. Click to load it

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

Re: Rolling codes and vehicle locks
Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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?).


Re: Rolling codes and vehicle locks

Quoted text here. Click to load it

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




Re: Rolling codes and vehicle locks

Quoted text here. Click to load it

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.


Re: Rolling codes and vehicle locks

Quoted text here. Click to load it
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




Re: Rolling codes and vehicle locks
Quoted text here. Click to load it


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.

<Far-fetched option>
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.
http://www.schneier.com

Re: Rolling codes and vehicle locks

Quoted text here. Click to load it

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.)

Re: Rolling codes and vehicle locks
Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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

Re: Rolling codes and vehicle locks
Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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

Re: Rolling codes and vehicle locks
On 19 Feb 2004 06:05:05 -0800, snipped-for-privacy@larwe.com (Lewin A.R.W. Edwards)

Quoted text here. Click to load it

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.)

Re: Rolling codes and vehicle locks
Hi,

Quoted text here. Click to load it

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

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


Re: Rolling codes and vehicle locks

Quoted text here. Click to load it

  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


Re: Rolling codes and vehicle locks

Quoted text here. Click to load it

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! :)


Re: Rolling codes and vehicle locks
Quoted text here. Click to load it

  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



Site Timeline