# Solving snurre80 @ MidnightsunCTF

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

def output(self):
var = bin(self.state)[2:].zfill(self.nbits)
v = [int(v) for v in var]
return v ^ v ^ v ^ v ^ \
v&v&v ^ \
v&v&v&v&v

def __str__(self):
j = 0
poly = []
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:
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)]

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 $\begin{array}{rcl} P(x) & = & x^{80} + x^{76} + x^{66} + x^{64} + x^{58} + x^{54} + x^{50} + x^{42} \\ & + & x^{38} + x^{34} + x^{24} + x^{22} + x^{18} + x^{10} + x^6 + x^2 + 1 \end{array}$

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 $q(x)$ such that $q(x) P(x) = u(x)$, where $u(x)$ is of low weight.

But wait. Every power is even, so it means it is a square $P(x) = p^2(x)$. Turns out we can easily find the square root of it; by simply dividing every power with $2$, we can find $p(x)$ from $P(x)$. $\begin{array}{rcl} p(x) & = & x^{40} + x^{38} + x^{33} + x^{32} + x^{29} + x^{27} + x^{25} + x^{21} \\ & + & x^{19} + x^{17} + x^{12} + x^{11} + x^{9} + x^{5} + x^3 + x + 1 \end{array}$

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 $x^i \bmod P(x)$ and use a generalized birthday attack to find $x^{i_1} + x^{i_2} + x^{i_3} + x^{i_4} = 0 \bmod P(x)$. 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 $x^{17399} + x^{13567} + x^{4098} + 1$

But it will not work for the polynomial $P(x)$? Well, that if no concern. If $q(x) p(x) = u(x)$, then $q^2(x) p^2(x) = q^2(x) P(x) = u^2(x)$. Since $u(x)$ has weight $w$, $u^2(x)$ will have weight $w$.

    p = [17399, 13567,  4098]
S = sum(
z[i + 2*p] ^ z[i +
2*p] ^ z[i +
2*p] ^ 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!!!}