State is the mutable data a deterministic system carries from one step to the next. A PRNG initializes state from a seed, then repeatedly transforms it; the resulting state determines later outputs and when the sequence eventually repeats. Keeping state distinct from output is a core security boundary: when output reveals state, an observer can reproduce future behavior. section 2.2.2 section 2.2.3
For a linear-feedback shift register (LFSR), state is the ordered sequence of register bits. The register also stores tap positions, which select the state bits XORed to form the next shift-in bit. Each generated bit is the old rightmost state bit; the remaining bits shift right and the computed feedback bit enters on the left. Thus, one state transition both emits a bit and replaces the current state. section 4.2.1
Listing 4.2 impl_lfsr.go
func (lfsr *LFSR) GenerateBit() byte {
outputBit := lfsr.state[lfsr.length-1]
newShiftBit := byte(0x00)
for i := 0; i < lfsr.length; i++ {
if lfsr.taps[i] == 1 {
newShiftBit = newShiftBit ^ lfsr.state[i] #1
}
}
for i := lfsr.length - 1; i > 0; i-- {
lfsr.state[i] = lfsr.state[i-1] #1
}
lfsr.state[0] = newShiftBit
return outputBit
}
Trace the transition in order: save the rightmost bit, XOR tapped state bits, shift the register, and insert the feedback bit. section 4.2.1
An LFSR can generate a keystream for XOR encryption, making its initial state the encryption key in this construction. The implementation first generates and discards as many bits as the register length so that plaintext is not XORed with the initial key bits directly. It then assembles eight generated bits into each keystream byte. section 4.2.1
Recovering a stream-cipher state
Known plaintext and its ciphertext reveal the corresponding keystream through XOR. For an LFSR, linear algebra can recover the internal state from that keystream; an attacker can then clone the register and generate later keystream bits. Discarding initial output does not address recovery from sufficient later keystream. section 10.1.2 section 4.2.1
The same distinction between state and output explains failures in other generators. An LCG outputs its state directly, allowing observed values to reveal its configuration and support cloning. MT19937 transforms each state word before output, yet observing and reversing 624 transformed outputs recovers its full 624-word state and permits a clone to match future values. section 2.2.2 section 3.1.2
State exposure can also create attacks outside random-number generation. A Merkle–Damgård digest exposes the hash function's internal state, allowing an attacker to resume hashing from a known digest and append data in a length-extension attack. Sponge constructions instead absorb input into part of their state and squeeze output while repeatedly permuting that state. section 7.3.2 section 6.3.2
Treat mutable cryptographic state as security-sensitive data:
- Do not treat a generator as cryptographically secure merely because its outputs look random; exposed or reversible state can enable prediction and cloning. section 2.2.3 section 10.1.1
- Avoid LFSRs as standalone stream-cipher generators when an attacker may obtain keystream, because recovered state yields subsequent keystream bits. section 10.1.2
- Avoid secret-prefix MACs built from Merkle–Damgård hashes when a digest lets an attacker resume the internal state. section 7.3.2
