Rolling Code

May 16, 2014

Since our interest is exploring the rolling code protocol and not implementing an actual system, we will use simple algorithms for encryption and random number generation. For encryption, we will XOR with a single, fixed 32-bit integer. For random numbers, we will use a mixed linear congruential generator a x + c (mod m).

We begin with the functions that implement the fobs, because they are simpler. When they are manufactured, the fobs have an id number, crypto key, and random-number parameters set once for all time. For ease of key maintenance, most manufacturers only change the parameters once per model year; our example is for 2008 Ford cars:

(define fob1
  (let ( ; permanent read-only memory
         (id 111) (k #36rFORD08)
         (a 69069) (c 1234567) (m 4294967296))
    (let ( ; non-volatile read/write memory
           (seed (modulo (* id k) m)))
      (define (encrypt x) (bitwise-xor x k))
      (define (next s) (modulo (+ (* a s) c) m))
      (lambda (signal)
        (set! seed (next seed))
        (if signal (auto id seed signal) 'DENY)))))

(define fob2
  (let ( ; permanent read-only memory
         (id 222) (k #36rFORD08)
         (a 69069) (c 1234567) (m 4294967296))
    (let ( ; non-volatile read/write memory
           (seed (modulo (* id k) m)))
      (define (encrypt x) (bitwise-xor x k))
      (define (next s) (modulo (+ (* a s) c) m))
      (lambda (signal)
        (set! seed (next seed))
        (if signal (auto id seed signal) 'DENY)))))

To simulate sending a signal, say something like (fob1 'LOCK) or (fob2 'UNLOCK). To simulate an out-of-range keypress, say (fob1 #f) or (fob2 #f).

The receiver is a little bit more complicated. It must save the same crypto and random-number parameters as the fobs, and also the id, seed, and previous seed for each fob to which it is paired. And it must run in two modes: programming mode, when it is paired to one or more fobs, and operating mode, when it responds to signals:

(define receiver
  (let ( ; permanent read-only memory
         (k #36rFORD08)
         (a 69069) (c 1234567) (m 4294967296))
    (let ( ; non-volatile read/write memory
           (len 0) (ids (vector))
           (seeds (vector)) (prevs (vector)))
      (define (decrypt x) (bitwise-xor x k))
      (define (next s) (modulo (+ (* a s) c) m))
      (define (ok s z)
        (let loop ((i 256) (s (next s)))
          (cond ((zero? i) #f)
                ((= (vector-ref seeds z) s) s)
                (else (loop (- i 1) (next s))))))
      (define (which id)
        (let loop ((i 0))
          (cond ((= i (vector-length ids)) -1)
                ((= (vector-ref ids i) id) i)
                (else (loop (+ i 1))))))
      (case-lambda
      ((new-ids) ; programming mode
        (set! len (length new-ids))
        (set! ids (list->vector new-ids))
        (set! seeds (make-vector len 0))
        (set! prevs (make-vector len 0)))
      ((id seed signal) ; operating mode
        (let ((z (which id)))
          (cond ((negative? z) 'DENY) ; unrecognized fob
                ((ok seed z) => ; recognized fob and code
                  (lambda (s)
                    (vector-set! seeds z s)
                    (vector-set! prevs z s) signal))
                ((= (next (vector-ref prevs z)) seed)
                  (vector-set! seeds z seed) ; resynchronize
                  (vector-set! prevs z seed) signal)
                (else ; recognized fob, unrecognized code
                  (vector-set! prevs z seed) 'DENY))))))))

Here is a sample sequence of operations, showing the initial programming of the receiver, operation of fob1, resynchronization of fob1 after too many out-of-range keypresses, and operation of fob2:

> (receiver '(111 222))
> (fob1 'LOCK)
DENY
> (fob1 'LOCK)
LOCK
> (do ((i 300 (- i 1))) ((zero? i)) (fob1 #f))
> (fob1 'LOCK)
DENY
> (fob1 'LOCK)
LOCK
> (fob2 'UNLOCK)
DENY
> (fob2 'UNLOCK)
UNLOCK

You can run the program at http://programmingpraxis.codepad.org/es7MLJJL.

By the way, the real-life instructions for reprogramming automobile receivers are hilariously tedious. For my car: 1) Cycle the ignition key between the OFF and RUN positions eight times within ten seconds, ending in the RUN position. 2) Press the LOCK key on each of up to four key fobs within twenty seconds. 3) Turn the ignition key off. 4) Press the LOCK key on each fob twice.

Pages: 1 2

2 Responses to “Rolling Code”

  1. matthew said

    Do key fob systems really reset if they get two successive numbers from the sequence? Sounds like an easy replay attack there.

  2. programmingpraxis said

    Some do. Some don’t. Those that don’t require the whole “turn the key eight times and …” reset sequence whenever they get out of sync.

    Auto manufacturers are walking a fine line here. If they make their system too secure, then too many people will mess things up, and get mad at them, and buy their next car from a different manufacturer. If they make it too weak, too many cars get stolen, and people get mad at them, and buy their next car from a different manufacturer.

    Look at the WikiPedia article for KeeLoq to learn about replay attacks and side-channel attacks, which are a significant problem for the protocol that most auto manufacturers use.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: