有事可直接私信＋Q 3431550587
首先，最主要的两个附件如下：
problem.py:
from Crypto.Util.number import *
from magic_box import *
from secret import mask1, mask2, seed1, seed2, seed3
n1, n2 = 64, 12
flag = 'SUSCTF{***}'
def encrypt(cipher, ipath, opath):
ifile=open(ipath,'rb')
ofile=open(opath,'wb')
plaintext=ifile.read()
for ch in plaintext:
c=ch^cipher.getrandbit(8)
ofile.write(long_to_bytes(c))
ifile.close()
ofile.close()
def problem1():
r = getRandomInteger(6)
magic = 1<<r
lfsr1 = lfsr(seed1, mask1, n1)
lfsr2 = lfsr(seed2, mask2, n2)
cipher = generator(lfsr1, lfsr2, magic)
encrypt(cipher, "MTk4NC0wNC0wMQ==_6d30.txt", "MTk4NC0wNC0wMQ==_6d30.enc")
def problem2():
magic = getPrime(64)
lfsr1=lfsr(seed1, mask1, n1)
lfsr2=lfsr(seed3, mask2, n2)
cipher = generator(lfsr1, lfsr2, magic)
encrypt(cipher, "MTk4NC0xMi0yNQ==_76ff.txt", "MTk4NC0xMi0yNQ==_76ff.enc")
# flag in it?
print(f'hint={magic}')
# hint = 15193544052573546419
problem1()
problem2()
magic_box.py:
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
class generator():
def __init__(self, lfsr1, lfsr2, magic):
self.lfsr1 = lfsr1
self.lfsr2 = lfsr2
self.magic = magic
def infinit_power(self, magic):
return int(magic)
def malicious_magic(self, magic):
now = (-magic & magic)
magic ^= now
return int(now), int(magic)
def confusion(self, c1, c2):
magic = self.magic
output, cnt = magic, 0
output ^= c1 ^ c2
while magic:
now, magic = self.malicious_magic(magic)
cnt ^= now >> (now.bit_length() - 1)
output ^= now
output ^= cnt * c1
return int(output)
def getrandbit(self, nbit):
output1 = self.lfsr1.getrandbit(nbit)
output2 = self.lfsr2.getrandbit(nbit)
return self.confusion(output1, output2)
本题让我对于格的应用又有了更加深入的理解，包括在lfsr中的运用和lfsr反推导的思想都更加开阔。
解题的主要思路如下：
首先，我们先看problem1()
def problem1():
r = getRandomInteger(6)
magic = 1<<r
lfsr1 = lfsr(seed1, mask1, n1)
lfsr2 = lfsr(seed2, mask2, n2)
cipher = generator(lfsr1, lfsr2, magic)
encrypt(cipher, "MTk4NC0wNC0wMQ==_6d30.txt", "MTk4NC0wNC0wMQ==_6d30.enc")
magic值为1<<r，所以magic一定为2(n)，我们将其代入generator()中验证，不妨发现，当magic取值为2(n)时，返回magic为0，now为magic的值。所以while magic函数只循环一遍，cnt取值为1，最终输出为c2，又发现在文件给出的明文实例中，我们可以猜出前五个字符串为 Data：，所以problem1便可以求解了。
def malicious_magic(self, magic):
now = (-magic & magic)
magic ^= now
return int(now), int(magic)
第一部分总代码求解：
with open("problem/MTk4NC0wNC0wMQ==_6d30.enc","rb") as f:
data1 = f.read()
start = time()
data = data1[:4]
for i in tqdm(range(4095)):
for j in range(4095):
lfsr2 = lfsr(i, j, n2)
s = ""
for ch in data:
tmp = lfsr2.getrandbit(8)
# print(ch)
c = chr(tmp ^^ int(ch))
if c not in "Date":
break
s+=c
else:
if s == "Date":
print(i,j,s)
end = time()
print(f"The Consumption of time is{end - start}")
73 % |███████▎ | 2987 / 4095[02:09 < 00: 46, 23.65it / s]2989 2053 Date
我们此时将第一部分加密的密文进行复原，设置lfsr2 = lfsr(seed2,mask2,12)，将密文代入进行异或操作，在循环后，我们即可求得原来的明文。
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.
第一部分求解结束后，我们便可以求得problem1()中的seed2、mask2的值。接下来便需要我们去求解problem2()的值，在这种情况下，我们知道magic的值，代入进行验证，将所有的循环走完后，最后的输出是output = input ^ c1 ^c2。
在求得的明文中，第一行为Data：开头，后为日期，将文件名进行base64解密后，可以发现即为文件中的日期。所以我们可以知道明文中的前16字节，所以可以进行爆破。
def problem2():
magic = getPrime(64)
lfsr1=lfsr(seed1, mask1, n1)
lfsr2=lfsr(seed3, mask2, n2)
cipher = generator(lfsr1, lfsr2, magic)
encrypt(cipher, "MTk4NC0xMi0yNQ==_76ff.txt", "MTk4NC0xMi0yNQ==_76ff.enc")
# flag in it?
print(f'hint={magic}')
# hint = 15193544052573546419
在problem2()中，mask2的值是已知的，seed3、seed1、mask1的值未知。我们明文的前十六字节已知，所以我们可以爆破mask3在4095长度，在爆破的假设下，我们可以复原出c1的值的大小。当我们知道c1的128bit的输出后，我们便可以通过构造格的方法求解出lfsr1中哪些位参与了下一个输出的生成，便可以求解出mask1的值，
代码：
seed2 = 2989
mask2 = 2053
magic = 15193544052573546419
lfsr2 = lfsr(seed2,mask2,12)
m1 = ''
for i in data1:
ch = lfsr2.getrandbit(8)
m1 += chr(ch^^i)
print(m1)
with open('problem/MTk4NC0xMi0yNQ==_76ff.enc','rb')as f:
data2 = f.read()
data = data2[:16]
a = 'Date: 1984-12-25'
num = []
for i in tqdm(range(4095)):
c1 = ''
lfsr2 = lfsr(i,mask2,n2)
for j in range(16):
ch = lfsr2.getrandbit(8)
c1 += bin(ch^^int(data[j])^^ord(a[j]))[2:].zfill(8)
c1 = [int(j) for j in c1]
A1 = [c1[t:t+64] for t in range(64)]
A = matrix(GF(2),A1)
if not A.det():
continue
B = vector(GF(2),c1[64:128])
x = A^(-1)*B
mask1 = ''.join(str(k) for k in x)
# print(mask1)
求出mask1的值后，我们在lfsr1中便只剩下seed的值不知道。此时，由于我们知道初始的128bit的输出，同样可以使用造格的方法还原开始的64bit，这就是seed1的值。（这个格子确实nb，以前没遇到过）
第二部分总代码求解：
seed2 = 2989
mask2 = 2053
magic = 15193544052573546419
lfsr2 = lfsr(seed2,mask2,12)
m1 = ''
for i in data1:
ch = lfsr2.getrandbit(8)
m1 += chr(ch^^i)
print(m1)
with open('problem/MTk4NC0xMi0yNQ==_76ff.enc','rb')as f:
data2 = f.read()
data = data2[:16]
a = 'Date: 1984-12-25'
num = []
for i in tqdm(range(4095)):
c1 = ''
lfsr2 = lfsr(i,mask2,n2)
for j in range(16):
ch = lfsr2.getrandbit(8)
c1 += bin(ch^^int(data[j])^^ord(a[j]))[2:].zfill(8)
c1 = [int(j) for j in c1]
A1 = [c1[t:t+64] for t in range(64)]
A = matrix(GF(2),A1)
if not A.det():
continue
B = vector(GF(2),c1[64:128])
x = A^(-1)*B
mask1 = ''.join(str(k) for k in x)
# print(mask1)
num.append(mask1)
A2 = []
for i1 in range(64):
B = []
for i2 in range(64):
if i2 == i1 - 1:
B.append(1)
elif i2 == 63:
B.append(int(mask1[i1]))
else:
B.append(0)
A2.append(B)
A2[-1][-1] = int(mask1[-1])
M = matrix(GF(2),A2)
M = M^64
if not M.det():
continue
# print(M[0])
MM = ''.join(str(N) for N in vector(GF(2),c1[:64])*M^(-1))
seed1 = int(MM,2)
# print(seed1)
lfsr1 = lfsr(seed1, int(mask1,2), n1)
lfsr2 = lfsr(i, mask2, n2)
m_final = ''
for N in data2:
C1 = lfsr1.getrandbit(8)
C2 = lfsr2.getrandbit(8)
m_final += chr(N^^C1^^C2)
if m_final[16] == '\r':
print(m_final)
输出：
75%|███████▍ | 3059/4095 [02:56<00:56, 18.30it/s]
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 --.
100%|██████████| 4095/4095 [04:01<00:00, 16.99it/s]