cryptomaze picoCTF 2026 Solution

Description

1. Step 1Understand the LFSR structure

   Observation

   The description names an LFSR as the key derivation, and output.txt gives both tap positions and an initial state. Before reproducing the keystream, work out whether this is the Fibonacci or the Galois variant.

   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

   Observation

   output.txt hands over the 64-bit initial state and the tap positions in plaintext, so the seed is fully known. Replay 128 clock cycles and the 16-byte AES key falls out with no 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 use the same tap set and still produce different bitstreams, because the XOR order and shift direction differ. Pick the wrong one and the key bytes are wrong, so AES returns garbage or a padding error. Reproduce the exact left shift: pop the first element, XOR the tap positions for the feedback bit, append it 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 most significant first, so the first bit clocked out becomes the top bit of the first key byte. Pack them the other way and you get a different 16-byte key. Both are valid lengths and AES accepts either without complaint, 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 taps [63, 61, 60, 58] here are list indices into the 64-bit state, not exponents: the recurrence the code implements is s_n+64 = s_n+63 XOR s_n+61 XOR s_n+60 XOR s_n+58, whose characteristic polynomial x⁶⁴ + x⁶³ + x⁶¹ + x⁶⁰ + x⁵⁸ factors as x⁵⁸(x⁶ + x⁵ + x³ + x² + 1) and is therefore not primitive. That costs nothing here: only the first 128 output bits are consumed and the seed is published in output.txt, so period length never comes into play. Maximal period matters when the keystream must not repeat, not when you are replaying a known seed.

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

   Observation

   AES runs after the key derivation, and the ciphertext comes with no IV or nonce, which means ECB mode. Feed the recovered key straight into pycryptodome.

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

   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 wants a bytes object of exactly 16, 24, or 32 bytes. A 32-character hex string is technically 32 bytes, but of ASCII digits and letters rather than the 16 binary bytes you meant, so the cipher uses a different key entirely. Convert hex to bytes before constructing the cipher.

   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 holds for the first block only. CBC decryption XORs each recovered block with the previous ciphertext block, so with a zero IV block one comes out identical to ECB and every block after it comes out as garbage. A flag longer than 16 bytes spans two or more blocks, so the tail is wrong and unpad() raises. Use ECB, as the source does.

   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). A flag is short and its blocks all differ, so no repeated block leaks here, but that is luck rather than a property of the mode.

   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.