[De1CTF2019]Babylfsr

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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

题目给出了504bits的output，可惜的是连掩码mask都是未知的。所以首要任务是求出掩码mask。考虑矩阵求解，建立256×256的init矩阵A，以及256×1的output矩阵C，显然需要512bits的output，故尝试遍历后8bits的情况。代码如下：

import hashlib 
from itertools import product

cipher = '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'

for maybe in product([0, 1], repeat = 8):
    A = Matrix(GF(2),256,256)
    C = Matrix(GF(2),256,1)
    output = [int(i) for i in cipher] + list(maybe)
    
    for i in range(256):
        A[i] = [int(each) for each in output[i:i+256]]
        C[i] = [int(output[i+256])]
        
    try:
        #mask = A.inverse()*C
        mask = A.solve_right(C)#两种方式求出来的结果不尽相同，所以这个原理到底是什么呢？
        mask = [int(mask[i][0]) for i in range(256)]#得int化
        
    except:
        pass
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

接下来就是简单的还原过程，通过后生成的255bits的output推出前1bit的output或key。

(从阮师傅博客中看到了更简洁的方法😋，之前遇到的是32bits的mask，就直接挑出里面为1的位😂)

import hashlib 
from itertools import product

cipher = '001010010111101000001101101111010000001111011001101111011000100001100011111000010001100101110110011000001100111010111110000000111011000110111110001110111000010100110010011111100011010111101101101001110000010111011110010110010011101101010010100101011111011001111010000000001011000011000100000101111010001100000011010011010111001010010101101000110011001110111010000011010101111011110100011110011010000001100100101000010110100100100011001000101010001100000010000100111001110110101000000101011100000001100010'

for maybe in product([0, 1], repeat = 8):
    A = Matrix(GF(2),256,256)
    C = Matrix(GF(2),256,1)
    output = [int(i) for i in cipher] + list(maybe)
    
    for i in range(256):
        A[i] = output[i:i+256]
        C[i] = output[i+256]#[]
        
    try:
        #mask = A.inverse()*C
        mask = A.solve_right(C)#两种方式求出来的结果不尽相同，所以这个原理到底是什么呢？
        mask = [int(mask[i][0]) for i in range(256)]#得int化
        
        key = []
        for i in range(256):
            init = [0] + key + output[0:255-i]
            res = [init[k] & mask[k] for k in range(len(a))]
            if res.count(1)%2 == output[255-i]:
                key = [0] + key
            else:
                key = [1] + key
        
        key = hex(int(''.join(str(i) for i in key),2))[2:]
        sha = hashlib.sha256(key.encode()).hexdigest()
        if sha[:4] == '1224':
            print('de1ctf{' + sha + '}')
    except:
        pass
#de1ctf{1224473d5e349dbf2946353444d727d8fa91da3275ed3ac0dedeb7e6a9ad8619}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

---

参考：

Babylfsr writeup (ruanx.net)