Score:-1

Crypto

Attack on cipher that adds modulo FF output of two LFSRs (LFSR-12 and LFSR-19)

Mike

12/3/23, 4:26 PM

LFSR-12 with poly $x^7+x^2+1$ and LFSR-19 with poly $x^{11}+x^5+1$ are used to produce 8 bit of output each, output is then added together modulo FF

(LFSR-12+LFSR19)mod FF

I know first 8 bytes (-> 8 cycles of registers) of this sum. I am pretty sure there is better solution than just brute force - which is currently running on my pc;-)

I would appreciate any hints on this.

Though about algebraic attack but not sure how it works?

1 + 7

stream-cipher

lfsr

fgrieu

12/3/23, 5:04 PM

_"I know first 8 bytes (-> 8 cycles of registers) of this sum"_: is there a single bit shift of the registers for each byte output, or eight? If one, I think at least 3 of the bits of LFSR19 do not matter to the first 8 output bytes, thus it's not me possible to recover the full state. Also, are the LFSRs in Fibonacci or Galois form ? (for a Fibonacci LFSR of k bits, the first k output bits are the initial state). Is this a CTF ?

Mike

12/3/23, 5:44 PM

LFSRs are Fibonacci and I know 8 consecutive bytes of sum of outputs of both LFSRs mod FF , to be precise LFSR12 = 12bits LFSR19=19 bits. No it is not CTF, homework. Standard LFSRs which produce 8 bits each, then this 8 bits of each are added together mod FF and the result of this sum I know for 8 consecuitve bytes

Daniel S

12/3/23, 6:49 PM

This could use more detail. A LFSR is usually described as operating on bits with registers of length equal to the degree of the polynomial producing streams of bits. A useful hint is probably that the sum of two LFSR outputs produced by polynomials $f(x)$ and $g(x)$ can be written as the output of an LFSR with polynomial $f(x)g(x)$.

Dilip Sarwate

12/5/23, 4:17 AM

Is there a typo in the problem statement? The polynomial $x^{11}+x^5+1$ does not give an LFSR-19; it gives an LFSR-11 at best. Should that have been $x^{19}+x^5+1$ instead? @Daniel S. The problem here is it is not the XOR sum of the LFSR outputs (to which the $f(x)g(x)$ stuff is applicable) but rather that the bytes are interpreted as integers in $[0,255]$ and their integer sum is being computed mod 255 (effectively ones-complement arithmetic addition), which makes the analysis a lot harder.

Mike

12/5/23, 9:07 PM

OK, maybe I made a mistake, by polynomial I meant taps position. So I understand that even if taps are only on 11 and 5 the poly is defined like this x^19+x^11+x^5+1? Right?

Dilip Sarwate

12/7/23, 2:57 AM

$x^{19}+x^{11}+x^5+1$ is _not_ an irreducible polynomial since it has $x+1$ as a factor. Now, it is not absolutely necessary for a shift register polynomial to be irreducible, but having $x+1$ as a factor is a terrible option: it makes the sequence $010101010101\cdots$ one of the possible outputs of the shift register. So please don't blow off my comment as just nitpicking. You need to to give some serious thought as to what the degree-19 polynomial is that you want to use instead of just pulling one out of the hat.

Mike

12/9/23, 8:34 PM

Register LFSR-12 is defined as 12 bits ( 1 to 12) with taps at 2 and 7, the LFSR19 is defined as 19 bits with taps at 5 and 11 -> what are the polys for such registers?

Score:1

Crypto

poncho

12/3/23, 7:05 PM

I would appreciate any hints on this.

Meet-in-the-middle. This works by rearranging the equation you have:

$$\text{LFSR-12} + \text{LFSR-19} \bmod 255 = \text{Known}$$

into:

$$\text{LFSR-12} \equiv \text{Known} - \text{LFSR-19} \pmod{255}$$

If you compute all possible 8-byte outputs (mod 255) on the left size, and store them in some data structure that allows quick lookup, well, the rest of the steps should be fairly straight-forward...

+ 5

Mike

12/3/23, 7:41 PM

Not sure If I got you right, let say known = 0x504050 (24bits), , you mean I should calculate all the possible outputs from (LFSR-12+LFSR+19)mod255 and then just lookup to find in this table these known bytes? right? but sine we have 12bits*19bits*let say 3 bytes wouldn't it be also rather big task?

poncho

12/3/23, 7:52 PM

@Mike: don't look at the original equation, look at the second equation I rearranged it into...

Mike

12/3/23, 8:49 PM

ok, so I should generate (and save) for all possible seeds these 8 bytes output values (for LFSR-12 ), then for each value of LFSR-19 seed I generate 8 bytes output and substract it from " 8 bytes of known", Result of this substraction to be checked in lookup table of LFSR-12 generated at step 1?

poncho

12/3/23, 10:35 PM

@Mike: do you think that'll work?

Mike

12/4/23, 7:59 AM

Probably yes but it can be also probably limited to just 3 bytes of "known" as 3 bytes is larger than LFSR-19

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Attack on cipher that adds modulo FF output of two LFSRs (LFSR-12 and LFSR-19)

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.