|
data中是部分解密的文件，文件名是一个日期的base64加密。经过对比发现这个日期就是文件内容开头的日期。
因此也就确定了加密文件前 244 比特的明文内容（包括日期后面的\r\n）。
经过分析可知 confusion 函数可以做如下化简：
def bit_count(self, x):
res = 0
while x:
if x & 1: res += 1
x >>= 1
return res
def confusion(self, c1, c2):
if self.bit_count(self.magic) & 1:
return c2
return c1 ^ c2
也就是说如果 magic 二进制下‘1’的个数是奇数则为 12bit 加密，否则为 12bit 和 64bit 加密结果的异或值。
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")
对于problem1 因为 magic 是
2
r
2^r
2r ，因此是 12bit 加密，因此只需枚举 seed2 和 mask2 然后比对解密内容即可得到正确的 seed2 ，mask2 以及解密后的文件。
from Crypto.Util.number import long_to_bytes
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
n2 = 12
plaintext = b"Date: 1984-04-01\r\n"
ifile = open("MTk4NC0wNC0wMQ==_6d30.enc", 'rb')
ciphetext = ifile.read(len(plaintext))
ifile.close()
def check(cipher):
for _ in range(len(plaintext)):
if ciphetext[_] ^ cipher.getrandbit(8) != plaintext[_]:
return False
return True
def decrypt(cipher, ipath, opath):
ifile = open(ipath, 'rb')
ofile = open(opath, 'wb')
ciphetext = ifile.read()
for ch in ciphetext:
c = ch ^ cipher.getrandbit(8)
ofile.write(long_to_bytes(c))
ifile.close()
ofile.close()
if __name__ == '__main__':
for seed2 in range(1 << n2):
for mask2 in range(1 << n2):
if check(lfsr(seed2, mask2, n2)):
print("seed2 = " + str(seed2))
print("mask2 = " + str(mask2))
decrypt(lfsr(seed2, mask2, n2), "MTk4NC0wNC0wMQ==_6d30.enc", "MTk4NC0wNC0wMQ==_6d30.txt")
解得：
seed2 = 2989
mask2 = 2053
MTk4NC0wNC0wMQ==_6d30.txt 内容为：
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.
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")
print(f'hint={magic}')
对于 problem2 ，由于 magic = 15193544052573546419 ，因此涉及 64bit 加密。
mask2 在 problem1 已经求出，因此只需枚举 seed3 。
将 lfsr2、明文、密文三者前 244bit 异或起来，就可以得到 lfsr1 产生的前 244bit 序列。
由于 lfsr1 的 bit 序列生成是有当前 n1 bit 与 mask1 与的结果中二进制形式 1 的个数的奇偶性决定下一 bit 的结果，因此可以列出一个异或线性方程组，求解即可得到 mask1，然后就可以解密出明文。
import numpy as np
from Crypto.Util.number import long_to_bytes
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
n1, n2 = 64, 12
mask2 = 2053
plaintext = b"Date: 1984-12-25\r\n"
ifile = open("MTk4NC0xMi0yNQ==_76ff.enc", 'rb')
ciphetext = ifile.read(len(plaintext))
ifile.close()
ifile = open("MTk4NC0xMi0yNQ==_76ff.enc", 'rb')
ifile.read(8)
text = ifile.read()
ifile.close()
def gauss(a):
r = 0
for c in range(n1):
t = r
for i in range(r, a.shape[0]):
if a[i][c] == True:
t = i
break
if a[t][c] == False: return -1
a[[t, r], :] = a[[r, t], :]
for i in range(r + 1, a.shape[0]):
if a[i, c] == True:
a[i] ^= a[r]
r += 1
for i in range(n1, a.shape[0]):
if a[i, n1]: return -1
for i in range(n1 - 1, -1, -1):
for j in range(i + 1, n1):
a[i, n1] = a[i, n1] ^ (a[j, n1] & a[i, j])
mask1 = 0
for i in range(n1):
mask1 <<= 1
if a[i, n1] == True: mask1 |= 1
return mask1
if __name__ == '__main__':
s = []
for i in range(len(plaintext)):
s.append(plaintext[i] ^ ciphetext[i])
for seed3 in range(1 << n2):
r = s.copy()
cipher2 = lfsr(seed3, mask2, n2)
for i in range(len(plaintext)):
r[i] ^= cipher2.getrandbit(8)
b = []
for i in range(len(plaintext)):
for j in range(7, -1, -1):
b.append((r[i] >> j) & 1)
a = np.zeros((len(plaintext) * 8 - n1, n1 + 1), dtype=bool)
for i in range(len(plaintext) * 8 - n1):
for j in range(n1 + 1):
a[i, j] = b[i + j]
mask1 = gauss(a)
if mask1 == -1: continue
seed1 = 0
for i in range(64):
seed1 = (seed1 << 1) | b[i]
cipher1 = lfsr(seed1, mask1, n1)
cipher2 = lfsr(seed3, mask2, n2)
for _ in range(8): cipher2.getrandbit(8)
res = b"Date: 19"
for ch in text:
c = ch ^ cipher1.getrandbit(8) ^ cipher2.getrandbit(8)
res += long_to_bytes(c)
if b"SUSCTF" in res:
print("seed3 = " + str(seed3))
print("mask1 = " + str(mask1))
ofile = open("MTk4NC0xMi0yNQ==_76ff.txt", "wb")
ofile.write(res)
exit(0)
解得：
seed3 = 3054
mask1 = 9223372036854775811
MTk4NC0xMi0yNQ==_76ff.txt 内容为：
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 --.
|