Rolling Code Generation?
Michael Hofmann
and would like to employ rolling code for authentication. Unfortunately
I wasn't able to find in-depth information about rollcode generation (or
code hopping, as Microchip names it)on the web. The relevant Microchip
appnote is only available under a license agreement. My code will
however most likely be written for the ST7 controller.
I'd be grateful for links to flow charts or code snippets or even
mathematical papers on the subject.
Since the security demands are not as stringent as in e.g. the
automotive sector, I would also consider other approaches providing a
lesser amount of security.
TIA,
Michael
Craig Rodgers
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
"Michael Hofmann" <west...@gmx.net> wrote in message
news:3EFC004C...@gmx.net...
Robert Scott
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.)
Michael Hofmann
> On Fri, 27 Jun 2003 10:29:00 +0200, Michael Hofmann
> <west...@gmx.net> wrote:
>
>>I have to design an RF remote control for (low) security applications
>>and would like to employ rolling code for authentication.
>
Fixcode only IMHO is too easy to compromise. I'd like to employ at least
some sort of alternating 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.
>
> One of the practical problems that any rolling code implementation
> needs to address is failure of syncronization.
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.
> If you still want to implement a rolling code, then I suggest you
> forget about the Microchip algorithm and use something like Skipjack.
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
Tom Woodrow
Start from here .. http://www.crowcroft.net/kitsrus/k180.pdf the follow
the links.
Good Luck
Tom Woodrow
www.dacworks.com
rickman
>
> 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.
This has to be limited to stop the most obvious mode of attack,
recording the transmission and replaying it. I belive the rolling code
will only synchronize to the future. All past codes are blocked from
being reused. So the receiver has to remember where it started. At any
point it will only resync to a code that is ahead in the sequence and
will not sync to a code that is between the start point and the last
valid code received.
> 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.)
Actually, nearly any scrambling can be used for a "low security"
method. One way is to use a non linear code like LFSR (linear feedback
shift register) or grey code. Although these can be recorded and
"decrypted", that is a much larger effort than just recording one event
and playing it back.
--
Rick "rickman" Collins
rick.c...@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
Robert Scott
wrote:
>Actually, nearly any scrambling can be used for a "low security"
>method. One way is to use a non linear code like LFSR (linear feedback
>shift register) or grey code. Although these can be recorded and
>"decrypted", that is a much larger effort than just recording one event
>and playing it back.
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.
rickman
>
> On Fri, 27 Jun 2003 11:56:18 -0400, rickman <spamgo...@yahoo.com>
> wrote:
>
> >Actually, nearly any scrambling can be used for a "low security"
> >method. One way is to use a non linear code like LFSR (linear feedback
> >shift register) or grey code. Although these can be recorded and
> >"decrypted", that is a much larger effort than just recording one event
> >and playing it back.
>
> 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.
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...
Ralph Mason
news:3EFC958F...@yahoo.com...
Only 16 bits, just use brute force.
Ralph
rickman
Please show me... ;)
onestone
some time delay between succesive code attempts, and definitely after 2
or 3 failed sequences most will shut down for a period.
Al
Robert Scott
wrote:
>
>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
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.
>
>But to crack a code, the first thing you have to do is figure out what
>code it is...
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.
rickman
I am not trying to say an LFSR rolling code is terribly robust. My
point is that it is a *lot* better than a fixed code that can just be
recorded and retransmitted. Someone said an LFSR is easy to crack with
20 samples and I have provided 20 samples. So far no one in this group
has offered to try. So clearly it is not all that easy. I am even
telling you that it is an LFSR, and no one has tried or at least they
have not succeeded.
I have worked places that make tools to facilitate this sort of
analysis. A receiver can be bought for $1000 or less, but the tools go
for $10K the last time I checked. And you likely would not get a copy
unless the federal government approved.
That is my only point. If you are looking for a level of security that
is significantly better than the old style, fixed code garage door
opener, then an LFSR rolling code will do the trick.
BTW, even if you use encryption, you should use something other than an
incrementing counter to drive the encryption. If you use a simple
counting pattern, you leave the code open to attack from having known
plaintext.
Robert Scott
wrote:
>
>I am not trying to say an LFSR rolling code is terribly robust. My
>point is that it is a *lot* better than a fixed code that can just be
>recorded and retransmitted. Someone said an LFSR is easy to crack with
>20 samples and I have provided 20 samples. So far no one in this group
>has offered to try. So clearly it is not all that easy. I am even
>telling you that it is an LFSR, and no one has tried or at least they
>have not succeeded.
>
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.
Philip Koopman
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
Michael Hofmann <west...@gmx.net> wrote:
Phil Koopman -- koo...@cmu.edu -- http://www.ece.cmu.edu/~koopman
rickman
an LFSR is in any way secure in a true sense. All I am saying is that
an LFSR rolling code is one level better than a fixed code. Recording
and playing back a fixed code only requires a bit of simple hardware.
To get past *any* rolling code would require that you capture a number
of samples that might well require a number of days and then analysis.
Clearly this is a level of effort far more than a simple redcording of
one useage.
I am still waiting for someone to crack the code I posted. Obviously it
is a level of effort more than trivial.
--
jetmarc
> and would like to employ rolling code for authentication.
The easiest, yet secure way is the following:
1. Choose bit width for a counter, so that it will never repeat throughout
the lifetime of the product. If in doubt, choose 64 bits.
2. Choose secure(-enough) block cipher, with blocksize == counter width.
RC5 is good in that it's fast and requires only very little code size,
however it is not be free of patent claims.
3. Choose microcontroller with non-volatile memory (eg EEPROM or SRAM
with Lithium battery) for counter value storage. Initialize both
sender and receiver counter to 0.
4. When sending a code, the sender increments its non-volatile counter
and encrypts it using the block cipher. The result is sent over RF.
5. When receiving a code, the receiver decrypts the code and compares it
with its own non-volatile counter memory. If the received value is
LOWER OR SAME than the memory, it is bad (replay attack). If the
received value is SLIGHTLY HIGHER, the is accepted (and stored
into the non-volatile memory). If the received value is A LOT HIGHER,
it is rejected.
To differentiate between "slightly higher" and "a lot higher", you
can introduce a parameter called WINDOW SIZE. If in doubt, set it
to 1000, meaning that the received counter may be up to 1000 increments
higher. When the user of the token presses the button up to 1000 times
(offline), the token still works. When he presses it more often in
a row, outside of the receiver reception range, the receiver must be
synchronized.
6. Provide a synchronize button on the receiver, effectively receiving
and storing a counter value into its non-volatile memory without prior
verification.
Marc
jetmarc
> synched. This isn't strictly true (see the patents for a "trick" to
> providing a secure resynch capability).
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
Robert Scott
wrote:
>Someone
[..I..]
>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).
The best I can imagine would eliminate the need for non-volatile
memory in the transmitter, but raise the requirement for non-volatile
memory in the receiver. The transmitter could use a random number
generator instead of a non-volatile state counter. The receiver could
keep a complete log of all used codes, and reject all repeats. If
each code is a 32-bit number, and if the system is used twice a day
for ten years (a reasonable lifetime for a garage door opener), then
the receiver will have to store 7300 32-bit numbers, or 29,300 bytes.
That's a lot of NV memory to put in a receiver just to avoid putting
any NV memory in the transmitter. (If that is what is in the patent,
and it took me just 3 minutes to think of it, then our patent system
is out of control.)
Philip Koopman
>
>The best I can imagine would eliminate the need for non-volatile
>memory in the transmitter, but raise the requirement for non-volatile
>memory in the receiver. The transmitter could use a random number
>generator instead of a non-volatile state counter. The receiver could
>keep a complete log of all used codes, and reject all repeats. If
>each code is a 32-bit number, and if the system is used twice a day
>for ten years (a reasonable lifetime for a garage door opener), then
>the receiver will have to store 7300 32-bit numbers, or 29,300 bytes.
>That's a lot of NV memory to put in a receiver just to avoid putting
>any NV memory in the transmitter. (If that is what is in the patent,
>and it took me just 3 minutes to think of it, then our patent system
>is out of control.)
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.
Philip Koopman
>To get past *any* rolling code would require that you capture a number
>of samples that might well require a number of days and then analysis.
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.)
rickman
>
> rickman <spamgo...@yahoo.com> wrote:
>
> >To get past *any* rolling code would require that you capture a number
> >of samples that might well require a number of days and then analysis.
>
> 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.)
You need to read back a little further. The point I am trying to make
(and I am not sure if I have made it or not) is that adding a rolling
LFSR code is a significant improvement over a fixed code. I am not
saying it is hard to break, just that it is a lot harder than a fixed
code.
My point about the capture is that such a system might only be used once
a day. Then you have to repeat the capture over several days rather
than just one time as with a fixed code. That alone is a significant
increase in effort before anyone trys to actually unravel the code.
I am still not convinced a "brute force" attack is so easy. I am also
not sure what you mean by it. Are you saying you just try all the
possible codes until you hit one that works? If the code is sent out
(or not ignored) once per second then it will be some 18 hours before
you cover all the codes. Assuming the receiver does not detect such an
event and shut down, this is still a much higher level of effort
required than the fixed code.
Robert Scott
wrote:
>Robert Scott wrote:
>
>>
>>The best I can imagine would eliminate the need for non-volatile
>>memory in the transmitter, but raise the requirement for non-volatile
>>memory in the receiver. The transmitter could use a random number
>>generator instead of a non-volatile state counter. The receiver could
>>keep a complete log of all used codes, and reject all repeats. If
>>each code is a 32-bit number, and if the system is used twice a day
>>for ten years (a reasonable lifetime for a garage door opener), then
>>the receiver will have to store 7300 32-bit numbers, or 29,300 bytes.
>>That's a lot of NV memory to put in a receiver just to avoid putting
>>any NV memory in the transmitter. (If that is what is in the patent,
>>and it took me just 3 minutes to think of it, then our patent system
>>is out of control.)
>
>You only have to keep the last few, and you don't have to keep all the
>bits of the number.
If you do not keep a record of all previous transmissions in the
receiver then an attacker could simply replay a captured transmission
that was a few months old, and the receiver would have no basis on
which it could be rejected. Of course, that requires some long-range
planning on the part of the attacker, but when you are stealing luxury
cars, it is worth waiting a while. Once the pipeline (of captured
transmissions) is full, you don't even notice the wait.
>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.
I include battery-backed RAM as a type of NV memory, so I was already
considering that possibility. I still think 29K of RAM is not an
insignificant amount.
>So you thought of a way, but in 3
>minutes it wasn't a practical way.
Yes, I agree. But storing a hash of the transmission history and
storing only recent transmissions is not practical either.
>...And since it was a
>very pressing problem worth big bucks, if it were "obvious" someone
>would have thought of it.
I don't see how doing away with any persistent state memory saves any
money. You have to have some RAM in the FOB. It costs next to
nothing to keep that RAM alive with the FOB battery (as opposed to
letting the RAM die every time the user takes his finger off the
button). So you might as well use a persistent counter in the FOB.
Robert Scott
wrote:
>
>I am still not convinced a "brute force" attack is so easy. I am also
>not sure what you mean by it. Are you saying you just try all the
>possible codes until you hit one that works?
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.
jetmarc
So, are you saying that this patent "gets rid of NV memory" by
storing the data in a "battery-backed RAM" instead?
In my understanding, NV (non-volatile) memory is not a certain type
or brand of memory. Other than "Flash", "battery-backed" or "ferro-
magnetic" (which clearly makes are reference to the underlying
technology), "nv memory" is just memory that doesn't loose its data
during normal operation states of the device.
Marc
James Horn
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
James Horn
byte. You end up with a shift-left LFSR implimentation if I'm guessing
right.
rickman
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.
Rafael Deliano
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
rickman
>
> Plain LFSR are insecure.
Dude, you are going way off track here. No one ever suggested that an
LFSR is secure. The only point is that it is harder to defeat than a
fixed pattern with no code. It is always a matter of how much effort do
you want to spend to require the hacker to spend more effort?
Robert Scott
wrote:
>Rafael Deliano wrote:
>>
>> Plain LFSR are insecure.
>
>Dude, you are going way off track here. No one ever suggested that an
>LFSR is secure. The only point is that it is harder to defeat than a
>fixed pattern with no code.
..and for just a tiny bit more effort on the part of the designer to
move from an LFSR to a real encryption algorithm, you can raise the
difficultly level for the attacker to the point of making it almost
impossible to crack. That is why is makes no sense to design a simple
LFSR into a rolling code device.
rickman
>
> On Thu, 03 Jul 2003 14:06:32 -0400, rickman <spamgo...@yahoo.com>
> wrote:
>
> >Rafael Deliano wrote:
> >>
> >> Plain LFSR are insecure.
> >
> >Dude, you are going way off track here. No one ever suggested that an
> >LFSR is secure. The only point is that it is harder to defeat than a
> >fixed pattern with no code.
>
> ..and for just a tiny bit more effort on the part of the designer to
> move from an LFSR to a real encryption algorithm, you can raise the
> difficultly level for the attacker to the point of making it almost
> impossible to crack. That is why is makes no sense to design a simple
> LFSR into a rolling code device.
>
> -Robert Scott
> Ypsilanti, Michigan
I see your point, but I don't agree that it is a "tiny" extra effort. I
can implement an LFSR in my sleep and there are even free programs
available to generate the taps and HDL (which is easy to change into C)
for any LFSR you wish. So the transmitter could easily be implemented
in hardware without an MCU. I expect I could do the entire design in an
afternoon.
But then you may have experience with a "real encryption" algorithm that
I don't. So to each his own. :)
Philip Koopman
>So, are you saying that this patent "gets rid of NV memory" by
>storing the data in a "battery-backed RAM" instead?
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).
rickman
>
> jet...@hotmail.com (jetmarc) wrote:
>
> >So, are you saying that this patent "gets rid of NV memory" by
> >storing the data in a "battery-backed RAM" instead?
>
> Not quite. The transmitter has RAM and is expected to lose its memory
> once in a while (thus the need for resync).
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?
> 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 -- koo...@cmu.edu -- http://www.ece.cmu.edu/~koopman
--
jetmarc
> each time? How could it work with any real security in that case?
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
Ralph Mason
> Robert Scott wrote:
>
> I see your point, but I don't agree that it is a "tiny" extra effort. I
> can implement an LFSR in my sleep and there are even free programs
> available to generate the taps and HDL (which is easy to change into C)
> for any LFSR you wish. So the transmitter could easily be implemented
> in hardware without an MCU. I expect I could do the entire design in an
> afternoon.
When you have a hammer, everything tends to look like a nail.
I bowed out of this one a while back. But a simple rolling counter, with a
encryption algorithm can run on a tiny MCU, they generally have a little bit
of EE in there also to keep where it's up to.
All you need is a 'sync' phase between transmitter and receiver so they can
share encryption keys and current counter value and your done. It's really
very simple, and very secure.
As has been said many time here before the receiver gets the encryped data,
and starts rolling forard it's counter looking for a match (up to say 1000
counts). If it finds one, it's saved counter is updated to the found value
and Aladins treasure is revealed.
>
> But then you may have experience with a "real encryption" algorithm that
> I don't. So to each his own. :)
Have a look at TEA. I like it because it's tiny, simple, fast, and in C.
Ralph