null
文章目录
  1. wordle
  2. Nanomaze
  3. the Ohio State University
    1. 后记
  4. Ranma½
  5. quantum
  6. Cat&Soup
    1. Cat
    2. Soup
  7. OTP
    1. Step 1
    2. Step 2
    3. 后记
  8. 写在最后

TQLCTF Official Writeup By Nano

这次的 TQLCTF 我负责了 7 道题的出题工作,把很多以前攒的出题灵感都变成了真实的题目。虽然有些题目被非预期解了比较遗憾,但总体而言没有什么大问题,还是挺满意的。

wordle

本题需要选手在加强版 Wordle 游戏中连续 512 轮四次以内猜中词语才会获得最终的 flag。

可能很多人会吐槽说,怎么好端端的一个 CTF 比赛变成了算法比赛?

首先需要明白一点,纯算法连续 512 轮四次之内猜测正确的可能性是近乎为 0 的,为了尽可能降低用算法通过的可能性我还增大了答案库的大小(当然如果有师傅用纯算法的方法过了这题请联系我让我膜一下)

如果答案库大小没变的话,大家可以参考 https://jonathanolson.net/wordle-solver/ ,用算法的力量通过本题!

主要漏洞点出在 get_challenge 处:

def get_challenge():
# id = random.getrandbits(32)
# answer = valid_words[id % len(valid_words)]
# return hex(id)[2:].zfill(8), answer

# To prevent the disclosure of answer
id = random.randrange(len(valid_words) * (2 ** 20))
answer = valid_words[id % len(valid_words)]
id = (id // len(valid_words)) ^ (id % len(valid_words))
return hex(id)[2:].zfill(5), answer

valid_words 大小为 $4090$,乘上 $2^{20}$ 约等于 $2^{32}$,而 randrange 的结果是可以通过正确答案以及每道题的 ID 逆推获得的。

让我们跟踪进去看看 random 内部的实现:

_randbelow = _randbelow_with_getrandbits

def _randbelow_with_getrandbits(self, n):
"Return a random int in the range [0,n). Raises ValueError if n==0."

getrandbits = self.getrandbits
k = n.bit_length() # don't use (n-1) here because n can be 1
r = getrandbits(k) # 0 <= r < 2**k
while r >= n:
r = getrandbits(k)
return r

def randrange(self, start, stop=None, step=1, _int=int):
"""Choose a random item from range(start, stop[, step]).

This fixes the problem with randint() which includes the
endpoint; in Python this is usually not what you want.

"""

# This code is a bit messy to make it fast for the
# common case while still doing adequate error checking.
istart = _int(start)
if istart != start:
raise ValueError("non-integer arg 1 for randrange()")
if stop is None:
if istart > 0:
return self._randbelow(istart)
raise ValueError("empty range for randrange()")

# ....

从这里可以看出,randrange 实际上就是在调用 getrandbits(32),所以这里就可以套用 Python random module cracker 来预测答案!

总结一下:通过两轮 Easy Mode 获得前 624 道题的答案,结合 ID 反推 getrandbits(32) 的值并丢进 random-cracker 获得预测随机数的能力

注意到 $4090\times2^{20}$ 离 $2^{32}$ 还有一定的差距,结合代码可知如果 getrandbits(32) 大于 $4060\times2^{20}$,则该数将会被丢弃导致预测随机数失败。经过计算可知,成功率为 $\left(\frac{4090}{4096}\right)^{624}=0.4006237250$ ,十分可观。

exp: https://github.com/Konano/CTF-challenges/blob/master/wordle/exp.py

顺便还埋了一些彩蛋:

  • Easy Mode 通关后会获得「NULL」
  • Normal Mode 通关后会获得「UWNYZ1c5dzR3UWQ9dj9oY3Rhdy9tb2MuZWJ1dHVveS53d3cvLzpzcHR0aA==」
  • Hard Mode 通关后会获得经过 random.shuffle 后的 flag
  • Insane Mode 通关后会获得完整的 flag

有请受害者一位

Nanomaze

这是一道纯黑箱题目,考察选手们黑灯瞎火走迷宫的能力(大雾)

题目背景是 Revomaze,一款出自英格兰的 Puzzle 系列。题目基本上还原了 Puzzle 的地图和声音,让选手们能够身临其境免费游玩 Puzzle!选手在题目中只能通过 wasd 上下移动,且能听到咔哒一声(指 [click])。Puzzle 的具体情况可以看 GM 的秘密基地的游玩视频,本题正是复刻了 Revomaze Green 的迷宫。

最后为了加大难度,本题还抛弃了单位移动距离,改成了随机实数距离。

地图

黑箱交互的题怎么做呢?首先通过乱按发现 wasd 这四种输入能够触发有效的回显,并且知道了随机移动距离这个特点;然后通过左右走动发现可以无限往左走,猜测是一个循环地图;触发了 [click] 之后往回走发现撞墙了,猜测 [click] 指的是单向门……

当然你也可以在知道这是个循环地图后无视 [click] 直接遍历全图,这样也可以到达终点。

exp: https://github.com/Konano/CTF-challenges/blob/master/Nanomaze/exp.py

the Ohio State University

题目名称解读:此 OSU 非彼 OSU。

附件是一个 osz 文件,是著名音乐游戏 Osu! 的铺面打包格式。如果电脑上有安装 Osu!,那么直接打开即可加载游戏铺面!通关最高难度即可获得 flag!

咳咳,说正经的。osz 文件实际上就是 zip 文件,修改后缀名解压即可获得背景图、音频、音效和铺面文件。通过查看铺面文件,我们可以获得该铺面所对应的 ID,然后去 Osu! 官网下载官方的铺面进行对比,发现有四个文件经过了修改。(或者可以直接看文件的修改日期)

  • flag 的第一部分被加密在背景图片中,经过了 steghide 加密,密码在图片的属性内可被找到
  • flag 的第二部分被加密在 boom.wav 中,经过了 silenteye 加密,密码被写在 EASY 难度的铺面文件内
  • flag 的第三部分被隐藏在最高难度的铺面文件中,通过游戏内置的编辑器可以发现最后的尾杀部分被修改成了一串无理多押,将 Note 转为 0/1 再通过二进制的解读可以获得 flag

铺面解读

最后拼接三部分获得 flag。

后记

这题是我在玩 Osu! 的时候拍脑子想出来的……

Osu! 的铺面文件真的适合出 Misc,因为压缩包、图片、音频啥的都有……

人老了,只能打 4* 难度了

老年复健

Ranma½

众所周知,UTF-8 是可变长编码,那么我们能否用这个特性去隐藏信息呢?

UTF-8 Wikipedia

通过上表,我们可以获得将 ASCII 码范围的字符用长度为 2/3 的 UTF-8 编码所表示的能力。当然由于 first/last code point 的限制,这将在大部分文本编辑器上显示为乱码(除了神奇的 vim)以达到隐藏信息的目的,而 UTF-8 编码长度的自由度则又可以隐藏另一部分的信息。

解题过程如下:使用 vim 打开文件或者经过自行解析获得 ASCII 密文,通过观察猜测经过了维吉尼亚加密;依次列举出 UTF-8 编码文字的长度,长度为 1 的字符转换为点,长度为 2 的字符转换为线,长度为 3 的字符转换成分隔符,经过 Morse 解读获得密钥;最后经过维吉尼亚解密得到明文和 flag。

quantum

本题为 CCSP2022 C 题改。

程序内实现一个简单的量子电路模拟器,通过量子门进行了若干次量子计算,这里直接使用截图来对原理进行解释:

这题包含有近 $199916$ 个量子门,如果暴力计算则需要进行 $2^{24}\times199916$ 次复数计算,需要优化。实际上程序已经内置了一些优化,例如量子门顺序调换、重编号等,增加了逆向的复杂度,但因为优化的预处理并不会像主算法那样耗时,可以直接设个钩子获取得到优化后的量子门顺序,从而不需要逆向该优化逻辑。

即便如此,程序仍然需要 12-24 小时才可以出解。通过对逆向得到的数据进行分析,可以很容易发现数据的分布并不是完全随机的,量子门所影响的量子比特一部分都在 0-11 号量子比特上,一部分都在 12-23 号量子比特上,此时的电路可以被切分为两个基本独立的部分:

此时的复杂度降为 $2^{12}\times199916$,可以承受。

当然考虑到这是 CTF,本题还有一种办法可以解。通过对控制流的分析和运行时间的测量,可以知道即使不经过优化,该程序也能在一天内跑完,那么可以在运行结束的时候把内存 dump 下来,然后对数据进行搜索,推导出 flag 即可。

Cat&Soup

ByteCTF2021 Final 出了道 Lisa’s Cat,在 YUV 色彩空间中使用 Arnold’s cat map 变换算法,参数则隐藏在某个 LSB 内。当时的我,没看到参数,也没使用 YUV 色彩空间,但最后还是做出来了……于是便有了这题。

选手们可以获得一个加密压缩包,但这个压缩包的密码就是 flag 本身,所以是不可能解开来的。这里本来想用常规伪加密的方法,但想了想,要不就直接把原文塞进 zip 中加密后的数据块里面吧(好像还没见到有人这么做过)。提取出原图后可以看到一张为 cat.png, 一张为 soup.png,这是两个独立的子任务。

Cat

先说说 cat.png,从文件名可以知道大概率使用了 Cat 变换算法,同时我们在 RGB 三个通道的 LSB 都发现了奇怪的水印。通过观察水印的分布规律,可以推测出 Cat 变换中的两个变换参数(补充:这种情况只在 Cat 变换重复次数为 1 时才可能通过观察水印猜测得到水印的分布规律)

为了验证参数是否正确,我们可以把疑似水印给染上色,然后对此图进行 Cat 变换,观察变换后的图像,实际上只需要少量的水印像素就可以确定图像了。

变换前

变换后

当然,爆破参数也是可行的,但需要先爆破横向变换的参数。Arnold’s cat map 变换算法本质上就是一次纵向变换加上一次横向变换,所以两个参数可以分别爆破。写个程序枚举参数并输出横向变换后的图,挑一些明显的看。如下图是参数差 1 的结果,是不是有一条明显的斜线?参数 +1 后这条斜率为 1 的斜线也就变成了直线并且变成了边框,说明我们成功爆破除了 Arnold’s cat map 的横向变换参数。

爆破结果

对三个通道的 LSB 各做一次 Cat 变换猜测,得到三段 flag,按照猫猫的分布从上到下连接得到 flag 的前半部分。

那么有人会问了,你不是说这种情况只对重复一次的 Cat 变换有效,ByteCTF Final 那题不是重复了 66 次吗?的确,所以后来我仔细研究了出题人给的 exp.py,发现它实现有问题,实际上只重复了一次……

Soup

soup.png 这里实际上是使用了 EZStego 调色板隐写算法。所以直接照着实现一下就好了,就可以获得flag 的后半段。具体算法实现看 exp 吧。

exp: https://github.com/Konano/CTF-challenges/blob/master/Cat%26Soup/soup_exp.py

不过这题不需要知道 EZStego 也可以解,就留给各位思考了,以后有机会的话可能还会将这个思路出成新的题!

OTP

这题实现了一种略显复杂的一次性密码加密算法。

这题的难点还挺多的,特别在加入了 DangerousBehavior 的监测机制和 secret 之后。

加密过程:shuffle(xor_bits_shuffle(M, Rand(len(M), f1+s1))+f1, f2+s2)+f2

Step 1

拿到密文,很容易知道 shuffle 所用的 token 是什么,但由于有 secret,并不能反推出 shuffle 的打乱规则,继而更难推导后面 xor 所用的 token。

注意到题目解密时如果发现有非法字符,会返回一个带有下标的提示,可以利用这个爆破出明文在经过 shuffle 后的位置,这样可以将 shuffle 的可能性减少到 24 种(并不能知道 token 经过 shuffle 后的顺序)

注意到 shuffle 和数组长度是有关的,所以在加入了 DangerousBehavior 的监测机制之后,想要得到和 flag 同长度情况下的 shuffle 情况是不可能的,这时候只能退而求其次求得 flag_length±1 时同 token 的 shuffle 情况,然后推导在 flag_length 不变的情况下 shuffle 的情况。

如何从两个 ±1 的 shuffle 情况推导出中间的 shuffle 情况?通过研究源码可以知道 random.shuffle 是通过 n-1 次两两交换来打乱序列,交换对象由 random.getbelow 决定,所以某些情况下相邻长度的 shuffle 情况是相似的。(这步建议可以用人脑或者程序研究研究)

那么此时我们知道了 shuffle(?, f2+s2) 的打乱规则,获得了 xor_bits_shuffle(M, Rand(len(M), f1+s1)) 和 f1 的信息。

Step 2

根据源码可知,xor_bits_shuffle 是指对字符串做 xor 后再一个个字节进行 bits_shuffle,且中间不重置 random.seed。

首先因为 DangerousBehavior 的监测机制,我们需要随机一个 token 替代 f2 用来做 shuffle,并用第一步的方法获得特定长度下 shuffle 的结果。

xor 的结果只和 f1 有关,所以此时也可以通过爆破获得 xor 的 Rand(len(M), f1+s1),进而得到 bits_shuffle 的结果。

但是,注意到这里的 bits_shuffle 和明文长度有关(中间不重置 random.seed),而 DangerousBehavior 的监测机制又阻止我们在只改变 shuffle_token 的情况下爆破 bits_shuffle,看似又是一个无解的情况。

还记得之前说过的 random.shuffle 的实现吗?random.getbelow 的实现也是基于 getrandbits,再深挖 getrandbits 的实现我们可以知道,在未来的某一个长度下,bits_shuffle 的情况会重复出现!所以只需要爆破后续某些特定长度下的 bits_shuffle 情况,然后结合 xor 尝试破解 flag 的密文。如果前缀匹配上的话那么大概率就是正解了。

后记

这题的 DangerousBehavior 判断放得太后了,导致所有在比赛场上做出这道题的人都利用了 valid_pos 的报错而绕过了 DangerousBehavior,从而出现了更加简单的非预期解法。虽然即便是这样解出这道题的队伍也只有 4 个,但还是略显遗憾,没能让大家真的去预测 shuffle 后的结果……放在 GitHub 上的题目代码已经修复了该处 Bug,有兴趣的可以自己试试看。

exp: https://github.com/Konano/CTF-challenges/blob/master/OTP/exp.py

(exp 写了 600+ 行,没优化过所以很拉,建议自己动手试试)

写在最后

我一直认为好的 Misc 手是不需要通过大量经验积累才可以解出题目的,他需要有足够的思维能力才能够解开一些新思路的题目,这也是为什么我个人不喜欢纯工具题的原因(实际是因为我题做太少所以知道的工具没几个)当然这次还是出了工具题,主要是为了照顾大家的参赛体验。

这次出的 Nanomaze 和 wordle 我觉得算是新类型的 Misc 题,可以叫做游戏题吧 hhhhhhh。Cat&Soup 则是从 ByteCTF2021Final 里面的某些题目获得的灵感。这其实提醒了我们:如果我们用一种比官方题解还简单的方法解出了题,那么我们就可以把这种方法出成题接着继续伤害其他选手(?

这次还挑战了下出了道 Crypto 题,虽然最后有点遗憾,留了个 Bug 导致了非预期解,但第一次出如此复杂且精妙的 Crypto 题还是挺有成就感的。

出题不易,耗费了将近两三周的时间才出完,其中还浪费了一些时间去验证出题灵感是否能出成题,总之希望大家能够在我出的题里面玩的开心,也做得开心。

支持一下
资助 Nano 让 Nano 吃得更胖!
  • 微信扫一扫
  • 支付宝扫一扫