On Mon, 9 Jun 1997 00:11:53 +0000 John Payson writes: [major deletion] >> (2.3) With 65K of codes, the life span of a Keeloq system is more >> than 20 years for a typical user who use the transmitter 8 >times >> a day to open his/her car doors. So running out of code >> is not a concern. Actually, the actual number of codes >> available in Keeloq might be as high as 120K. > >In some applications, a lifetime limit of 65,536 transmissions might >be >adequate. In some other applications, it would be totally >unacceptable. >In such cases, it may be possible to use a higher "starting-count" >value, >but doubling the value will potentially double the amount of >computation >required to generate codes. In practice, using the computational >efficiency improvement I mentioned (and possibly having the PC >precompute >the 16384th, 32768th, 49152nd, etc. hash values and store them in >"flash" >or EEPROM) would probably make this approach quite workable. > >Note that I think Keeloq was documented as having the codes simply >"wrap >around" after 65,536 uses; if this is the case then it is almost >certainly >not using the "pre-computed hash" method I described; that method will >totally fail once the counter is exhausted (unless the transmitter >signals >the receiver that it needs to change to a new key). > >> (2.4) A key can only be programmed into the Keeloq's EEPROM by >first >> erasing all old data first. So I assume each time you >> program a new key into Keeloq, you would also reset the >> counter. > >I would expect that to be the case. > >> Here's all I know about Keeloq: >> >> * The system is one way. Transmission only goes from the >> transmitter to the receiver. > >Does simplify things, certainly. > >> * Programmed into each transmitter and receiver are a >> manufactorer's code. In addition to that, the transmitter >> also needs a user code which can be programmed using a rather >> expensive programmer. > >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. > >> * The reciver can "learn" a new transmitter by seeing two >> consecutive transmissions. That implies programmed into >> each receiver are the "smarts" to decode any transmitter >> message. So in theory, an employee of Microchip who designed >> the Keeloq system could decode any Keeloq transmission. > >"Decode" in a sense, yes. Determine from two transmissions what the >next >valid transmission should be, not necessarily [if knowlege of the >algorithm is sufficient to allow someone to infer the seed from two >transmissions, the code is woefully insecure]. > >> * Keeloq transmissions are 64-bits in lenght of which 32 bits >> are fixed and the other 32 bits are varied with each >> transmission. > >Not as much as I'd like, but probably not too bad. This indicates >that >the maximum possible length of the key is 64 bits; most likely it's >under >40 and possibly under 32 [#$)#$ ITAR regulations!] 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. 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. 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. 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. 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. > [...] >While I don't have complete specs for any good has functions, one >which >you might consider would be a variation on the Unix password encode >function: > > If h[n] is the n'th hash function, compute h[n+1] by > h[n+1] = DES(DES(DES(0x0001000100010001 * n, h[n]), h[n]), h[n]) > [use the low 40 or 56 bits] > >where DES(x,y) is the result of encrypting text 'x' with key 'y'. >Note >that DES is probably a little slow to compute on the PIC (you *DON'T* >want >to have the PIC compute h[65536] if you can have a PC pre-compute it!) >but >I don't know of anything easier to compute which would not be weaker. > I would doubt the KEELOQs use any sort of sequential scheme, it is probably just a once-thru combinational process like DES(x,y) once where x is the 32-bit message and y the 64-bit key, and then it's likely not nearly as thorough as DES. Bear in mind the the intended applications are not national security level of security. There will always be relatively easy ways to open houses and cars without the proper keys. The KEELOQ is to address consumer fears that electronic break-in could be easier than conventional break-in. But, the fact that a "code grabber" could be built if the manufacturer code were ever comprimised, may place the standard KEELOQ scheme even below the acceptable consumer security level.