LFSR StreamCipher Challenge

Other Write-Ups I’m aware of

• sasdf’s write-up

Challenge Description

I was told you know something about crazy crypto?

Maybe you can help us out then. We are looking into these arcade machines from our rivaeehm friend. Eeh.. He ‘lost’ his programming machines and his backups (of course he had backups) and asked us, if we can help him with reversing the code from his game machine. We were also already able to dump everything from the machine, but it is encrypted with some custom stream cipher, build in the hardware of the machine.

Our friend was able to.. remember some details of this stream cipher (after some longer ‘interview’ we had). Apparently it is a filter generator with the following details:

Characteristic Polynomial: x^256 + x^10 + x^5 + x^2 + 1
Filter Function:

  x0*x64*x96*x128*x192*x255
  + x0*x64*x96*x128*x192
  + x0*x64*x96*x128
  + x0*x64*x96*x192
  + x0*x64*x128*x192*x255
  + x0*x64*x192*x255
  + x0*x64*x192
  + x0*x64*x255
  + x0*x96*x128*x192
  + x0*x96*x128*x255
  + x0*x96*x128
  + x0*x96*x192
  + x0*x128*x192*x255
  + x0*x128*x192
  + x0*x128*x255
  + x0*x128
  + x0*x192
  + x0*x255
  + x0
  + x64*x96*x128*x192*x255
  + x64*x96*x128*x192
  + x64*x96*x192
  + x64*x96*x255
  + x64*x128
  + x64*x192*x255
  + x64*x192
  + x64*x255
  + x64
  + x96*x128*x192*x255
  + x96*x128*x255
  + x96*x128
  + x96*x192*x255
  + x96*x192
  + x96*x255
  + x96
  + x128*x192*x255

(crazy guy that he is able to remember this nice filter function!) Luckily we were also able to extract the first keystream bits, because of the fileformat details our friend gave us:

First 1001 Output Key-Bits (LSB = 0th output, MSB = 1000th output):

  0x131018c85020813093200c6ae4822e400261853722f054a1e0\
  80560034008605080380810640342825506829c0209a04134010\
  1b54f1848425aa208035d40510068044597575a02b115a900243\
  6958884d110a2515022240aec060e0a0200c4296081062829a00\
  328250210001533404b206301482800234000501d0104

But now we are stuck and need your help. Find the secret seed of the stream cipher so that we can decrypt the remaining game code and get our friend out of the jam.

Hints

Thanks to a real friend of us, we found some more info about this strange LFSR. Its somewhat wiredly clocked:

new_x0 = old_x1, new_x1 = old_x2, ... new_x254 = old_x255, new_x255 = old_x0 + old_x2 + old_x5 + old_x10

And the first output bits for seed 0x1 are (without filter function):

0x5c96048400000000000000000000000000000000000000000000000000000001104010000000000000000000000000000000000000000000000000000000000148400000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000001

Analysis

Filter Generator

It says that the stream cipher is a filter generator using the filter function $f$. In general, this is an LFSR seeded with a the secret key $s$ and the $i$th key stream $k_i$ is the output of the $f$ function, which gets as input the state of the LFSR after $i$ clocks: $$ k_i = f(s_i) = f(C(\text{LFSR})^i \cdot s), $$ where $C(\text{LFSR})$ is the matrix describing the clocking of the LFSR.

LFSR

This matrix depends on the feedback or characteristic polynomial, which is given as $p(x) = x^{256} + x^{10} + x^5 + x^2 + 1$. But the hint also gives a more detailed clocking instruction.

def clock(state):
    return state[1:] + [state[10] ^^ state[5] ^^ state[2] ^^ state[0]]

example_seed = [1] + [0]*255
example_state = example_seed[:]

def output(state):
    return state[0]

example_outputs = ZZ("5c960484000000000000000000000000000000000000000"\
                     "0000000000000000110401000000000000000000000000000"\
                     "0000000000000000000000000000000148400000000000000"\
                     "0000000000000000000000000000000000000000000000100"\
                     "0000000000000000000000000000000000000000000000000"\
                     "0000000000001", 16).digits(base=2)
for example_bit in example_outputs:
    assert output(example_state) == example_bit
    example_state = clock(example_state)

We can either use this to generate the above mentioned matrix $C(\text{LFSR})$, or we make use of Sage’s functionality. The matrix we are looking for is called the companion matrix of $p(x)$.

#first a printable example
p = GF(2)["x"]("x^16 + x^10 + x^5 + x^2 + 1")
C = companion_matrix(p)
C

#then the correct one
p = GF(2)["x"]("x^256 + x^10 + x^5 + x^2 + 1")
C = companion_matrix(p, format="bottom")
C

And we can now use C for clocking the LFSR:

example_state = (GF(2)^256)([1]+[0]*255)
for i, example_bit in enumerate(example_outputs):
    assert output(C^i * example_state) == example_bit

Et voilà!

Reversing the seed from an LFSRs output is now easy:

eqns = matrix(GF(2), [mtr[0]
                      for mtr in [C^i
                                  for i in range(len(example_outputs))
                                 ]
                     ])
target = vector(GF(2), example_outputs)
d = eqns.solve_right(target)
ker = eqns.right_kernel()

possible_seeds = [list(d + v) for v in ker]
example_seed in possible_seeds
possible_seeds

Let’s now look at the filter function $f$.

Filter Function

This filter function looks a bit scary, but let’s check its cryptographic properties.

from sage.crypto.boolean_function import BooleanFunction
R = BooleanPolynomialRing(6, names=["x0", "x64", "x96", "x128", "x192", "x255"])
f_anf = R("x0*x64*x96*x128*x192*x255 + x0*x64*x96*x128*x192 + x0*x64*x96*x128 + x0*x64*x96*x192 + x0*x64*x128*x192*x255 + x0*x64*x192*x255 + x0*x64*x192 + x0*x64*x255 + x0*x96*x128*x192 + x0*x96*x128*x255 + x0*x96*x128 + x0*x96*x192 + x0*x128*x192*x255 + x0*x128*x192 + x0*x128*x255 + x0*x128 + x0*x192 + x0*x255 + x0 + x64*x96*x128*x192*x255 + x64*x96*x128*x192 + x64*x96*x192 + x64*x96*x255 + x64*x128 + x64*x192*x255 + x64*x192 + x64*x255 + x64 + x96*x128*x192*x255 + x96*x128*x255 + x96*x128 + x96*x192*x255 + x96*x192 + x96*x255 + x96 + x128*x192*x255")
f = BooleanFunction(f_anf)
f

f.algebraic_degree()

f.algebraic_immunity()

Whoops, that’s already something. Having an algebraic immunity of one means $f$ has an annihilator of degree one.

f.annihilator(1)

Annihilator

Given a Boolean Function $f$, an annihilator $g$ of $f$ fulfills $$ \forall x : f(x) \cdot g(x) = 0 $$

So what do we learn from this? Using the above relation we can learn something about $g$’s outputs from $f$’s. In particular, for every $x$, with $f(x) = 1$ the annihilator has to output 0: $g(x) = 0$.

Solution Idea

Using the annihilator, we can thus set up a system of equations for the stream cipher’s output, similar to the approach for a standard LFSR, that is linear and reveals the initial seed.

For this we have to combine the equations from the state $s_i = C(\text{LFSR})^i \cdot s$ that show up in the annihilator: $$ s_i[0] + s_i[64] + s_i[96] + s_i[128] + s_i[192] + s_i[255] $$ (note that we have to translate the $x_i$ from the annihilators ANF back to the original indices ${0, 64, 96, 128, 192, 255}$).

Solution

def annihilator_attack(outputs):
    from sage.geometry.hyperplane_arrangement.affine_subspace import AffineSubspace

    L = companion_matrix(GF(2)['x']("x^256 + x^10 + x^5 + x^2 + 1"), format="bottom")

    x0, x1, x2, x3, x4, x5 = [0, 64, 96, 128, 192, 255]

    # f Annhilator = x0 + x1 + x2 + x3 + x4 + x5 + 1

    eqns = matrix(GF(2), [(mtr[x0] + mtr[x1] + mtr[x2] + mtr[x3] + mtr[x4] + mtr[x5])
                          for mtr in [L**i for (i, zi) in outputs if zi == 1]])

    target = vector(GF(2), [1]*eqns.nrows())

    d = eqns.solve_right(target)
    kern = eqns.right_kernel()

    return AffineSubspace(d, kern)

Some small comments on this:

• we filter and use only the clocks where the output keystream bit is 1
• the constant 1 addition in the ANF of the annihilator is not represented in the eqns matrix, thus we add it to the target (recap that the output beeing one implies the annihilators output to be zero, moving the one the right hand side of the equation turning it one again)

keystream = 0x131018c85020813093200c6ae4822e400261853722f054a1e080560034008605080380810640342825506829c0209a041340101b54f1848425aa208035d40510068044597575a02b115a9002436958884d110a2515022240aec060e0a0200c4296081062829a00328250210001533404b206301482800234000501d0104
print("Got keystream: %x\n" % (keystream))

keystream = list(enumerate(ZZ(keystream).digits(base=2)))
sol = annihilator_attack(keystream)

print("Solutions for LFSR seed:")
print(sol)
print("\nSolution candidates:")
for vec in [v + sol.point() for v in sol.linear_part()]:
    i = ZZ(list(vec), 2)
    s = hex(i).decode('hex')
    print("0x%x - %s" % (i,s))