The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [lfsr]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
158 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
74 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
38 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
36 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
66 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
41 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
161 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
44 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
159 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
63 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
422 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 ...
3
votes
1answer
357 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
241 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
83 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
91 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
197 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
318 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
111 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
204 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
87 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
165 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
152 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
93 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
226 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
166 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
600 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
166 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 ...
7
votes
0answers
175 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
73 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
424 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
54 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
62 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
574 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
609 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
86 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
140 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
480 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
166 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
658 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
118 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
731 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
195 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?
3
votes
2answers
321 views

When does a feedback shift register count as non-linear?

It seems that a feedback shift register is counted as a linear feedback shift register whenever it only includes XOR operations. This leads me to believe that a non-linear feedback shift register is ...
5
votes
0answers
79 views

Rueppel's example of self-clocking LFSR

Consider the following excerpt from Rueppels paper, titled When Shift Registers Clock Themselves: His example includes $C(D) = 1 + D + D^2 + D^3 + D^4 + D^5$ as a primitive connection polynomial. ...
1
vote
1answer
258 views

Linear-Feedback Shift Register in Mod 3

I have an exercise for a crypto class that I'm working on and trying to understand. In the problem I have a Linear-Feedback shift register working in mod 3 with digits {0, 1, 2}. The LFSR is using ...
0
votes
1answer
223 views

An (N)LFSR…but for bytes!

A linear feedback shift register can be thought of as an array of bits where NEW_BIT is calculated using F(REGISTERS). ...
0
votes
1answer
824 views

Cipher feedback mode with shift registrers

Can someone please explain to me how the Cipher Feedback Mode works? From what I have read some examples have a shift register in its explanation but some examples don't. Is there two versions of CFB ...