shift registers picoCTF 2026 Solution

Description

1. Step 1

   Understand the LFSR

   Observation

   I noticed the challenge is named 'shift registers' and chall.py implements an LFSR with an 8-bit state, which suggested I first understand the register width, feedback taps, and how the keystream is generated before attempting any attack.

   The LFSR has an 8-bit initial state (seed), which means there are only 256 possible starting values. The output keystream is XORed with the flag bytes.

   Learn more

   A Linear Feedback Shift Register (LFSR) is a sequential circuit that generates a pseudorandom bit sequence. It consists of a shift register of n bits where the input bit is computed as an XOR of certain register positions called feedback taps. At each clock cycle, all bits shift right by one and the leftmost bit (the new MSB) receives the XOR result. A textbook LFSR outputs just the rightmost bit as the keystream bit, but watch the code: this challenge uses the entire 8-bit register value as that step's keystream byte (see below).

                     taps: 7, 5, 4, 3
                      |    |  |  |
                      v    v  v  v
                    +---+---+---+---+---+---+---+---+
      feedback <-- XOR  XOR XOR XOR  |   |   |   |   |
      bit (in)        \___________________________/
                                     |
      shift ---->  [b7][b6][b5][b4][b3][b2][b1][b0]
   
      Each clock (as in chall.py):
        fb   = b7 XOR b5 XOR b4 XOR b3   (the tap positions)
        lfsr <- (fb << 7) | (lfsr >> 1)  (shift right, new MSB = fb)
        ks   = lfsr                      (whole byte is the keystream)

   The feedback taps are the positions XORed to compute the new MSB. In chall.py the step function reads bits 7, 5, 4, and 3 explicitly (b7 ^ b5 ^ b4 ^ b3), so the taps are [7, 5, 4, 3] (bitmask 0b10111000 = 0xB8). The seed is just the low byte of a longer random value (lfsr = key & 0xFF), which is why only 256 starting states are possible.

   LFSRs have elegant mathematical properties: a well-chosen tap polynomial over GF(2) makes the LFSR produce a maximum-length sequence (m-sequence) of period 2^n - 1. For an 8-bit LFSR, this is a cycle of 255 values before repeating. Despite this nice mathematical structure, LFSRs are not cryptographically secure because they are completely linear - given enough output bits, the entire future (and past) output can be predicted using the Berlekamp-Massey algorithm.

   LFSRs are used legitimately in hardware applications: CRC computation (error detection), spread-spectrum communications, and as components in some stream ciphers (though modern stream ciphers add nonlinear components on top of LFSRs to break the linearity). The famous A5/1 cipher used in GSM mobile phones is based on three combined LFSRs with a nonlinear output function - and it was broken anyway.

2. Step 2

   Brute-force the 8-bit seed

   Observation

   I noticed chall.py truncates the key to 8 bits with lfsr = key & 0xFF, limiting the seed space to only 256 values, which suggested that exhaustive brute-force combined with the known picoCTF{ prefix as a correctness check would recover the flag trivially.

   Try all 256 possible initial states, generate the LFSR keystream for each, XOR with the ciphertext, and check if the result starts with picoCTF{...}.

   python

   python3 - <<'EOF'
   for seed in range(256):
       pt = decrypt_with_seed(seed)
       if pt.startswith(b'picoCTF{'):
           print(pt.decode())
           break
   EOF

   Copied!

   Expected output

   picoCTF{lf5r_t00_sm4ll_...}

   What didn't work first

   Tried: Apply Berlekamp-Massey to recover the tap polynomial before brute-forcing the seed.

   Berlekamp-Massey recovers the feedback polynomial from output bits, but it gives you the tap structure (which you already know from reading chall.py), not the initial seed. You still need either a 256-candidate brute-force or a known-plaintext XOR to pin down the exact starting state.

   Tried: XOR the entire ciphertext with the string 'picoCTF{' repeated to extract the keystream directly.

   Repeating the 8-byte prefix only produces valid keystream bytes for those first 8 positions. The LFSR keystream is not periodic with period 8 - it has period up to 255 for an 8-bit register - so the pattern breaks after byte 8 and the rest of the plaintext comes out as garbage.

   Learn more

   An 8-bit seed space means only 256 possible initial states. This is a classic example of insufficient entropy - the key space is so small that an exhaustive search is trivial even without any mathematical insight. A proper stream cipher like ChaCha20 uses a 256-bit key, giving 2^256 possible keys - a number so large that exhaustive search is computationally impossible with any foreseeable technology.

   The known plaintext attack here exploits the fact that CTF flags always begin with picoCTF{. This 8-byte prefix provides enough information to uniquely identify the correct key from 256 candidates: XOR the first 8 bytes of ciphertext with picoCTF{ to get the first 8 keystream bytes, then reconstruct the LFSR state from those keystream bits and verify it against all 256 seeds. This reduces the attack to O(1) rather than O(256), though the exhaustive search is already fast enough that optimization is unnecessary.

   This challenge mirrors historical cryptographic attacks: the German Lorenz cipher in WWII used a system of multiple interacting shift registers and was broken by Alan Turing's team at Bletchley Park using similar principles - exploiting known plaintext ("Weather report: ..." message headers) combined with the algebraic linearity of the cipher to recover the key. The principle of attacking small key spaces through exhaustive search has been relevant since the dawn of modern cryptography.

   Berlekamp-Massey: the algebraic alternative to brute force. Even without a known plaintext prefix, the Berlekamp-Massey algorithm recovers an n-bit LFSR's tap polynomial and full state from just 2n consecutive output bits. For n = 8, that is 16 keystream bits = 2 ciphertext bytes. The algorithm runs in O(n^2) time and works as follows:

   • Init: connection polynomial C(x) = 1, current LFSR length L = 0, "step counter since last C update" m = 1, prior-discrepancy polynomial B(x) = 1.
   • For each new bit s_i, compute discrepancy d = s_i XOR (sum of c_j * s_(i-j) for j = 1..L).
   • If d = 0, just bump m. If d != 0 and 2L <= i, save T = C, update C = C - x^m * B, set L = i + 1 - L, B = T, m = 1. Otherwise update C the same way without changing L or B.
   • After 2n steps, C(x) is the minimum-degree feedback polynomial that generates the observed sequence.

   "Apply the inverse LFSR" means running the LFSR backward to recover the initial state. Because this challenge outputs the entire 8-bit register as the keystream byte at each clock cycle, the very first keystream byte you observe IS b0..b7 at time zero - the seed itself. To invert: XOR the first byte of ciphertext with the first byte of the known plaintext prefix (picoCTF{) to recover the first keystream byte, which is directly the initial seed. You can then verify by re-running the LFSR forward from that seed and checking the rest of the decrypted plaintext.

   Berlekamp-Massey trace on an 8-bit LFSR:
     Observed keystream bits (16 needed for length-8 LFSR):
       s = 1 0 1 1 0 1 0 0  1 1 0 1 0 0 1 1
   
     Initial C(x) = 1, L = 0
     i=0: d = s0 = 1.  Set B(x)=1, m=1, then C(x) = C - x*B = 1 + x.
          Now L = 1.
     i=1: d = s1 + c1*s0 = 0 + 1*1 = 1.  d != 0, but 2L=2 > i=1 (false branch).
          Update C(x) = C - x^m*B = (1+x) - x*(1) = 1. L stays 1, B stays 1, m increments.
     ... (the algorithm proceeds for 16 iterations) ...
     Final: C(x) = 1 + x^4 + x^5 + x^6 + x^8
   
   The recovered tap polynomial is x^8 + x^6 + x^5 + x^4 + 1, and the
   internal state is the first 8 keystream bits. Apply the inverse LFSR
   to recover the full keystream and XOR with the ciphertext.
   
   For this challenge, with only 8 bits of state, both approaches
   work in microseconds. The brute-force is simpler to code; the
   Berlekamp-Massey approach is more elegant and generalizes to
   arbitrary register sizes.

   See stream ciphers in CTFs for the broader treatment of LFSR-based keystreams and their attacks.

Flag

An 8-bit LFSR has only 256 possible initial states - exhaustive brute-force is trivial.