Questions tagged [lfsr]

Linear Feedback Shift Register, a pseudorandom bit generator which can be efficiently implemented in hardware.

Filter by
Sorted by
Tagged with
0
votes
1answer
29 views

What does “Clocked” mean in alternating step generators

In the wiki article, it says "An ASG comprises three linear-feedback shift registers, which we will call LFSR0, LFSR1, and LFSR2 for convenience. The output of one of the registers decides which of ...
3
votes
1answer
56 views

Explanation of $z^{-1}$ and $T_{1,2}$ within E0 Bluetooth encryption algorithm

I am trying to understand how E0 Bluetooth algorithm exactly works. I know that $y_t$ is the sum of $x_1$ to $x_4$ and can take values $0, 1, 2, 3, 4$. Also $S_{t+1}$ = $(y_t + c_t)/2$ and can be $\{0,...
1
vote
1answer
42 views

Forward Security of Symmetric Encryption Schemes with LFSR based PRNG

Forward security can be achieved using symmetric encryption schemes by combining with a pseudo-random number generator (PRNG). Does LFSR based PRNG provide forward security in this case?
1
vote
1answer
69 views

M-Sequence Properties in LFSR

I test this law with a 7-bits primitive polynomial LFSR. and the run property could be found according to output. Is there any theoretical to prove m-sequence property, I could just find some ...
2
votes
1answer
210 views

Linear Feedback Shift Registers analysis

Cryptanalysis of Linear Feedback Shift Registers. From this site I found that lfsr could be break by Berlekamp-Massey algorithm. What is the specific progress of this algorithm? And if there is any ...
1
vote
1answer
245 views

Understanding LFSR stream ciphers and the content scrambling system

I'm a little confused over how exactly Linear Feedback Shift Registers (LFSR) work, I kind of get it, but not really, can someone help me understand it? I know it XORs bits in a loop against some mask,...
2
votes
1answer
92 views

Are there any LFSR-based ciphers with variable feedback polynomials?

All LFSR-based stream ciphers that I know of use a fixed feedback polynomial (i.e. the taps are always in the same position). I know that, at least for non-trivial output lengths, it is necessary to ...
2
votes
0answers
47 views

Known-plaintext attack against E0 with 2745 bits per frame instead of 24

In the paper The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption, an attack against the E0 cipher is described which can break it efficiently in a known-plaintext attack: ...
1
vote
0answers
40 views

MULalpha and DIValpha operations in SNOW 3G

I'm not able to appreciate the importance of mul alpha and div alpha operations in feedback polynomial of LFSR in SNOW 3G. What problems or weakness do they help in mitigating and how ?
2
votes
1answer
121 views

How to perform the lfsr scrambling used in PCIe for 2 byte input?

In PCIe Gen 3 on-wards there is 128b/130b encoding used which scrambles incoming bit using a LFSR with polynomial: $$G(X) = X^{23} + X^ {21} + X^{16} + X^{8} + X^5 + X^2 + 1.$$ Is there any way to ...
1
vote
1answer
58 views

About LFSR based M209 Cipher Machine

Can some one please express M209 Cipher Machine in terms of LFSR with Diagram or any simple method?
0
votes
1answer
163 views

Mixing Cipher Lower Bounds

Let Z be a cipher system consisting of three m-sequence linear feedback shift registers (LFSR) of length 128 bits each which are assumed to be not cryptographically secure and the registers are seeded ...
2
votes
0answers
54 views

LFSR expected period

What is the expected value of the length of the period of a n-bit linear-feedback shift register with a random tap? I am asking because I am curious what security issues would appear if the tap would ...
1
vote
1answer
261 views

LFSR: finding the period for an irreducible Polynomial

From what I understand an LFSR produces a maximal length sequence if its characteristic polynomial $p(x)$ of degree $n$ is irreducible, i.e. if it cannot be factored and the smallest integer $k$ for ...
1
vote
1answer
86 views

Building an LSFR Logical bit map using characteristic polynomials

How would one build an LSFR logical map, with a characteristic polynomial such as $$P(x) = x^4 + x^3 + 1$$? Also how would you interpret it, and what would you do to do the reverse it in order to ...
-2
votes
1answer
817 views

How to crack LFSR with known plain text attack?

I'm learning stream ciphers and I'm at LFSR cipher, and I've been trying to solve the question that states if given a 5th degree lfsr with the cipher text ...
4
votes
1answer
959 views

Relationship between Fibonacci LFSR and Galois LFSR

I'm studying about LFSR and have some troubles understanding LFSRs. For Galois LFSR, it is clear that LFSR just multiplies $x$, the primitive element of $GF(2^n)$, so that it makes all the elements ...
0
votes
1answer
378 views

How many bits are needed for an LFSR to generate a specific number of sequences?

I need to generate 64-bit data sequences 16 times pseudorandomly. How many bits should the linear-feedback shift register (LFSR) have in order to do so? That is, what is the number of bits for the ...
1
vote
0answers
110 views

Explaining Berlekamp-Massey Algorithm in simple/layman term?

My foundation in Mathematics is not great. But I would like to understand how Berlekamp-Massey Algorithm works and how it is used in lay-man terms. The only thing I find out there is the emphasis on ...
2
votes
0answers
116 views

Understanding LFSRs and Berlekamp-Massey Algorithm [duplicate]

I have a tutorial question which focuses on LFSRs and Berlekamp-Massey Algo (which is totally out of my syllabus). Please forgive me if my questions seem stupid. I'm given these information: {"...
1
vote
2answers
259 views

Berlekamp Massey Algorithm

I am trying to solve the BM algorithm to find the shortest LFSR and the feedback polynomial but i keep getting stuck. Is there anybody who could solve any binary code so the steps could be little ...
4
votes
2answers
424 views

Why are stream ciphers based on linear-feedback shift registers so popular?

I was conducting research on stream ciphers and LFSRs was a subtopic of my research and I was wondering why are LFSRs so popular?
1
vote
2answers
137 views

Can a LFSR has more than one repeat cycle?

It's clear that an LFSR has finite states and eventually will end up with repeating cycle. However, is it possible for an LFSR to have more than one repeating cycle? For example, with initial state $A$...
5
votes
1answer
1k views

Decrypting Ciphertext with partial Key Fragment using LFSR and Berlekamp-Massey

Edit Does the state register (the LFSR) always have to remain with 16 bits (I'm assuming yes). If so, are we shifting the register right by one (lfsr>>1) ...
2
votes
1answer
272 views

Attack on stream cipher that XOR's the output of two LFSRs

There are two LFSRs of different lengths: LFSR-17 and LFSR-25. LFSR-17 Initially contains a two byte seed, with a 1 injected into the fourth bit, for a total of 17 bits. LFSR-25 operates in the same ...
1
vote
0answers
91 views

Why does the Content Scrambling System have two different length LFSRs

CSS uses two LFSRs of length 17 and 25. If we have two periodic functions $f(t)$ and $g(t)$ and consider the function $h(t) = (f(t), g(t))$, then $h$ will have period $pq/\gcd(p, q)$ where $p$ and $q$...
1
vote
0answers
183 views

How to use Galois LFSR to find multiplicative inverses

My question is how can a Galois Linear Feedback Shift Register be used to discover multiplicative inverses of polynomials? This is a homework assignment. Here is a list of things I did before asking ...
2
votes
1answer
165 views

LFS Kolmogorov Randomness

Consider following LFS register (where + denotes addition modulo 2) I have found the output sequence as 1,0,1,1. I know that The K(s) of a string s is defined as the length of the shortest computer ...
0
votes
1answer
123 views

Expected Linear Complexity of a sequence

Let (s) be a sequence of length n. What are the expected linear complexities of (s) and $(s)^{\infty}$ (meaning that the periodic version of s)? I have no idea of the answer to this question? What ...
1
vote
1answer
359 views

Confused by the definition of Linear Complexity of an LFSR sequence?

The Linear Complexity of a sequence is defined as the length of the shortest LFSR that produces this sequence. It also corresponds to the degree of the minimal polynomial ( i.e. the smallest ...
2
votes
1answer
199 views

period of the lfsr sequence after some manipulations

Here is the question I am dealing with. I have some sort of a solution but I need more specific results. If someone can help I'd appreciate: Given 3 maximum length (max period) LFSR's of lengths L1,...
4
votes
2answers
757 views

LFSR Jump Ahead Algorithm

A related question has been asked and answered here. My question is specifically about figuring out C for very large J. I have searched the web and found many scholarly articles on "jump ahead" and ...
2
votes
1answer
76 views

Unbalanced Feistel network only generates complete permutations with square lengths

I'm generating permutations with a generalized Feistel network which will output integer values $r_j$ in a specified range $[0,period]$ pseudo-randomly, according to the counter input, which will then ...
2
votes
1answer
205 views

Reproducable pseudorandom permutation

I there a way to calculate two similar pseudorandom periodic sequences by exchanging some sort of initial value and generator polynomial? Like a linear-feedback shift register but with a finite ...
15
votes
0answers
274 views

Adding bit constants to the key schedule to reduce rounds?

Bit constants are often added to the key schedule to reduce slide attacks. I have reviewed David Wagner's work, where he showed that the increased rounds in a Feistel network do not help if you have ...
1
vote
1answer
75 views

Looking for title of encryption machines book

I am looking for a title of book in the field of stream crypography. I vaguely remember, that I saw this book at online shop (maybe amazon) near 5-10 years ago. This book is devoted to electronic ...
3
votes
1answer
484 views

Find a LFSR given 2n (or more) non-consecutive keystream bits

How can I calculate the polynomial and state of a LFSR given 2n (or more) non-consecutive keystream bits? It is known to be n bit. If they were consecutive, I could use the Berlekamp–Massey algorithm. ...
1
vote
0answers
60 views

Can I deduce the info such as the bitsize of an LFSR from multiple ciphertext messages?

If I encrypt the same message multiple times (>10000 times) with the same LFSR can I then somehow retrieve some information on the LFSR? I'm looking for information like bit size, polynomial used. The ...
1
vote
2answers
64 views

is it correct that for a nbit LFSR (galois algorithm in particular) the maximum number of unique 32byte keys can only be 255?

In fact I have more than just the one question as I try to better understand the whole topic. for a CTF challenge I am currently reading up on LSFR. The code the challenge provides as an example is a ...
1
vote
2answers
689 views

Is it possible to crack a LFSR encrypted file without using bruteforce?

Let's say I was given a file from which I know that it is encrypted using a 5 bit LFSR with a given poly. I already know that it is possible to deduce the state of an LFSR and thus all future outputs ...
5
votes
1answer
673 views

Are ciphertext-only attacks on LFSRs possible?

Reading about LFSR, I know that breaking an LFSR by knowing it's design and having enough (plaintext, ciphertext) pairs is an relatively easy task but let's assume we know the design of LFSR and a ...
4
votes
1answer
97 views

Difference between one-level and two-level E0 encryption

I am trying to understand the practical security implications of the way E0 is used in Bluetooth 2.1 devices. In reading up on the subject, I am seeing that encrypting a large amount of data with E0 ...
0
votes
1answer
181 views

Finding non-zero coefficients in 8 bit polynomial LFSR

I have a following crypto problem and I have been struggling with for some time An 8-bit linear feedback shift register with connection polynomial C(X) = 1+aX +bX^2 +cX^3 +dX^4 +eX^5 + fX^6 +gX^7 +hX^...
1
vote
1answer
590 views

Finding max period of 8-bit LFSR

I am a bit stuck there and trying to figure out the approach for given problem. What is the maximim period of a pseudo-random sequence generated by the 8-bit LFSR with connection polynomial C(X) = 1+...
1
vote
1answer
175 views

Linear Feedback shift register over integers

The Solina's paper Generalized Mersenne Numbers contains a Linear Feedback shift register I am not able to understand. Here it is: It is supposed to be a normal Linear Feedback shift register but it ...
4
votes
1answer
942 views

How secure is the E0 stream cipher used in Bluetooth?

The question is about E0, the stream cipher used to secure Bluetooth communication. The impression I get is that it's more secure than A5/1. Also, why wasn't AES used instead?
1
vote
1answer
132 views

In what way is KeeLoq a block cipher?

I'm just going by this diagram of KeeLoq encryption and it resembles these diagrams of Crypto-1 and Hitag2. I'm wondering how it is a block cipher. If it is one and that diagram represents most or all ...
0
votes
2answers
899 views

LFSR Tap sequence 15 bit LFSR

I have been asked to create an LFSR with a polynomial of x^15 + x + 1 and i am confused where the tap sequence would go. The examples I was given show a 4 bit tap sequence with two polynomials: x^3 + ...
1
vote
1answer
1k views

Attack on stream cipher

I am trying to decrypt a message, which was encrypted using a stream cipher and 8 bit LFSR. First two letters of plain text are given: K and ...
-1
votes
2answers
210 views

LFSR, polynomial , finite field

I'm having a hard time understanding the concept of LFSR, polynomials and finite field and how to solve exercises like picture below. Could anyone give me some pointer on where to start?