cryptomaze picoCTF 2026 Solution

Description

1. Step 1

   Understand the LFSR structure

   Observation

   I noticed the challenge description explicitly names LFSR as the key derivation mechanism and output.txt includes tap positions and an initial state, which suggested I first needed to pin down whether the implementation used a Fibonacci or Galois variant before attempting to reproduce the keystream.

   Read the source to identify the LFSR variant: Fibonacci (XORs are computed externally before shifting in) or Galois (XORs happen at internal positions during the shift). The two produce different bitstreams from the same seed and tap set, so getting this right is critical.

   Learn more

   A Linear Feedback Shift Register (LFSR) is a shift register whose input bit is a linear function (XOR) of its previous state. At each clock cycle, all bits shift one position, a new bit is computed by XORing specific bits called taps or the feedback polynomial, and the output bit (usually the MSB or LSB) is recorded. LFSRs produce pseudo-random bitstreams and are used in stream ciphers, scrambling, CRC computation, and spread-spectrum communications.

   Fibonacci vs Galois: a Fibonacci LFSR XORs the tap bits together externally and feeds that single bit back into the register; the Galois LFSR shifts and conditionally XORs the output bit into multiple internal positions on the way out. They can be configured to produce equivalent sequences, but the implementation details (which bit is "output", which positions XOR, the order of operations) differ. Verify against the source by computing the first 8 output bits by hand from the seed and matching them to the bytestream in output.txt.

   Berlekamp-Massey can recover the feedback polynomial and full internal state from just 2L observed output bits, where L is the register length - useful if the source hides the taps but leaks the keystream. The Python galois library implements galois.berlekamp_massey() and a full LFSR class (galois.FLFSR, galois.GLFSR) so you don't have to roll the math yourself.

   In this challenge, the LFSR is used as a key derivation function: its output bitstream seeds an AES key. If the initial seed (and tap positions) are known, the entire key is deterministic. See the Stream Ciphers in CTFs post for LFSR attack patterns and AES for CTF for the second half of this challenge.

2. Step 2

   Recover the LFSR key

   Observation

   I noticed output.txt provides both the 64-bit initial_state and tap positions [63, 61, 60, 58] in plaintext, which suggested the LFSR seed is fully known and I could deterministically replay 128 clock cycles to reconstruct the 16-byte AES key without any brute force.

   Read the initial_state (a list of 64 bits) and taps directly from output.txt. Implement the LFSR as a list operation: at each clock, output the first bit, compute feedback by XORing the bits at the tap indices, then left-shift the list (drop the first element and append the feedback bit). After 128 clocks, group the collected bits into 8-bit chunks and pack them into the 16-byte AES key.

   python

   python3 << 'EOF'
   # Values copied directly from output.txt
   initial_state = [0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0,
                    1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1,
                    0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1,
                    1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1]
   taps = [63, 61, 60, 58]
   encrypted_flag_hex = "YOUR_CIPHERTEXT_HEX_FROM_OUTPUT_TXT"
   
   def get_aes_key(state, taps, length=128):
       current_state = list(state)
       key_bits = []
       for _ in range(length):
           # Output the first (leftmost) bit
           out_bit = current_state[0]
           key_bits.append(out_bit)
           # Feedback: XOR the bits at each tap index
           new_bit = 0
           for t in taps:
               new_bit ^= current_state[t]
           # Left shift: drop first element, append new feedback bit
           current_state = current_state[1:] + [new_bit]
       # Pack bits MSB-first into bytes
       key_bytes = bytearray()
       for i in range(0, length, 8):
           chunk = key_bits[i:i+8]
           key_bytes.append(int("".join(str(b) for b in chunk), 2))
       return bytes(key_bytes)
   
   aes_key = get_aes_key(initial_state, taps)
   print("AES key (hex):", aes_key.hex())
   EOF

   Copied!

   What didn't work first

   Tried: Using a Galois-style LFSR (shifting right and XORing the feedback bit into the tap positions) instead of the Fibonacci left-shift variant the source implements.

   Both variants share the same tap set but produce different bitstreams because the internal XOR order and shift direction differ. The resulting key bytes will be wrong, and AES decryption will return garbled output or a padding error. The correct approach is to reproduce the exact list-based left-shift: pop element 0, XOR bits at the tap indices to get the feedback, then append that bit on the right.

   Tried: Packing the 128 output bits LSB-first into each byte (reversing the bit order within each 8-bit group) before assembling the AES key.

   The source packs bits MSB-first - the first bit clocked out becomes the most significant bit of key byte 0. Reversing to LSB-first produces a different 16-byte key that decrypts to garbage. The giveaway is that both keys are the same length and AES accepts either without raising an exception, so the only symptom is an unpadding error or nonsense plaintext.

   Learn more

   The tap positions define which bits of the state are XORed together to produce the feedback bit. For a maximal-length LFSR (producing a sequence of period 2^L - 1), the tap positions must correspond to a primitive polynomial over GF(2). The specific taps [63, 61, 60, 58] correspond to the primitive polynomial x⁶⁴ + x⁶¹ + x⁶⁰ + x⁵⁸ + 1.

   The challenge implements a Fibonacci-style left-shift LFSR stored as a list of bits: at each clock cycle, element 0 (the leftmost bit) is emitted as output, the bits at the tap indices are XORed together to form the feedback, and the list shifts left by one position with the feedback bit appended at the right end (current_state = current_state[1:] + [new_bit]). Critically, the initial state is provided in output.txt as a plain Python list of 64 integers (0 or 1), not as a single integer - so list-based indexing is both natural and correct.

   Once you reproduce this exact list-based LFSR in Python and clock it 128 times starting from the provided initial_state, you get the same bitstream that was used to derive the AES key. This is the essence of deterministic key derivation: given the initial state and taps, the key is fully determined. A cryptographically secure PRNG (CSPRNG) is necessary when the key must be unpredictable - LFSRs, being linear, are easily reconstructed from just 2L output bits via the Berlekamp-Massey algorithm.

3. Step 3

   Decrypt the ciphertext with AES-ECB

   Observation

   I noticed the challenge description states AES is applied after LFSR key derivation and the ciphertext in output.txt has no associated IV or nonce, which pointed to AES-ECB mode and meant the recovered 16-byte key could be fed directly into pycryptodome to recover the flag.

   Use the recovered 16-byte key to decrypt the AES-ECB ciphertext from output.txt.

   python

   python3 << 'EOF'
   from Crypto.Cipher import AES
   from Crypto.Util.Padding import unpad
   
   key = bytes.fromhex("YOUR_KEY_HEX_HERE")
   ct  = bytes.fromhex("YOUR_CIPHERTEXT_HEX_HERE")
   cipher = AES.new(key, AES.MODE_ECB)
   plaintext = unpad(cipher.decrypt(ct), 16)
   print(plaintext)
   EOF

   Copied!

   Expected output

   picoCTF{lf5r_k3y_d3r1v3d_...}

   What didn't work first

   Tried: Passing the key as a UTF-8 string to AES.new() instead of converting the hex string with bytes.fromhex() first.

   AES.new() requires a bytes object of exactly 16, 24, or 32 bytes. Passing the 32-character hex string directly gives a 32-byte key made of ASCII digits and letters rather than the intended 16 binary bytes, so AES uses a completely different key and decryption produces garbage. Always call bytes.fromhex() on any hex-encoded key before feeding it to a cipher object.

   Tried: Decrypting with AES-CBC (AES.MODE_CBC) using a zero IV instead of AES-ECB, since ECB is described as equivalent to CBC with an all-zero IV.

   The equivalence only holds for a single-block plaintext and is conceptual - the modes are not drop-in substitutes in pycryptodome. AES.MODE_CBC with a zero IV decrypts the first block identically to ECB, but CBC requires an explicit 16-byte IV argument and the cipher construction differs internally. For the output.txt ciphertext the result would actually match here, but relying on this equivalence breaks the moment the flag spans two blocks. Use AES.MODE_ECB directly as the source specifies.

   Learn more

   AES-ECB (Electronic Codebook mode) encrypts each 16-byte block independently using the same key. This makes it deterministic and parallelizable, but means identical plaintext blocks produce identical ciphertext blocks - a serious weakness for encrypting structured data (the famous "ECB penguin" image demonstrates this visually). For a single-block payload like a CTF flag, ECB is functionally equivalent to CBC with an all-zero IV, so the weakness does not manifest here.

   The pycryptodome library (imported as Crypto) is the standard Python cryptography library for CTF work. AES.new(key, AES.MODE_ECB) creates an AES-ECB cipher object. For other modes: AES.MODE_CBC requires a 16-byte IV as a third argument, AES.MODE_CTR requires a nonce, and AES.MODE_GCM requires a nonce and provides authenticated encryption.

   The decryption ends with PKCS#7 padding: 1-16 bytes whose value equals the count, e.g. \x0b\x0b\x0b...\x0b for 11 bytes of padding. Always strip with pycryptodome's unpad(data, 16) from Crypto.Util.Padding; it validates the padding is well-formed and raises if the key is wrong, which is a useful sanity check. Avoid .rstrip(b'\x0b') - it silently mangles plaintext that legitimately ends in those bytes.

Flag

The flag is revealed after decrypting the AES-ECB ciphertext using the key generated by the LFSR.