Rating:
A correlation attack on a LFSR, this challenge artificially demonstrates how you can attack a filtered LFSR.
If you have 48 (= length of seed) clean bits, then you can invert the LFSR stream and find the seed. As each bit in the output stream is correct with 80% probability, you should expect to try 1 / 0.8^48 = 45,000 different subsets of the output stream before it works. As you are given 20,000 output bits, this is no problem at all.
Unmodified information set decoding also works, mainly because the dimension of the LFSR is so small.
You can also solve this with a customized fast correlation attack if you find sparse linear relations for the LFSR. As the state space is 2^48, you can use a birthday attack/meet-in-the-middle to find random linear relations each of length 3 which collide. That will give you a length 6 linear relation for the LFSR. This is much more complicated than the other solutions.
