**Note**: I was the author of this challenge. This is my intended solution. Some details have been left out.

Two teams solved this one: TokyoWesterns and LC↯BC, in that chronological order.

class Snurre80: """ Snurre80 is a proprietary stream cipher designed for low-power devices, i.e., in Internet of Things contexts. More importantly, it offers an incredibly high security level of 2^80 (who would need more?). It has the following structure: +--------+----+------+ | | | | +---+---+- -+---+ | | | | ... | | c +-----------------+ Snurre80 is resistant to distinguishing attacks, since it uses a non-linear(tm) boolean function f as filtering output function. Snurre80 is quantum resistant and blockchain ready. It is the stream cipher of the future. It is 100 % cyber. We charge a reasonble fee of $0.00001 / encrypted bit. -- The Designers """ def __init__(self, key): self.state = key self.mask = 1284576224436276739441733 self.nbits = self.mask.bit_length()-1 def output(self): var = bin(self.state)[2:].zfill(self.nbits) v = [int(v) for v in var] return v[0] ^ v[1] ^ v[2] ^ v[31] ^ \ v[1]&v[2]&v[3] ^ \ v[25]&v[31]&v[32]&v[33]&v[34] def __str__(self): j = 0 poly = [] x = self.mask while x > 0: if x & 1: poly = ["x^{}".format(j)] + poly x >>= 1 j += 1 return " + ".join(poly) def keystream(self, n): for _ in xrange(n): self.state = (self.state self.nbits if xor != 0: self.state ^= self.mask yield self.output() # Generate a sequence of 800 bits, with a random key. key = int(os.urandom(10).encode('hex'), 16) cipher = Snurre80(key) z = [c for c in cipher.keystream(800)] # Additionally, this may help you solve the CAPTCHA. def solve_proof_of_work(prefix): i = 0 while True: if sha256(prefix+str(i)).digest()[:3] == "\x00\x00\x00": return str(i) i += 1

The feedback polynomial of the stream cipher is

To create a distinguisher, we may use the feedback polynomial as parity check. Unfortunately, the output is not linear, but we can approximate it as a linear function. However, by the piling-up lemma, the bias quickly becomes small since there are many terms. So, we need to find a low-weight polynomial multiple to avoid getting too small bias: there exists such that , where is of low weight.

But wait. Every power is even, so it means it is a square . Turns out we can easily find the square root of it; by simply dividing every power with , we can find from .

Now, we can solve the problem of finding a low-weight multiple in a smaller dimension. This can be done in a couple of seconds. In fact, if you stalked my Github repos you will find that I have written code for this exact problem. The idea behind it is to generate a long list of powers and use a generalized birthday attack to find . There are several papers on it. This is not as difficult as it may be time consuming to write functional code.

Nonethless, one suitable parity check is

But it will not work for the polynomial ? Well, that if no concern. If , then . Since has weight , will have weight .

p = [17399, 13567, 4098] S = sum( z[i + 2*p[0]] ^ z[i + 2*p[1]] ^ z[i + 2*p[2]] ^ z[i] for i in range(0, 1000)) return S < 430 # appropriate magic constant

Running it for every sequence, we can efficiently decide the source. This gives the flag

midnight{1z_3z_2_BR34K_W1D_L0W_w31gHTz!!!}