SUSCTF - Ez_Pager_Tiper

Ez_Pager_Tiper

分析magic_box中的代码，测试发现malicious_magic中的now = (-magic & magic)的值取决于magic二进制末尾0的个数，即$now = 2^{二进制末尾0的个数}$，进而每次执行该函数，magic的二进制中最后一个1改为0，故confusion函数中的循环次数为magic二进制中的1的个数。

再来看看confusion循环中的output的值。由于每次now都等于magic二进制中最后一个1及后面部分，于是乎在循环结束后
$$
\begin{align}
output &= output \oplus now_1\oplus now_2\oplus …\oplus now_n
\\&= output \oplus magic(最初始)
\\&=magic(最初始) \oplus c1 \oplus c2 \oplus magic(最初始)
\\&=c1 \oplus c2
\end{align}
$$
而每次循环中cnt ^= 1，故循环次数为偶数时（magic二进制中1的个数为偶数个）cnt = 0，反之则cnt = 1。

循环完后output ^= cnt * c1，故循环次数为偶数时output = c1^c2，反之则output = c2。

根据上述分析可得problem1的加密简化为ch ^ c2，problem2的加密简化为ch ^ c1 ^ c2。

通过已知的部分文段可以分析文本格式以Date: yyyy-mm-dd作为开头，日期信息由文件名称b64decode得到。利用已知明文密文对，可以恢复lfsr的内部状态。

problem1

在problem1中由于n2 = 12，可以对mask2进行爆破，求出mask2后可以反推出（或爆破）seed2，于是就可以解密出对应的文本。

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
from Crypto.Util.number import *
from magic_box import *

n1, n2 = 64, 12

with open('MTk4NC0wNC0wMQ==_6d30.enc','rb') as f:
    cipher1 = f.read()

date1 = 'Date: 1984-04-01'#少了个空格，淦！一个晚上就这么没了
known_output = ''
for i in range(len(date1)):
    bit8 = ord(date1[i]) ^ cipher1[i]
    known_output += bin(bit8)[2:].zfill(8)

#爆破mask2(12位bit)
mask2 = 0
for mask in range(4096):
    output = 0
    lfsr2 = lfsr(int(known_output[:n2],2), mask, n2)#known_output[:n2],否则就拿低位去&了
    for i in range(len(known_output) - n2):
        output = (output << 1) ^ lfsr2.next()
    if output == int(known_output[n2:],2):
        mask2 = mask
        print(f'mask2 = {mask2}')
#爆破seed(12位bit)
seed2 = 0
for seed in range(4096):
    output = 0
    lfsr2 = lfsr(seed, mask2, n2)
    for i in range(len(known_output)):
        output = (output << 1) ^ lfsr2.next()
    if output == int(known_output,2):
        seed2 = seed
        print(f'seed2 = {seed2}')

lfsr2 = lfsr(seed2,mask2,n2)

txt1 = ''
for i in range(len(cipher1)):
    txt1 += chr(lfsr2.getrandbit(8) ^ cipher1[i])

print(txt1)

结果如下

1
2
3
4
5
6
7
mask2 = 2053
seed2 = 2989
Date: 1984-04-01
The pursuit was renewed, till the water was again muddied.  But he could not wait.  He unstrapped the tin bucket and began to bale the pool.  He baled wildly at first, splashing himself and flinging the water so short a distance that it ran back into the pool.  He worked more carefully, striving to be cool, though his heart was pounding against his chest and his hands were trembling.  At the end of half an hour the pool was nearly dry.  Not a cupful of water remained.  And there was no fish.  He found a hidden crevice among the stones through which it had escaped to the adjoining and larger pool—a pool which he could not empty in a night and a day.  Had he known of the crevice, he could have closed it with a rock at the beginning and the fish would have been his.
Thus he thought, and crumpled up and sank down upon the wet earth.  At first he cried softly to himself, then he cried loudly to the pitiless desolation that ringed him around; and for a long time after he was shaken by great dry sobs.
He built a fire and warmed himself by drinking quarts of hot water, and made camp on a rocky ledge in the same fashion he had the night before.  The last thing he did was to see that his matches were dry and to wind his watch.  The blankets were wet and clammy.  His ankle pulsed with pain.  But he knew only that he was hungry, and through his restless sleep he dreamed of feasts and banquets and of food served and spread in all imaginable ways.
He awoke chilled and sick.  There was no sun.  The gray of earth and sky had become deeper, more profound.  A raw wind was blowing, and the first flurries of snow were whitening the hilltops.  The air about him thickened and grew white while he made a fire and boiled more water.  It was wet snow, half rain, and the flakes were large and soggy.  At first they melted as soon as they came in contact with the earth, but ever more fell, covering the ground, putting out the fire, spoiling his supply of moss-fuel.

problem2

由于lfsr2中的n2 = 12，故对seed3进行爆破，根据得出的lfsr2流推出lfsr1流。进而恢复seed1和mask1。从而对加密文本解密，筛选出flag。

（嗯！这个BM算法还没搞懂，贴一下别人的代码，from DengFeng）

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#sage
from base64 import *
import libnum
n1, n2 = 64, 12

class lfsr():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^^= (i & 1)
            i = i >> 1
        next_state ^^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^^ self.next()
        return output

def get_key(mask,key,degree):
    R = ""
    index = 0
    key = key[degree-1] + key[:degree]
    while index < degree:
        tmp = 0
        for i in range(degree):
            if mask >> i & 1:
                # tmp ^= int(key[255 - i])
                tmp = (tmp+int(key[degree-1-i]))%2
        R = str(tmp) + R
        index += 1
        key = key[degree-1] + str(tmp) + key[1:degree-1]
    return int(R,2)

def get_int(x,degree):
    m=''
    for i in range(degree):
        m += str(x[i])
    return (int(m,2))

def BM(r,degree):
    a=[]
    for i in range(len(r)):
        a.append(int(r[i]))       #将 r 转换成列表a = [0,0,1,...,]格式    
    res = []
    for i in range(degree):
        for j in range(degree):
            if a[i+j]==1:
                res.append(1)
            else:
                res.append(0)
    sn = []
    for i in range(degree):
        if a[degree+i]==1:
            sn.append(1)
        else:
            sn.append(0)
    MS = MatrixSpace(GF(2),degree,degree)        
    MSS = MatrixSpace(GF(2),1,degree)         
    A = MS(res)
    s = MSS(sn)                       #将 res 和 sn 的值导入矩阵空间中
    try:
        inv = A.inverse()            # 求A 的逆矩阵
    except ZeroDivisionError as e:
        return -1,-1
    mask = s*inv 
    return get_key(get_int(mask[0],degree),r[:degree],degree),get_int(mask[0],degree)

seed2 = 2989
mask2 = 2053

date2 = b'Date: 1984-12-25'
cipher2 = b'\x18\xff\xa57\xa65"\x00\xfd/\x8d\x06\xe7z\xa4\xe6\t$\xec\x94$`\xaalB\xb6\x90`\x9e\'7\x9f\xcca\xaa1\x96\x19\t\xa2\xb8U\xde\xc5\xa0\xc7\xd23\xcd\xa0\xafRHP\x90\x8a\xa9M\x17@\xef8:]\xe1\xdc\x10\xad\xdfI\x04=\x01\x82\x1a\xec\x1e\x19\xdaV\x95\xc1K\x86\xfdZ\x90O7r\xeeZCewY8\xf1\x80\x81\x16NC\x94\xb0\xa0<\xd5\xc9\x1a\xeb.\xf6\xaa\xbb\xa6\x9a<t\xce\xdcQ$\xfdK\x89v\xee\xe0\x9dc\x9b6\xe6\xf0\xc9\xb6[l\xd3\xdc\xf8\n\xb7\xc6\xf9^\x0eIr\'>\x1dD!\x83\xfd\xc6Q\xf9\xce\xee%\xa7l\xb9\xfc\xcc\xf9;\x0b\x04\xce\x07\x97\xae\xf5C\xa5\x96\xfeU\xe8\xfb\x06\x96\xe3Dr\x8a\xc8\xb7\xa0\xe4s\xe3\xac\x9dT\t\x0eL*Vys\x03\xbb\xf2$\xa8pR\x8c\xa8h\xf6\x04<I4@}\xe5\x12\x8d\x14\xbe\xe4\xb1\x86V`\xcf\x9bE\x8e\xf0m\xbd\xedP\xe3\xafo7\xbd\xb1\xb9R\x9a2*\xaabz@\xb2\xf9\xf59c\xf9\x13\xf12\x8b\xc2z\xda\xf4\x87\x130\xc2\x93\xf3\xce\x84\xe8q.\x01\xeec\xb1\x10X\xcd\x00\x91%\xb7|yW\xf2\xc4\xb3\x997\xc1\xb45\xe5)K \xfc\x93\x04\xee-\xf9\xc3\x06Js\xe1\tZ\x86=k8:\x17\x9e}\xb1$\xce\xaa\xbc\x05\x97d\x83c~\xf57\x02\x08\xa2\tHz\xecq\x07Y\xe6}\xf8\xf0\xaa\x00\x1e\x12f\xf5\xab\xf62u\x12\xf5\xcfx\xc3)B\xd4\xd1\x9dxX\x0b#\x9f\xf1\xa0"\xb9M\xe9\xcf\x17\xc9\\\xbf\xf3y\xb1E\xc0\xa1\x88\x83\x95\xa6\xc9\xde=Md\xaf\xb4\x14\x815;\x18X\x9bQ2\x86\xa0`x{\x18\xde\xean\xcd\xc3*y\x82\x8c\xe4l\x88\x96\xb7\x0e\x03u\xe7\xe8."!\xfb\xb1Bg\xea\xa2`\x99\xab\xa4d\xedA\x0e\x86\xd5\xaf5D\'\xcd3\xbf\xcd5\xb4\xc3^\xfe\x14t\x90\xf9\x01\x98\xd5~s\xdc\xa7\xb1\x8d\xf6\xd9\x92\xb9\xe0\x996?\x8f\\\x1d\xb2\x12\x97\xf6\x07;\xfaTL\x92.\xaf\x16$\xfa\x94\xcb0\xbf\x8a\xad](\xc6}K\xc87\xfc\xc9\xc6\xdb\x08\x99\x9f(<\x1e\x97\xe1\x00^\x13]\x16\xe13\xee\xebS1h\xdd\xe11n\x1a\xe6\x12\x01\xb5\x0c|\xf5\x8a\xbd=5S\xe4\xf9$\xf1\xedp\xce\x1f\x96.\x97\xe4;\x02 \x17&\xd7\xd9*\x1f\xa4u\xe6\xad\xfd\xbaIR\x1f\x1a=F\xbf\xf3\x07\x19!=\xf7\xd8/\xe4i\xc6+\x9c5^t\x7f\xb2\x06\xe8\xf2\xac=\x16\x00r\xdd\x7f\xe34w\xde)\x86\x82\xb6gj\xf4\xfa\x18Pd\xd9\x82\xcd\xda\xee\x8bv\xd1NKu\\\x04\xe2\xbbt\x94\x82\x11\xc9\x1d\xdd\xb1\xb5\x8c\x86\xbfg\xa8L\x1eI\xb4\xddF\x8b\xa7\xd1\x16\x9c\x80\x94UXS\x13\x91\xf8\xe6=\x15\x16\x9a,\x0b8\xd2\xfeE\xa04"\xaa1}\xc7\x93\x9f\xb2%p\xb4\x01\x17r*\xd5\xc6\xfd\xfb\xb0<\x18j\x86\xab\xe0\x17\xf2R\xdfZ\xc3Ty\xe9\xd2j\x8b\x15\t\xabrHwi~1K\x89\xebVZ\xec}\x1av\xc5\x90\xb7\xa5$k\xd3"\x05\xfa\xc6\x1d\xfe\xb5\x9e;#ig\xdd\xa3\x9b.[\x96\xf1r\x01D\xe7\xdeqkj%\x9cvU\xec\x04\xb0\xab\x9e4\x13\xd7\x07\xa8\xcarK<-\xd1x\xb7|\xdf\xc5c\x13R\xd9\x1b\xd8\xa0=F\xbc9\xf2\x8c\xfc\xe8KO\xb6bfv\xaf\xb3\x9c\xa4\x1f(\xc4O\xa9\x0f]x\x832\x89\xd9\xc77\x1fa0\xe4\xac\xa7AA\xc4\x14\x9cm\xd5\xf0\x02\xb4\x9c(ej\xdb\x88U\xa7!+\x83]N\xee\x8c\x87*\x84W\x12$\xfc\x0eEC\xcb\x14\x88\x1eEr\x12N\x8fY\xd6\x18\x8b^\x98z\xbf\x84\xc1\xc8!\x8a\x1a\xaaQ\x89aP\xadL\xa4w\xda\xb9WN\x90\xe1\x9e\xcf\x1fx\xc7\x84\xf4\x0f\x9a8Q\xcc-\xbasuc0\x988\xf8"\xecmFeI?\x13m1\x11D\xe3l\x0b\x16\xf7\xa4\x05[\xd0\xeac\x16\xc6\n`\xcf\xbcf\xda\xc6\xf8n\xbc\xea*\x857n\xb2\x91\x12#\xe0\xf9\x12\xc3\x83\x8f\xfb\x1b\xb2\xd8\xf6\x1fmwC\xaa\x8b\xaeV\xabQ\xd3\xe2\xd6\x1e\xf1u\xc5\xfd\x8a\xf7rw\'\x12\x95\x9dl:o\r\r\x13\xf9\x02\xab\'.{\xc0b\x9f\xc1.\xde\xeb\xce\xf1Cd\xbf\xdfOAMi\xc3\x96bhC\xc7\xa6\x1ch\x06X\xed\xafR\xda\x80\xee \x1c=\x92\xf9&\x8b\xbf\x7f\xf1^k[\x94\xd26C\xfe\x1fY16\xc8Q\x9f7`\xc1\xf8D_\xef\xbb$L>R)\xef\xd7\xf5\r\x91\x17@\x8dZ\xa0\x81\x8a<F+\x8d\xd5\n5/\x10\x0ed\xb4\xc1\xc0\xb8a\xe5\x81\x85}\x0f2\x90\xa4\xaeg\xb7\xe8#\xe85h"?\x90\x99\x7f\xe46\xf7y\xe1o\x1e5\xe6o\xda?!\xeb\xc2\x98\xcf\x98\xb0\x15\x01]E\xa5V\x032\xaa\x16\x83K*\xe3$\xcb\xfc\xe6\xb4\x8f\xa2\xa7\x900\x04G\xd8\x95\x98$\x9fN~\xb1\xa7\x0c\x8bGd\xa6\xa7\xe0F\xdd\xa2\xfbU\x9bE\xdc\x025\x1e\xfe\xc5v#\xb1Ft\xc1\x9c\x909\xd9\xb8\xe1h\xc1G*\x02c\xe5\xc7\x91q\x86/\xab\xfaS\xb9Tk\x90\xcc\x07\xb1\xa3E\x11e\x95fw\x02\xbfF\xb7j\x82\r\x92hD\x92\'FD\xb9\x9b\x0c\xc4%\xb6>:\x1cZ \xc7\x1b\xa9\x15h[\xff?\x88\xcd\xbb\xe5\xf6\xb3\xb6B\xac\xda\xcd\xa7h\x81 \xcd\xeeu@\xef\x92!\xe2Vr+\x1d\xa6\x83Z\xdb\xb7\x1a\xd7#$)\xf1\x1f\x82\xdd\x80A\x94W\xf4\xa1\xe7J$\xda\x02\xd4\xb6\xe5\x84\xbegH\xb9\xc2\xe3\x82\xc5\xfd\xb1\xe7!\xeb\xe0\xd1J\x94\x04\x7f\x81\xee\xafn\xe3\x0e;\x17\xb6\x18\x9e;\xca\xb6`\x89\xd0\'\x87\xff\xcc \xf4yW#*j\x00ad\x9f.5/\xfc\tx1\xa6\xf7V.]\xfa\xec\xc9\x93\x87\x9a;\xb4\xe0\x0eC\x98<5\x14a\xb1c\xaa\x91\x08O\xbaIz*Y\xf0\t\x8e\x96\x92\xa8\x0b\xeb\xa7\xdep\xa2zl\xd6_\x05%\x96\xda\x9e"\x80\xeb\xf2bc\xfb\t\x1a\xe2h\xd1\x00tb|M\xf6\xd7\xc4.\xb5\xb1\xe3a\xa1\x96\x08\x9f\xa6:\xa8\xccouN^#fq\x03\xcan\x8cRJD6&\n\xda\xe0T\xf5\x18\xfcp\xcd\x8f`\xdcS\x10\x00;\xd2\xb2\x14\xbd\xe4xa\x88v\x03p\x83\xdeL\xb0\xa0\xe8D\x04\xdd~\xa0\xacR\xc6 \xe0\x83t\xbf\xbf\x1d#\xc4`\xbe\xc6\xd7\xf9Z\x08\x88Tm\x81\xd6f*\xdc\x13\x0e\xc7\xae-\xadSmQ\x02y\xa4.\xbe\x8b\xf4\xe7\x9c\xbd\xdc5\xc3\x98{Qw\xba\xeb\xf5\xc6jMy\xcaj\xd5\x01L8<c\xf0k\xd6p\xe7\x1cz\xffW72\xd3>Q\xe1\xab\xc3\x87tTW\xfdb\x88\x07Xu\xf8V\x92\x8e-\xffG\x80j\xd0/\x0e\xe1?W\x8f\xe7\xd2A\x80L\x19d\xce\xd0\xd4]\x00\x92\xde\xb9\xb3|\xda\x13mLQ_4\xbb1\xd3w\xa3f&\xd4=\xd6~/=\x83U\xb6W\xc7\x95\x95\x05\xcb\xe3\xde\xc1\x15\xc9\x9bB\xce\tH\\z\xc1\xf3c\xc1v\xca\xbd\x06,\xea\n\x03\x1b\x12!C\xefj\x97\x96K\x07O\xa9\x98\xca\t\x1e\xd9\xc5\x98=\x9cq\x80\xd0\xba?`\x14\x91\x8c\xa9\xab\x83\\\xa6\xb5>zq\xed\xc68\x0b\xba\xed\xda\xb2N\xfbI\xde\x8d\xb7\x1fu\xce\xf0[D\x9a\x8cW\xea\xd4\xebGz}\x81\xd4\xf4\'N\\\xceW\x96:E\x06\xed\xd3\x06\xf8\x18d\x9e\x0edW\xdcb\xe1\xea\x1c+I\xf8\xdc\xd4\xda\\r~\x96\xb9?yd\xd9\xb7}\xfb\x9ek\x85\xa84h\xf9\x8b\'(\xa9\xb4S\x87\xc7\x87\xa7\xf1\xdaIy\x95D\xfe\xe3\x90\xf0\x08\xf3\xfc\x00\x8e\x81\xc2k\xb8a3\xc1}@\x8d\\\xf9T\xfc\xb0J\xeb\x8f\x99\xc9~\x95_\x14\xdde\x1c\xaf\xbeG\xd8\xdc\x99))\xb5\x8f\xdd\xdc\x06O~(\x0c\xa1\x1d\xa5c4\xf9=~Z\xc2\xea5G\xed\x10\x85S\x00~\x0c*\x14$\xcb\x0b\x08$0\x89\x1e\xd6Qq\x81\x18_\xb0\xc9o\x81,_\x9c\xcfi\xb7\x86\xf1\xbd\xa8\xa2N\x84@~\xaf.\x9f\x89\xbd/\xc3n\xcd\xf1\xc0\x83\xbaQ\xe1,\x9c6"p]\xb5\xae\x835\xd1\xb6m\xe7M0&q\xb3\x91S\xd0o\xdbF\xbc<\x17{eP6\xc3c\x7fR\x9a\xacWd3?\xb6joQ\x1d\xb2_\xc1\x9d`\xb8\x08!\x97\xc3z3Y_\xb8@\x88\xecc\r\xc1\xb7y\x80'
bits =''
for i in range(len(date2)):
    tmp = bin(cipher2[:len(date2)][i]^^date2[i])[2:].zfill(8)
    bits += tmp

for seed3 in range(1<<n2,0,-1):
    lfsr2 = lfsr(seed3,mask2,n2)
    output2 = ''
    for j in range(len(date2)):
        tmp = lfsr2.getrandbit(8)
        output2 += bin(tmp)[2:].zfill(8)
    output1 = int(bits,2)^^int(output2,2)
    output1 = bin(output1)[2:].zfill(128)
    seed1, mask1 = BM(output1,64)
    if seed1 == -1 and mask1 == -1:
        continue
    lfsr1 = lfsr(seed1,mask1,n1)
    lfsr2 = lfsr(seed3,mask2,n2)
    flag = ''
    for i in cipher2:
        temp = i^^lfsr1.getrandbit(8)^^lfsr2.getrandbit(8)
        #flag += libnum.n2s(int(temp))
        flag += chr(temp)
    print(seed3)
    if 'SUSCTF' in flag or 'CTF' in flag or 'ctf' in flag:
        print(flag)

'''
seed3 = 3054
Date: 1984-12-25
Though the hunger pangs were no longer so exquisite, he realized that he was weak.  He was compelled to pause for frequent rests, when he attacked the muskeg berries and rush-grass patches.  His tongue felt dry and large, as though covered with a fine hairy growth, and it tasted bitter in his mouth.  His heart gave him a great deal of trouble.  When he had travelled a few minutes it would begin a remorseless thump, thump, thump, and then leap up and away in a painful flutter of beats that choked him and made him go faint and dizzy.
In the middle of the day he found two minnows in a large pool.  It was impossible to bale it, but he was calmer now and managed to catch them in his tin bucket.  They were no longer than his little finger, but he was not particularly hungry.  The dull ache in his stomach had been growing duller and fainter.  It seemed almost that his stomach was dozing.  He ate the fish raw, masticating with painstaking care, for the eating was an act of pure reason.  While he had no desire to eat, he knew that he must eat to live.
In the evening he caught three more minnows, eating two and saving the third for breakfast.  The sun had dried stray shreds of moss, and he was able to warm himself with hot water.  He had not covered more than ten miles that day; and the next day, travelling whenever his heart permitted him, he covered no more than five miles.  But his stomach did not give him the slightest uneasiness.  It had gone to sleep.  He was in a strange country, too, and the caribou were growing more plentiful, also the wolves.  Often their yelps drifted across the desolation, and once he saw three of them slinking away before his path.
The content is an excerpt from Love of Life, by Jack London. The problem is mainly about LFSR and I've tried not to make it hard (with the cost of some running time, actually). Your flag is SUSCTF{Thx_f0r_y0uR_P4ti3nce_:)_GoodLuck!_1bc9b80142c24fef610b8d770b500009} and I hope you will enjoy our game. You'll find this problem so ez while solving other problems, which is created by --.
'''

参考：

[SUSCTF2022_official_wp/Ez_Pager_Tiper wp.md at main · susers/SUSCTF2022_official_wp (github.com)](https://github.com/susers/SUSCTF2022_official_wp/blob/main/crypto/Ez_Pager_Tiper/Ez_Pager_Tiper wp.md)

[SUSCTF-Crypto方向所有赛题 - Love_DengFeng’s Blog](https://love-deng-feng.top/2022/03/02/Writeup of SUSCTF/)

Crypto
#Crypto #流密码
SUSCTF - Ez_Pager_Tiper
http://example.com/2022/06/28/CTF/Ez_Pager_Tiper/
作者
gla2xy
发布于
2022年6月28日
许可协议