LFSRs and Stream Cipher Concepts (Lecture 7) Flashcards

Front

LFSR

Back

A Linear Feedback Shift Register is a sequence of flip-flops with XOR-based feedback that shifts bits each clock tick. It generates pseudo-random keystream bits used in stream ciphers. Proper tap selection can produce maximal-length sequences.

Front

Flip-flop

Back

A flip-flop is a bistable memory element that holds one bit and updates its output on a clock edge. In LFSRs, D flip-flops are commonly used so the input value becomes the stored bit at each clock. Flip-flops arranged in series form the shift register.

Front

Feedback tap

Back

A feedback tap selects which flip-flop outputs are XORed together to form the new input bit. The choice of taps defines the LFSR's feedback polynomial and affects the sequence period. Different tap combinations can yield maximal or shorter periods.

Front

XOR gate

Back

An XOR gate outputs 1 when an odd number of inputs are 1 and 0 otherwise. In LFSRs it combines selected tap bits to produce the new incoming bit. The XOR operation is equivalent to addition modulo 2.

Front

Max period

Back

The maximum possible period of an $m$-bit LFSR is $2^m - 1$, achieved when the feedback polynomial is primitive. This excludes the all-zero state, which is a fixed point and halts the sequence. Choosing primitive taps is key to long periods.

Front

Seed

Back

The seed (starting values) is the initial state loaded into the flip-flops before operation. It must be agreed upon a priori between communicating parties or derived from a key. The seed determines the starting point of the keystream sequence.

Front

A5/1

Back

A5/1 is a stream cipher used in GSM for over-the-air voice encryption and uses three LFSRs with irregular clocking. It was initially secret but became public through leaks and reverse engineering. Several practical weaknesses and attacks have been found.

Front

A5/2

Back

A5/2 is a deliberately weakened export variant of A5/1 developed for certain regions. It offers less security and was designed to be easier to break. It illustrates how deliberately reduced algorithms can be vulnerable.

Front

A5/3

Back

A5/3 is the KASUMI-based cipher used in 3G networks and is stronger than A5/1. It replaced weaker algorithms in newer generations to improve confidentiality. It demonstrates migration to more robust standards.

Front

A5/4

Back

A5/4 corresponds to the SNOW 3G based cipher used in 4G LTE networks. It reflects further evolution of stream cipher design for modern cellular standards. It provides stronger security guarantees than older A5 variants.

Front

Clocking

Back

Clocking controls when flip-flops sample their inputs and shift outputs; a rising edge causes the new bit to be stored. In some LFSR designs the feedback XOR may be not clocked, appearing continuous, which affects timing reasoning. Irregular clocking can be used to complicate attacks.

Front

D Flip-flop

Back

A D flip-flop captures the value on its input when the clock edge occurs and holds it until the next clock. LFSRs use D flip-flops so that all stage updates occur synchronously. This creates the discrete shifting behavior of the register.

Front

Majority clocking

Back

Majority clocking is a technique where multiple LFSRs are clocked depending on a majority function of selected bits, as used in A5/1. It introduces irregular step patterns that aim to harden prediction of the keystream. However, it also enabled special attacks exploiting the clocking rule.

Front

Stream cipher

Back

A stream cipher encrypts plaintext by XORing it with a keystream bit-by-bit or byte-by-byte. LFSRs are common keystream generators for stream ciphers due to their efficiency. Security depends on keystream unpredictability and key/seed secrecy.

Front

Keystream

Back

A keystream is a sequence of bits produced by a generator like an LFSR and XORed with plaintext to produce ciphertext. It must be as unpredictable as possible and should never repeat within the same key usage. Length requirements depend on the data rate and call duration.

Front

Periodicity

Back

Periodicity refers to the length of the repeating sequence produced by an LFSR before it cycles. For an $m$-stage LFSR with primitive feedback the period is $2^m - 1$. Longer periods reduce the chance of repeating keystream within a session.

Front

Feedback polynomial

Back

The feedback polynomial encodes which taps participate in the XOR feedback of an LFSR. If the polynomial is primitive over GF(2) the LFSR attains maximal period. Polynomials are a concise algebraic way to represent tap configuration.

Front

Kerckhoffs' principle

Back

Kerckhoffs' principle states that a system should be secure even if everything except the secret key is public knowledge. The history of A5/1 exemplifies this: secrecy failed and the algorithm was analyzed openly. Designing with this principle encourages relying on key secrecy alone.