Re: CYPHERPUNKS TO THE RESCUE

[Matt Blaze <mab@research.att.com>]

norm@netcom.com (Norman Hardy) writes:

>At 09:51 1994/07/26 -0400, Russell Nelson wrote:
>>Why not generate a random number, checksum it, and sign it using a
>>public key?  Or is that overkill?
>...
>Seems good. But to thwart replay of the signed message the garage unit must
>never accept the same signed number twice. How about the car unit signing
>successive numbers. The garage unit would remember the last number that it
>accepted and only accept signed numbers larger than that. Garbled
>transmissions would then cause no problems. They would be fixed by yet new
>transmissions, just as with current units.
>

As Eric Hughes points out (a couple of messages after these), you don't
need public-key signatures for this; any secret key cipher or hash function
will do, since the  base and remote trust each other unconditionally
(at least for garage doors; nuclear weapons may be a different story).

Both base and remote need to store a shared key and a counter; the remote 
needs a transmitter and the base needs a receiver.  To authenticate
itself, the remote sends {counter, hash(key,counter)} and then increments
its counter.  The base calculates the hash for the received counter value,
verifies that it matches the received hash value, verifies that the counter
increases the stored counter value, stores the new value,  and opens
the door.  A practical system system also probably include some mechanism
for rekeying and for zeroizing the counters.

There is no need for public key cryptography, two way communication (except
for key setup), synchronized clocks, or extensive storage at either side.

This protocol as described is very simple, almost trivial; given the right
constraints it follows almost directly from the problem.  I mention
it because very small variations and poorly chosen parameters render
it vulnerable to several classic protocol failures.

First, observe that this system has a work factor to break of no more than
the SMALLER of the secret hash key and the size of the hash output.  Clearly,
a single {counter, hash(key,counter)} message contains enough information to
permit an conventional exhaustive search for key.  If the hash space is
too small (say, 16 bits or so), the adversary can select an unused counter
value and probe the receiver with random hash values until the door opens.
Worse, if the bad guy selects a counter value that is much larger than the 
remote's counter value, it has the added bonus of denial-of-service to the
real user.

Also, note that the order of operation on the receiver's part is critical.
If the received counter value is stored BEFORE the hash is received, we
are also vulnerable to denial-of-service (but at least not false
authentication).

Finally, there is the "man in the middle" attack, in which the bad guy
intercepts a message intended for but never received by the base,
records it, and plays it back later (but before the real owner returns
to increment the counter again).  A likely scenario involves pushing the
button twice on return home, but where only the first message is received by
the base. One way to deal with this is to encourage frequent resyncs between
the base and remote; for example, the remote, when in the garage, could send
periodic "null" commands that increment the counters without actually
opening the door.  (Of course, you'd need to make sure that these messages
themselves cannot be used to construct spoofed open-door messages.)  Basing
the counter in part on a real-time clock would also help here, but again,
this complicates the protocol greatly and increases the opportunities for
both denial-of-service (if the clocks get too far out of sync) and false
authentication (if the clocks get reset - say at daylight savings time...)

My point is not that this is a particularly hard problem, only that
even simple cryptographic protocols can have serious bugs.

-matt