Description
I learned about lfsr today in school so I decided to implement it in my program. It must be safe right? Download: chall.py and output.txt .
Setup
Download chall.py and output.txt.
Read chall.py to understand the LFSR size and feedback taps.
cat chall.py
cat output.txt
Solution
- Step 1Understand the LFSRThe 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.
- Step 2Brute-force the 8-bit seedTry all 256 possible initial states, generate the LFSR keystream for each, XOR with the ciphertext, and check if the result starts with 'picoCTF{'.python3 << 'EOF' from chall import lfsr # import the LFSR function from the challenge source ct = bytes.fromhex(open("output.txt").read().strip()) for seed in range(256): keystream = lfsr(seed, len(ct)) pt = bytes(c ^ k for c, k in zip(ct, keystream)) if pt.startswith(b"picoCTF{"): print(f"Seed: {seed}") print(pt.decode()) break EOF
Flag
picoCTF{lf5r_t00_sm4ll_...}
An 8-bit LFSR has only 256 possible initial states -- exhaustive brute-force is trivial.