Keep rolling, rolling, rolling

In the last post about technologies used in alarms, I discussed the use of spread spectrum. Another really common keyword seen on marketing material is “rolling code”. What is it, why is it used, and what problems are there with it?

Why?

A wireless alarm system might send a signal from a keyfob to the panel to say “disarm the system”. If the content of this packet does not change in any way from time to time, we could simply record this packet and replay it at a later time.

This is commonly called a replay attack. There are alarm systems available that are vulnerable to this attack – the older Yale Wireless Alarm systems (434MHz ones) and Friedland SL series are examples. There are “Universal cloning remotes” on eBay for less than £5 that will clone any alarm using 434MHz OOK signalling. You can also use an Arduino and cheap receiver to listen out for signals and store them for later replay.

It is desirable to have a means of stopping these replay attacks from happening.

There is nothing in the EN50131-5-3 specification that means a grade 2 alarm needs any protection against these attacks. Most newer alarms do however have some protection.

How?

The attack is possible because the signal doesn’t ever change – it is always “disarm the system”.

To protect against a pure replay attack, we just need to add something that changes each time the signal is sent. How about the time? “disarm the system 21:22:32 26/04/2013″

This works. There is now no way for me to record a packet and use it again later.

But a really malicious attacker could work out how to take a packet recorded earlier, modify the time, and replay it.

This is where rolling code comes into play – instead of appending the time, we add a code to the packet. This code changes each time a packet is sent. The receiver and transmitter have agreed how this code will change – generally using a psuedo-random number generator.

The packet now becomes “disarm the system 204389473692″, the next time it will be “disarm the system 937459384322″ and so on.

The sequence of this codes is essentially random to an observer, and the code is long enough that it makes guessing the next one very difficult.

Unlike spread spectrum, this sequence is generally extremely long in small systems.

Keeloq is a proprietary implementation of a rolling code protocol, often used in car keyless entry systems. The rolling code is 32-bit, which essentially means it is impossible for someone to guess the next code.

Keeloq does have weaknesses. The major one is that it is possible to recover the key used to seed the random number generator. Once you have this, it is far easier to guess the next code. It’s still very challenging though.

What issues are there with rolling code?

Again, the devil is in the detail. Rolling code is a sound principal – but it must be implemented correctly.

Predictable codes

The whole thing falls over if someone can guess the sequence of codes you are using. There are a number of ways that this can happen.

If your code is short (say, 8bits), the an attacker has a 1/256 chance of getting the next code correct if he chooses randomly. If your code is long (say, 32 bits), then it is 1/4294967296. Whatever method you are using to guess the codes, you can clearly see that the longer the code, the harder it will be.

A good pseudo-random number generator (PRNG) can be seeded – you give it a key which determines how it will hop. It shouldn’t matter what the algorithm is or if the attacker knows the algorithm, as long as they don’t know the seed, they shouldn’t be able to predict the sequence. Unfortunately, many products either used a fixed seed across all products (this makes protocol design, especially with a one-way radio, much easier) or the algorithm is bad.

How can the algorithm be bad? Say we have a PRNG with this output when seeded with “1”:

7, 3, 4, 1, 3, 6, 1, 3, 2

If I were to seed it with “2”, the output should be completely different:

8, 3, 3, 2, 7, 1, 5, 3, 1

But some systems simply use the seed to skip some of the output i.e. with a seed of “2”:

3, 4, 1, 3, 6, 1, 3, 2, 8

Notice this is just the first sequence shifted along one digit!

If I know the entire sequence, then all I need to do is gather a few packets and I can work out where we are in the sequence. The number of packets I need varies, but with a poor PRNG or short code, it’s not very many!

Worse still, some “rolling code” systems use a code like:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Whilst this might protect against casual replay attacks, it is not hard for an attacker to guess the next number.

Limitations with one-way radios

If your keyfob can transmit but not receive, there is a small problem. Each time it transmits, the code rolls forward. There is no guarantee that the receiver will hear the transmission.

This means that the transmitter’s code can be further ahead in the sequence than the receiver. This needs to be taken account of – what happens if you are idly pressing the disarm button in your pocket whilst waiting for the bus?

Most systems deal with this by checking for a valid code over a “window” of acceptable values. This could, say, be the next 256 codes. This has an interesting effect on guessing. If I have a 16 bit code, there are 65,536 possibilities. If the window was only 1 long, I would have a 1/65,536 chance of randomly guessing the code. If the window is 256 long, we reduce this by a factor of 256 – to 1/256. That’s a big difference.

Message substitution

A very simple rolling code implementation just appends the pseudo-random code onto the message i.e. “disarm the system 878463098273″

There is no link between the message (“disarm the system”) and the code (“878463098273″).

This means we can change the message and use the same code, providing that the receiver hasn’t received the code.

How could this be done? I’ll give one possible attack.

When you press “arm the system” on the keyfob, it will actually send more than one packet, to ensure that the receiver gets the message. We have something like:

arm the system 736474747363

arm the system 093219457437

arm the system 384838738383

arm the system 732878476655

If I am in the position to jam the receiver, but still receive the genuine packet, I can do the following:

1. Record all 4 packets.

2. Immediately replay the first two to arm the alarm so the user does not see an issue:

arm the system 736474747363

arm the system 093219457437

3. Hold onto the last two packets.

4. Change the messages on the second two packets to:

disarm the system 384838738383

disarm the system 732878476655

And bang, we have disarmed the system.

Replay attacks still work

As long as the packet never reaches the receiver, we can still grab a transmission from a keyfob and use it later. This means someone could press the disarm button on your keyfob whilst you are away from the house (say, when you pass your keys to the checkout assistant to scan your loyalty card), and then replay it later.

Conclusion

Rolling code, again, is a good idea, and if implemented well, can protect against a lot of attacks. Many systems do not implement it well though – the above vulnerabilities can be found in real world alarm systems.

A much more robust solution is to use timestamps in the messages and then use encryption and a message authentication code.

If anyone is interested, Atmel have a really good app note on implementing a secure algorithm with one-way radios.

4 thoughts on “Keep rolling, rolling, rolling

  1. Permalink  ⋅ Reply

    occam

    July 2, 2013 at 2:10am

    A rolling code with a time interval based increment will foil record and play attacks because by the time the signal is recorded it is obsolete until the PRN sequence wraps. Encryption of a message containing the rolling code obfuscates the message rendering message field analysis futile as essentially every message will be completely from every other with no visible pattern.

    An encrypted message with a timed interval rolling PRN sequence + any other changing content would be very tough to spoof

    • Permalink  ⋅ Reply

      cybergibbons

      July 2, 2013 at 5:44am

      Indeed, they would, but they just don’t seem to be used.

      Two reasons, I think.

      Accurate timing is hard and expensive. If they can use an internal oscillator and avoid the use of a crystal, that’s great.

      Anything timing based really needs to be able to resynchronise, and these devices frequently use uni-directional radios, making this hard.

Leave a Reply

Your email will not be published. Name and Email fields are required.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">