Babylfsr writeup

　　一道很有意思的 lfsr 题。给了一个 task.py 如下：

import hashlib
from secret import KEY,FLAG,MASK

assert(FLAG=="de1ctf{"+hashlib.sha256(hex(KEY)[2:].rstrip('L')).hexdigest()+"}")
assert(FLAG[7:11]=='1224')

LENGTH = 256

assert(KEY.bit_length()==LENGTH)
assert(MASK.bit_length()==LENGTH)

def pad(m):
    pad_length = 8 - len(m)
    return pad_length*'0'+m

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**(length+1)-1

    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output


if __name__=="__main__":
    l = lfsr(KEY,MASK,LENGTH)
    r = ''
    for i in range(63):
        b = 0
        for j in range(8):
            b = (b<<1)+l.next()
        r += pad(bin(b)[2:])
    with open('output','w') as f:
        f.write(r)

　　另外给了一条信息：

001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010

　　分析程序，是一个很普通的 lfsr，但是我们初始状态和掩码都不知道，需要利用出题人给定的 504 个 bit 的信息，推出这所需的 MASK、KEY 一共 512 bit 的信息。

　　先考虑如何推出掩码。由于 lsfr 的性质，每一次生成的 bit 都会加到向量的最低位，同时丢弃掉最高位那个 bit. 于是在连续 256 次生成之后，原有的 KEY 所有的位都被丢弃，lfsr 的状态会转为我们已知的 256 个 bit —— 也就是题目所给出的串的前 256 位。从此之后，我们完全知道了 lfsr 的状态，只需要在已知状态的情况下推出掩码了。

　　每连续 256 个 bit 可以生成下一个 bit. 我们知道这 256 个 bit，也知道下一个 bit，但我们不知道掩码。目前面临的问题与下面的任务等价：在 $GF(2)$ 上，256 位的已知的状态向量，点乘上 256 位的掩码向量，得到的数已知。现在求掩码向量。

　　上面是一个方程；而状态向量有 256 维，我们需要 256 组方程才能解出整个掩码向量。但我们现在只有 504 - 256 = 248 个方程可用，显然秩是不够用的。容易想到，直接猜测 lfsr 此后生成的 8 个 bit，于是就有 256 组方程了；当然求出的答案只有一条是正确的，我们最后会用题目脚本给出的 sha256 条件逐一检验。

　　解方程组的问题可以转化为矩阵求逆的问题。把 lfsr 的状态一行一行地写在矩阵上，形成的矩阵记为 $M$. 把 lsfr 每次所生成的结果也拼成一个向量，记为 $T$. 那么掩码向量 $v$ 使得：$$M \cdot v = T$$

　　于是两边左乘 $M ^ {-1}$，可以得到掩码向量：$$v = M ^ {-1} \cdot T$$

　　爆破掩码的脚本如下：

def test(padding):
    s = [int(x) for x in '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'] + padding

    M = matrix(GF(2), 256, 256)
    T = vector(GF(2), 256)

    for i in range(len(s) - 256):
        M[i] = s[i : i + 256]
        T[i] = s[i+256]
    try:
        mask = M.inverse() * T
        print(hex(int(''.join(map(str, (mask))), base=2)))
    except:
        return
    

for x in itertools.product([0, 1], repeat = 8):
    test(list(x))

　　接下来考虑求出初始状态 KEY. 我们目前有的东西是：（猜测的）连续 512 个 lfsr 输出，以及与之对应的掩码。注意到第 256 个输出，是由 KEY 的末位，拼接上前 255 个输出所形成的；第 255 个输出，是由 KEY 的倒数两位，拼接上前 254 个输出所形成的。我们可以先求出 KEY 的末位，再求出倒数第二位……以此类推，整个 KEY 就求出来了。

　　完整的代码如下：

import itertools, hashlib, numpy as np

def int2bin(a, n):
    assert 0<=n and a < 2**n
    res = np.zeros(n, dtype = int)

    for x in range(n):
        res[n-x-1] = a % 2
        a = a // 2
    return res.tolist()

def bin2int(a):
    return reduce(lambda x,y: x*2+y, a)

def bitAnd(a, b):
    assert len(a) == len(b)
    return list(map(lambda x,y: int(x)&int(y), a, b))
    
def test(padding):
    s = [int(x) for x in '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'] + padding

    M = matrix(GF(2), 256, 256)
    T = vector(GF(2), 256)

    for i in range(len(s) - 256):
        M[i] = s[i : i + 256]
        T[i] = s[i+256]
    try:
        mask = M.inverse() * T
    except:
        return

    suf = []
    for i in range(256):
        if bitAnd([0] + suf + s[0:255 - i], mask).count(1) % 2 == s[255 - i]:
            suf = [0] + suf
        else:
            suf = [1] + suf

    key = hex(bin2int(suf))[2:]
    sha = hashlib.sha256(key.encode()).hexdigest()
    
    if sha[:4] == '1224':
        print('de1ctf{' + sha + '}')
    

for x in itertools.product([0, 1], repeat = 8):
    test(list(x))

　　于是得到了 flag: de1ctf{1224473d5e349dbf2946353444d727d8fa91da3275ed3ac0dedeb7e6a9ad8619}