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 🔥)
