Re: Rolling Code Generation?

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
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


Quoted text here. Click to load it



Re: Rolling Code Generation?
On Fri, 27 Jun 2003 10:29:00 +0200, Michael Hofmann

Quoted text here. Click to load it

For lower security, you could just use a fixed code.  Rolling code
requires that the transmitter and receiver have non-volatile memory to
maintain a state counter.  A fixed code does not require non-volatile
memory, and is therefore easier to implement.

Basically, a rolling code can be made out of any encryption algorithm.
The transmitter encrypts the current state count and sends it.  The
receiver decrypts the count.  If it is in sequence with what was sent
before, or nearly so, it unlocks the door.

One of the practical problems that any rolling code implementation
needs to address is failure of syncronization.  If the transmitter
button is pressed when it is out of range of the receiver, then the
transmitter state counter gets advanced while the receiver does not.
(This is especially a problem when kids play with Daddy's garage door
opener on a cross-country trip.  By the time they get home, the
transmitter and receiver can be out of sync by a large amount.)  In
addition to defining an acceptance window of maybe 16 counts into the
future, the receiver also recogizes two successive transmissions with
sequential counts to resyncronize to practically anywhere.

If you still want to implement a rolling code, then I suggest you
forget about the Microchip algorithm and use something like Skipjack.
It was once part of the Clipper Chip initiative, but has since been
declassified and info is available on the net.  Skipjack is
well-suited to small microcontroller implementations.
-Robert Scott
 Ypsilanti, Michigan
(Reply through newsgroups, not by direct e-mail, as automatic reply address is
fake.)


Re: Rolling Code Generation?
Quoted text here. Click to load it

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

 > Rolling code
Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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





Re: Rolling Code Generation?
Michael,

Start from here .. http://www.crowcroft.net/kitsrus/k180.pdf the follow
the links.

Good Luck
Tom Woodrow
www.dacworks.com


Michael Hofmann wrote:
Quoted text here. Click to load it


Re: Rolling Code Generation?

Quoted text here. Click to load it

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.)


Re: Rolling Code Generation?
Quoted text here. Click to load it

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

snipped-for-privacy@XYarius.com
We've slightly trimmed the long signature. Click to see the full one.
Re: Rolling Code Generation?
Quoted text here. Click to load it

Only 16 bits, just use brute force.

Ralph



Re: Rolling Code Generation?
Quoted text here. Click to load it

Please show me...  ;)

--

Rick "rickman" Collins

snipped-for-privacy@XYarius.com
We've slightly trimmed the long signature. Click to see the full one.
Re: Rolling Code Generation?
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 Mason wrote:
Quoted text here. Click to load it

Re: Rolling Code Generation?

Quoted text here. Click to load it

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.


Quoted text here. Click to load it

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.)


Re: Rolling Code Generation?

Quoted text here. Click to load it

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.)


Re: Rolling Code Generation?
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

Re: Rolling Code Generation?
Quoted text here. Click to load it

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

snipped-for-privacy@XYarius.com
We've slightly trimmed the long signature. Click to see the full one.
Re: Rolling Code Generation?

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
http://www.ece.cmu.edu/~koopman/patents/us005363448.pdf
is probably the main one.  It should have enough detail to be useful.

There are several other relevant patents from about that timeframe.
See:
http://www.ece.cmu.edu/~koopman/personal.html#patent

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



Quoted text here. Click to load it


Phil Koopman -- snipped-for-privacy@cmu.edu -- http://www.ece.cmu.edu/~koopman

Re: Rolling Code Generation?
Quoted text here. Click to load it

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

Re: Rolling Code Generation?

Quoted text here. Click to load it

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 -- http://www.ece.cmu.edu/~koopman

Re: Rolling Code Generation?

Quoted text here. Click to load it

Not quite.  The transmitter has RAM and is expected to lose its memory
once in a while (thus the need for resync).

The car has battery-backed RAM (via the car battery, not a special
battery) and only takes 4 bytes per transmitter (if memory serves), not
umpty-ump Kbytes.  If you only cache resync commands, it takes a long
time for the resync queue to wrap around in the threat scenario included
in the customer requirements document.

I have to switch my attention to other things.  The patents spell it all
out and are probably more accessible to engineers than most (I insisted
they be more in "real" English and less in patentese to the degree the
lawyers would go along with it).



Phil Koopman -- snipped-for-privacy@cmu.edu -- http://www.ece.cmu.edu/~koopman

Re: Rolling Code Generation?
Quoted text here. Click to load it

If the transmitter loses its RAM, won't it restart at the same point
each time?  How could it work with any real security in that case?


Quoted text here. Click to load it

--

Rick "rickman" Collins

snipped-for-privacy@XYarius.com
We've slightly trimmed the long signature. Click to see the full one.
Re: Rolling Code Generation?
Quoted text here. Click to load it

At the first glance, one might answer that a human-operated device
has a good source for true random data.  After a second thought,
though, one must realize that the device is supposed to open the
door even at the first button-press (even after RAM failure), so
actually there's not much random to learn - thus not really lots of
security.

On the other hand, I never got the impression that this rolling code
stuff is high security art.  Most developers, be it big players or
small people, seem to cut corners whereever they see fit.  Many
regard a system resistant to occasional playback attacks already
as "high security".

I think this has a long tradition, even with locks in general.  Many
house frontdoor locks have 5 bits with 3 possible positions each, and
total at only about 250 possible keys.  Many rolling codes can be
defeated easily, because they were designed by the same guys.

Marc

Re: Rolling Code Generation?

Quoted text here. Click to load it

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 -- http://www.ece.cmu.edu/~koopman

Site Timeline