---
title: Feedback Shift Registers
categories: [cheatsheets]
tags: [crypto]
---
## Feedback Shift Registers (FSR)

used in stream ciphers to generate a (random) stream of bits.


have an "array" of bits, which is state (R). And there is an update function
which changes the state f(R).

```
R(t+1) = R(t) << 1 | f(R(t))
```

The Bit, which is shifted out ( << 1) is the output bit for the keystream)


## Linear Feedback Shift Registers (LFSR)

A FSR is Linear if the update function f() is linear. eg. Xoring the bits in the array.

a (L)FSR needs to have at least a period of 2^n-1. -1 because the state: 0 always stays zero. To get the maximal period, the feedback polynomial (basically f()) needs to be primitive.

Linear FSR are cryptographically weak! (because they are linear!)

Result: filtered LFSR

-> adding a nonlinear function g()


Still not 100% secure, following attacks are available for filtered LFSR:

* Algebraic Attacks
* Cube Attacks
* Fast correlation attacks

Hardware Algorithms: Grain-128a and A5/1