Remote keyless entry systems with rolling code: are transmitters really clonable?

rickman <gnuarm@gmail.com> writes:
>> There's a unique key in each device.
> But the algorithm can be determined.  With a few samples you can
> determine the key.

Looking at the KeeLoq wiki article, this can be done but it's harder
than it sounds.  It could be that the cloneable units are using a weaker
system.  If the things were designed by cryptographers, then finding the
key by eavesdropping would be essentially impossible.  On the other
hand, the attacker can always break into the car by smashing the window.

On Sat, 12 Dec 2015 22:53:37 +0000, Waldek Hebisch wrote:

> To avoid reply attacks you need two way communication

Not necessarily; you can use timestamps. Transmitter and receiver both
have reasonably-accurate clocks (like, "digital watch" accuracy, not
"atomic clock"). The transmitter sends the current time as well as a code
which is derived from the current time and the device's unique key. The
receiver rejects the code if the code doesn't match the timestamp or ID,
or if the timestamp is too far from what it should be, proportional to the
elapsed time since the last accepted code.

Some form of re-synchronisation needs to be performed if either end needs
to be replaced. Multiple transmitters would need the receiver to track
each one separately.

With a strong cipher (or hash), and a key too large for a brute-force
search, even a few million plaintext/ciphertext pairs shouldn't be enough
to derive the key.

> - you need more complicated device (probably processor)
>   instead of simple hardware used for existing systems

This is the real issue.

Strong ciphers (or hashes, or pseduo-random number generators) need
significantly more silicon than a weak pseudo-random number generator
(e.g. LFSR). Accurate timekeeping needs a crystal rather than an RC
oscillator, and backup power to avoid needing to re-synchronise if you
change the transmitter battery or the vehicle has the battery disconnected
during servicing.

Whereas wireless fobs seem to aim for the complexity of a 74-series chip.

And that's the ones used for protecting cars. When it comes to things like
wireless doorbells, you're lucky if it only gets triggered by random EMI
once an hour.

On 12/14/2015 5:33 AM, Nobody wrote:
> On Sat, 12 Dec 2015 22:53:37 +0000, Waldek Hebisch wrote:
>
>> To avoid reply attacks you need two way communication
>
> Not necessarily; you can use timestamps. Transmitter and receiver both
> have reasonably-accurate clocks (like, "digital watch" accuracy, not
> "atomic clock"). The transmitter sends the current time as well as a code
> which is derived from the current time and the device's unique key. The
> receiver rejects the code if the code doesn't match the timestamp or ID,
> or if the timestamp is too far from what it should be, proportional to the
> elapsed time since the last accepted code.
>
> Some form of re-synchronisation needs to be performed if either end needs
> to be replaced. Multiple transmitters would need the receiver to track
> each one separately.
>
> With a strong cipher (or hash), and a key too large for a brute-force
> search, even a few million plaintext/ciphertext pairs shouldn't be enough
> to derive the key.

I don't think anyone is doing that.  I expect it is too costly in some 
regard, power, computation, dollars....


>> - you need more complicated device (probably processor)
>>    instead of simple hardware used for existing systems
>
> This is the real issue.
>
> Strong ciphers (or hashes, or pseduo-random number generators) need
> significantly more silicon than a weak pseudo-random number generator
> (e.g. LFSR). Accurate timekeeping needs a crystal rather than an RC
> oscillator, and backup power to avoid needing to re-synchronise if you
> change the transmitter battery or the vehicle has the battery disconnected
> during servicing.
>
> Whereas wireless fobs seem to aim for the complexity of a 74-series chip.
>
> And that's the ones used for protecting cars. When it comes to things like
> wireless doorbells, you're lucky if it only gets triggered by random EMI
> once an hour.

So build a better doorbell and the world will beat a path to your door?

-- 

Rick

Am 14.12.2015 um 11:33 schrieb Nobody:
> On Sat, 12 Dec 2015 22:53:37 +0000, Waldek Hebisch wrote:

>> To avoid reply attacks you need two way communication

No.

> Not necessarily; you can use timestamps.

No.

Every attacker can make timestamps at least as easily as the keyfob, 
probably better, because he's not bound by having to work for a long 
time on a very limited energy source.  So time doesn't add any safety to 
the system.

Replay attacks are blocked by adding _sequence_ to the mix, not time. 
I.e. the receiver and sender both keep a record of what their previous 
key was.  That key is burnt, and only the next (few) keys are accepted.

The real weak points, however, are transmissions not seen by the 
receiver, and re-synchronization after power loss.

The lock, being (somewhat) stationary, with more power available, may be 
save its state to non-volatile memory on apparently imminent power loss, 
so that can be kept reasonably painless.  Power loss of the keyfob is 
harder.  There has to be some way to re-synchronize the fob after 
exchanging its battery over the air, or by putting the lock into a 
special "learning" mode.

Car keys use a combination of approaches:

* Key presses that the receiver didn't see are tolerated to some extent 
by allowing any of the next N keys in the sequence, at the price of 
throwing some of the cryptographic power away.

* If you waltz further off-sequence (think of kids playing with the 
blinky light on the fob, or some object in your pocket pressing it on 
every step), or after a battery change in the fob, re-synchronization is 
achieved by checking that the receiver sees two or more rolling keys in 
the right order.

* The final back-up solution is that a repair shop can re-synchronize 
any key (including an entirely new one) to the lock by physical access 
from inside the car.  In somewhat current systems this is further 
strengthened by requiring a secured internet link to the manufacturer's 
database servers, which only licensed dealerships get to use. That way 
the true master key never leaves the manufacturer's site(s).

Hans-Bernhard Br&ouml;ker <HBBroeker@t-online.de> writes:
> Every attacker can make timestamps at least as easily as the keyfob...
> So time doesn't add any safety to the system.

The idea is the timestamp is authenticated by a secret key in the fob.
So if the attacker captures an authenticated timestamp, it's only useful
for 30 seconds or whatever, and the authenticated timestamp was
presumably only sent when the car owner was standing in front of the
car.  Alternatively if the attacker gets access to the physical fob in
the owner's absence, they have only 30 seconds to use the code, so they
must be close enough to the car by using the real ones.

> There has to be some way to re-synchronize the fob after exchanging
> its battery over the air, or by putting the lock into a special
> "learning" mode.

How about just clicking the fob after pressing a button inside the car,
or turning the physical key in the lock.  That updates the lock to the
fob's idea of the time.

> * repair shop can re-synchronize any key ... requiring a secured
> internet link to the manufacturer's database servers

This is good if you have to initialize a new fob, but sounds like
overkill if you still have the original fob with the internal secret
key, and only need to resynchronize it after a battery change.

Nobody <nobody@nowhere.invalid> writes:
> Whereas wireless fobs seem to aim for the complexity of a 74-series chip.

When was the last time you saw a 74-series chip?  You can get an MCU
today for what a 7400 used to cost.

Am 14.12.2015 um 19:31 schrieb Paul Rubin:
> Hans-Bernhard Br&ouml;ker <HBBroeker@t-online.de> writes:
>> Every attacker can make timestamps at least as easily as the keyfob...
>> So time doesn't add any safety to the system.
>
> The idea is the timestamp is authenticated by a secret key in the fob.

One could do that, but choosing a timestamp for that job, instead of any 
other pseudo-random data, offers no benefit at all.  The keyfob will 
just continuously burn precious power running its clock, instead of only 
waking up on key-press.  And all that consumption will be for nothing.

Actually, using a timestamp would be a heck of a lot worse than any 
remotely sensible pseudo-random number.  With a rolling code they would 
at least have to observe or guess how often you used the original key 
since they recorded your signal to generate the next one to use for 
their attack.  With a timestamp, all they need is a clock.  It doesn't 
get any easier.

> So if the attacker captures an authenticated timestamp, it's only useful
> for 30 seconds or whatever, and the authenticated timestamp was
> presumably only sent when the car owner was standing in front of the
> car.

And if you do it properly, the captured data is _completely_useless_ to 
him, because the moment it's been received by the lock, it immediately 
becomes invalid for future use.  Not 30 seconds later, but right then 
and there.

>> There has to be some way to re-synchronize the fob after exchanging
>> its battery over the air, or by putting the lock into a special
>> "learning" mode.
>
> How about just clicking the fob after pressing a button inside the car,
> or turning the physical key in the lock.  That updates the lock to the
> fob's idea of the time.

That's one possibility to re-synchronize.

But really, get that "timestamp" idea out of your head.  It makes no 
sense; it offers exactly zero protection value.

>> * repair shop can re-synchronize any key ... requiring a secured
>> internet link to the manufacturer's database servers
>
> This is good if you have to initialize a new fob, but sounds like
> overkill if you still have the original fob with the internal secret
> key, and only need to resynchronize it after a battery change.

That's what the "press it multiple times" intermediate scheme is for, 
which you opted to skip over.

Hans-Bernhard Br&ouml;ker <HBBroeker@t-online.de> writes:
>> The idea is the timestamp is authenticated by a secret key in the fob.
> One could do that, but choosing a timestamp for that job, instead of
> any other pseudo-random data, offers no benefit at all.

I don't understand that.  It's just like TOTP which is used widely:

https://en.wikipedia.org/wiki/Time-based_One-time_Password_Algorithm

> The keyfob will just continuously burn precious power running its
> clock,

In the microamp range, like a digital watch.  The limiting factor is
the battery shelf life as much as the device's power drain.

> With a rolling code they would at least have to observe or guess how
> often you used the original key since they recorded your signal to
> generate the next one to use for their attack.  With a timestamp, all
> they need is a clock.  

In both cases they need the secret key that's inside the fob, and if the
crypto is any good and they can't destructively examine the fob, they
have no way to get that.  They can't generate any new codes without it.

> And if you do it properly, the captured data is _completely_useless_
> to him, because the moment it's been received by the lock, it
> immediately becomes invalid for future use.  Not 30 seconds later, but
> right then and there.

If the lock opening invalidates the code, then you can't use the fob
again for the next 30 seconds.  That might be annoying.  OTOH lowering
the interval to 5 seconds could take care of that.

> But really, get that "timestamp" idea out of your head.  It makes no
> sense; it offers exactly zero protection value.

You keep saying that but you haven't explained why you think it's true.

Hans-Bernhard Br&ouml;ker <HBBroeker@t-online.de> wrote:

> Actually, using a timestamp would be a heck of a lot worse than any 
> remotely sensible pseudo-random number.  With a rolling code they would 
> at least have to observe or guess how often you used the original key 
> since they recorded your signal to generate the next one to use for 
> their attack.  With a timestamp, all they need is a clock.  It doesn't 
> get any easier.

I don't remember where I heard this attack described, but:
- When the user clicks the fob, an attacker records the transmission 
while also blocking reception by the car.
- When the car doesn't react, the user clicks the fob again. The 
attacker also records the second signal.
- The attacker now replays the first signal, activating the lock. He 
still has the second signal with the next code in the sequence banked, 
and can use it to unlock the car.

-a

Nobody <nobody@nowhere.invalid> wrote:
> On Sat, 12 Dec 2015 22:53:37 +0000, Waldek Hebisch wrote:
> 
> > To avoid reply attacks you need two way communication
> 
> Not necessarily; you can use timestamps.

Yes, that also works.

> > - you need more complicated device (probably processor)
> >   instead of simple hardware used for existing systems
> 
> This is the real issue.
> 
> Strong ciphers (or hashes, or pseduo-random number generators) need
> significantly more silicon than a weak pseudo-random number generator
> (e.g. LFSR). Accurate timekeeping needs a crystal rather than an RC
> oscillator, and backup power to avoid needing to re-synchronise if you
> change the transmitter battery or the vehicle has the battery disconnected
> during servicing.
> 
> Whereas wireless fobs seem to aim for the complexity of a 74-series chip.
> 
> And that's the ones used for protecting cars.

Well, IMO there is no excuse for bad security of car keys.  Replacement
keys seem to cost well beyond $50 and decent processor costs 30 cents.
And keys seem to have fancy functions that require processor (and
probably also two way communication)

-- 
                              Waldek Hebisch