Rating:

### crypto/correlated

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](https://grocid.net/2018/06/29/writeup-for-snurre128/) 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.

Original writeup (https://hackmd.io/fmdfFQ2iS6yoVpbR3KCiqQ?view#cryptocorrelated).