shift registers

Challenge Description

I learned about lfsr today in school so i decided to implement it in my program. It must be safe right?

Approach

A Linear Feedback Shift Register (LFSR) is a shift register whose input bit is a linear function (XOR) of its previous state. LFSRs are commonly used to generate pseudo-random bit sequences, but they are not cryptographically secure because:

1. Known-plaintext attack: If you know any portion of the plaintext and the corresponding ciphertext, you can recover the keystream. Since the keystream is generated by an LFSR, knowing enough consecutive bits of the keystream allows you to recover the LFSR’s initial state and feedback polynomial.

2. Berlekamp-Massey algorithm: Given 2n bits of LFSR output (where n is the register length), the Berlekamp-Massey algorithm can recover the feedback polynomial and initial state, completely breaking the cipher.

3. Known prefix attack: If the flag starts with a known prefix like picoCTF{, we already know enough plaintext to recover a significant portion of the keystream.

How LFSRs work:

An LFSR of length n has:

• A state of n bits (the register contents)
• A feedback polynomial (or tap positions) that determines which bits are XORed together to produce the next input bit
• At each clock cycle, the register shifts and a new bit is computed from the taps

For encryption, the LFSR output bits form a keystream that is XORed with the plaintext to produce ciphertext:

ciphertext = plaintext XOR keystream

Attack strategy:

1. The challenge likely provides the ciphertext (encrypted flag) and possibly the LFSR parameters (tap positions, register size) or the source code.
2. Since picoCTF{ is a known prefix, XOR the ciphertext with this known plaintext to recover the first bytes of the keystream.
3. Use the recovered keystream bits to determine the LFSR initial state via:
   • Brute force (if the register is small, e.g., <= 32 bits)
   • Berlekamp-Massey algorithm (for larger registers)
   • Solving a system of linear equations over GF(2)
4. Once the LFSR state is recovered, generate the full keystream and decrypt the entire message.

Solution

Step 1: Analyze the challenge files

The challenge should provide either:

• Source code showing the LFSR implementation
• The encrypted flag (ciphertext)
• LFSR parameters (tap positions, initial state hint, register size)

Step 2: Recover keystream from known plaintext

Since the flag starts with picoCTF{, XOR the first 8 bytes of ciphertext with picoCTF{ to get 8 bytes (64 bits) of keystream.

Step 3: Recover LFSR state

If the LFSR register size is n bits, we need 2n bits of keystream for the Berlekamp-Massey algorithm. For a 32-bit LFSR, 64 bits of known keystream (from the picoCTF{ prefix) is exactly enough.

Step 4: Generate full keystream and decrypt

With the recovered initial state and feedback polynomial, generate the complete keystream and XOR it with the entire ciphertext to recover the flag.

Solution Script

python3 solve.py

Flag

picoCTF{...}  (placeholder - actual flag varies per instance)