Description
In this challenge, you are tasked with recovering a hidden flag encrypted using a combination of LFSR and AES encryption. The LFSR is used to derive a key for AES encryption. Download the encrypted flag from output.txt .
Setup
Download output.txt which contains the LFSR output and AES-encrypted flag.
Inspect the file to understand the LFSR parameters: tap positions, initial state length, and the ciphertext.
cat output.txt
Solution
- Step 1Understand the LFSR structureThe LFSR produces a bitstream. After 128 bits have been generated, they form a 16-byte AES key. The LFSR uses known tap positions (feedback polynomial) that can be found in the source or inferred from the output.
- Step 2Recover the LFSR keyIf the LFSR initial state is partially known or the tap polynomial is given, generate 128 bits from the LFSR to reconstruct the AES key.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) # Group into 8-bit chunks for AES key 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
- Step 3Decrypt the ciphertext with AES-ECBUse the recovered 16-byte key to decrypt the AES-ECB ciphertext from output.txt.python3 << 'EOF' from Crypto.Cipher import AES key = bytes.fromhex("YOUR_KEY_HEX_HERE") ct = bytes.fromhex("YOUR_CIPHERTEXT_HEX_HERE") cipher = AES.new(key, AES.MODE_ECB) print(cipher.decrypt(ct)) EOF
Flag
picoCTF{lf5r_k3y_d3r1v3d_...}
The flag is revealed after decrypting the AES-ECB ciphertext using the key generated by the LFSR.