Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Linear Feedback Shift Registers (LFSRs)

In this post I'll provide a very simple description of linear feedback shift registers (LFSR for short). Further, we'll see how they are used to create stream ciphers. And all these things without going into mathematical details, for which I refer the interested reader to documents such as the Handbook of Applied Cryptography or this LFSR Reference.

Shift Registers

A shift register is basically a construction with interconnected several memory cells, where every cell stores one bit. So, the value of these cells conforms the so-called state of the register. When the register steps from one state to the next one (usually at each clock tick), the new state is created by simply shifting the bit in a cell to the cell next to it. Thus, the right-most bit goes out of the register, and a new bit goes into the left-most cell.

In this picture we can see an implementation of a 4 bit shift register:

Shift register

We can see an input line (Data in), 4 points where one can read the current state (Q1-Q4) and a clock input, which governs the register telling it in which moment it should step into the next state.

Linear Feedback Shift Registers (LFSRs)

Well, once you know what a shift register is, it is fairly straightforward to understand how a LFSR works. We just take the previous register and set the input as a linear combination of the different cells. Since there is a loop which feeds the register based on its previous state, we have feedback. Further, since this feedback is based on a linear function, then we have linear feedback, hence the name :).

LFSR

LFSRs' use in cryptography

So far, you probably have guessed that the main use of an LFSR in encryption systems is generating a series of pseudo-random bits to be used as a key stream in a stream cipher.

The idea is to generate a stream of bits with the minimum repetition possible, i.e. with maximal period. For its study, the connections in an LFSR are usually represented as a polynomial and the properties such a polynomial needs to meet to achieve maximal period are analyzed.

Basically, we need to get the LFSR to run through all its possible states before going back into the first one. So, if we have 16 bit registers, we'd want to have the LFSR pass through the 2^16-1 states before cycling back to the first one. And yes, I said 2^16-1 instead of 2^16 because the zero state should never appear. Otherwise the LFSR will never leave this state, since the feedback function is linear. For the curious readers, an LFSR will have maximal period if its generating polynomial is a so-called primitive polynomial (I'm pretty sure this name will ring a bell for some of you guys, although maybe not as a happy memory :P).

Setting aside the study of these polynomials, which involves somewhat comlex maths (to my non-mathematician opinion 😆 ), an LFSR by itself should not be used as a key stream generator because its properties make it fairly predictable. In fact, given an n bit LFSR, obtaining 2n bits of its output it is possible to recover the generating polynomial and be able to decrypt any subsequent text.

Therefore, LFSRs are not directly used in crypto, but they are generally used in one of these modes:

• Nonlinear combination of LFSRs: the output from several LFSRs is combined in a non-linear fashion to obtain a key stream.
• Nonlinear filter generator: the output is generated from a non-linear combination of the state.
• Clock-controlled generators: In this mode, several LFSRs step based on some rules, instead of stepping for every clock cycle.

With this kind of constructions it is possible to improve LFSR's properties for the creation of secure stream ciphers. And that's it for LFSRs from my side, for more information refer to these references:

Handbook of Applied Cryptography

LFSR Reference

LFSR @ Wikipedia