Re: Rolling Code Generation?

There is a chapter (Ch 6) on stream ciphers and LFSR's that would be relevant to you in this application in "Handbook of Applied Cryptography" by Menezes, Oorchot & Vanstone. Sorry all the details I have as only have a copy of a couple of sections.. It covers Linear feedback shift registers which would be suitable for generating a rolling code, and covers the issues related with synchronisation of such devices.

Hope it helps

Craig

Fixcode only IMHO is too easy to compromise. I'd like to employ at least some sort of alternating code.

I am familiar with this as I used to be part of a remote keyless entry SW group a few years ago. It's just that I never dealt directly with the encryption algorithms.

Thanks for the pointer. The Skipjack algorithm specification is a bit over my head, I was hoping for a simpler explanation, but it's a start :-)

Michael

Michael,

Start from here ..

the follow the links.

Good Luck Tom Woodrow

Michael Hofmann wrote:

I don't know. It seems that the major investment for an attacker is putting together a receiver and a recording device. Once you have that, it is not much harder to record 20 events than to record one event. And if you suspect they are using a LFSR, it really takes very few events to determine the taps on the LFSR. Someone could explore the possibilities off-line using software at their leisure, then come back days later and break in.

-Robert Scott Ypsilanti, Michigan (Reply through newsgroups, not by direct e-mail, as automatic reply address is fake.)

Ok, you gave me a recorder and I got the following results...

0 216D 1 50CA 2 B085 3 611B 4 D026 5 A14C 6 5180 7 B001 8 6102 9 C014 10 8138 11 1160 12 20C0 13 4081 14 8013 15 0136 16 006C 17 10D8 18 30B1 19 6063

BTW, recording this cost you a bunch of bucks since the code is only used once a day and I had to record it over nearly a month.

I understand your point, but if you are going to get past such an operation, recording the transmission is the first step and will have to be done for *any* of the security methods. It really is not a big deal since the data rates are typically pretty low. If you want, I can sell you some gear... ;)

But to crack a code, the first thing you have to do is figure out what code it is. Even the low tech codes provide a reasonable amount of security since there are so many to choose from. For example, you don't know if the sequence above is an LFSR, or if it is something subtly different. You tell me. And don't forget there may be reception bit errors...

--

Rick "rickman" Collins

rick.collins@XYarius.com
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design      URL http://www.arius.com
4 King Ave                               301-682-7772 Voice
Frederick, MD 21701-3110                 301-682-7666 FAX

Only 16 bits, just use brute force.

Ralph

Please show me... ;)

--

Rick "rickman" Collins

rick.collins@XYarius.com
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design      URL http://www.arius.com
4 King Ave                               301-682-7772 Voice
Frederick, MD 21701-3110                 301-682-7666 FAX

You can't use brute force. Even the most simple systems usually require some time delay between succesive code attempts, and definitely after 2 or 3 failed sequences most will shut down for a period.

Al

Ralph Mas>

You are not seriously questioning the fact that LFSRs are crackable with this few number of samples are you? But I understand your point that unless I know it is an LFSR, I'm not likely to even try to crack it. Certainly for one person making a homemade rolling code scheme, this is adequate security. But as long as you are going to the trouble to make any such system at all, why not use some real encryption? There are encryption algorithms that are not much harder to implement than an LFSR. See Schneier, "Applied Cryptography" for examples.

For a one-of-a-kind homemade system, this is a real problem for the attacker. But if anything is mass-produced, then you have to assume that the bad guys will find out, one way or another, what the code is. They will be able to amortize their initial efforts over many cracked systems.

-Robert Scott Ypsilanti, Michigan (Reply through newsgroups, not by direct e-mail, as automatic reply address is fake.)

Right now the incentive is not high enough for anyone here to bother. I know that 20 samples is enough to crack a 16-bit LFSR, and if I were using it to break into your garage, maybe I would get enough merchandise to make it worthwhile.

-Robert Scott Ypsilanti, Michigan (Reply through newsgroups, not by direct e-mail, as automatic reply address is fake.)

A reasonably complete description of a production rolling code system can be found in US Patents for the UTA/Lear system. This has been deployed in probably millions of production vehicles for several years.

For example: US Patent #5,363,448

is probably the main one. It should have enough detail to be useful.

There are several other relevant patents from about that timeframe. See:

Note that, of course, these patents are still in force and probably Lear would want licensing fees if anyone did something that infringed on the claims. But there is probably a bit to be learned from them just the same.

Those algorithms are significantly more secure than an LFSR. A plain LFSR just isn't secure (and yes, a 16-bit LFSR as mentioned previously is trivially easy to crack, especially since you can just brute force it).

Someone stated that non-volatile memory is required to keep things synched. This isn't strictly true (see the patents for a "trick" to providing a secure resynch capability).

I recommend that you not trust an unpublished algorithm. The one described above is published for scrutiny by anyone who cares to look.

Any challenge that does not include a precise specification of the encryption algorithm is a waste of time. This is well known in the crypto community (last time I checked was in their newsgroup's FAQ). There may be many codes, but if you can count on your algorithm eventually being found out.

Also, be sure you use a secure method for generating keys! Almost everyone gets this wrong in a major way the first time. (More patents on this topic on my web site.)

BTW, if you need primitive polynomials I have those on my web site as well.

Have fun,

-- Phil

Michael Hofmann wrote:

Phil Koopman -- snipped-for-privacy@cmu.edu --

I haven't read the patents you cite. Actually many people says it's a good idea to never read patents at all.

However, I can't think of any "trick" to get rid of the non-volatile memory requirement, as long as the communication is strictly one-way (token -> lock).

Can you please elaborate on this?

Marc

You only have to keep the last few, and you don't have to keep all the bits of the number. And it can be in RAM instead of NV memory in the receiver because if you can compromise the power supply of the vehicle you can likely get access other ways. So you thought of a way, but in 3 minutes it wasn't a practical way.

You miss the point of the patent system. I told you it was possible so you thought of a way. At the time the patent was filed everyone told me it was impossible, so nobody had thought of a way. And since it was a very pressing problem worth big bucks, if it were "obvious" someone would have thought of it. The novelty was deciding it was possible. The inventor was one who recognized a problem and addressed it; invention doesn't mean that nobody else could have addressed it. The best inventions are the simple ones (in retrospect).

Lots of people trash talk our patent system. Most of people who do that don't really understand how it works and what it accomplishes. Of course I can't really say what your state of understanding is, and reasonable people can disagree on this topic.

Phil Koopman -- snipped-for-privacy@cmu.edu --

If it is just an LFSR and you expose all the bits, then you probably only need 2 or 3 samples to narrow the search space enough for a brute force attack to be successful. (This assumes a known algorithm, but that is the only realistic assumption for a mass produced system.)

Phil Koopman -- snipped-for-privacy@cmu.edu --

No, when people say "brute force" they mean off-line analysis, not involving the receiver. If the attacker knows the general design of the encryption algorithm (in your case, the LFSR), but only lacks the key (i.e. the taps in your case), and if the key is short enough, he can run through all the possible keys off-line to find the one that gives a result that is consistent with what was captured off the air.

-Robert Scott Ypsilanti, Michigan (Reply through newsgroups, not by direct e-mail, as automatic reply address is fake.)

Hi, Rick & all -

Your example code sequence appears on cursory inspection to have the bytes swapped and the nybbles swapped within them. The lower 13 bits are used. That's by looking at the first few entries; a simple C program can verify or correct that. Still less obvious than simpler codes, as you say.

Great discussion, folks - I've been learning a lot. Thanks!

Jim Horn, WB9SYN/6

Ooops - a correction to my prior note - just swap the nybbles in each byte. You end up with a shift-left LFSR implimentation if I'm guessing right.

Good job. I figured I would toss it out there and see if anyone felt strongly enought to crack it. I agree that it is not hard to do. My only point is that it is another step beyond just recording a fixed code and the fact that it took several days for anyone to get around to doing it proves my point.

How did you determine this? Did you just look at the movement of the bits from one sample to the next? I expect swapping the bits more randomly would have made this a bit harder, but not a lot. I have seen software that can do a good job of showing patterns in the data like this. Once you see the pattern you can see the extra three bits are doing nothing which gives you the LFSR size. Then it is not hard to get the taps. I expect a formula can be found for finding the taps. Manually you could use something like a Karnaugh map.

--

Rick "rickman" Collins

rick.collins@XYarius.com
Ignore the reply address. To email me use the above address with the XY
removed.

Arius - A Signal Processing Solutions Company
Specializing in DSP and FPGA design      URL http://www.arius.com
4 King Ave                               301-682-7772 Voice
Frederick, MD 21701-3110                 301-682-7666 FAX

If the generator is a 16 bit LFSR and about 20 consecutive samples ( = 16 bit words ) are captured: Only 2048 of the 65535 possible "keys" are m-sequences ( shorter sequences could be used which would give more keys ). Assuming these 2048 have already been tabulated ( not unreasonable nowadays ) then of each of these 65535 states have to counted and checked against the samples. This is simple and could be done on a 16 bit controller in assembler in perhaps 100usec/state.

65535 * 2048 * 100usec = 3,6 hours Its possible that more then one possible key will be found that fits the 20 samples, but if more samples are captured there will be soon only one key left.

More efficient would be the Berlekamp-Massey algorithm known since the late 60ies. To quote from: Proceeedings of the IEEE december 1967 letters "Open Letter to Communication Engineers. It is a common belief among engineers that a pseudo-random sequence, obtained by a feedback shift register, can be used as a key-stream to obtain cryptographic secrecy. Communication engineers are advised that this method is fallacious. ... It is a well known theorem that the shift-register connections can be reconstructed from a knowledge of of 2n-1 successive digits of shiftregister sequences ..."

Plain LFSR are insecure. But stream ciphers based on them are safer and still efficiently implemented. "Published" algorithms that are safe are usually much to complicated for small inexpensive controllers.

MfG JRD