• #### Two XORed LFSRs

From Cascade Research@21:1/5 to All on Sun Mar 12 18:42:31 2017
How do you cryptanalyze two XORed LFSRs?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Peter Pearson@21:1/5 to Cascade Research on Sat Mar 18 04:10:49 2017
On Sun, 12 Mar 2017 18:42:31 -0400, Cascade Research <cascares@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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Cascade Research@21:1/5 to Peter Pearson on Sun Apr 9 06:58:09 2017
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 <cascares@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.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Peter Pearson@21:1/5 to Cascade Research on Sun Apr 9 15:37:34 2017
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.

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Cascade Research@21:1/5 to Peter Pearson on Wed Apr 12 16:06:57 2017
On Sunday, April 9, 2017 at 11:37:35 AM UTC-4, Peter Pearson wrote:
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.

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

OK, do you have a URL or PDF?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Peter Pearson@21:1/5 to Cascade Research on Thu Apr 13 01:29:30 2017
On Wed, 12 Apr 2017 16:06:57 -0700 (PDT), Cascade Research wrote:
On Sunday, April 9, 2017 at 11:37:35 AM UTC-4, Peter Pearson wrote:
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.

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

OK, do you have a URL or PDF?

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

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From William Unruh@21:1/5 to Peter Pearson on Thu Apr 13 14:05:13 2017
On 2017-04-13, Peter Pearson <pkpearson@nowhere.invalid> wrote:
On Wed, 12 Apr 2017 16:06:57 -0700 (PDT), Cascade Research wrote:
On Sunday, April 9, 2017 at 11:37:35 AM UTC-4, Peter Pearson wrote:
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.

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

OK, do you have a URL or PDF?

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

Or he could go to a library and copy it.

Mind he might have to pay for it.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From Cascade Research@21:1/5 to Peter Pearson on Sun Apr 16 08:20:49 2017
On Wednesday, April 12, 2017 at 9:29:31 PM UTC-4, Peter Pearson wrote:
On Wed, 12 Apr 2017 16:06:57 -0700 (PDT), Cascade Research wrote:
On Sunday, April 9, 2017 at 11:37:35 AM UTC-4, Peter Pearson wrote:
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.

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

OK, do you have a URL or PDF?

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

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

How about you scan the paper reprint?

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)
• From rsharris.bx.psu.edu@gmail.com@21:1/5 to Peter Pearson on Fri Sep 15 14:01:10 2017
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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)