Hot answers tagged

14

With a 64-bit known polynomial, future output of an LFSR can be trivially predicted from the last 64 bits output. Even if the 64-bit polynomial is unknown, the last 128 bits are enough, using the Berlekamp–Massey algorithm. Thus indeed, the LFSR-based PRNG in the hardware described in a section 27 of the document linked to in question, with some additional ...


10

If the initial state is $b_0,b_1,\dots,b_{k-1}$ and the recurrence relation is $b_k = \sum_{i = 0}^{k-1} a_ib_i$, then in linear-algebraic terms we have $$ \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_k \end{pmatrix} = U \begin{pmatrix} b_0 \\ b_1 \\ \vdots \\ b_{k-1} \end{pmatrix}, $$ and more generally $$ \begin{pmatrix} b_{n} \\ b_{n+1} \\ \vdots \\ b_{n+k-1}...


10

The obvious way to do this is to generate N words, and use logical operations to combine them in a single word such that each bit of the output word is a 1 with probability approximately 0.1 (and the individual bits are uncorrelated). In the simplest case, you could generate 3 words, and just AND them together into a single one. In C, this would be: ...


9

The variable of a polynomial is traditionally noted $x$, not $X$; and, when dealing with LFSRs, the polynomial is seldom considered a function. Thus I'll rewrite the polynomial as $P(x)=x^4+x^3+1$, a polynomial of degree $n=4$. This is a polynomial with coefficients in the field $\operatorname{GF}(2)$, also noted $\mathbb Z_2$ or $(\{0,1\},+,\cdot)$ [note: ...


9

For text known to be ASCII encoded as octets with high-order bit of octets at zero, that reveals one bit of the output of the LFSR out of 8. It allows finding the original state of the LFSR from (say) the first 51 octets of the ciphertext by merely solving a system of linear boolean equations; then decipher the rest. There is no guesswork involved. For 7-...


8

Bluetooth has gone through a few transitions in protocol. Bluetooth BR/EDR uses E0/SAFER for a cipher and Bluetooth LE uses AES-CCM. Fundamentally, when you write a specification as an engineer, you are looking for a minimally viable CMOS implementation. You make choices that are not always the best from a cryptographic standpoint because you have space ...


7

The fundamental property that you will use is that the output of an $A$-bit LSFR (using the $A$-bit feedback polynomial $P$) xored with the output of a $B$-bit LSFR (using the $B$-bit polynomial $Q$) is the same as the $A+B$ bit LSFR with the feedback polynomial $P \cdot Q$. And, don't forget, when you multiply the feedback polynomials, you use polynomial ...


7

Sure enough, if you use xor with the words, what you do have is the bitwise LFSR repeated 32 times in parallel, each in a different state, but each one having a $2^{16}-1$ period, so the period of your construction should be $2^{16}-1$ as well. If LFSR period wasn't exactly $2^{16}-1$ this will be another history.


6

This is basically the problem of finding a generator $g$ in a group $G$ of order $2^n-1$, where the factorization of $2^n-1$ is unknown. Here is a pragmatic solution that should work fine in practice. Use ECM factoring to find all small factors of $2^n-1$; in this way, find as many prime factors of $2^n-1$ as you can. Now, pick $g$ uniformly at random. ...


6

Well, one way to look at this is to notice that, if the feedback polynomial is prime, then the result of starting with state $E$, and then stepping the LFSR forward $N$ steps is the value $2^N \cdot E$, where we do the computation in $GF(2^K)$, using the polynomial representation (with the feedback polynomial being the polynomial). In addition, I believe ...


6

There were popular once upon a time; They were very easy to implement in the hardware. Think about you only need latch and $\oplus$. For combining functions some $\wedge$ operation. Their periodic properties are well studied, the minimal polynomial and characteristic polynomial etc. You can see a glimpse in the classical book of Solomon Golomb. They are ...


6

Are the taps placed correctly on the above figure? No. That's acknowledged in the errata to the second edition, on the section for page 375 (AFAIK the 20th anniversary edition is essentially the second edition with a little extra at the beginning). My preferred method to determine the hardware implementation for a Fibonacci LFSR from the polynomial: Use a ...


6

Yes, there is a python library LFSR-Automatic-Draw that can output $\LaTeX$ Tikz code and that can be converted to PNG images by pdflatex -shell-escape lfsr.tex The library has many parameters to draw; One can print the feedback polynomial on the bottom One can enable/disable printing the name of the boxes One can enable/disable printing the initial ...


5

Berlekamp-Massey is designed for the situation where you have observed $2n$ consecutive output bits from a $n$-bit LFSR. It doesn't work if the observed bits are scattered randomly, at random non-contiguous offsets in the stream. Information-theoretically, a minimum of $2n$ bits of output are needed to reconstruct the LFSR. Intuitively, this is because ...


5

I have argued so 15 years ago, and not been proven wrong since. Basically, A5/1, with a $n$-bit state, offers a resistance of roughly $2n/3$ bits of security. With $n = 64$, the resistance is very low, thus amenable to not only direct breaking, but also all kinds of trade-offs. All the attacks published so far are dances around that resistance level of ...


5

Galois LFSR In a Galois LFSR with polynomial $P$ of degree $n$, the state is a vector of $n$ bits assimilated to the binary coefficients of terms of degree $n-1$ to $0$ of a polynomial; we note both the state and its polynomial $S_j$ when at step $j\ge0$ . The next state is computed as $S_{j+1}=S_j\,x\bmod P$. Equivalently, the state is shifted towards the ...


5

Consider a Galois LFSR with feedback polynomial $x^3 + x + 1$ and initialization $1 + 0x + 0x^2$, that is, the shift register shifts its initial content $(1,0,0)$ rightwards, and the output bit (the rightmost bit) is fed back into the shift register into the $1$ and the $x$ position. The initial loading of the LFSR is the Galois field element $1$, and ...


5

First of all, LFSR's are not secure when they are used alone. They have good statistical properties and one can calculate their period given the feedback polynomial. The LFSR is maximal-length if and only if the corresponding feedback polynomial is primitive. In this case, it visit all states except the all-zero state if it started with a non-zero sate. To ...


5

The number of consecutive plaintext-ciphertext pairs $(x_i,y_i)$ of bits necessary is 256 if we know the LFSR taps (equivalently: the reduction polynomial) in advance, for the reason explained in the question. 512 is when we do not, because it creates more unknowns: the coefficients of the polynomial, in addition to the initial state. If we know the LFSR ...


5

The clock term comes from electronic engineering; in each clock, the cells of LFSRs ( flip-flops) are clocked and the data moves. In the shift registers, the data moves from one to another in one direction. As we can see from the below, each flip-flop has a clock input where each has the same clock. In the LFSRs ( Linear Feedback Shift Register) there is ...


4

There are no issues with negative indices, even the first (or zero-th depending on how you want to count them) iteration. The quantity $d$ is called the discrepancy. During the $N$-th iteration, $d$ is the difference between $s_N$, the $N$-th bit of the given sequence for which you are finding the LFSR, and the bit computed by the LFSR that you have ...


4

Background: An infinite sequence $c_0,c_1,c_2,\dots$ is generated by a (linear feedback shift register (LFSR) with) polynomial $f(x) = \sum_{i=0}^n f_i x^i$ if for any $j$, $$\sum_{i=0}^n c_{j+i} f_{n-i} = 0 \text.$$ We can consider the sequence as a power series $\sum_{i=0}^{\infty} c_i x^i$. If we multiply this power series with the polynomial $f(x)$, we ...


4

It is very easy to predict and should not be used as a main cryptographic component on its own. Firstly, many $k-$decimations $s_{kt}$ of LFSR sequences (those with $gcd(k,2^n-1)=1$) are shifted LFSR sequences themselves so this can be used for prediction. If you can find a template $T=\{0,t_1,\ldots,t_{n-1}\}$ (with $0<t_1<t_2<\cdots<t_{n-1}$ ...


4

Given any $n-$bit sequence $(a_1,\ldots,a_n)$ with $a_k \in \{0,1\}$ you can use the Berlekamp Massey algorithm (which is conveniently recursive) to obtain minimal degree characteristic polynomials $C_m(X)$ where $C_m(X)$ is the output polynomial of Berlekamp Massey, when its input is $(a_0,\ldots,a_m)$ with $1\leq m\leq n.$ The linear complexity profile of ...


4

A binary sequence of period $105$ will have characteristic polynomial that is a divisor of $x^{105}-1$. Since $x^{105}-1$ has irreducible factors of degrees $12, 4, 3$, and $1$, it is possible to have an LFSR of length $4+3=7$ generate a sequence of period $105$, and that is exactly what has happened here. Note that $$x^7+x^6+x^5+x+1 = (x^3+x+1)(x^4+x^3+1)$$...


4

The polynomial factorisation of $X^{2^L-1}+1$ into irreducible factors gives you all the polynomials $g_i(X)$ that can be used as LFSR polynomials in generating any sequence of period $2^L-1.$ Say your goal is to generate a sequence of this period with linear complexity $c.$ Assume $$(X^{2^L-1}+1)=\prod_{i=1}^v g_i(X),$$ there will be no repeated factors. ...


4

Although I cannot speak to the first part of your question, I can answer the second part. Also, I have never seen a formal explanation of how to map polynomials to a LFSR. In retrospect, I honestly do not know if the polynomials that I have been given were picked because it was known that they would map to circuits, but here is how I do it. As our example,...


4

You made a mistake in the propagation of the feedback. If you follow the LFSR very slowly this is what you get: initial state: +--------------------------------------------------------------+ | | | | | | +-----+ +-----+ | +-----+ | +-----+ | +-----+ | | | | | | v | | ...


4

In this answer I will consider the Galois LFSR mentionned at this question: Sequence output by a Galois type LFSR see the image below. First we assume that the 5 positions of bits are numbered from left to right: 0 .. 4 The Galois representation is as follows: +--------------------------------------------------------------+ | | ...


4

First up: a 5 bit LFSR is horribly small, so getting the initial seed which was used is a piece of cake. But indeed, it’ll basically boil down to a (rather quick) brute-force job where – unless that file contained purely random data – you’ld have good chances detecting the initial state (resulting in successful decryption) by just looking at the first ...


Only top voted, non community-wiki answers of a minimum length are eligible