10
$\begingroup$

Katz and Lindell mention in their book 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, 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)?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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? $\endgroup$
    – Tyson Williams
    Sep 6, 2011 at 12:33
  • 2
    $\begingroup$ I am not 100% sure if this is on-topic for cstheory, it might be better suited at crypto.SE. $\endgroup$
    – Artem Kaznatcheev ♦
    Sep 6, 2011 at 12:57
  • $\begingroup$ @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) $\endgroup$
    – Jay
    Sep 6, 2011 at 13:12
  • 2
    $\begingroup$ @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. $\endgroup$
    – Kaveh
    Sep 6, 2011 at 13:12
  • 1
    $\begingroup$ @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, I remember that he said something about this issues (but I am not sure if it is in his lecture notes). $\endgroup$
    – Kaveh
    Sep 6, 2011 at 14:27

2 Answers 2

Reset to default
9
$\begingroup$

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)"

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"

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thank you! These papers will no doubt be useful. $\endgroup$
    – Jay
    Sep 6, 2011 at 14:04
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.