Brain Dump

Linear Feedback Shift Registers

Tags
security

A [see page 9, way] to quickly generate a continuous sequence of random bits using state (binary number) transitions.

Note: An instance of an LFSR (state + LFF) is often referred to as a register.

Given a current state we:

  1. Calculate a feedback-bit using the current-state and a linear-feedback function.
  2. We extract the right-most bit as the stream-bit and right-shift.
  3. We insert the feedback-bit to the left-most position.
  4. We return the stream-bit as the current output of the LFSR.

See [see page 9, example]:

            1   2   3   4   5   6   7   8
          ┌───┬───┬───┬───┬───┬───┬───┬───┐
S_n     = │ a │ b │ c │ d │ e │ f │ g │ h │
          └───┴───┴───┴───┴───┴───┴───┴───┘
          ┌────────────┬───┬───┬───┬───┬───┬───┬───┐
S_{n+1} = │ f(S_{n-1}) │ a │ b │ c │ d │ e │ f │ g │
          └────────────┴───┴───┴───┴───┴───┴───┴───┘

v(S_n)     = h
v(S_{n+1}) = g

The continuous sequence of states entered through this cycle produces a series of numbers (a bit-stream). The initial-state can be seen as the seed for the LFSR.

Ideally we'd like this stream to be random looking and not [see page 10, repeat] itself too quickly (although repeats are guaranteed and inevitable). The maximal-period (duration before the stream repeats) for an $n$-bit register state is \( {2}^{n}-1 \).

Encryption Vulnerabilities

LFSR are not good for direct encryption (I.E. through a Vernam Cipher). Because for an \( n \)-bit LFSR, if you can guess the first \( n \) bits of the plaintext you can [see page 14, reverse-engineer] the complete initial state of the key-stream from the ciphertext. With this you can essentially decode the entirety of the ciphertext.

Suck it Hitler!

Note: We don't have to identify all \( n \)-bits. If we can find the first \( m \)-bits we can simply try all permutations of the remaining \( n-m \)-bits to vastly reduce the search-space.

A very simple [see page 15, model] can get around this by adding another layer of indirection. Rather than outputting the last bit in the state we pass we pass our state through some function, of the current state, (eg. \( {s}_{2} \xor {s}_{0} \)). to produce the output bit.

Now each output-bit is defined as some [see page 16, linear function] of the elements of the initial state and can be [see page 17, derived] through linear-algebra. This is slightly better than the initial approach because it requires more calculation than simply guessing the plaintext but this is still trivially solvable.

Combined LFSR Series

Rarely do we use a single LFSR to produce a random stream. Often we use [see page 18, multiple] LFSR registers, each of possibly varying length, but all iterating forward at the same time. Each of the key-bits of each register are fed into a function \( f \) which produces a single output bit that is the current output of the stream.

The secret-key is the initial-state of all the registers in the system. Note This means this approach can be seen as essentially splitting up one large key among multiple smaller LFSRs.

Warn: The definition of \( f \) can affect the security of the system. For [see page 24, example] if you have an \( n \)-bit key but can guess the first \( m \) bits you can reduce the effective key-size down to \( n-m \)-bits.

Links to this note