> John, > It is quite fascinating indeed. I considered using the Keeloq > chipsets for a keyless entry system I'm building, but back down > because of the high cost of the programmers for those chips. So now > I'm thinking about doing my own secure transmission by encoding the > transmission with a 12C5XX in the transmitter and decoding with > a 16F84 in the receiver. Hmm... I'd think a 16F84 both places would probably be a better choice. You don't want your transmitters to go dead when you switch batteries, after all, and the memory of the 12C5xx is rather limitted. Also, since I've not looked in detail at the Keeloq systems I have no idea what claims their patents make. I do know that the method[2] I described has been published for quite some time in the computer/networking world. > Questions on the two systems you described. > > (1) I should have paid more attention in my networking class > in college. Oh well. > Anyway. What's the relationship between the public key and > the private key?. I suppose the public was generated using > the private key and each transmission would have this public > key attached? As I recall, this would require a two way > communication between the transmitter and the receiver. This > isn't the system that Keeloq uses because it's only a one > way system. The primary notion in a public key system is that of a key-pair. Once a message has been encrypted with one half, it can only be decrypted using the other half. One popular public-key cryptosystem (which will be covered by a somewhat debatable patent until 2001) is called RSA (after the initials of its inventors). It is based upon the observation that if X and Y are integers and X is relatively prime to Y, then X^(Y-1) mod Y == X, [For example, 3^9 mod 10 == 19683 mod 10 == 3] and that (X^Y)^Z = X^(YZ). To produce a key pair, find two prime numbers, p and q, and then find two numbers R and S such that RS = (pq)-1. Note that this is easy to do given p and q, but is [believed to be] intractable given only pq. The public key is then the pair of numbers {pq, R} while the private key is the pair {pq, S}. To run a number X through the public key with result Y, simply compute Y=(X^R) mod pq. To run Y through the public key with result Z, simply compute Z=(Y^S) mod pq. Note that all of the values in these formulae are usually quite large (200 decimal digits minimum; 300 decimal digits preferred) but the exponentiation is tractible given that: x^y mod q == (x mod q)^y and x*y mod q = (x mod q)*(y mod q) and x^(y+z) = x^y * x^z Of course, the maths are still going to be a bit slow, but not impossibly so. > (2.2) How can the receiver decode the transmission without knowing > the seed? Unless the seed is sent with each transmission? > Like the public key in (1) above? The receiver isn't trying to 'decode' the transmission; merely authenticate it. The trick is that if you know the contents of any valid transmission of mine (e.g. my "19th" transmission, with hash value X) you can determine whether a subsequent transmission (e.g. my "23rd" transmission, with hash value Y) is valid by seeing whether it hashes into the earlier one (e.g. if I run the hash function on Y four times I should get X). Note that the receiver doesn't care about the transmitter's seed value; the seed value is only important because it lets the transmitter find a code which will hash to an earlier code it sent. > (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 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 receiver will immediately accept transmission with the > counter value in the range of 16 in respect to the current > counter value. eg. if the current counter value is 10, > then all counter values from 10 through 26 will be accepted > immediately. If a counter value is out of this 16 count > range, then two consecutive counter value transmissions are > needed to sync up the receiver. eg. if the current counter > value is 10 and the transmitter transmits two consecutive > counts of 20 and 21, then the transmission will be > accepted and the receiver will sync to the new value of 22. > This was done to solve the problem of junior plyaing Star > Wars with daddy's remote. This is probably a good approach, especially if the message is only 32 bits and has no other CRC/validation information. Since it would be *very bad* for the receiver to falsely register as valid a message that was, in fact, not (esp. if the hash function isn't 1:1--it would be possible though highly unlikely for receipt of a bogus message to make the receiver expect a signal the transmitter could never, in fact, generate. > So I think the Keeloq system encripts the user code with the > manufacturer's code built into each chip and then the encripted > code, along with the counter, are ran through a hash function like > John suggested. Anyone can suggest a good hash function for this > purpose? A good hash function would be one that would generate > each successive outcomes (the next counter value) with each bit > having a 50% probability of not being equal to the same bit in the > previous outcome. There are a number of good hash functions in the mathematical and computer science literature. I do *not*, off hand, remember any in sufficient detail to implement them and would not presume that any which I could invent would be even remotely strong against cryptographic attack. Note that your requirement (the 50% probability one) is necessary to a good cryptographic hash, but is not at all sufficient. Many popular hash functions (such as CRC) pass your 50% test (as well as more stringent statistcal tests) with flying colors and yet are woefully inadequate for cryptography. 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.