# Re: Rolling Code Generation? - Page 2

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

Translate This Thread From English to

•  Subject
• Author
• Posted on
Re: Rolling Code Generation?

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

Re: Rolling Code Generation?

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

Re: Rolling Code Generation?

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?

--

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?

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

Re: Rolling Code Generation?

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

--

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?

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

Have a look at TEA.  I like it because it's tiny, simple, fast, and in C.

Ralph

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