Programming Praxis

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