shift registers picoCTF 2026 Solution

Description

1. Step 1Understand the LFSR

   Observation

   The name says shift registers, and chall.py implements one with an 8-bit state. Get the register width, the feedback taps, and the keystream generation straight before attacking anything.

   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, which for 8 bits would be a cycle of 255 values before repeating. This register is not one of those. Bit 0 is never tapped, so it is simply shifted out and forgotten: the step function is not a bijection (only 128 of the 256 states have a preimage), and the state walks a short tail into a cycle of length 31, not 255. The reason is that the feedback only ever reads bits 7, 5, 4 and 3, so the bit stream obeys a degree-5 recurrence, not a degree-8 one. Despite the nice mathematical structure of LFSRs in general, they 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

   Observation

   chall.py masks the key down to 8 bits, so the seed space is 256 values. Try all of them and check each against the known flag prefix.

   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{l1n3ar_f33dback_sh1ft_...}

   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, which is the tap structure you already read out of chall.py, not the seed. Pinning the starting state still takes 256 candidates or a known-plaintext XOR.

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

   Repeating the eight-byte prefix gives valid keystream for those eight positions and no further. This register cycles with a period of 31 bytes, not 8, so everything past the prefix 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 a sequence's minimal feedback polynomial and state from 2L consecutive output bits, where L is the linear complexity. Feed it the MSB of each successive register value here and it settles on L = 5, so 10 bits are enough; 16 bits (2 ciphertext bytes worth of known plaintext) leaves margin. 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 an earlier state. Because this challenge outputs the entire 8-bit register as the keystream byte, the first keystream byte you observe is the whole register, but note the order inside the loop: chall.py steps first and emits second, so that byte is the state one clock after the seed, not the seed itself. That is enough: XOR the first ciphertext byte with p from picoCTF{ to get keystream byte 0x51, then clock forward from 0x51 to decrypt the rest, with no brute force at all. Stepping all the way back to the seed is impossible anyway, because bit 0 is untapped and is discarded on every shift; the search finds 0xA2, but any seed differing from it only in bit 0 produces the same keystream.

   Berlekamp-Massey on the real keystream:
   
     The register values (seed 0xA2, stepped then emitted):
       0x51 0xA8 0xD4 0x6A 0x35 0x1A 0x0D 0x86 ...
     Take the MSB of each; that is the bit the feedback just produced:
       u = 0 1 1 0 0 0 0 1  1 1 0 0 1 1 0 1  ...
   
     Run Berlekamp-Massey over those bits and it converges to
       L    = 5
       C(x) = 1 + x + x^3 + x^4 + x^5
   
     which is exactly the recurrence you get by rewriting the tap set
     in terms of the bit stream. State bit i at time t is u(t-7+i), so
       feedback = b7 ^ b5 ^ b4 ^ b3
                = u(t) ^ u(t-2) ^ u(t-3) ^ u(t-4)
       u(n)     = u(n-1) ^ u(n-3) ^ u(n-4) ^ u(n-5)
   
     Degree 5, not 8: the untapped low bits contribute nothing, which
     is why the cycle is at most 2^5 - 1 = 31 states long, and 31 is
     what this register actually walks.
   
   Clock that recurrence forward to regenerate the keystream and XOR
   it with the ciphertext.
   
   For this challenge both approaches work in microseconds. The
   brute-force over 256 seeds is simpler to code; Berlekamp-Massey
   needs no known plaintext beyond a couple of bytes 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. The flag is shown abbreviated on this page; work the steps above to recover the full value.