How does a rolling code work?

I have general questions regarding rolling codes. Basically there is a sender and a receiver. Both have a sequence generator. The receiver checks if the received sequence matches the newly generated. An example used is KeeLoq.

Assuming a car opener (sender) and a car (receiver):

• What happens if the sender is at another point in the sequence? Think of that the key is pressed while out of range to the car.
• How does they sync the point of the sequence?
• Is there any prevention to detect replay attacks? How are they implemented?
-
The whole point is to prevent replay attacks. Otherwise you wouldn't bother with rolling the code and you wouldn't need to deal with the issues introduced by mismatch between sender and receiver. –  qris Jul 24 '14 at 12:56

What happens if the sender is at another point in the sequence? ... the key is pressed while out of range to the car.

In a rolling code (code hopping) system, the keyfob transmitter maintains a synchronization counter C, incremented every time a button is pushed. The car receiver stores the most recent validated synchronization counter it has received N.

When a rolling code receiver gets a message with a keyfob serial number that seems to match one of the authorized keyfobs in its internal memory, it extracts the keyfob's synchronization number C from the message and compares it to the most recent validated synchronization number N.

In the normal case:

• C in the rolling window of acceptance -- C is more than but within "a few" codes K of the last validated transmission ( 0 < C-N < K+1 ).

When the counter C in the message is in the window of acceptance, then the car accepts that message as an authentic message, the car overwrites N with the latest value C, and the car unlocks the doors or does whatever else the message says to do.

(As long as you hold down the button, the keyfob will repeatedly transmit bit-for-bit the same message over and over several times a second. It isn't until you let up the button and press it down again that it transmits a message with the next sequential counter number).

So it is possible that the sender will get out of range of the k accepteded codes?

Yes. The AVR411 receiver defaults to WINDOW_SIZE = 100. So with a typical AVR411 system, if the car doesn't hear 100 consecutive button-presses, then the car will ignore the keyfob when it finally gets back in range.

With a typical KeeLoq system, if the car doesn't hear 16 consecutive button-presses, then the car will not unlock the doors on the first button-press of the keyfob when it finally gets back in range. However, if the car then hears 2 consecutive button-presses within the resynchronization window ( K < C-N < Resynchonization_Window ), typically over a thousand button-presses, the car will resynchronize and unlock the doors. With a typical HCS301 system, if the car doesn't hear a few thousand consecutive button-presses, then the car will ignore the keyfob when it finally gets back in range.

How does they sync the point of the sequence? ... How are they implemented?

Before the keyfob can be used, the car must "learn" the keyfob. Typically holding down the "learn button" ("learn switch") for 10 seconds erases the receiver's memory of every keyfob; then letting up on that button makes the receiver go into "learn mode". Typically, pressing both the lock and the unlock button simultaneously on the keyfob makes the keyfob transmit its unique secret key to the receiver. The receiver -- in learn mode -- memorizes the keyfob serial number(s) it hears as authorized keyfobs, and also memorizes the secret key and the current synchronization counter N. After everything is quiet for 10 consecutive seconds with no button presses, the receiver times-out of learn mode and goes into normal mode.

After that, that receiver -- in normal mode -- is now synchronized to the keyfobs.

The tiny amount of battery power available to the keyfob, and the fact that the keyfob only transmits -- never receives -- makes it difficult or impossible to use many cryptographic algorithms.

For details on two popular rolling code implementations, see:

-

In a rolling code both the sender and the receiver always move forward in the sequence. If the sender has sent the $n$th code, then it will send the $(n+1)$th next. Contrarily, if the receiver has seen the $n$th code it will only accept the $(n+1)$th code or some later code.

What happens if the sender is at another point in the sequence? Think of that the key is pressed while out of range to the car. How does they sync the point of the sequence?

The receiver will have to skip those intermediate points. One strategy is to scan the next $k$ possible codes and compare. If the received code is in the range $[n+1, n+k]$, then it is accepted.

Is there any prevention to detect replay attacks? How are they implemented?

A replay attack will not work, because the captured codes are no longer within accepted range – and never will be if the sequence period is long enough.

-
So it is possible that the sender will get out of range of the $k$ accepteded codes? And therefor the car would not open anymore...A denial of service attack against environmental pollution ;-) But is there a method on how to prevent those attacks? –  matcauthon Jul 25 '14 at 4:46
@matcauthon, assuming it uses that method of synchronization, then yes, and I think most do. It would be possible to have a different algorithm that sends a sequence counter in addition to the code – then you need cryptographically strong primitives and not just obfuscation. –  otus Jul 25 '14 at 8:04