cryptomaze picoCTF 2026 Solution

Description

1. Step 1Understand the LFSR structure
   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 2Recover the LFSR key
   If the LFSR initial state is partially known or the tap polynomial is given, generate 128 bits from the LFSR to reconstruct the AES key.
   python

   python3 << 'EOF'
   # LFSR: 64-bit initial state, taps at positions [63, 61, 60, 58]
   # Left-shift operation: output MSB, XOR tap positions, append to LSB
   def lfsr(state, taps, n_bits):
       bits = []
       for _ in range(n_bits):
           # Output the MSB
           bits.append((state >> 63) & 1)
           # Compute feedback from tap positions
           feedback = 0
           for t in taps:
               feedback ^= (state >> t) & 1
           # Shift left and insert feedback at bit 0
           state = ((state << 1) & ((1 << 64) - 1)) | feedback
       return bits
   
   # Read seed from output.txt
   seed = 0xYOUR_64BIT_SEED  # from output.txt
   taps = [63, 61, 60, 58]   # confirmed taps
   bits = lfsr(seed, taps, 128)
   
   # Bit-packing convention: bits[0] is MSB of the first key byte.
   # If the AES key looks wrong, flip to LSB-first by reversing each chunk:
   #   key = bytes(int(''.join(map(str, bits[i:i+8][::-1])), 2) for i in range(0, 128, 8))
   key = bytes(int(''.join(map(str, bits[i:i+8])), 2) for i in range(0, 128, 8))
   print("AES key (hex):", key.hex())
   EOF

   Copied!
   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 implementation here uses a Fibonacci LFSR (external XOR) rather than a Galois LFSR (internal XOR). Both produce the same sequence but with different internal state representations. The shift direction and which bit is the "output bit" also vary by convention - reading the source carefully to identify these details is critical before implementing the reconstruction.

   Once you have the correct Python implementation of the LFSR matching the one in chall.py, running it with the seed from output.txt produces the exact same bitstream that was used to derive the AES key. This is the essence of deterministic key derivation: given the seed, the key is fully determined. A cryptographically secure PRNG (CSPRNG) is necessary when the key must be unpredictable - LFSRs, being linear, fail this requirement.

3. Step 3Decrypt the ciphertext with AES-ECB
   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!
   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.

Alternate Solution

Flag

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