<p>Katz and Lindell were recommending against using LFSRs <em>by themselves</em> as pseudorandom generators. However, it might be possible to construct a pseudorandom generator <em>using</em> an LFSR in conjunction with other mechanisms. (In particular, PRGs based on LFSRs must include some non-linear component.)</p>

CC BY-SA 3.0
2012-04-24T00:51:05.393Z
2012-04-24T00:51:05.393Z
user6584
<p>There are many types of cryptanalytic attacks: <strong>Linear approximations, Algebraic attacks, Time-memory-data-tradeoff attacks, fault attacks</strong>.</p>

<p>For example you can read the survey: "<a href="http://www.mathnet.or.kr/mathnet/kms_tex/982876.pdf" rel="noreferrer">Algebraic Attacks On Stream Ciphers (Survey)</a>"</p>

<p><strong>Abstract</strong>: <em>Most stream ciphers based on linear feedback shift registers (LFSR)
are vulnerable to recent algebraic attacks. In this survey paper, we describe
generic attacks: existence of algebraic equations and fast algebraic attacks. ...</em></p>

<p>At the end you can find other relevant references.</p>

<p>Another good paper about fault attacks to stream ciphers is: "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.3748&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Fault Analysis of Stream Ciphers</a>"</p>

<p><strong>Abstract</strong>: <em>... Our goal in this paper is to develop general techniques which can be used to attack the standard constructions of stream ciphers based on LFSR’s, as well as more specialized techniques which can be used against specific stream ciphers such as RC4, LILI-128 and SOBERt32. While most of the schemes can be successfully attacked, we point out several interesting open problems such as an attack on FSM filtered constructions and the analysis of high Hamming weight faults in LFSR’s.</em></p>

<p>For time-memory-data tradeoffs attacks you can read: "<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.766&amp;rep=rep1&amp;type=ps" rel="noreferrer">Cryptanalytic Time/Memory/Data tradeoffs for stream ciphers</a>".</p>

CC BY-SA 3.0
2011-09-06T14:04:24.560Z
Thank you! These papers will no doubt be useful.
Jay
CC BY-SA 3.0
2011-09-06T13:46:36.633Z
2011-09-06T14:02:14.290Z
2011-09-06T14:02:14.290Z
Marzio De Biasi
<p>Katz and Lindell mention in <a href="http://www.cs.umd.edu/~jkatz/imc.html" rel="nofollow">their book</a> that LFSR have been horrible as basis for pseudorandom generators, and advocate that they are not used anymore (well, they also recommend that people use block ciphers instead of stream ciphers).
But I see for example that one of the ciphers in the estream portfolio (<a href="http://www.ecrypt.eu.org/stream/grainp3.html" rel="nofollow">Grain</a>, targeted for hardware) uses an LFSR, so the opinion that LFSRs are not good is not a consensus.</p>

<p>I'd like to know if there many cryptologists sharing Katz and Lindell's opinion on LFSRs (and on stream ciphers)? </p>

CC BY-SA 3.0
2011-09-06T12:33:07.327Z
I think the question in your title and the question in the body of your post are at odds. Although I am not a cryptologist, I would say "Yes" to the title and "No" to the question in the post body. Can you improve your question so that it has only one harmonious question?
Tyson Williams
CC BY-SA 3.0
2011-09-06T12:57:14.123Z
I am not 100% sure if this is on-topic for cstheory, it might be better suited at [crypto.SE](http://crypto.stackexchange.com/).
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-06T13:12:28.123Z
@Artem Kaznatcheev: I didn't know about crypto.SE. I believe my reputation is not enough to migrate the question, but I wouldn't mind if it had migrated. (I suppose crypto.SE is not just about implementation issues)
Jay
CC BY-SA 3.0
2011-09-06T13:12:52.133Z
@Artem, IMHO, the question is in cstheory scope. I am not a crypto expert, but generally people do many things in practice that have no foundations, e.g. simple functions are used as psuedo-random number generators in programs but they are not really psuedo-random and can be predicted easily. Jay, If you want to know about the reason why Katz and Lindell say that LFSR should not be used cstheory is the right place for the question. On the other hand, asking if there is consensus is not a good question, the answer is obvious, i.e. there isn't. Also polling questions are not constructive.
Kaveh
CC BY-SA 3.0
2011-09-06T13:14:46.777Z
@Tyson Williams: You're right, thanks! I've changed the title.
Jay
CC BY-SA 3.0
2011-09-06T13:21:59.230Z
@Kaveh: as I understand the reason they do not engourage using LFSRs is how often stream ciphers are broken (my interpretation) because (and this is not interpretation, this is what they say) they're not as well understood, and block ciphers would do the same job just as well.
Jay
CC BY-SA 3.0
2011-09-06T14:27:09.967Z
@Jay, I guess what they mean by not being well-understood is that they are not based on plausible hardness or crypto assumptions, i.e. there are not strong arguments for their unbreakability. You may want to check lecture notes of [Charles Rackoff](http://www.cs.toronto.edu/~rackoff/), I remember that he said something about this issues (but I am not sure if it is in his lecture notes).
Kaveh
<soft-question><cr.crypto-security><pseudorandom-generators>
Are linear feedback shift registers being generally discouraged by cryptologists?
Jay
# Are linear feedback shift registers being generally discouraged by cryptologists?

(Asked by: username_0 on 2011-09-06)

Katz and Lindell mention in [their book](http://www.cs.umd.edu/~jkatz/imc.html) that LFSR have been horrible as basis for pseudorandom generators, and advocate that they are not used anymore (well, they also recommend that people use block ciphers instead of stream ciphers).
But I see for example that one of the ciphers in the estream portfolio ([Grain](http://www.ecrypt.eu.org/stream/grainp3.html), targeted for hardware) uses an LFSR, so the opinion that LFSRs are not good is not a consensus.

I'd like to know if there many cryptologists sharing Katz and Lindell's opinion on LFSRs (and on stream ciphers)?

**Tags:** soft-question, cr.crypto-security, pseudorandom-generators

> **Comments:**
> **username_1**: I think the question in your title and the question in the body of your post are at odds. Although I am not a cryptologist, I would say "Yes" to the title and "No" to the question in the post body. Can you improve your question so that it has only one harmonious question?  
> **username_2**: I am not 100% sure if this is on-topic for cstheory, it might be better suited at [crypto.SE](http://crypto.stackexchange.com/).  
> **username_0**: @username_2: I didn't know about crypto.SE. I believe my reputation is not enough to migrate the question, but I wouldn't mind if it had migrated. (I suppose crypto.SE is not just about implementation issues)  
> **username_3**: @Artem, IMHO, the question is in cstheory scope. I am not a crypto expert, but generally people do many things in practice that have no foundations, e.g. simple functions are used as psuedo-random number generators in programs but they are not really psuedo-random and can be predicted easily. username_0, If you want to know about the reason why Katz and Lindell say that LFSR should not be used cstheory is the right place for the question. On the other hand, asking if there is consensus is not a good question, the answer is obvious, i.e. there isn't. Also polling questions are not constructive.  
> **username_0**: @username_1: You're right, thanks! I've changed the title.  
> **username_0**: @username_3: as I understand the reason they do not engourage using LFSRs is how often stream ciphers are broken (my interpretation) because (and this is not interpretation, this is what they say) they're not as well understood, and block ciphers would do the same job just as well.  
> **username_3**: @username_0, I guess what they mean by not being well-understood is that they are not based on plausible hardness or crypto assumptions, i.e. there are not strong arguments for their unbreakability. You may want to check lecture notes of [Charles Rackoff](http://www.cs.toronto.edu/~rackoff/), I remember that he said something about this issues (but I am not sure if it is in his lecture notes).  

---

## 2 answers

### Answer by username_5 on 2011-09-06. Score: 9 | Accepted answer

There are many types of cryptanalytic attacks: **Linear approximations, Algebraic attacks, Time-memory-data-tradeoff attacks, fault attacks**.

For example you can read the survey: "[Algebraic Attacks On Stream Ciphers (Survey)](http://www.mathnet.or.kr/mathnet/kms_tex/982876.pdf)"

**Abstract**: *Most stream ciphers based on linear feedback shift registers (LFSR)
are vulnerable to recent algebraic attacks. In this survey paper, we describe
generic attacks: existence of algebraic equations and fast algebraic attacks. ...*

At the end you can find other relevant references.

Another good paper about fault attacks to stream ciphers is: "[Fault Analysis of Stream Ciphers](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.100.3748&rep=rep1&type=pdf)"

**Abstract**: *... Our goal in this paper is to develop general techniques which can be used to attack the standard constructions of stream ciphers based on LFSR’s, as well as more specialized techniques which can be used against specific stream ciphers such as RC4, LILI-128 and SOBERt32. While most of the schemes can be successfully attacked, we point out several interesting open problems such as an attack on FSM filtered constructions and the analysis of high Hamming weight faults in LFSR’s.*

For time-memory-data tradeoffs attacks you can read: "[Cryptanalytic Time/Memory/Data tradeoffs for stream ciphers](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.23.766&rep=rep1&type=ps)".

> **Comments:**
> **username_0**: Thank you! These papers will no doubt be useful.  

---

### Answer by username_4 on 2012-04-24. Score: 3

Katz and Lindell were recommending against using LFSRs *by themselves* as pseudorandom generators. However, it might be possible to construct a pseudorandom generator *using* an LFSR in conjunction with other mechanisms. (In particular, PRGs based on LFSRs must include some non-linear component.)


---

