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


11

The Berlekamp-Massey algorithm is an iterative method for finding the shortest LFSR that can generate a given sequence of bits. The given sequence might or might not be generated by an LFSR: the Berlekamp-Massey algorithm does not care. It just finds the shortest LFSR that can generate the given sequence, and if the sequence has been generated by an LFSR of ...


10

If there was no non-linearity, then every bit of keystream output would be a (known) linear function of the unknown key bits. Consequently, in a known-plaintext attack scenario, each bit of known keystream output would allow us to write a linear equation on the unknown key bits. If we have a 128-bit key, there are 128 boolean unknowns (variables), so once ...


10

The Berlekamp-Massey algorithm is an iterative algorithm that solves the following problem. Given a sequence $s_0, s_1, s_2, \ldots$ of elements of a field, find the shortest linear feedback shift register (LFSR) that generates this sequence. Here, LFSR is a linear array of $n$ elements with initial value $$(s_0, \quad s_1,\quad \ldots, \quad s_{n-2}, ...


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

Berlekamp-Massey can be used if you do not know the feedback polynomial and you do not know the initial fill. If you do know the feedback polynomial but do not know the initial fill, you can use other simpler methods. For instance, if you just look at any $n$ consecutive bits of output (where the register is $n$ bits wide), then you immediately learn the ...


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.


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


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

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

As fgrieu points out, the number of states reached is at most $2^\ell-1$ and that is achieved only if the feedback polynomial is a primitive polynomial (and the initial state is not all zero). If the feedback polynomial is irreducible but not primitive, then with nonzero initial loading, the LFSR state will cycle through $N$ states, where $N$ is a divisor ...


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


5

@Sarwate gave a clear answer. I'm just following with an example to demonstrate his answer for the potential benefit of other readers: Consider the sequence with minimal polynomial $\Lambda(z)=z^6+z^5+z^4+z+1$. With initial state $100111$ this starts as $1001110110000011\dots$ and repeats every $63$ bits ($63$ is its period). So here $L=6$. If we try ...


5

The Berlekamp-Massey algorithm find the shortest LFSR that can produce the given sequence. Formally, if the sequence has $n$ elements $S_0, S_1, \ldots, S_{n-1}$, then the algorithm finds $\lambda_1, \lambda_2, \ldots, \lambda_t$ such that for $i = t, t+1, \ldots, {n-1}$, the following equation holds: $$ S_{i} +S_{i-1}\lambda_{1} + S_{i-2}\lambda_2 + \...


5

Read chapter 6 of the HAC. It will tell you that no, the $2^ℓ$ states are never reached, at most $2^ℓ-1$ are. And that occurs for taps chosen per a primitive polynomial, and initial state not all zero. For lists of primitive polynomials, I use jj's useful and ugly page of mathematical data.


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

When I need something on that tune I might use Jörg's useful and ugly page of mathematical data. In particular, all-trinomial-primpoly gives primitive GF(2) trinomials (LFSR with 2 taps, the minimum number) to degree 400. 100,63,0 tells you that $x^{100}+x^{63}+1$ is primitive, meaning the same as 100|100,63 at LFSR Feedback Taps to 168 bits. Also of ...


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


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

I have never met this, but it can still be analyzed in the framework of Linear Feedback Shift Registers, and is unsafe as a key stream generator. I'll assume that $2^{\mathtt L-1}\le \mathtt{TAPS}<2^\mathtt L$. The operation state = tick(state) then is the normal operation for a Fibonacci LFSR with the binary polynomial $Q(x)$ of degree $\mathtt L$ ...


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

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


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