CryptoCTF 2023 medium分类团队解题writeup 之三

这次 medium 分类题量是最多的，内容方面是最丰富的，两极分化比较严重。

有脑筋急转弯的，有考察 SageMath API 使用的，有 MISC 题目混进来的……

总之 medium 分类最难的比 tough 还要更难……

Resuction

题目描述

和 easy 分类里面的 Suction 类似，不过有加强。

RSA 中，$N=pq$，$p, q$ 有 1024 位。

题目给出的 $(N, e, c)$ 的后 8 位均未知，且 $d$ 为 64 位素数。

求明文 $m$。

我的解答

因为 $d$ 较小，所以可以采用 Wiener 攻击得出 $d$ 的值。

所以就是枚举 $N$ 和 $e$ 的低 8 位，然后如果能够通过 Wiener 攻击成功得到 64 位的 $d$ 来。

然后再枚举 $c$ 的低 8 位去解密就行。

这样好像要挂个 40 分钟的样子，因为 Wiener 攻击需要求在每次都要求连分数，以及判断是否为解。

for Nl in trange(2^7):
    for el in range(2^8):
        N = Nh + 2 * Nl + 1
        e = eh + el
        d = solve_pell(N, e)
        if (d is not None):
            print('AOLIGEI!!!')
            print(f'{N = }')
            print(f'{e = }')
            print(f'{d = }')

但是实际上发现，因为我们只有 $N$ 和 $e$ 的末尾 8 位不知道是什么，所以 $N/e$ 的连分数表示在前面应该和高位的连分数是相等的，所以只需要求一次连分数即可，然后用 64 位素数的判据去确定 $d$ 的值，最后枚举 $N$ 和 $e$ 低 8 位即可。

代码如下：

from tqdm import trange

PKEY = 14192646310719975031517528381795548241077678859071194396837281472399230674325587198691913743313024193030641258581477544395982020385534616950314446352119543012689979705497443206671093873748633162188213109347667494028713308821945628880987033909436936504594085029207071182583896573425433818693447573712242776054326253393149643818428222532313129014785625379928796322492111783102063504659053965652092334907431265629283336869752591405010801363428649651892548988084920295512198406822149854508798413366425646089176325412867633899847841343293434518769693835679828109184625256833518392375615524221729773443578746961887429674099018040291053535429314874943299587513900900515776980848746070077651676814430155460898107362207677739452859298842563030631706907437662807884529549746843462830493900480079096937402325307522965877069080418178692616875205678928420840955518031258855869218152431304423803589723140983606576549207164114711076498723237274262054605174412193097533550076687418481230734706280737017543741247718967059747548710091320650704988384742281590019869955579949961574733610565593105027342454880292474482792325237942870408329807427182014062811782475262070063065860763705715879581562335668163076088547827008755841277828137570366416095778
enc = 93313196155732054514477836642637636744872135106456047659057794344503071105783322399713135615723000054324693644981340568454628360027598469597864407205974007198804288563284521413279406211756674451582156555173212403946908121125010635246043311803494356106191509999360722019559999844621905376368824621365540442906142224342650371557766313381899279520110833822291649001754956653102495882094754863493058001964760438040783400782352466943990226083197340594364084294954324101604417550048379969516185353765224920719355485680872367930581872987972421836853197205534334204586713387469939986387582911728909524428102693874671302382

ne = f'{PKEY:b}'
print(len(ne))

Nh, eh = ne[:2040], ne[2040:]
Nh, eh = map(lambda x: ZZ(int(x, 2) << 8), (Nh, eh))

d_bits = 64

def solve_pell(N, e):
    cf = continued_fraction (N / e)
    i = 0
    while True:
        denom = cf . denominator ( i )
        numer = cf . numerator ( i )
        d = numer
        if d.nbits() == 64 and is_prime(d):
            return d
        i += 1

d = solve_pell(Nh, eh)

for Nl in trange(2^7):
    for el in range(2^8):
        N = Nh + 2 * Nl + 1
        e = eh + el
        g = 2
        if pow(g, e*d, N) == g:
            print('AOLIGEI!!!')
            print(f'{N = }')
            print(f'{e = }')
            print(f'{d = }')

求出 $N$ 和 $e$ 之后，枚举 $c$ 的低 8 位解密即可：

from Crypto.Util.number import *

N = 28781418259071163834545208786492597316357138268450456443121779857237190669654679502925616925907115061139426651454246296829614929839091896732956124186768298711851015827257060255218333952539548249210858753648965921585289379414151961197198777686222970660319202167442420274437451557166736926361972983650143650097981777542950972139757680517744639660898696901009088978971506526002932830312595664154921938706240176536981793499426543601513874115451315768319593051858239793153849410530285884330866972048864103208648273010126369559341912163849839663249252300813799486995834473605326584986843653735963725697383056972744506296271
e = 19152712448778858582528734875468196678366984818842265525346340114296810907435357813959451387293270496095878944786775775749129832803842508074794234774568097809721690831345120778762600713106116293626590641716601095020202233532544196547654794913903350183891867544539554967347396716482565232986995497267273877597593761608770699282404807896050347585632153075234094034163801474316224123620090879021107631960008144066862084573910442635526649884938724881478713853362879412453150893601267748827792136092224063120914443976032390554506925020506643629449426005820918745312311984391868895996772772355715765028825561022860823765675
d = 10254340117704573547

enc = 93313196155732054514477836642637636744872135106456047659057794344503071105783322399713135615723000054324693644981340568454628360027598469597864407205974007198804288563284521413279406211756674451582156555173212403946908121125010635246043311803494356106191509999360722019559999844621905376368824621365540442906142224342650371557766313381899279520110833822291649001754956653102495882094754863493058001964760438040783400782352466943990226083197340594364084294954324101604417550048379969516185353765224920719355485680872367930581872987972421836853197205534334204586713387469939986387582911728909524428102693874671302382

for i in range(2 ** 8):
    c = (enc << 8) + i
    m = pow(c, d, N)
    msg = long_to_bytes(m)
    if (all(32 <= x < 127 for x in msg)):
        print(msg)

解得 flag 为：

1	CCTF{aIr_pr3s5urE_d!Ff3rEn7i4L_8eTw3eN_ArEa5!}

Blobfish

题目描述

首先用 AES 加密 flag，得到密文的十六进制表示。其中 AES 密钥是某个 8 字节内容的重复 2 次，IV 是根据密钥的 MD5 计算而来。

然后将 flag 密文的十六进制表示 作为文本，画到一个固定大小的 PNG 中，存成 flag.png

最后将用 AES 密钥的前 10 字节当成密钥，对 flag.png 加密，存成 flag.zip，具体命令如下：

1	os.system(f'/bin/zip -0 flag.zip flag.png -e -P \"$(/bin/echo -en \"{hkey}\")\"')

试求 flag。

我的解答

对 MISC 比较熟悉的同学应该会知道，flag.png 拥有着固定的 PNG 头，也就是说知道 flag.png 的头若干字节，那么要对 flag.zip 解密的话，应该就是 bkcrack 的套路：

https://github.com/kimci86/bkcrack

它 release 里面就有可执行版本，并且里面也有一个 example 文件夹，有一个 tutorial.md 手把手教如何破解。基本上直接抄这个 tutorial.md 里面的过程就行了。

Guessing plaintext 因为我们的生成的 PNG 大小都是固定的，这意味着 PNG 的 IHDR 块中的内容是固定的，所以我们可以生成一个一模一样大小的 PNG 图像，来获得前 0x21 个字节的内容，内容如下：

$ xxd plain
00000000: 8950 4e47 0d0a 1a0a 0000 000d 4948 4452  .PNG........IHDR
00000010: 0000 0320 0000 0032 0802 0000 002b e428  ... ...2.....+.(
00000020: 32                                       2

Running the attack 直接依葫芦画瓢：

1	bkcrack -C flag.zip -c flag.png -p plain

得到如下 3 组密钥：

1	Keys: 03492be6 b81a5123 24d7b146

Recovering the original files 仍然依葫芦画瓢：

1	bkcrack -C flag.zip -c flag.png -k 03492be6 b81a5123 24d7b146 -d flag_deciphered.png

得到 flag_deciphered.png 如下：

用 QQ 截图的 OCR+肉眼比对验证，结果为：

1	69f421d9e241933cbc62a9ffe937779c864ffa193de014aeb57046b16c40c7353910c61a2676f14f4c7737f038a6db53262c50

Recovering the original password 剩下就是要通过 3 组密钥反推 AES 密钥了。依旧依葫芦画瓢：

1	bkcrack -k 03492be6 b81a5123 24d7b146 -r 10 ?b

得到结果：

1	as bytes: ad 6e fb 79 2a ea 5a aa ad 6e

然后就是朴实无华的解密了：

from hashlib import md5
from Crypto.Cipher import AES

key_hex = 'ad 6e fb 79 2a ea 5a aa'
enc = '69f421d9e241933cbc62a9ffe937779c864ffa193de014aeb57046b16c40c7353910c61a2676f14f4c7737f038a6db53262c50'
enc = bytes.fromhex(enc)
key = bytes.fromhex(key_hex.replace(' ', ''))

key = key * 2
iv = md5(key).digest()

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
msg = cipher.decrypt(enc)
print(msg)

得到 flag 为：

1	CCTF{d3ep-Zip_fi5h_0f_tH3_knOwN_pL4!n_7exT_ATtAcK!}

ASIv1

题目描述

首先将 flag 转成三进制的 012 序列，记为 $\{m_i\}$，即 $m_i \in \{0, 1, 2\}$，其中 $i = 1, 2, \ldots, l$

生成一个 $l^2 \times l$ 的 012 随机矩阵 $R=[r_{ij}]$，即 $r_{ij} \in \{0, 1, 2\}$，该随机矩阵已知。

然后还知道一个向量 $s$，其中

$s_i = \left(\sum_{j=1}^{l}{r_{ij} m_{j}}\right) \bmod 3$

对于 $i = 1, 2, \ldots, l^2$

已知 $R, s$，求 flag。

我的解答

如果把整个过程看成是 $GF(3)$ 内的运算，一切都是那么自然：直接就是进行一个线性系统的解。

然后把解得的三进制结果转回 flag 即可。

代码如下，直接一套不解释连招：

with open('output.txt') as f:
    s = f.read().splitlines()

A = eval(s[0][4:])
b = eval(s[1][4:])
print('Read OK')

l = 2 * len(A[0])
A = matrix(GF(3), A[:l])
b = vector(GF(3), b[:l])
print('Matrix & vector build OK')
x = A.solve_right(b)

msg = ''.join(str(xi) for xi in x)
msg = int(msg, 3)
from Crypto.Util.number import *
print(long_to_bytes(msg))

注意一下上面如果取 $A$ 和 $b$ 的所有行来构成线性系统的话，复杂度会爆炸；而如果取 $A$ 和 $b$ 的前 $l$ 行的话，$A$ 不是满秩的矩阵，解出来的东西会让人森肽煲咂。所以综合考虑，取前 $2l$ 行构成方程组。得到 flag 为：

1	CCTF{3Xpl0i7eD_bY_AtT4ck3r!}