zer0lfsr 2021 Full Writeup (0CTF/TCTF 2021)

This writeup is a compilation of my thoughts and discussions with others.

My solutions are at https://github.com/rkm0959/Cryptography_Writeups/tree/main/2021/0ctfquals.

 

Problem 1 : zer0lfsr- (35 solves)

 

#!/usr/bin/env python3
 
import random
import signal
import socketserver
import string
from hashlib import sha256
from os import urandom
from secret import flag
 
def _prod(L):
    p = 1
    for x in L:
        p *= x
    return p
 
def _sum(L):
    s = 0
    for x in L:
        s ^= x
    return s
 
def n2l(x, l):
    return list(map(int, '{{0:0{}b}}'.format(l).format(x)))
 
class Generator1:
    def __init__(self, key: list):
        assert len(key) == 64
        self.NFSR = key[: 48]
        self.LFSR = key[48: ]
        self.TAP = [0, 1, 12, 15]
        self.TAP2 = [[2], [5], [9], [15], [22], [26], [39], [26, 30], [5, 9], [15, 22, 26], [15, 22, 39], [9, 22, 26, 39]]
        self.h_IN = [2, 4, 7, 15, 27]
        self.h_OUT = [[1], [3], [0, 3], [0, 1, 2], [0, 2, 3], [0, 2, 4], [0, 1, 2, 4]]
 
    def g(self):
        x = self.NFSR
        return _sum(_prod(x[i] for i in j) for j in self.TAP2)
 
    def h(self):
        x = [self.LFSR[i] for i in self.h_IN[:-1]] + [self.NFSR[self.h_IN[-1]]]
        return _sum(_prod(x[i] for i in j) for j in self.h_OUT)
 
    def f(self):
        return _sum([self.NFSR[0], self.h()])
 
    def clock(self):
        o = self.f()
        self.NFSR = self.NFSR[1: ] + [self.LFSR[0] ^ self.g()]
        self.LFSR = self.LFSR[1: ] + [_sum(self.LFSR[i] for i in self.TAP)]
        return o
 
class Generator2:
    def __init__(self, key):
        assert len(key) == 64
        self.NFSR = key[: 16]
        self.LFSR = key[16: ]
        self.TAP = [0, 35]
        self.f_IN = [0, 10, 20, 30, 40, 47]
        self.f_OUT = [[0, 1, 2, 3], [0, 1, 2, 4, 5], [0, 1, 2, 5], [0, 1, 2], [0, 1, 3, 4, 5], [0, 1, 3, 5], [0, 1, 3], [0, 1, 4], [0, 1, 5], [0, 2, 3, 4, 5], [
            0, 2, 3], [0, 3, 5], [1, 2, 3, 4, 5], [1, 2, 3, 4], [1, 2, 3, 5], [1, 2], [1, 3, 5], [1, 3], [1, 4], [1], [2, 4, 5], [2, 4], [2], [3, 4], [4, 5], [4], [5]]
        self.TAP2 = [[0, 3, 7], [1, 11, 13, 15], [2, 9]]
        self.h_IN = [0, 2, 4, 6, 8, 13, 14]
        self.h_OUT = [[0, 1, 2, 3, 4, 5], [0, 1, 2, 4, 6], [1, 3, 4]]
 
    def f(self):
        x = [self.LFSR[i] for i in self.f_IN]
        return _sum(_prod(x[i] for i in j) for j in self.f_OUT)
 
    def h(self):
        x = [self.NFSR[i] for i in self.h_IN]
        return _sum(_prod(x[i] for i in j) for j in self.h_OUT)        
 
    def g(self):
        x = self.NFSR
        return _sum(_prod(x[i] for i in j) for j in self.TAP2)  
 
    def clock(self):
        self.LFSR = self.LFSR[1: ] + [_sum(self.LFSR[i] for i in self.TAP)]
        self.NFSR = self.NFSR[1: ] + [self.LFSR[1] ^ self.g()]
        return self.f() ^ self.h()
 
class Generator3:
    def __init__(self, key: list):
        assert len(key) == 64
        self.LFSR = key
        self.TAP = [0, 55]
        self.f_IN = [0, 8, 16, 24, 32, 40, 63]
        self.f_OUT = [[1], [6], [0, 1, 2, 3, 4, 5], [0, 1, 2, 4, 6]]
 
    def f(self):
        x = [self.LFSR[i] for i in self.f_IN]
        return _sum(_prod(x[i] for i in j) for j in self.f_OUT)
 
    def clock(self):
        self.LFSR = self.LFSR[1: ] + [_sum(self.LFSR[i] for i in self.TAP)]
        return self.f()
 
class zer0lfsr:
    def __init__(self, msk: int, t: int):
        if t == 1:
            self.g = Generator1(n2l(msk, 64))
        elif t == 2:
            self.g = Generator2(n2l(msk, 64))
        else:
            self.g = Generator3(n2l(msk, 64))
        self.t = t
 
    def next(self):
        for i in range(self.t):
            o = self.g.clock()
        return o
 
class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)
 
    def proof_of_work(self):
        random.seed(urandom(8))
        proof = ''.join([random.choice(string.ascii_letters + string.digits + '!#$%&*-?') for _ in range(20)])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
        self.dosend('Give me XXXX:')
        x = self.request.recv(10)
        x = (x.strip()).decode('utf-8') 
        if len(x) != 4 or sha256((x + proof[4: ]).encode()).hexdigest() != digest: 
            return False
        return True
 
    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass
 
    def timeout_handler(self, signum, frame):
        raise TimeoutError
 
    def handle(self):
        try:
            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(30)
            if not self.proof_of_work():
                self.dosend('You must pass the PoW!')
                return
            signal.alarm(50)
            available = [1, 2, 3]
            for _ in range(2):
                self.dosend('which one: ')
                idx = int(self.request.recv(10).strip())
                assert idx in available
                available.remove(idx)
                msk = random.getrandbits(64)
                lfsr = zer0lfsr(msk, idx)
                for i in range(5):
                    keystream = ''
                    for j in range(1000):
                        b = 0
                        for k in range(8):
                            b = (b << 1) + lfsr.next()
                        keystream += chr(b)
                    self.dosend('start:::' + keystream + ':::end')
                hint = sha256(str(msk).encode()).hexdigest()
                self.dosend('hint: ' + hint)
                self.dosend('k: ')
                guess = int(self.request.recv(100).strip())
                if guess != msk:
                    self.dosend('Wrong ;(')
                    self.request.close()
                else:
                    self.dosend('Good :)')
            self.dosend(flag)
        except TimeoutError:
            self.dosend('Timeout!')
            self.request.close()
        except:
            self.dosend('Wtf?')
            self.request.close()
 
class ThreadedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass
 
if __name__ == "__main__":
    HOST, PORT = '0.0.0.0', 31337
    server = ThreadedServer((HOST, PORT), Task)
    server.allow_reuse_address = True
    server.serve_forever()
 

 

Introduction

There are three LFSR/NFSR based keystream generators. We are given

• first 40000 bits of the keystream
• SHA256 hash value of the key

We need to find the key for each generators, but actually we only need to do 2 out of 3. 

Note that the three problems are completely independent in this challenge. We will do #1, #3.

 

Solution for Generator3

Generator3 is a good target because it doesn't have any NFSR parts. However, it does have a "filter function" $f$. 

There are two methods to get around this filter function $f$, both which can be derived from classic approaches.

NOTE : Read https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/boolean_function.html

 

The first method computes the algebraic immunity of $f$. Sagemath gives us that $f$ has algebraic immunity of $2$, which means that there exists a polynomial $g$ of degree $2$ such that $fg = 0$ for all inputs. If $f = 1$, which we can directly verify using the output bit, we can immediately recover $g = 0$. Since $g$ has degree $2$ and every LFSR bit is a linear combination of the initial 64 bit key, each information $g = 0$ gives us a linear equation on $\displaystyle 64 + \binom{64}{2}$ monomials of degree no more than $2$. Note that $x^2 = x$ on $\mathbb{F}_2$. Since we have 40000 bits of keystream, we will get about 20000 linear equations. We can now solve the system of linear equation, and recover the 64 bit key as desired.  

 

The second method notes that for $$f_3(x_0, x_1, x_2, x_3, x_4, x_5, x_6) = x_1 + x_6 + x_0 x_1 x_2 x_3 x_4 x_5 + x_0 x_1 x_2 x_4 x_6$$ we have the incredibly precise linear approximation of $$\overline{f}_3(x_0, x_1, x_2, x_3, x_4, x_5, x_6) = x_1 + x_6$$ which matches $f_3$ for a ton of inputs, I believe $31/32$ of them.

 

This implies that we have a alternate keystream that directly follows the LFSR recurrence and matches the actual keystream quite well. This alternate keystream can now be found by fast correlation attack. The real key can be quickly derived from the alternate keystream. 

 

NOTE : Read https://iacr.org/archive/fse2011/67330055/67330055.pdf for the fast correlation attack.

 

I used the first method for solving this part, as I was not (and still not) familiar with the fast correlation attack.

 

Solution for Generator1

I chose Generator1 as a good target, because we can bruteforce all $16$ bits of the LFSR part of the key.

If we do this, we can derive all LFSR results by direct calculation. We now need to recover the NFSR part. 

 

The key idea here is that the function $h_1$, which is $$h_1(x_0, x_1, x_2, x_3, x_4) = x_1 + x_3 + x_0 x_3 + x_0 x_1 x_2 + x_0 x_2 x_3 + x_0 x_2 x_4 + x_0 x_1 x_2 x_4$$ has a close function independent of $x_4$, which is $$\overline{h}_1(x_0, x_1, x_2, x_3) = x_1 + x_3 + x_0 x_3 + x_0 x_1 x_2 + x_0 x_2 x_3$$ This matches $h_1$ for $15/16$ of the input. If we look at how the function $h$ is calculated, it takes the first four bits from the LFSR and the last bit from NFSR. The problem is that we don't really know much about the NFSR. However, we can now use $\overline{h}_1$ and the four bits from LFSR. 

 

This implies, after bruteforcing the 16 bits of the LFSR, we can calculate all $h$ values, each with probability $15/16$. Since we know the output bits $f$, which is the XOR of the first bit of NFSR and $h$, this means we can recover each NFSR bit with probability $15/16$.

We do this $48$ times to find all NFSR bits. The success probability is around 4%, which is pretty decent. This solves Problem 1.

 

Problem 2 : zer0lfsr+ (2 solves)

 

def b2n(x):
    return int.from_bytes(x, 'big')
 
def n2l(x, l):
    return list(map(int, '{{0:0{}b}}'.format(l).format(x)))
 
def split(x, n, l):
    return [(x >> (i * l)) % 2**l for i in range(n)][::-1]
 
def combine(x, n, l):
    return sum([x[i] << (l * (n - i - 1)) for i in range(n)])
 
class KDF:
    def __init__(self, key: int):
        self.msk = key
        self.SBOX = [12, 5, 1, 2, 7, 15, 9, 3, 0, 13, 14, 6, 8, 10, 4, 11]
        self.idx = [[0, 3], [0, 1], [2, 3], [0, 3]]
 
    def substitue(self, x):
        return [self.SBOX[i] for i in x]
 
    def expand(self):
        h = sha256(str(self.msk).encode()).digest()
        rnd_key = [h[: 2], h[2: 4], h[2: 4], h[4: 6]]
        rnd_key = list(map(b2n, rnd_key))
        chunk = split(self.msk, 4, 16)
        sub_key = [combine(self.substitue(split(chunk[self.idx[i][0]] ^ chunk[self.idx[i][1]] , 4, 4)), 4, 4) for i in range(4)]
        final_key = [rnd_key[i] ^ sub_key[i] for i in range(4)]
        return combine(final_key, 4, 16)
 
class zer0lfsr:
    def __init__(self, msk: int):
        self.key = []
        for i in range(3):
            msk = KDF(msk).expand()
            self.key.append(msk)
        self.g1 = Generator1(n2l(self.key[0], 64))
        self.g2 = Generator2(n2l(self.key[1], 64))
        self.g3 = Generator3(n2l(self.key[2], 64))
 
    def next(self):
        o1 = self.g1.clock()
        o2 = self.g2.clock()
        o2 = self.g2.clock()
        o3 = self.g3.clock()
        o3 = self.g3.clock()
        o3 = self.g3.clock()
        o = (o1 * o2) ^ (o2 * o3) ^ (o1 * o3)
        return o
 
class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)
 
    def proof_of_work(self):
        random.seed(urandom(8))
        proof = ''.join([random.choice(string.ascii_letters + string.digits + '!#$%&*-?') for _ in range(20)])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
        self.dosend('Give me XXXX:')
        x = self.request.recv(10)
        x = (x.strip()).decode('utf-8') 
        if len(x) != 4 or sha256((x + proof[4: ]).encode()).hexdigest() != digest: 
            return False
        return True
 
    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass
 
    def timeout_handler(self, signum, frame):
        raise TimeoutError
 
    def handle(self):
        try:
            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(30)
            if not self.proof_of_work():
                self.dosend('You must pass the PoW!')
                return
            lfsr = zer0lfsr(random.getrandbits(64))
            for i in range(20):
                keystream = ''
                for j in range(1000):
                    b = 0
                    for k in range(8):
                        b = (b << 1) + lfsr.next()
                    keystream += chr(b)
                self.dosend('start:::' + keystream + ':::end')
            signal.alarm(100)
            self.dosend('k1: ')
            k1 = int(self.request.recv(100).strip())
            self.dosend('k2: ')
            k2 = int(self.request.recv(100).strip())
            self.dosend('k3: ')
            k3 = int(self.request.recv(100).strip())
            if lfsr.key == [k1, k2, k3]:
                self.dosend(flag)
            else:
                self.dosend('Wrong ;(')
        except TimeoutError:
            self.dosend('Timeout!')
            self.request.close()
        except:
            self.dosend('Wtf?')
            self.request.close()

 

Introduction

The three Generators are identical to the first problem. The major differences here is 

• We now have the "majority" of the three output bits from each generators. 
• We now have 160000 bits, but we don't have the SHA256 hash of each key.
• The three keys are related by the "KDF" function, i.e. $key_2 = KDF(key_1)$, $key_3 = KDF(key_2)$.
• We have to find all three keys in 100 seconds to solve the problem.

Of course, the majority function has a 75% correlation with each generator's output bits. 

If we know one generator keystream, we can guarantee about 25% of the other generator keystream bits.

If we know two generator keystreams, we can guarantee about 50% of the other generator keystream bits.

 

A look at the KDF

After having a miserable day with this challenge, barkingdog noted an important property of the KDF function. 

His intuition was that the KDF function was way too complicated for it to be a "random function". Indeed, if we just wanted a random output, we can just return some bits of the SHA256 hash. Also, he noted that the repeated values in the round key and subkeys are suspicious.

These suspicions are indeed valid, as there is a important result on this KDF.

 

Claim : Let $K = K_0 || K_1 || K_2 || K_3$. Assume we know $KDF(K)$.

If we know one value out of $K_0 \oplus K_1$ and $K_2 \oplus K_3$, we can calculate the other value very fast. 

 

To explain this, note that the two round keys in the middle are the same, which means we can recover the XOR value of the two subkeys from $KDF(K)$. The two subkeys are some reversible and bijective transformations applied on $K_0 \oplus K_1$ and $K_2 \oplus K_3$.

This gives a straightforward method to accomplish our objective of the Claim. This result is very strong, and used heavily in my solution. 

 

Let's think about the order in which we are going to solve the problem. 

• If we start from Generator1 and succeed in finding $key_1$, we can just use KDF function to directly finish.
• If we start from Generator3 and succeed in finding $key_3$, we can use the KDF property to make solving Generator2 easier.

Of course, analyzing Generator1 with just 75% correlation seems very difficult, so we have to start from Generator3. 

Therefore, the natural idea is to go from 3 to 2 to 1, utilizing known keys and the KDF property to make things easier each step. 

 

Solution for Generator3

The fast correlation attack solution works here, since we still have nearly 75% correlation to a simple LFSR.

I had some time trying to make this solution stable, as the attack is probabilistic. I ended up doing

• Find 64 bits that have highest probability of being correct, and assume at most one is incorrect.
• We compute all possible values for $key_3$, and calculate the Generator3 keystream.
• If it matches at least 7000 out of the first 10000 given output bits, then we found the key.

Honestly, I'm definitely not the person to ask how to write a reliable fast correlation attack :(

My attack for Generator3 succeeded in about 50% probabilty, and it worked in 8 seconds.

 

Solution for Generator2

From solving Generator3, we have some additional information at our hands, i.e.

• We know around 40000 bits of the Generator1 output, and the same for Generator2.
• We know $key_3 = KDF(key_2)$, so we can use the KDF property, giving easy 16 bits of information.

To solve Generator2, we need two properties of $f_2$ and $h_2$. First, note that $$h_2(x_0, x_1, x_2, x_3, x_4, x_5, x_6) = x_0 x_1x_2 x_3 x_4 x_5 + x_0 x_1 x_2 x_4 x_6 + x_1 x_3 x_4$$ is $0$ for $7/8$ of the inputs. Therefore, we can ignore the $h$ part of the clock output with high probability. Also, we note that $$f_2(x_0, x_1, x_2, x_3, x_4, x_5)$$ which is a very long polynomial defined by array f_OUT, has a linear approximation $$\overline{f}_2 (x_0, x_1, x_2, x_3, x_4, x_5) = x_1 + x_2 + x_5$$ which matches $f_2$ with a $3/4$ probability. This can be found by calculating the nonlinearity of $f_2$. 

 

Therefore, the output of Generator2 is close (matches with significantly higher probability than 0.5) to a keystream generated by a LFSR with the same recurrence. If we find this LFSR keystream, we can find the LFSR part of the $key_2$. The NFSR part of the $key_2$ can be directly derived by the KDF property. To find this LFSR keystream, we use yet another fast correlation attack. To be exact, I did

• I only considered the approximately 40000 guaranteed Generator2 bits.
• I found 32 bits that have the highest probability of being correct, and assumed at most one is incorrect.
• Now we have around $32 \times 2^{16}$ possibilities for the LFSR part of the key.
• Here, the $32$ part comes from assuming one bit is incorrect.
• The $2^{16}$ part comes because the LFSR part is 48 bits, and we know 32 bits of the LFSR output.
• If we know LFSR part of the key, the NFSR part of the key can be computed by the KDF property. 
• For each possible key, we compute the KDF and see if it matches $key_3$. 

My attack for Generator2 succeeded in about 25% probability, and it worked in 20 seconds.

 

Solution for Generator1

From solving Generator2, we have some additional information at our hands, i.e.

• We know around 80000 bits of the Generator1 output.
• We know $key_2 = KDF(key_1)$, so we can use the KDF property, giving easy 16 bits of information.

Here's a rough idea. If we bruteforce LFSR part, using the same ideas as Problem 1, we can get 24 bits of the NFSR part. Also, we have the 16 bits of information from the KDF property. This adds up to 40 bits of extra information. Therefore, intuitively, we can find about $2^{24}$ candidates for the first key. After that, we can test each of them by either calculating the KDF or calculating the Generator1 output, and testing if it matches the guaranteed Generator1 bits. To be more detailed, I did as follows : 

• I bruteforced the 16 bit LFSR part, and this gives approximately 24 bits of NFSR information
• This means we have full $K_3$ and around 8 bits of each of $K_0, K_1, K_2$. 
• We bruteforce the undecided bits of $K_2$. Now we know $K_2 \oplus K_3$, so $K_0 \oplus K_1$ as well.
• We know around 16 bits of $K_0, K_1$ in total, and we know $K_0 \oplus K_1$.
• This is enough to get a small number of candidates for $K_0, K_1$. 
• In total, this is around $2^{24}$ level of bruteforce to find all candiates. 

I did this in C++ with 10 cores. I checked the validity of each key by testing if the Generator1 output matches the guranteed bits. 

My attack for Generator3 succeeded in about 20% probability because the code had to run in time. I set a timeout of 60 seconds.

 

Overall, my code found the 3 keys in about 25 trials, but I made a dumb programming mistake, forcing me to fix and try again.

The next time, the code found the 3 keys in about 90 trials, and I got the flag. I think the code works in about 2~3% probability.

 

Problem 3 : zer0lfsr++ (1 solve)

 

class zer0lfsr:
    def __init__(self):
        self.key = [random.getrandbits(64), random.getrandbits(64), random.getrandbits(64)]
        self.g1 = Generator1(n2l(self.key[0], 64))
        self.g2 = Generator2(n2l(self.key[1], 64))
        self.g3 = Generator3(n2l(self.key[2], 64))
 
    def next(self):
        o1 = self.g1.clock()
        o2 = self.g2.clock()
        o2 = self.g2.clock()
        o3 = self.g3.clock()
        o3 = self.g3.clock()
        o3 = self.g3.clock()
        o = (o1 * o2) ^ (o2 * o3) ^ (o1 * o3)
        return o
 
class Task(socketserver.BaseRequestHandler):
    def __init__(self, *args, **kargs):
        super().__init__(*args, **kargs)
 
    def proof_of_work(self):
        random.seed(urandom(8))
        proof = ''.join([random.choice(string.ascii_letters + string.digits + '!#$%&*-?') for _ in range(20)])
        digest = sha256(proof.encode()).hexdigest()
        self.dosend('sha256(XXXX + {}) == {}'.format(proof[4: ], digest))
        self.dosend('Give me XXXX:')
        x = self.request.recv(10)
        x = (x.strip()).decode('utf-8') 
        if len(x) != 4 or sha256((x + proof[4: ]).encode()).hexdigest() != digest: 
            return False
        return True
 
    def dosend(self, msg):
        try:
            self.request.sendall(msg.encode('latin-1') + b'\n')
        except:
            pass
 
    def timeout_handler(self, signum, frame):
        raise TimeoutError
 
    def handle(self):
        try:
            signal.signal(signal.SIGALRM, self.timeout_handler)
            signal.alarm(5)
            self.dosend('Input the flag of zer0lfsr+: ')
            guess = self.request.recv(100).strip()
            assert guess == flag_plus
            signal.alarm(50)
            if not self.proof_of_work():
                self.dosend('You must pass the PoW!')
                return
            lfsr = zer0lfsr()
            for i in range(20):
                keystream = ''
                for j in range(1000):
                    b = 0
                    for k in range(8):
                        b = (b << 1) + lfsr.next()
                    keystream += chr(b)
                self.dosend('start:::' + keystream + ':::end')
            signal.alarm(180)
            self.dosend('hint: ')
            idx = int(self.request.recv(10).strip())
            assert idx in [0, 1, 2]
            self.dosend(str(lfsr.key[idx] >> 48))
            self.dosend('k1: ')
            k1 = int(self.request.recv(100).strip())
            self.dosend('k2: ')
            k2 = int(self.request.recv(100).strip())
            self.dosend('k3: ')
            k3 = int(self.request.recv(100).strip())
            if lfsr.key == [k1, k2, k3]:
                self.dosend(flag)
            else:
                self.dosend('Wrong ;(')
        except TimeoutError:
            self.dosend('Timeout!')
            self.request.close()
        except:
            self.dosend('Wtf?')
            self.request.close()

 

Introduction

The change from lfsr+ to lfsr++ is

• The three keys are independent of each other, so no KDF property to exploit.
• We can ask for the first 16 bits of one of the three keys.
• We have more time, 180 seconds instead of 100 seconds

It's clear that Generator3 can be solved in the exact same way. The problem is Generator2 and Generator1.

 

Solutions and Thoughts

 

Assume we use the hint on Generator2. Then we can get the NFSR part of the key. 

Therefore, it's clear that the solution from Problem 2 works in this challenge as well. 

Of course, we need to check the validity of the key differently (instead of using KDF) but this is not hard. 

We can just check if the Generator2 output matches the guaranteed Generator2 bits. 

 

If we use the hint on Generator2, we have nothing to use on Generator1, other than around 80000 bits of Generator1 guranteed.

This can be solved in two ways, as shown by the author and the only solver hellman : 

• The author used the methods in https://www.iacr.org/cryptodb/archive/2006/FSE/3235/3235.pdf.
• hellman used z3 to recover the first key. z3 is indeed very powerful...

 

I thought about using the hint on Generator1 (which makes solving Generator1 relatively the same) and optimizing the fast correlation attack for Generator2, making it more reliable. For example, if I could find 48 bits that I can guarantee with high probability, allowing at most one mistake, I would be able to solve the problem. I was able to get 43 out of 44 bits correct, giving a complexity of around $44 \cdot 2^{20}$, which may be feasible. However, according to the author, the NFSR part of the key may not be uniquely determined. Therefore, this approach leads to a solution that is both slow (but probably within time limit with sufficient computational power) and has low success rate.

I was tired staying up all night solving lfsr+ and I didn't have a lot of time, so I did not implement my approach. 

 

Looking back, if I had just decided to use z3 on Generator1, I think I would've solved it. I need to practice using z3...