Two XORed LFSRs

[Cascade Research]

How do you cryptanalyze two XORed LFSRs?

[Peter Pearson]

On Sun, 12 Mar 2017 18:42:31 -0400, Cascade Research <casc...@yahoo.com> wrote:
> How do you cryptanalyze two XORed LFSRs?

Each output bit is simply a linear combination of the initial bits
in the two LFSRs. If the number of output bits that you know is at
least as great as the number of bits in the LFSRs, then you can solve
that many equations in that many unknowns (which typically requires
inverting a matrix of elements of the field GF_2).

If you want a more specific answer, you'll have to ask a more specific
question.

--
To email me, substitute nowhere->runbox, invalid->com.

[Cascade Research]

You mean one equation per one bit of the LFSR? What do those equations look like?

[Peter Pearson]

On Sun, 9 Apr 2017 06:58:09 -0700 (PDT), Cascade Research wrote:
> On Saturday, March 18, 2017 at 12:10:52 AM UTC-4, Peter Pearson wrote:

>> On Sun, 12 Mar 2017 18:42:31 -0400, Cascade Research wrote:
>> > How do you cryptanalyze two XORed LFSRs?
>>
>> Each output bit is simply a linear combination of the initial bits
>> in the two LFSRs. If the number of output bits that you know is at
>> least as great as the number of bits in the LFSRs, then you can solve
>> that many equations in that many unknowns (which typically requires
>> inverting a matrix of elements of the field GF_2).
>>
>> If you want a more specific answer, you'll have to ask a more specific
>> question.

[snip]

>
> You mean one equation per one bit of the LFSR? What do those equations
> look like?

If we designate one particular moment as time t=0, and name the
unknown contents of LFSRs A and B at that moment as a0, a1, ...
and b0, b1, ..., and if we know that a certain number of
LFSR steps later the XORed outputs of A and B give the value z,
then we get an equation of the form

z = ca0 * a0 + ca1 * a1 + . . . + cb0 * b0 + cb1 * b1 + . . .

where the coefficients ca0, cb0, et cetera, can be computed from the
definition of the LFSRs (but not their contents, obviously) and the
number of steps. In these equations, "*" means logical AND and "+"
means XOR, but solving the equations works absolutely the same as what
you learned in high school because "*" and "+" still have all the
properties (commutative, associative, distributive, et cetera) that make
that solution work.

I wrote an article on this that was published in Cryptologia volume 12,
1988.

[Cascade Research]

OK, do you have a URL or PDF?

[Peter Pearson]

Are you kidding? This was 1988; I had to submit the manuscript
on paper.

Take your pick: I can send you the files that I printed on whatever
printer I had in 1988 to generate the manuscript I mailed to Cryptologia
(the files are almost entirely ASCII, with a few escape sequences for
superscripts and subscripts), or you can email me your postal address
and I'll mail you a genuine paper reprint. (Yes, I still have several.)

[William Unruh]

Or he could go to a library and copy it.

Or he could go online and read it there (google)
Mind he might have to pay for it.

[Cascade Research]

How about you scan the paper reprint?

[rsharris....@gmail.com]

On Saturday, March 18, 2017 at 12:10:52 AM UTC-4, Peter Pearson wrote:

> Each output bit is simply a linear combination of the initial bits
> in the two LFSRs. If the number of output bits that you know is at
> least as great as the number of bits in the LFSRs, then you can solve
> that many equations in that many unknowns (which typically requires
> inverting a matrix of elements of the field GF_2).

Circa 1980 I used exactly that technique to reverse engineer the noise generator in the old Atari video game system. Captured several output bits (probably less than 16) on an oscilloscope, then worked out the equations. I'm not sure why I did that -- it was part of a project to write games for that device, but knowing the exact circuit (or equivalent) that produced noise seems of no use.

Not that knowing this helps the OP in any way, shape, or form.

Bob H