feedback-shift-registers.md 1.0 KB
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