Writeup$^{[1]}$ for Some Easy Problems in TCTF 2021
[1] writeup:专文,专稿,详细报告。在 CTF 比赛中,代指解题报告。
ezRSA
看到题目中给出的 hint 变量,观察位数发现通过 magic 能够计算得到 k
的近似值,于是乎也能够拿到 l
,此后之后直接 d_q = invert(e, l)
然后分解 n
拿到 flag
。
当时拿到 d_p % 2**10 != d_p & (2**mask - 1)
后傻了,百思不得其解说怎么逆元还能不同的?结果是 d_p > k
, d_p = k + d_p
… 一看 flag 发现是非预期,激动的心颤抖的手拿下了 rsctf 赛道的一血$^{[2]}$…
[2] 一血:指一场比赛中首次解出某道赛题。
ezRSA+
这道题就没有给出 magic 变量了,想了一会儿,最终还是需得从 small_d_p_d_q
入手,题目生成方式眼花缭乱,于是乎翻翻发现了一篇很久很久之前出过的老paper,照着胡乱造了造非常简单的格子出了… 果然很久没好好打 CTF 手就生了,很多常见的 feature 都给忘了。
exp
n, e = (#, #)
M = [
[e * e, 1, 0, 0],
[e, 0, 1, 0],
[n - 1, 0, 0, 1],
]
M=Matrix(ZZ, M)
L = M.LLL()[0]
dp, dq, k, l = var('dp, dq, k, l')
solve([dp * dq == -L[1], dp * l - dp + dq * k - dq == -L[2], k * l == L[-1], k + l == -L[0] + 1], dp, dq, k, l)
ezMat
这题蛮好玩的,纵观题目像是一个 toycipher,随手一搜 Encrypt And Decrypt Messages Based On LU Decomposition Using Multiple Keys,约莫是没什么名气的期刊。动动我的小脑瓜想想,好像没什么漏洞点,也没搜到有什么攻击方法。
于是乎本地测试了一波,发现 $\mathbb{A}$ 很稀疏,非零元素在矩阵中的位置也是固定的,再联想到特意的 assert len(flag) == 24
,难不成是爆破?
不管三七二十一,跟着直觉便随手试了一发:固定 $\mathbb{A}$ 中的某行并将其他行置零得到 $\mathbb{A’}$,反求 $\mathbb{U’}=\mathbb{E}(\mathbb{A’}+\mathbb{R})$。显然 $\mathbb{U’}$ 中的对应行是一样的,而 $\mathbb{U}$ 为一上三角矩阵,故有其鲜明的特征以 check
。
话不多说,爆就完了,除去第 0 行无特征、第 1 行可能的结果较多外,剩下 9 行都可以直接拿到结果。
因为给出了 $sha256(flag)$,在所有结果的可能性上对第 0 行进行一个 $O(p^3)$ 的枚举,加以验证即可。
exp$^{[3]}$ 较丑不放了,见谅。
[3] exp:即 “exploit”,在信息安全的世界里常表示”漏洞利用脚本”。
halfhalf
上一次记忆深刻的 Re_Crypto_Challenge 还是 XCTF Final 的 bls。
看到 Description: half re half cry
我就冲了。
rust_reverse 也是如出一辙的恶心,不过好就好在算法本身难度不高,和杰哥通力合作的情况下,加上密码学的直觉也能一点一点啃完。
众所周知,逆向很考验耐心的——尤其是当你看见 IDA 反编译出来的是这样的玩意:
你要说它难看吧,流程也不是不够清晰;你要说它好看吧,调用绕来绕去还挟带着反编译可能出现的错误真是让人头疼。
我们卡了很久 proof_of_work
——我想,6 digit-hex,不就是 sha256[:6]/[-6:]
?nc 远端直接试了试,怎么都不对,那 PATCH 掉⑧,我们直接看后面。
结果发现梅开二度,他要我的 magic words
,看 IDA,发现过了之后会提示道:? Wow, you are indeed a huge fan of ?.
。想起 SJTU 是他的母校,我想,那也许… 好活!关键词和大小写都试试吧!
19260817/1926/0817/ha/ta/gou/glgjssy/glgjssyqyhfbqz...
出不来。
那没办法了,继续 PATCH 掉。进去发现是 emoji 菜单题——什么时候 emoji in CTF 轮到非蓝鲸的其他队伍整活了,还出成了题目?那没办法,回去看 IDA 吧——于是乎看到了一串神奇的 emoji:🐶🍐🍳🏠🐣💀💺👈👉🏁🦅🔥🪓👃🎶📄
,顿时恍然大悟,苟利国家生死以,岂因祸福避趋之
!要用魔法对抗膜法!
此外,🐶🍐🍳🏠🐣💀💺👈👉🏁🦅🔥🪓👃🎶📄
后正跟随着一串 0123456789abcdef
,我们想当然地认为,这便对应着 emoji 的 encode_num(), decode_num()
替换表。
然后看选项:
五个选项,因为不想看 IDA,初步猜测功能如下:
1. Get Cipher
2. Decrypt Oracle
3. Refresh for ?
4. GetFlag
5. Exit
完全不对,没有头绪,还得看 IDA。
看吧看吧看吧看吧看吧。
…
和杰哥进行了漫长的分析之后,终于知道了正确答案:
1. Get Modulus
2. Oracle (but is pow(x, e, modulus), where x := (3 * randint)**2 if guess >= x else 2*(3 * randint)**2)
3. Regenerate the Key and Tell The Old Key
4. GetFlag by Inputing the Key
5. Exit
那么流程很明显了:我们在 IDA 中看到 $x$ 的范围在 [1, 2**512]
之间,题目给了时限,那么显然是通过 Func 2 解雅可比符号,二分出答案即可!而 Func 3 可以有一个简单的本地验证正确与否的作用(赛后查询其采用的 rng 似乎是比较安全的,在本次比赛中不考虑预测随机数的方法)
已经凌晨两点多了,时不我待,写脚本吧。写到一半,discord 响起提示音——难不成一血出了?
点进去一看,洋人和国内选手提问:
[-]channel: 0ctf2021-finals
admin for halfhalf?
It seems @**** is sleeping now. 😦 Any admin can handle halfhalf?
oh nvm, he's awake
[-]channel: rsctf2021-finals
Who can I DM for the halfhalf??
一血还在,好!继续写脚本了。
写好了,打本地试试?发现得到的 modulus
甚至有偶数?离谱,答案也完全不对,60 秒的时间也根本不够。再次分析流程——完全没问题啊?试试远端?我连上 nc,发现 PoW 没了——出题人终于发现 PoW 有锅了。急忙删掉 PoW 继续交互,发现确实有问题,多试了几下,PoW 又出现了,大抵是修好了。
这意味着我们还是要去看 PoW 究竟取的哪几位。祭出 gdb 动调发现确实是 sha256(****)[-6:]
,冲吧。
过了一会儿,一血已经没了,可我还在纠结 n
为什么是偶数。实在没有头绪,最终归因于 emoji 和 digits 的转换不对应,于是反回去看 encode_num()
,看不太懂,一怒之下上 gdb 动调,拿到公钥及其对应 emoji 串,挨个对照拿到了对应表,发现确实不对。
换表,打本地,打远端。
打本地的时候发现最后答案应该 ++,遂 print(guess + 1)
,再打,怎么还是不对?Aidai 说,你这是 print
啊!我和杰哥方才如梦初醒,改成 guess += 1
打到远端,exp 其他部分完全正确,拿下!这场夜战终于落下了帷幕。
exp
from gmpy2 import *
from hashlib import sha256
from sympy.ntheory.residue_ntheory import jacobi_symbol
from pwn import *
def proof_of_work(digest):
table = [chr(i) for i in range(32, 128)]
for i in table:
for j in table:
for k in table:
for l in table:
guess = i+j+k+l
if sha256(guess.encode()).hexdigest()[-6:] == digest:
print(i+j+k+l)
return (i+j+k+l)
emo_table = [b'\x90\xb6', b'\x8d\x90', b'\x8d\xb3', b'\x8f\xa0', b'\x90\xa3', b'\x92\x80', b'\x92\xba', b'\x91\x88', b'\x91\x89', b'\x8f\x81', b'\xa6\x85', b'\x94\xa5', b'\xaa\x93', b'\x91\x83', b'\x8e\xb6', b'\x93\x84']
hex_table = "60145ab893edf72c"
magic_table = '🐶🍐🍳🏠🐣💀💺👈👉🏁🦅🔥🪓👃🎶📄'
def hex2emo(a):
try:
a = a.decode()
except:
pass
return b''.join([b'\xf0\x9f' + emo_table[hex_table.index(i)] for i in a])
def emo2int(a):
a = a.strip().split(b'\xf0\x9f')[1:]
a = [i if len(i) == 2 else i[:-1] for i in a]
return int(''.join([hex_table[emo_table.index(i)] for i in a]), 16)
def check(c, n):
return jacobi_symbol(c, n)
re = process('./123')
#re = remote('121.5.253.92', 34567)
re.recvline()
digest = re.recvline().strip().decode()
re.sendline(proof_of_work(digest).encode())
re.sendline(magic_table)
re.recvuntil(b'> ')
re.sendline('1')
re.recvline()
n = emo2int(re.recvline()[6:-1])
l = 1
r = 2**512
guess = 0
for i in range(512):
guess = l + r >> 1
re.recvuntil(b'>')
re.sendline('2')
re.recvuntil(b': ')
re.sendline(hex2emo(hex(guess)[2:]))
ans = emo2int(re.recvline())
if check(ans, n) == -1:
l = guess
else:
r = guess
print(i)
print(r-l)
guess += 1
re.recvuntil(b'>')
re.sendline('4')
re.recvuntil(b':')
re.sendline(hex2emo(hex(guess)[2:]))
print(re.recvall())
其他要说的话
剩下的两道密码学题目,一道逆得太难受不想看(babylogin),一道没什么头绪(ezHash)。
还以为快蒙蒙亮了,毕竟是青岛的天。走出南楼才发现,四五点和一点没什么差别,都是深蓝色的幕布里缀着十来颗明灭易逝的微光。唯一不同的是,回宿舍的路上反倒更有些人气了:一路上还经过了三两辆自行车与小车。Surager 说,食堂的大叔大妈这么早就赶着去做饭了。我有些生疑,直到在路口望见两辆轿车先后驶入食堂楼下,才隐约相信了。
快五点回到宿舍,一觉睡到 11:54,醒来拿起手机一看,Aidai 已经在群里发了排名:
写这篇 writeup,主要在于夜里看到四点终于出了的 halfhalf 让我起了兴致——虽然一开始的 proof_of_work, alarm(60)
部分略有瑕疵,但由于其趣味性(👍👓🐸🔥)所在,尽管本次比赛并未要求提交 writeup,但我依然纂下本文予以记录。
如果主办方不要求,writeup 这种东西感觉没有什么特别的必要来进行记录。而本文说是 writeup,不如说是闲聊。这正是本博客的第一篇 writeup,也大约是最后一篇了。
本次比赛体验尚佳,虽小有遗憾,但两天熬夜得到的结果 (risingstar TCTF rank 5) 也算很不错!
今年第二次刷新 Blue-Whale 历史比赛排名(Best Record in TCTF was rank 7),也第二次达成了”差一点点就第二”的成就(CISCN 2021 rank 5 tooooooo)(也是差一道题就上去了)。
既然每个人都已尽力,那么,也已够好了!
花絮
本部分图片均引用自 AiDai’s blog。
-
赛前纪念品:
-
《7k👴的替身与赛前视频》:
-
对了,Day 1 晚上腾讯安全公众号发战报的时候,咱们是登顶的,此处引用一张图片(榜文无关):
-
“赛前烟雾弹”:
-
-
对于学过 1、、人工智能的我,对 Aidai 做 AI 题所用的人 工 智 能嗤之以鼻,详参相关链接部分之 Aidai’s record。
-
欲了解更多蓝鲸日常相关,目前可供参考的主要资源是 Aidai’s blog 及 Surager’s travel collections,笔者也会在年终放出一篇流水账——大概不会咕。
相关链接
Other members’ angle of this game
Aidai’s record (mainly pwn, AI and 🔥)