Recently the problem of a secure Garage Door opener protocol was raised on the cypherpunks mailing list. Several interesting ideas were suggested. Here are my favorites. Of course one of them is mine.

The problem is for the unit in the car to emit a signal that is received by the unit in the garage. The signal is to cause the door to open. Eavesdroppers may capture signals and replay them. The garage unit must ignore these. Accumulated transmissions from the car unit must not provide sufficient clues on how to produce a signal that will open the door. Provision must be made for legitimate but garbled transmissions. There is no receiver in the car and no transmitter in the garage.

This protocol serves also for electronic car keys that unlock car doors and open trunks.

Here is my solution.

Eric Hughes’ Solution; (Like mine. Crossed mine in the mail; interesting comments)

Matt Blaze’s Protocol and general comments.(Note that a hash function may replace the block cipher.)

I think that Matt had the last word. Now the simplest scheme seems to me to be a slight variation on Matt’s. Each unit has a 100 bit counter. These counters will stay in approximate sync. The car unit increments its counter and transmits its hash. The garage unit copies its counter to ct, and then for a few dozen times does If loop never finds agreement then declare failure and keep old permanent counter.

Keying the two units merely puts the same random 100 bit counter value in each. This is conceptually simpler but may be marginally more complex to actually implement.

I think that this attack exploits the fact that the key holder need not act to enable the open-sesame.