「GKCTF X DASCTF应急挑战杯」 Random

Random

解压题目提供的压缩包，得到了出题人给出的 Python 脚本．其中使用写打开 Random.txt 文件并在其中填充由 Python 的 Random 模块生成的随机数据．

众所周知，在编程中通常使用的是伪随机数， Python 的 Random 模块生成的伪随机数可通过一定方式进行预测或重现．

info
INFO

将随机数的性质分为以下三类：[1]

• 随机性——不存在统计学偏差，是完全杂乱的数列．
• 不可预测性——不能从过去的数列推测出下一个出现的数．
• 不可重现性——除非将数列本身保存下来，否则不能重复相同的数列．

当时笔者想到了两种思路：

• 根据文件创建时间推测作为 Random 模块默认种子的系统时间的大致范围，并将其可能的取值区间进行遍历．试图找出其使用的随机数种子，并重现其生成的伪随机数．
• 根据已有输出预测新的随机数．

很明显这两条思路分别利用了不可重现性和不可预测性这两个真随机数应当具有的性质，或者说 Python 的 Random 模块生成的伪随机数具有的缺陷．

由于笔者查找了很久也没弄明白作为默认种子的时间格式，于是尝试思路 2．

通过查找发现 RandCrack 能通过读取前 624 次 random.getrandbits(32) 的结果来预测下一次 random.getrandbits(32) 的结果．

可以看到，出题人给出的脚本中进行 104 次循环，每次循环生成 一个 32 bits 随机数，一个 64 bits 随机数，一个 96 bits 的随机数．如果「1 个 64 bits 的随机数」可以拆成 「2 个 32 bits 的随机数」、「1 个 96 bits 的随机数」可以拆成 「3 个 32 bits 的随机数」．如果假设成立，一个循环也就是生成 6 个 32 bits 的随机数，那么 104 次循环也就是生成 624 个随机数．完美符合 RandCrack 的需求．

完美的像是出题人仿佛为此工具定制的题目一样．这样的巧合，让笔者觉得这绝非偶然，便尝试进行验证．

首先考虑如何拆分数字：
那么最方便的方式就是将字符串转换为 int 后，做位运算进行进行拆分．
笔者以 96 bits 的随机数拆分成低 32 bits 的随机数、中 32 bits 的随机数、高 32 bits 的随机数为例说明：
取 96 bits 的低 32 bits 仅需：

n & 0xffffffff

取 96 bits 的中 32 bits 仅需：

(n >> 32) & 0xffffffff

取 96 bits 的高 32 bits 仅需：

n >> 64

笔者在做题时，写出这段代码远没有此时写 WriteUp 这般自信．因为在 C 语言中，若对 整形变量 n 执行左移或右移操作，如果操作数大于等于 sizeof(n) * 8，那么便会对操作数取 sizeof(n) * 8 的模．

虽然笔者是在用 Python 解题，但 Python 是否允许对一个 int 右移 32 / 64 位，笔者并不确定．
当然最终的测试说明笔者的担心是多余的．

尝试时，会遇到新的问题：
64 bits 的随机数拆成 2 个 32 bits 的随机数，那么自然是高 32 bits 作为一个随机数、低 32 bits 作为另一个随机数．但 RandCrack 每次只能提交一个 32 bits 的随机数，该先提交高 32 bits 的随机数，还是低 32 bits 的随机数？ 当然，96 bits 的随机数也同理．

这确实令人感到困惑．

但好在只有两种可能性．尝试后发现需要先提交低 32 bits 的随机数．

from randcrack import RandCrack
import io
from hashlib import md5


rc = RandCrack()
file = io.open('random.txt', 'r')


def conversion(x: str):
    return int(x[:-1])


def getNumber():
    n1 = file.readline()
    rc.submit(conversion(n1))
    n2 = file.readline()
    n2 = conversion(n2)
    rc.submit(n2 & 0xffffffff)
    rc.submit(n2 >> 32)
    n3 = file.readline()
    n3 = conversion(n3)
    rc.submit(n3 & 0xffffffff)
    rc.submit((n3 >> 32) & 0xffffffff)
    rc.submit(n3 >> 64)
    return


for i in range(104):
    getNumber()

value = rc.predict_randrange(0, 4294967295)
value = str(value)
flag = md5(value.encode()).hexdigest()
print(flag)

参考资料

¹. 结成浩.图解密码技术[M].第3版.周自恒,译.北京:人民邮电出版社. ↩