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 > kd_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 反编译出来的是这样的玩意:

halfhalf1

你要说它难看吧,流程也不是不够清晰;你要说它好看吧,调用绕来绕去还挟带着反编译可能出现的错误真是让人头疼。

我们卡了很久 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() 替换表。

然后看选项:

halfhalf2

五个选项,因为不想看 IDA,初步猜测功能如下:

1. Get Cipher
2. Decrypt Oracle
3. Refresh for ?
4. GetFlag
5. Exit

完全不对,没有头绪,还得看 IDA。

看吧看吧看吧看吧看吧。

halfhalf3

和杰哥进行了漫长的分析之后,终于知道了正确答案:

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 其他部分完全正确,拿下!这场夜战终于落下了帷幕。

图源Aidai

 

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 已经在群里发了排名:

tctf

写这篇 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。

 

相关链接

Other members’ angle of this game

Aidai’s record (mainly pwn, AI and 🔥)

Milu’s record (only for win-win)

Surager’s record (ongoing)