> >Does Microchip publish the specs to the system?  If not, I'd be
> >somewhat
> >leery of it.  One of the reasons DES, RSA, IDEAcrypt, etc. command so
> >much
> >respect is that knowlege of the algorithm is insufficient to break it.
> > By
> >contrast, many proprietary encryption schemes may be easily broken
> >once
> >the algorithm has been discovered.
>
> The alogrithms are secret.  The system designer obviously has to know
> them to implement a receiver.  The pdfs hint that a license fee and
> nondisclosure agreement are required.  This may be more due to patent and
> license stuff than concerns over security.

Perhaps.  But anyone considering security should consider two things:

[1] Any method whose "security" relies upon secrecy of any widely-spread
element (e.g. the algorithm or a secret family key) is insecure.

[2] The greater the reward for cracking something, the sooner it will be
done (witness the cracking efforts on the 16C84).  Since having a family
key would allow one to build an "instant-repeater" box for the Keeloq
system fairly easily, the reward for cracking it would be great.

Unfortunately, the Keeloq system fails on these grounds.  I suspect that
if probably fails on a third as well, though this would probably be a bit
tricky to use advantageously: since the 32-bit section includes both the
counter and the encryption stuff, there are 32,768 semi-valid keys (I
would hope the system, when accepting keys outside of the 16-key forward
window, would look for two *consecutive* keys--else things are *really*
easy).  While the chip probably does not give any external indication that
such a key has been received, its current-draw pattern probably changes
when that happens.

My procedure, then, would be this:

[1] Buy a transmitter/receiver pair from a [targetted device] and build a
    transmitting-style device (data format must match, though encryption
    need not).  Teach the receiver the transmitter's code.

[2] When the receiver is idle, stick a current probe on its supply and
    observe the trace.  Also observe the trace after the receipt of an
    incorrect code and after receipt of a forward-sequenced (outside the
    16-code window) code.  There will probably be a difference where the
    receiver performs different logic.  [If Keeloq/Microchip made efforts
    to stymie this method, this won't yield anything useful.  But if they
    took no such measures this may let you recognize when a receiver has
    received a seemingly-valid code whose sequence number was early.

[3] Once the method of finding partial hits has been established, train a
    receiver (or a bunch of them) on the intended victim's transmission.
    Then feed the receiver(s) random codes (always use the same envelope,
    just vary the 32-bit encrypted part) until you score a "hit".  This
    should only take about 2^17 attempts on average.  If you have multiple
    receivers working on this, it should not take long.

[4] Once you've found a partial hit, keep repeating that code followed by
    random follow-on codes.  This should take about 2^17 more attempts; as
    before you may have multiple receivers working on it to speed things
    up.

[5] If each code attempt takes 0.1 second for step [3] and 0.2 seconds for
    step [4], then one receiver can break the code in half a day.  Using
    two or more would speed things up proportionally.

While step [2] is a bit speculative, I suspect it probably wouldn't be
hard to find a 'partial-hit' detection method.  If such a method can be
found, everything else in the system will be for naught; it can be broken
even without any access to confidential materials.

> The KEELOQ encoder chips use a 64-bit key to encrypt a 32 bit message (16
> bit counter, 2 overflow bits, 10 bit constant, and a 4 bit code for which
> user button(s) were pressed) into a 32 bit encrypted part.  The 10-bit
> constant need not be related to the serial number but it is suggested to.
>  Then the 28-bit constant serial number and the button code are
> transmitted in the clear (or optionally encrypted with a seperate 16-bit
> key using a different secret algorithm).  No error check bits are
> transmitted, though the button code is sent twice and the rest of the
> transmission is a strong check for validity.

In other words, once you've captured the envelope, there are 32768
possible partial-valid messages.  If the chip is proof against current
snooping, that might not be a problem (i.e. if there's no way of telling
when the chip has received a partial-valid message).  Otherwise, it's
exceptionally weak.

> All the paramters in the KEELOQ encoders are stored in EEPROM (all except
> the counter and overflow bits are constant), so a wide variety of
> different schemes of managing the keys can be implemented.  There is
> hardware protection against reading any part of the EEPROM out; a full
> erase must be performed upon entering the program/verify mode.

Does hardware confirm that the erase actually happened?  On some devices,
it's possible to drop the supply voltage during a supposed erase cycle and
prevent the erasure from actually occuring.

> The suggested method of key management (implemented by the receiver chip
> that Microchip sells) seems rather insecure.  When the transmitter is set
> up in the factory (field programming of transmitters is possible but not
> part of the standard method), it's 64-bit key is formed by hashing a
> 64-bit "manufacturer key" and a 28 bit serial number into a working
> 64-bit "secret key" (using yet another secret algorithm).  In order to
> learn new transmitters, the receiver needs a copy of the manufacturer key
> and this to me seems the weak link in the whole system.  To "learn" a new
> transmitter, the receiver gets the serial munber, then generates the
> corresponding secret key from the manufacturer key.  Thus any transmitter
> from the same manufacturer can be used to replace a lost or broken one by
> pressing the "learn" button on the receiver and transmiting.

The approach I offered had this same ability.  But making it so the
receiver can get the transmitter's key (not necessary in my approach) with
a normal transmission opens up the system to a variety of attacks.

> But, once the manufacturer key is known by a cracker (we will assume that
> crackers can find out the algorithms by reverse-engineering the receiver
> or asking Microchip politely), any transmitter using that key scheme may
> be easily "cloned" by decoding one transmission from it!  Even just
> knowing the serial number, there is a 1 in 2 chance that an arbitrary
> choice of the sequence number will be accepted.  The 16-bit "envelope
> key", if used, seems to offer a little more security but not much.  If
> the only unknown is the envelope key, it could be cracked in a few
> minutes by exhaustive searching.

This is another problem; if current snooping isn't possible, this may be
the next weakest point.

> Without the algorithms being published, the KEELOQ encoders are about
> useless for casual hacking (even if one also buys a decoder, which
> appears to be a CR84, the key generation scheme must be known to set up
> the transmitters), though the concept could be put into general-purpose
> PICs using different algorithms.

Personally, I'm disappointed that the algorithms aren't published.  A chip
with published algorithms and hardware to assist in their execution would
probably sell pretty decently even if competitors tried to implement their
own software versions (hardware competitors could be blocked by the patent
office).

Oh well, if anyone has a decent version of DES for the PIC (or a 40-bit
key variant for exportability) I could probably make a Keeloq-style system
which was both public and quantifiably secure.  Alternatively, if
Microchip wanted to make Keeloq more secure (from what I've read of how it
works) it would be possible to make the transmitter only send the full
serial number when the transmit button was held for, e.g., five seconds.
This would block the "mfr #" cloning technique though it wouldn't improve
the code length.