shift registers picoCTF 2026 Solution

Description

1. Step 1Understand the LFSR
   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, the leftmost bit receives the XOR result, and the rightmost bit is output as the keystream bit.

                     taps: 7, 5, 4, 0
                      |    |  |  |
                      v    v  v  v
                    +---+---+---+---+---+---+---+---+
      feedback <-- XOR  XOR XOR     |   |   |   |   |
      bit (in)        \___________________________/
                                     |
      shift ---->  [b7][b6][b5][b4][b3][b2][b1][b0]  --> output bit
   
      Each clock:
        out  = b0
        fb   = b7 XOR b5 XOR b4 XOR b0   (the tap positions)
        b0..b7 <- b1..b7, fb              (shift right, new MSB = fb)

   The tap polynomial encodes which positions feed back. Taps [7, 5, 4, 0] correspond to x^8 + x^6 + x^5 + x^4 + 1 (positions counted from the output), or as a bitmask 0b110110001 = 0x187. In chall.py you will see something like taps = [7, 5, 4, 0] or poly = 0x187. They mean the same thing.

   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 2Brute-force the 8-bit seed
   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!
   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. The forward LFSR knows b0..b7 and produces output = b0, then shifts and writes fb into the new MSB. To invert: given the first 8 output bits and the tap polynomial, treat each output bit as the LSB at that step. The 8 outputs you observed across 8 clock cycles ARE the original register contents, in time order. Reverse-shift them into place and you have b0..b7 at time zero - the seed.

   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.
          Update: T(x) = C, C(x) = C - x*B, B(x)=T, L=2-L=2-1=1.
     ... (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.

Alternate Solution

Flag

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